通信网理论基础（工程硕士）：ch2 Point-to-Point Protocols and Links The Data Link Layer ARQ Protocols

1、ch2: Point-to-Point Protocols and Links The Data Link Layer: ARQ ProtocolsIf let you back to the past, what would you do for designing of a Link layer protocol? 2The simplest form as networksThe main caring parts of networks in this course are the network, transport and physical layers. There are ma

2、ny similarities between the point-to-point protocols at these different layers, and it is desirable to discuss them together before addressing the more complex network-wide protocols for routing, flow control and multi-access control. The simplest form: the point-to-pointObjective? to deliver the pa

3、ckets in the order of arrival, with neither repetitions nor errors. How? By correcting the bit errors that occur on the virtual bit pipe, or, ARQ(Automatic Repeat Request) 3The simplest form as networks (cont. )The simplest form: the point-to-pointWhy the retransmission request is difficult?First, b

4、ecause the requests must be embedded into the data traveling in the opposite direction. Second, because the opposite direction is also subject to errors. Whats more, the retransmission introduces some control overhead to be communicated, it costs money. Question: How could the receiver know the bits

5、 are wrong? The error detection. Does this error detection consume communication capacity?Yes, it introduces CRC. 4This provides our first exposure to a real distributed algorithm, which is of particular conceptual interest since it must operate in the presence of errors.ARQ (Automatic Repeat ReQues

6、t)When the receiver detects errors in a packet, how does it let the transmitter know to re-send the corresponding packet?System which automatically request the retransmission of missing packets or packets with errors are called ARQ systemscorrectness: Does the protocol succeed in releasing each pack

7、et, once and only once, without errors, from the receiving DLC?efficiency: How much of the capability is wasted by unnecessary waiting and by sending unnecessary retransmissions. 5ARQ (Automatic Repeat ReQuest)Three common schemesStop & WaitGo Back NSelective R6Model of Frame Transmissions7Pure Stop

8、 and Wait ProtocolThe simplest retransmission methodEnsure that each packet has been received correctly before initiating transmission of next packetProblem: Packet lossSender will wait forever for an acknowledgementPacket may be lost due to framing errorsSolution: Use time-out (TO)Sender retransmit

9、s the packet after a 8Is Timeout Enough?If the transmitter at A times-out and sends packet 0 twice, the receiver B cannot tell whether the second frame is a retransmission of packet 0 or the first transmission of packet 9The Trouble with Unnumbered PacketsIs Timeout Enough? (Cont. )If the transmitte

10、r A times-out and sends packet 0 twice, the receiver B can use the sequence numbers to recognize that packet 0 is being repeated. It must send an ACK for both copies, however, and (since ACKs can be lost) the transmitter cannot tell whether the second ACK is for packet 0 or 1. 10The Trouble with unn

11、umbered ACKsSequence Number in Timeout SchemeProblem: unless packets are numbered the receiver cannot tell which packet it receivedSolution: use packet numbers (sequence numbers) 11ACK Request NumbersRequest numbersInstead of sending “ACK” or “NAK”, the receiver sends the number of the packet curren

12、tly awaited .Sequence numbers and request numbers can be sent modulo 12An Example of Stop and WaitPacket 0 repeated because node A times-outNode A delays repeating packet 1 on the 2nd request for itAvoid unnecessary 13Stop and Wait (Sender) (with initial condition SN=0) Accept packet from higher lay

13、er when available; assign number SN to it 2) Transmit packet SN in frame with sequence # SN 3) Wait for an error free frame from B i. if received and it contains RNSN in the request # field, set SN to RN and go to 1 ii. if not received within given time, go to 2 14Stop and Wait (Receiver)(with initi

14、al condition RN=0) Whenever an error-free frame is received from A with a sequence # equal to RN, release received packet to higher layer and increment RN.At arbitrary times, but within bounded delay after receiving any error free frame from A, transmit a frame to A containing RN in the request # fi

