Lectures 3&4 6.263/16.37 The Data link layer: aRQ Protocols Eytan Modiano MIT LIDS Eytan modiano
Lectures 3 & 4 6.263/16.37 The Data Link Layer: ARQ Protocols Eytan Modiano MIT, LIDS Eytan Modiano 1
Automatic Repeat ReQuest(ARQ) When the receiver detects errors in a packet, how does it let the transmitter know to re-send the corresponding packet? Systems which automatically request the retransmission of missing packets or packets with errors are called ARQ systems Three common schemes Stop Wait Go Back n Selective Repeat Eytan modiano
Automatic Repeat ReQuest (ARQ) • When the receiver detects errors in a packet, how does it let the transmitter know to re-send the corresponding packet? • Systems which automatically request the retransmission of missing packets or packets with errors are called ARQ systems. • Three common schemes – Stop & Wait – G o B a c k N – Selective Repeat Eyt an Modiano 2
Pure Stop and Wait Protocol Transmitter departure times at A Time packet CRC packet IIA packet 1 CRC ACK NAK arrival times at receiver Packet o Packet 1 ccepte Accepted Problem: Lost Packets Sender will wait forever for an acknowledgement Packet may be lost due to framing errors Solution: Use time-out ( TO) Sender retransmits the packet after a timeout Eytan modiano
Pure Stop and Wait Protocol Transmitter departure times at A Time ACK -----> NAK packet 0 CRC packet 1 CRC packet 1 CRC arrival times at receiver Packet 0 Accepted • Problem: Lost Packets – Sender will wait forever for an acknowledgement • Packet may be lost due to framing errors • Solution: Use time-out (TO) – Sender r etransmits the packet after a timeout Packet 1 Accepted Eyt an Modiano 3
The Use of Timeouts For Lost Packets requires Sequence Numbers packet CRC<--timeout-> packet CRC packet 0 or 1? cket o accepted Problem: Unless packets are numbered the receiver cannot tell which packet it received Solution: Use packet numbers(sequence numbers Eytan modiano
The Use Of Timeouts For Lost Packets Requires Sequence Numbers packet 0 CRC <---- timeout -----> packet 0 CRC packet 0 or 1? packet 0 accepted • Problem: Unless packets are numbered the receiver cannot tell which packet it received • Solution: Use packet numbers (sequence numbers) Eyt an Modiano 4
Request Numbers Are Required On ACKs To Distinguish Packet ACKed 0 packet 0 timeout o packet 0 1 packet 1 ACK ACK Packet o accepted REQUEST NUMBERS Instead of sending"ack"or "nak", the receiver sends the number of the packet currently awaited Sequence numbers and request numbers can be sent modulo 2 This works correctly assuming that 1)Frames travel in order( FCFS)on links 2)The CrC never fails to detect errors 3)The system is correctly initialized Eytan modiano
Request Numbers Are Required O n ACKs To Distinguish Packet ACKed ACK ACK 0 ut 0 ? packet 0 timeo 0 packet 1 packet 1 Packet 0 accepted • REQUEST NUMBERS: – Instead of sending "ack" or "nak", the rec eiver sends the number of the packet c urrently awaited. – Sequence numbers and request numbers can be sent modulo 2. Thi s works correctly assuming that 1) Frames travel in order (FCFS) on links 2) The CRC never fails to detect errors 3) The system is correctly initialized. Eyt an Modiano 5