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 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 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
Stop and Wait protocol Algorithm at sender(node A) (with initial condition SNEO 1) Accept packet from higher layer 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 if received and it contains rn>sn in the request#f field. set sn to rn and go to 1 if not received within given time, go to 2 Eytan modiano
Stop and Wait Protocol Algorithm at sender (node A) (with initial condition SN=0) 1) Accept packet from higher layer 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 RN>SN in the request # field, set SN to RN and go to 1 ii. if not received within given time, go to 2 Eyt an Modiano 6
Stop and wait Algorithm at receiver (node B) (with initial condition RN=O) Whenever an error-free frame is received from a with a sequence equal to RN, release received packet to higher layer and increment RN 2)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 field Eytan modiano
Stop and Wait Algorithm at receiver (node B) (with initial condition RN=0) 1) Whenever an error-free frame is received from A with a sequence # equal to RN, release received packet to higher layer and increment RN. 2) 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 # field. Eytan Modiano 7
Correctness of stop wait with integer SN, RN Assume, for a to( from)B transmission, that All errors are detected as errors Initially no frames are on link, SN=0, RN=O Frames may be arbitrarily delayed or lost Each frame is correctly received with at least some probability q>0 Split proof of correctness into two parts SAFETY: show that no packet is ever released out of order or more than once LIVENESS: show that every packet is eventually released Eytan modiano
Correctness of stop & wait with integer SN, RN • Assume, for A to (from) B transmission, that – All error s are detected as errors – Initially no frames are on link, SN=0, RN=0 – Frames may be arbitrarily delayed or lost – E a ch frame is correctly recei ved with at least some probability q>0. • Split proof of correctness into two parts: – SAFETY: show that no packet i s ever r eleased out o f order o r m ore than once – LIVENESS: show that every packet is eventually released Eyt an Modiano 8
Safety No frames on link initially, packet 0 is first packet accepted at A, it is the only packet assigned SN=o, and must be the packet released by B if B ever releases a packet Subsequently(using induction) if b has released packets up to and including n-1, then rn is updated to n when n-1 is released, and only n can be released next Eytan modiano
Safety • No frames on link initially, packet 0 is first packet accepted at A, it is the only packet assigned SN=0, and must be the packet released by B if B ever releases a packet • Subsequently (using induction) if B has released packets up to and including n-1, then RN is updated to n when n-1 is released, and only n can be released next Eytan Modiano 9
LIVENESS Node a Node B Packets out t,= time at which A first starts to transmit packet t 2 =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 that t, <t2 <t3 <oo. = Liveness Eytan modiano
LIVENESS i i i i SN RN Node A Node B x i+1 x i+1 t t t 1 2 3 i Packets out i t1 = time at which A first starts to transmit packet i t2 = 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 that t1 Liveness Eytan Modiano 10