Upload
rafael-scudelari
View
346
Download
1
Embed Size (px)
DESCRIPTION
Citation preview
Institut für Kommunikationstechnikwww.ikt.uni-hannover.de
Protokolle der OSI-Schicht 2Error Control, Link Layer Control
Kapitel 7.5
Netze und ProtokolleDr.-Ing. J. Steuer
(2)
FEC vs ARQ
FEC, Forward Error Correction, see Musmann, Kaisererrors must be detected and correctedhigh amount of redundant information applied if application is time critical and/or error rate is high
ARQ, Automatic Repeat Requesterrors need to detected onlyless amount of redundant informationapplied with low error rate and sufficient time to apply for data repetitionrepetition is initiated by a negative acknowledgement or a missing acknowledgement and a time out
(3)
Methods for error detection& error correction
one dimensional parity bittwo dimensional parity bitcodes
convolutional codesBCH codesReed Solomon codes
For details refer to lectures of Prof. Musmann and Prof. Kaiser
(4)
Verletzung des OSI-Modells
Hybride ARQ Typ2 Verfahren (Kontrolle Schicht 2, Daten der Schicht 1)
2
1
2
1
1.) Übertragung von gering geschützten Daten2.) Nach Fehler Sendung weiterer Redundanz auf Schicht 1
(5)
Process of error detection in L2
physical layer(1)
link layer (2):
1.take info from layer 32.calculate redundant
information, using anappropriate codingscheme
3.add redundant information to the layer 3-info
4. continue with othertasks of the link layer
5. hand over enhancedinformation to layer 1
network layer(3)
physical layer(1)
link layer (2):
1.in case of positive ack hand over L3 to L7 and user infoto layer 3, otherwise wait forrepetition
4. performe FEC or give positive ar negative acknowledgment
3.compare calculated redundancewith received redundance
2. calculate redundant info fromL3 to L7 and user info
1.seperate L3 to L7 anduser info
network layer(3)
user infoL7L6L5L4L3L2:Redundance, othersL1
netw
ork
(6)
ARQ-Protocols
differentiation:positive/negative acknowledgment (ack/nack)positive acknowledgment only, (be careful:timing)stop & wait ARQcontinous ARQpigy-packed ARQ
question: would a pure negative ack be a sensible solution?
(7)
ARQ-Protocols, Stop and Wait
using positive and negative acknowledgement or positive acknowledgment and timeout:
tim
e
frame n-1
positive acknowledgement
frame n
negativeacknowledg-ment
repetition offrame n
tim
e
frame n-1positiveacknowledg-ment
frame n
repetiton offrame n
tim
eout
remark: the ACK could belost as well
corruptioncorruption
(8)
ARQ-Protocols, Stop and Wait with lost frames (packets)
tim
eframe n-1
positive acknowledgement
frame n
repetition offrame n
tim
e
frame n-1positiveacknowledg-ment
frame n
repetiton offrame n
tim
eoutlost
tim
eout
lost
Question: Is it necessary to distinguish frame n from the repeated frame n at the receiver?
(9)
ARQ-Protocols, Stop and Wait with lost frames (packets) and Enquiry
tim
eframe n-1
positive acknowledgement
frame n
ENQ
tim
e
frame n-1positiveacknowledg-ment
frame n
tim
eoutlost
tim
eout
lost
repetition of positive acknowledgment
positiveacknowledg-ment
ENQrepetitionof positive acknowledg-ment
• Why not just repeating the frame which is not acknowledged?• how to differentiate which ACK is received? The transmitter does not know which frameis lost, its own or the ACK! The way out is the odd and even numbering of the ACK´s!
(10)
ARQ-Protocols, Continuous
stop and wait is time consuming, especially on links with high propagation delaytime saving:
continuous transmission without waiting for ACKproblem: propagation delay might result in late information fromthe transmitter on transmission errors, consequently
a number of packets need to be retransmittedsolution: sliding window mechanism
(11)
Continuous ARQ-Protocols for full duplex channels
Go back n is easier to implement, selective repeat is more efficient!
tim
eframe 1
ACK 1frame 2frame 3frame 4
ACK 2NACK 3
frame 5
frame 3frame 4
frame 5 ACK 4ACK 5
ACK 3
Go back n
tim
e
frame 1
ACK 1frame 2frame 3frame 4
ACK 2NACK 3
frame 5
frame 3
ACK 3
selectiverepeat
ACK 4
ACK 5
(12)
piggy packing of ACK
•The acknoledgement is partly transported with communication frames•Sequence count required!
tim
e
frame 1
frame 1,ACK 1frame 2frame 3
frame 4, ACK1frame2,ACK 2frame3, NACK 3
frame 5,ACK2frame 3,ACK3
frame 4
frame 5 frame5, ACK 4frame6, ACK 5
frame4, ACK 3
Go back n
ACK 4ACK 5ACK 6
(13)
Communications Efficiency of ARQ-stop&wait (1)
ioncommunicatofdirectiontheswitchtotimearoundturnt
linktheontimenpropagatiotratebitontransmissiR
mentacknowledgperbitstotalnceaccepgettomadeattemptsofnumberaverageN
frameainheaderperbitstotalnframeperbitstotalKdef
ttR
nKN
nKR
ceaccepfortimeTotalndestinatiothebyacceptedbitsdatauserofnumberR
rateontransmissidataeffectiveRdefsionsretransmisofionconsideratrequiresotocolsDLCofePerformanc
ta
p
a
h
tapa
he
e
e
=
===
===
+++
−=
=
=−
:
:::
tan::::.
)1.5.6())(2(
tan
::.:Pr
(14)
Communications Efficiency of ARQ-stop&wait (2)
Next we have to solve the average number of transmissions N:• consider P to be the probability of an error on any frame transmission• errors on different frames are independent• j transmissions will be required to be successful, this means we need j-1
erroneous transmissions followed by one successful:)2.5.6()1(1 PPP j
j −= −
• the average of j is the average number of transmissions N:
)3.5.6(]...321)[1()1(1
121∑∞
=
−∞− ++++−=−=j
j nPPPPPjPN
• with Bronstein 1.61:
)4.5.6()1(
1)1(
)1(1]...321[ 22
112
PPPPnPPP
−=
−∞++∞−
=+++++∞∞
−∞
)5.5.6(1
1)1()1(2 PP
PN−
=−−
=Ready?
No, we still miss theframe error rate P
(15)
Communications Efficiency of ARQ-stop&wait (3)
To get the average number of transmissions we have to find the probabilityfor disturbed frames P. The most common approach is to use the bit errorrate p and the number of bits per frame K (bit errors shall be independent of each other):
)6.5.6()1(1 KpP −−=
Which effect do we neglect with the given approach above?
considering p as burst error rate and combining 6.5.6 with 6.5.1 we get:
)7.5.6()(2
)()1(
))(2(1
1))(2(
apa
hK
e
tapa
h
tapa
he
ttRnKnKRpR
ttR
nKP
nK
ttR
nKN
nKR
+++−−
=
+++
−
−=
+++
−=
(16)
)(2)()1(
apa
hK
e ttRnKnKRpR+++−−
=
R:=4800bit/s;
nh:=48 bit;
ta:=0.1s; tp:=0.01s;
na:=48bit; note:• optimal frame length• effective frame rate
drops, if too manyrepetitions arerequiredp1:=10^(-5);
p2:=10^(-4);
Re:=effektive transmission ratein bit/s;
K := frame length in Byte
Which error rate do you need, in order to runIEEE802.3 efficient?
(17)
Communications Efficiency of error freecontinuous ARQ
in an error free environment the time for acceptance is just the serialization time:
ratebitontransmissiRframeainheaderperbitstotaln
frameperbitstotalKdefRK
nKR
ceaccepfortimeTotalndestinatiothebyacceptedbitsdatauserofnumberR
rateontransmissidataeffectiveRdef
h
he
e
e
===
−=
=
=
::::.
)8.5.6(
tan
::.
tim
e
K/R
(18)
Communications Efficiency for continuous ARQ and Go Back n (1)
each corrupted frame will cause a step of n frames backwards. The first frame can be correct. This means we transmit one frame to be successful. This causes an average of one frame to be transmitted. The first frame can be corrupted and request a repetition of n frames. The probability for that is:
)1(*:)1(
PPnframesdtransmitteaveragethewithPP
−−
• The second frame can be corrupted as well and request a repetition of 2n frames. The probability for that is:
)1(*2:)1(
2
2
PPnframesdtransmitteaveragethewithPP
−
−
• The third frame can be corrupted as well and request a repetition of 3n frames. The probability for that is:
)1(*3:)1(
3
3
PPnframesdtransmitteaveragethewithPP
−
−
(19)
Communications Efficiency for continuous ARQ and Go Back n (2)
• The average number N of frames to be transmitted is the sum of the average frames of the individual cases from the previous slide:
9.5.6...)1(*3)1(*2)1(*1 32 +−+−+−+= PPnPPnPPnN• again using Bronstein 1.61:
10.5.61
)1(1)1(
*1P
PnP
PnN−−+
=−
+=
• if we multiply now the average transmitted frames with the time to serialize one frame, we get the „total time to get the bits accepted“ and thus the effective transmission rate:
11.5.6]])1(1)[1(1[
)])()1(1[1(])1(1[))(1(
1)1(1
)(KpnRnKp
KPnRnKP
RK
PPn
nKR Kh
Khh
e −−−+−−−−
=−+−−
=
−−+−
=
(20)
KpnRnKpR K
hK
e ]])1(1)[1(1[)])()1(1[1(
−−−+−−−−
=R:=4800bit/s;
nh:=48 bit;
n:=5
p1:=10^(-5);
stop and wait
p2:=10^(-4);
stop and wait
p2:=10^(-4);
Go Back n
p1:=10^(-5);
Go Back n
(21)
unterer Fensterrand:Sendelaufnummer des ältesten noch nicht bestätigten Datenpaketes
oberer Fensterrand:Sendelaufnummer des ersten noch nicht zur Sendung freigegebenenDatenpaketes
obererFensterrand
(hier:3)
untererFensterrand
(hier:0)
7 0
6
5
4 3
2
1
w=3
FenstermechanismusSliding Window
(22)
0
upperwindow edge
(here:3)
lowerwindow edge
(here:0)
7
6
5
4 3
1
w=3
P0P0
P0P1
P1P2P1P2
direction A direction B
P2Q0
Q0Q0
Q1Q1 Q2
Q1
Q2Q2
P3P3
P3P4
P4P5P4P5P5
Q3
Q3Q3
Q4Q4 Q5
Q4
Q5tim
e
time
1
2
Sliding Window
(23)
demonstration of the sliding window
one packet underwindowcontrol
two packetsunderwindowcontrol
7 packetsunderwindowcontrol
(24)
sliding window mechanismn
(see notes)
(25)
performance of the sliding window-Acknowledgment at end of window- (1)
Tt : time to serializeτ : propagation timeTp : time to serialize the Acknowledgment
The delay d from the start of transmission until the complete receipt of the acknowledgment is
frame 1frame 2frame 3
tim
e
window size: W=3
Tt
WTt
frame 1frame 2frame 3
Ack1
d
τ
Tp
* 2 6.5.12t pd W T T τ= + +
with the data rate R we get the ratio: (efficient data rate Re):
* 6.5.13e tR W TR d=
(26)
performance of the sliding window-Acknowledgment at end of window- (2)
combining equation 6.5.12 with 6.5.13:
* 6.5.14* 2
te
t p
W TR RW T T τ
=+ +
the packet length is:
* 6.5.15tK R T=
6.5.15 in 6.5.14:
*6.5.16
* 2e
p
KWRR RKW T
Rτ
=+ +
* 6.5.15* 2e
p
W KR W K TR
τ=
+ +
(27)
performance of the sliding window-Acknowledgment at end of window- (3)
* 6.5.15* 2e
p
W KR W K TR
τ=
+ +
parameters:
R=4800bit/sekTp=20msτ =20ms
W=5W=3
W=1
(28)
performance of the sliding window-Acknowledgment after receipt of frame-(1)
Tt : time to serializeτ : propagation timeTp : time to serialize the AcknowledgmentThe delay d from the start of transmission until the complete receipt of the acknowledgment is:
frame 1frame 2frame 3
tim
e
window size: W=3
Tt
frame 4frame 5frame 6
Ack1
dτ
Tp2 6.5.16t pd T T τ= + +
with the data rate R we get the ratio: (efficient data rate Re):
* 6.5.18tW T d≥
Ack1
frame 7
WTt
Equ. 6.5.17 this expresses the continous data flowfor:
*min ,1 6.5.17e tR W TR d
⎧ ⎫= ⎨ ⎬⎩ ⎭
(29)
performance of the sliding window-Acknowledgment after receipt of frame- vs. -
Acknowledgment at end of window-
parameters:
R=4800bit/sekTp=20msτ =20msW=1
W=3
W=5W=3W=5
*min ,1 6.5.17e tR W TR d
⎧ ⎫= ⎨ ⎬⎩ ⎭
(30)
Fragen (2)
Wieviele Pakete können maximal ins Netz geschickt werden, bevor ein acknowledge (Bestätigung) für den Empfang kommen muß?Wie können N(R) und N(S) benutzt werden, um eine Fehlerfall-Steuerung zu realisieren?Auf welchen Leitungen werden Sie die Fenstergröße großund auf welchen klein machen?
(31)
Ab hier nicht mehr drucken
(32)
ARQ-Protocols
differentiation:positive/negative acknowledgmentpositive acknowledgment only, (be careful:timing)
question: would a pure negative ack be a sensible solution?Could be done, but it takes time to wait for the timer!
(33)
ARQ-Protocols, Stop and Wait with lost frames (packets)
tim
eframe n-1
positive acknowledgement
frame n
repetition offrame n
tim
e
frame n-1positiveacknowledg-mentframe n
repetiton offrame n
tim
eout
lost
tim
eout
lost
Question: Is it necessary to distinguish frame n from the repeated frame n at the receiver?
answer: Of course it is. The receiver does not know the content of the frame. The content should not be delivered twice at layer 3.
next Question: Propose the most simple method to differentiate both.answer: add simply one bit to the header, which is set to one for the original
message and zero for the repetition. When does this method fail?
(34)
Communications Efficiency of ARQ-Protocols(3)
To get the average number of transmissions we have to find the probabilityfor disturbed frames P. The most common approach is to use the bit errorrate p and the number of bits per frame K (bit errors shall be independent of each other):
)6.5.6()1(1 KpP −−=
Which effect do we neglect with the given approach above?
The error probability for the bits is (depending on the transmission media)is often not independent of each other. Very often, especially in radio systems we have burst errors. In such cases it is more realistic to consider burst errors as independent rather than the bit errors!
An approximation from experience is that the burst error rate is1/3 to 1/10
of the bit error rate.
(35)
p1:=10^(-5);
p2:=10^(-4);
)(2)()1(
apa
hK
e ttRnKnKRpR+++−−
=
R:=4800bit/s;
nh:=48 bit;
ta:=0.1s; tp:=0.01s;
na:=48bit; note:• optimal frame length• effective frame rate
drops, if too manyrepetitions arerequired
Re:=effektive transmission ratein bit/s;
K := frame length in Byte
Which error rate do you need, in order to runIEEE802.3 efficient? BetterThan p1, because the max.Frame length is about 1500 octetts; for that using p2 Reis already down.