[13] Nup 07 5

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.