ELEN 602 Lecture 5 Review of last lecture Error Detection parity CRC etc Automatic Retransmission Request ARQ Reading Chap 5 1 5 2 Peer to peer protocol across a single hop a A Packets Packets Data link Layer Data link Layer Frames 1 1 b 1 2 3 2 2 1 Medium A 1 2 B Physical Layer Physical Layer Physical layer entity Data link layer entity 3 1 2 3 B 2 1 2 2 1 Network layer entity Peer to peer across a network Protocol stack View Messages Messages Segments Transport Layer Transport Layer Network Layer Network Layer Network Layer Network Layer Data link Layer Data link Layer Data link Layer Data link Layer Physical Layer Physical Layer Physical Layer End system Physical Layer Network End system End to end versus Hop by hop Approaches End to end ACK NAK 1 2 Data 3 Data 4 5 Data Data Data Data Hop by hop Data 1 Data 2 ACK NAK 3 ACK NAK 4 ACK NAK 5 ACK NAK Basic elements of ARQ Error free packet sequence Information frames Packet sequence Transmitter Station A CRC Receiver Control frames Station B CRC Information packet Information Frame Header Header Control frame Possibilities with Unnumbered Frames a Frame 1 lost A Time out time frame 0 frame 1 ACK B b ACK lost A B frame 1 frame 2 ACK Time out time frame 0 frame 1 ACK ACK frame 1 ACK frame 2 In parts a and b transmitting station A acts the same way but part b receiving station B accepts frame 1 twice Unnumbered Acks time out A frame 0 ACK B time frame 0 ACK frame 1 frame 2 Transmitting station A misinterprets duplicate ACKs System State Information in Stop and Wait ARQ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Rnext Slast Timer Slast Transmitter Rnext Station A 0 0 Global State Slast Rnext Station B Error free frame 0 arrives at receiver ACK for frame 1 arrives at transmitter 1 0 Receiver Error free frame 1 arrives at receiver 0 1 ACK for frame 0 arrives at transmitter 1 1 Stop and wait ARQ Enquiry Frame Time out a Frame 1 lost A frame 0 B b ACK for frame 1 lost A B frame 0 time frame 1 ACK 1 ENQ frame 1 ACK 1 Time out time frame 1 ACK 1 ENQ ACK 0 frame 0 ACK 0 Basic Go back N ARQ 4 frames are outstanding so go back 4 Go Back 4 fr 0 fr 1 fr 2 A B A C K 1 fr 3 A C K 2 fr 4 A C K 3 fr 5 fr 6 fr 3 fr 4 fr 5 Out of sequence frames A C K 4 error fr 6 fr 7 A C K 5 fr 8 A C K 6 time fr 9 A C K 7 A C K 8 A C K 9 Go back N ARQ vs Stop and wait ARQ Stop and Wait A Time out expires fr 0 fr 0 B A C K 1 error 4 frames are outstanding so go back 4 Go Back N A time fr 1 fr 0 fr 1 fr 2 B fr 3 fr 0 fr 1 fr 2 fr 3 Out of sequence framesA erro r C K 1 fr 4 A C K 2 fr 5 A C K 3 time fr 6 A C K 4 A C K 5 A C K 6 Go Back N ARQ Transmitter Send Window Frames transmitted S last and ACKed Srecent Buffers Timer Slast Timer Slast 1 Timer Srecent Slast Ws 1 Receiver Receive Window Slast Ws 1 frames received Rnext The receiver will only accept a frame that is error free and that has sequence number Rnext Window with fixed number of bits M 22 4 Go Back 4 fr 0 fr 2 fr 1 fr 3 Transmitter goes back 4 fr 0 fr 1 fr 2 fr 3 time A B A C K 2 A C K 1 M 22 4 Go Back 3 fr 0 A C K 4 Transmitter goes back 3 fr 2 fr 1 A C K 3 fr 0 fr 1 fr 2 Receiver has Rnext 0 but it does not know whether its ACK for frame 0 was received so it does not know whether this is the old frame 0 or a new frame 0 time A B A C K 1 A C K 2 A C K 3 Receiver has Rnext 3 so it rejects the old frame 0 NAK Error Recovery Transmitter goes back to frame 1 Go Back 7 A fr 0 fr 1 fr 2 fr 3 fr 4 fr 5 fr 1 fr 2 fr 3 fr 4 fr 5 fr 6 fr 7 time fr 0 B A C K 1 N A K 1 error Out of sequence frames A C K 2 A C K 3 A C K 4 A C K 5 A C K 6 A C K 7 Station B Station A SArecent RA next Transmitter Receiver Transmitter Receiver SBrecent RB next A Receive Window ACKs are piggybacked in headers B Receive Window RA next RB next A Send Window SA last B Send Window SB last SA last WA s 1 Buffers Timer SA last Timer SA last 1 SArecent Timer Timer SA last WA s 1 SB last WB s 1 Buffers Timer SB last Timer SBlast 1 SBrecent Timer Timer SB last WB s 1 How large a Timeout Tout Tproc Tprop Tf Tf Tprop Selective Repeat ARQ Transmitter Receiver Receive Window Send Window Frames transmitted S last and ACKed Srecent Slast Ws 1 Buffers Timer Slast Timer Slast 1 Timer Srecent Slast Ws 1 Frames received Rnext Rnext Wr 1 Buffers Rnext 1 Rnext 2 Rnext Wr 1 Error Recovery in Selective Repeat ARQ A fr 0 fr 1 fr 2 fr 3 fr 4 fr 5 fr 6 fr 2 fr 7 A C K 2 A C K 2 fr 8 fr 9 fr 10 fr 11 time fr 12 B A C K 1 A C K 2 error N A K 2 A C K 2 A C K 7 A C K 8 A C K 9 A C K 1 0 A C K 1 1 A C K 1 2 Maximum Window size in Selective Repeat ARQ M 22 4 Selective Repeat Send Window Receive Window 3 Frame 0 resent fr 0 fr 2 fr 1 fr 0 time A A C K 2 A C K 1 B A C K 3 Receive Window 3 0 1 Send Window Receive Window 2 fr 0 fr 0 fr 1 Frame 0 resent A B A C K 1 A C K 2 frame 0 rejected Receive Window 2 3 time Delay Components in Stop and Wait ARQ t0 A tproc B tprop frame tf time tproc tack tprop Transmission Efficiency of ARQ Protocols 1 0 8 Selective Repeat Go Back N 0 6 0 4 0 2 Stop …