1、Chapter 5 Peer-to-Peer Protocols and Data Link Layer,Part I: ARQ Protocols and Reliable Data Transfer Service,5.2 ARQ Protocols and Reliable Data Transfer Service,5.2.1 SWP ( Stop-and-Wait) 5.2.2 GBN ( Go Back N ) 5.2.3 SRP (Select Repeat Protocol),Automatic Repeat Request (ARQ),Purpose: to ensure a

2、 sequence of information packets is delivered in order and without errors or duplications despite transmission errors block requests from higher layer If timeout expires: retransmit frame and reset timer If ACK received: If sequence number is incorrect or if errors detected: ignore ACK If sequence n

3、umber is correct (Rnext = Slast +1): accept frame, go to Ready state,2. Stop-and-Wait ARQ,Receiver: Always in Ready State Wait for arrival of new frame When frame arrives, check for errors If no errors detected and sequence number is correct (Slast=Rnext) accept frame, update Rnext, send ACK frame w

4、ith Rnext, deliver packet to higher layer If no errors detected and wrong sequence number discard frame, send ACK frame with Rnext If errors detected: discard frame,Applications of Stop-and-Wait ARQ,IBM Binary Synchronous Communications protocol (Bisync): character-oriented data link control Xmodem:

5、 modem file transfer protocol Trivial File Transfer Protocol (RFC 1350): simple protocol for file transfer over UDP,3. Stop-and-Wait Efficiency,10000 bit frame 1 Mbps takes 10 ms to transmit If wait for ACK = 1 ms, then efficiency = 10/11= 91% If wait for ACK = 20 ms, then efficiency =10/30 = 33%,St

6、op-and-Wait Model,S&W Efficiency on Error-free channel,Effective transmission rate:,Transmission efficiency:,Example: Impact of Delay-Bandwidth Product,nf=1250 bytes = 10000 bits, na=no=25 bytes = 200 bits,Stop-and-Wait does not work well for very high speeds or long propagation delays,S&W Efficienc

7、y in Channel with Errors,Let 1 Pf = probability frame arrives w/o errors Avg. # of transmissions to first correct arrival is then 1/ (1Pf ) “If 1-in-10 get through without error, then avg. 10 tries to success” Avg. Total Time per frame is then t0/(1 Pf),Example: Impact Bit Error Rate,nf=1250 bytes =

8、 10000 bits, na=no=25 bytes = 200 bits Find efficiency for random bit errors with p=0, 10-6, 10-5, 10-4,Bit errors impact performance as nfp approach 1,Chapter 5 Peer-to-Peer Protocols and Data Link Layer,Part I: Go-Back-N,Go-Back-N,Improve Stop-and-Wait by not waiting! Keep channel busy by continui

9、ng to send frames Allow a window of up to Ws outstanding frames Use m-bit sequence numbering If ACK for oldest frame arrives before window is exhausted, we can continue transmitting If window is exhausted, pull back and retransmit all outstanding frames Alternative: Use timeout,Go-Back-N ARQ,Frame t

10、ransmission are pipelined to keep the channel busy Frame with errors and subsequent out-of-sequence frames are ignored Transmitter is forced to go back when window of 4 is exhausted,Window size long enough to cover round trip time,Go-Back-N with Timeout,Problem with Go-Back-N as presented: If frame

11、is lost and source does not have frame to send, then window will not be exhausted and recovery will not commence Use a timeout with each frame When timeout expires, resend all outstanding frames,Go-Back-N Transmitter & Receiver,Sliding Window Operation,4,5,0,1,2,0,1,2,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3

12、,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,sender,ACK1,ACK4,receiver,ACK0,ACK2,ACK4,超時,ACK3,Go-Back-N ARQ,Maximum Allowable Window Size,Maximum Allowable Window Size is Ws = 2m-1,ACK Piggybacking in Bidirectional GBN,Applications of Go-Back-N ARQ,HDLC (High-Level Data Link Cont

13、rol): bitoriented data link control V.42 modem: error control over telephone modem links,Required Timeout & Window Size,Timeout value should allow for: Two propagation times + 1 processing time: 2 Tprop + Tproc A frame that begins transmission right before our frame arrives Tf Next frame carries the

14、 ACK, Tf Ws should be large enough to keep channel busy for Tout,Required Window Size forDelay-Bandwidth Product,Efficiency of Go-Back-N,GBN is completely efficient, if Ws large enough to keep channel busy, and if channel is error-free Assume Pf frame loss probability, then time to deliver a frame i

15、s: tf if first frame transmission succeeds (1 Pf ) tf + Wstf /(1-Pf) if the first transmission does not succeed Pf,Example: Impact Bit Error Rate onGBN,nf=1250 bytes = 10000 bits, na=no=25 bytes = 200 bits Compare S&W with GBN efficiency for random bit errors with p = 0, 10-6, 10-5, 10-4 and R = 1 M

16、bps & 100 ms 1 Mbps x 100 ms = 100000 bits = 10 frames Use Ws = 11, Go-Back-N significant improvement over Stop-and-Wait for large delay-bandwidth product Go-Back-N becomes inefficient as error rate increases,Chapter 5 Peer-to-Peer Protocols and Data Link Layer,Part I: Selective Repeat ARQ,Selective

17、 Repeat ARQ,Go-Back-N ARQ inefficient because multiple frames are resent when errors or losses occur Selective Repeat retransmits only an individual frame Timeout causes individual corresponding frame to be resent NAK causes retransmission of oldest un-acked frame Receiver maintains a receive window

18、 of sequence numbers that can be accepted Error-free, but out-of-sequence frames with sequence numbers within the receive window are buffered Arrival of frame with Rnext causes window to slide forward by 1 or more,Selective Repeat ARQ,4,5,0,1,2,0,1,2,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0

19、,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,sender,ACK1,ACK4,receiver,NAK0,ACK3,超時,ACK3,Selective Repeat ARQ,Send & Receive Windows,What size Ws and Wr allowed?, Example: M=22=4, Ws=3, Wr=3,Frame 0 resent,Old frame 0 accepted as a new frame because it falls in the receive window,Ws + Wr = 2m is m

20、aximum allowed, Example: M=22=4, Ws=2, Wr=2,Frame 0 resent,Old frame 0 rejected because it falls outside the receive window,Applications of Selective Repeat ARQ,TCP (Transmission Control Protocol): transport layer protocol uses variation of selective repeat to provide reliable stream service Service

21、 Specific Connection Oriented Protocol: error control for signaling messages in ATM networks,Efficiency of Selective Repeat,Assume Pf frame loss probability, then number of transmissions required to deliver a frame is: tf / (1-Pf),Example: Impact Bit Error Rate onSelective Repeat,nf=1250 bytes = 100

22、00 bits, na=no=25 bytes = 200 bits Compare S&W, GBN & SR efficiency for random bit errors with p=0, 10-6, 10-5, 10-4 and R= 1 Mbps & 100 ms,Selective Repeat outperforms GBN and S&W, but efficiency drops as error rate increases,Comparison of ARQ Efficiencies,Assume na and no are negligible relative t

23、o nf, and L = 2(tprop+tproc)R/nf =(Ws-1), then,Selective-Repeat:,Go-Back-N:,Stop-and-Wait:,For Pf0, SR & GBN same,For Pf1, GBN & SW same,ARQ Efficiencies,Chapter 5 Peer-to-Peer Protocols and Data Link Layer,Part I: Flow Control,Flow Control,Receiver has limited buffering to store arriving frames Several situations cause buffer o