15、eld. 15Correctness of stop & wait with integer SN, RN Assume for A to (from) B transmission, thatAll errors are detected as errorsInitially no frames are on link, SN=0, RN=0Frames may be arbitrarily delayed or lostEach frame is correctly received with at least some probability q0Split proof of corre

16、ctness into two partsSAFETY: show that no packet is ever released out of order or more than onceLIVENESS: show that every packet is eventually 16Correctness of stop & wait with integer SN, RN Assume for A to (from) B transmission, thatAll errors are detected as errorsInitially no frames are on link,

17、 SN=0, RN=0Frames may be arbitrarily delayed or lostEach frame is correctly received with at least some probability q0Split proof of correctness into two partsSAFETY: show that no packet is ever released out of order or more than onceLIVENESS: show that every packet is eventually 17SafetyNode B is i

18、nitially awaiting packet 0, and the only packet that can be released is packet 0Subsequently (use induction), node B has released all the packets in order up to RN (not included)Packet RN is the only packet that it can next accept and releaseWhen an error-free frame containing packet RN is received

19、and released, then value of RN is incrementedThe situation above is repeated with the new value of RN 18Liveness t1 = time at which A first starts to transmit packet it2 = time at which B correctly receives & releases i, and increases RN to i+1 t3 = time at which SN is increased to i+1 Will prove th

20、at t1 t2 t3 Liveness 19Liveness AugmentLet SN(t), RN(t) be values of SN and RN at time t From the algorithm, (1) SN(t) and RN(t) are increasing in t and SN(t) ?RN(t) for all t (2) From safety (since i has not been sent before t1) RN(t1) i and SN(t1) = I From (1) and (2), RN(t1) = SN(t1) = i RN is in

21、cremented at t2 and SN at t3, so t2 0, t2 is finite B transmits RN=i+1 repeatedly until correctly received at t3, and q0 implies that t3 is finite. 20Correctness of Stop and Wait w/ binary (finite) SN, RN Assume that frames travel on link in order Note that with integer SN, RN, eitherSN=RN (from t1

22、to t2) or (3) SN=RN-1 (from t2 to t3) (4) Since frames travel in order, the sequence numbers arriving at B and the request numbers arriving at A are increasing, so a single bit can resolve the ambiguity between (3) and (4) RN = 0 and SN = 1 or RN =1 and SN = 0 = received packet is an old packet RN =

23、 0 and SN = 0 or RN = 1 and SN = 1 = received packet is new 21Efficiency of stop and waitLet S = total time between the transmission of a packet and reception of its ACK DTP = transmission time of the packet 22Stop and wait in the presence of errors Let P = the probability of an error in the transmi

24、ssion of a packet or in its acknowledgment S = DTP + 2DP + DTA TO = the timeout interval X = the amount of time that it takes to transmit a packet and receive its ACK. This time accounts for retransmissions due to errors EX = S + TO*P/(1-P), Efficiency = DTP/EX Where, TO = DTP in a full duplex syste

25、m TO = S in a half duplex system 23Quiz about STOP and WAIT 24Quiz about STOP and WAIT(Cont.) 25Go Back N ARQStop and Wait is inefficient when propagation delay is larger than the packet transmission timeCan only send packet per round-trip timeGo Back N ARQ is the most widely used type of ARQ protoc

26、olGo Back N ARQ allows the transmission of new packets before earlier ones are acknowledgedGo Back N uses a window mechanism where the sender can send packets that are within a “window” of packetsThe window advances as acknowledgements for earlier packets are 26Features of Go Back N Window size = N

27、Sender cannot send packet i+N until it has received the ACK for packet i Receiver operates just like in Stop and WaitReceive packets in order Receiver cannot accept packet out of sequence Send RN = i + 1 = ACK for all packets up to and including i Use of piggybacking When traffic is bi-directional R

28、Ns are piggybacked on packets going in the other direction Each packet contains a SN field indicating that packets sequence number and a RN field acknowledging packets in the other direction 27Go Back N ARQ The transmitter has a window of N packets that can be sent without acknowledgements This wind

29、ow ranges from the last value of RN obtained from the receiver (denoted SNmin) to SNmin+N-1 When the transmitter reaches the end of its window, or times out, it goes back and retransmits packet SNmin Let SNmin be the smallest number packet not yet ACKed Let SNmax be the number of the next packet to

30、be accepted from the higher layer (I.e., the next new packet to be transmitted) 28Example of Go Back 7 ARQ 29Note that packet RN-1 must be accepted at B before a frame containing request RN can start transmission at B Go Back N Sender RulesSNmin = 0; SNmax = 0 RepeatIf SNmax SNmin SNmin = RN; If SNm

31、in NBecause at most N packets can be sent simultaneouslyReceiver can only accept packets in orderReceiver must deliver packets in order to higher layerCannot accept packet i+1 before packet iThis removes the need for bufferingThis introduces the need to re-send the entire window upon errorThe major

32、problem with Go Back N is this need to re-send the entire window when an error occurs. This is due to the fact the receiver can only accept packets in order 36Efficiency of Go Back NWe want to choose N large enough to allow continuous transmission while waiting for an ACK for the first packet of the

33、 window, N S/ DTP Without errors the efficiency of Go Back N is E = min1, N*DTP/S 37Efficiency of Go Back N with Transmission Errors Approximate AnalysisAssume: N =S/DTP TO = N*DTP When an error occurs the entire window of N packets must be retransmitted Let X = the number of packets sent per succes

34、sful transmission EX = 1*(1-P) + (X+N)*P = 1 + N*P/(1-P) Efficiency = 1/EX 38Selective Repeat Protocol (SRP) Selective Repeat attempts to retransmit only those packet actually lost (due to errors)Receiver must be able to accept packets out of orderSince receiver must release packets to higher layer

35、in order, the receiver must be able to buffer some packetsRetransmission requestsImplicitThe receiver acknowledges every good packet, packets that are not ACKed before a time-out are assumed lost or in errorNotice that this approach must be used to be sure that every packet is eventually receivedExp

36、licitAn explicit NAK can request retransmission of just one packetThis approach can expedite the retransmission but is not strictly neededOne or both approaches are used in 39SRP RulesWindow protocol just like Go Back NWindow size WPackets are number Mod M where M=2WSender can transmit new packets a

37、s along as their number is with W of all un-ACKed packetsSender retransmit un-ACKed packets after a timeoutOr upon a NAK if NAK is employedReceiver ACKs all correct packetsReceiver stores correct packets until they can be delivered in order to the higher 40BufferingSender must buffer all packets unt

38、il they are ACKedUp to W un-ACKed packet are possibleReceiver must buffer packets until they can be delivered in order I.e., until all lower numbered packets have been received Needed for orderly delivery of packets to the higher layer Up to W packets may have to be buffered (in the event that the f

39、irst packet of a window is lost) Implication of buffer size = W Number of un-ACKed packets at sender = 2W (using log2(M) bits) 41EfficiencyFor ideal SRP, only packets containing errors will be retransmittedIdeal is not realistic because sometimes packets may have to be retransmitted because their wi

40、ndow expired. However, if the window size is set to be much larger than the timeout value then this is unlikelyWith ideal SRP, efficiency = 1-PP = probability of a packet errorNotice the difference with Go Back N whereefficiency(Go Back N)=1/(1+N*P/(1-P)When the window size is small performance is a

41、bout the same, however with a large window SRP is much betterAs transmission rates increase we need larger windows and hence the increased use of SRP 42Why are packets numbered Modulo 2W? Lets consider the range of packets that may follow packet i at the receiver Packet i may be followed by the first packet of the window (i-W+1) if it requires retransmissionPacket i may be followed by the first packet