16.36: Communication Systems Engineering Lectures 15: ARQ Protocols Eytan modiano
16.36: Communication Systems Engineering Lectures 15: ARQ Protocols Eytan Modiano
Automatic repeat request (ARQ) Break large files into packets FILE PKT PKT PKT Check received packets for errors Use a feedback channel to request retransmissions Retransmit packets containing errors acket Receive ACK
Automatic repeat request (ARQ) • Break large files into packets PKT H FI LE PKT H PKT H • Check received packets for errors • Use a feedback channel to request retransmissions • Retransmit packets containing errors packet ACK Sender Receiver
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
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
The stop and wait protocol Original ARQ protocol Sender transmits one packet at a time and waits for an ACK Receiver ACKs packets Sender retransmits packet after a timeout PKT-0 PKT-1 PKT-2 PKT-2 ACK-0 ACK-1 ACK-2 Packet numbering Sender numbers packets with sequence numbers (sN) Receiver uses request numbers(Rn) to ACK packets RN=jis the same as an ACK for packet j-1 ote Transmitter idle while waiting for ACK Efficiency limited by round trip delay time Requires no storage of packets
The stop and wait protocol • Original ARQ protocol • Sender transmits one packet at a time and waits for an ACK – Receiver A C K’s packets – Sender retransmits packet after a timeout PKT-0 X ACK-0 PKT-1 ACK-1 PKT-2 PKT-2 ACK-2 TO • Packet numbering – Sender numbers packets with sequence numbers (SN) – Receiver uses request numbers (RN) to ACK packets RN = j is the same as an ACK for packet j-1 • Note: – Transmitter idle while waiting for ACK – Efficiency limited by round trip delay time – Requires no storage of packets
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 3 Wait for an error free packet from B if received and it contains rn>sn in the request# field, set sn to rn and go to 1 li. if not received within given time(to), go to 2
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 3) Wait for an error free packet 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 (TO), go to 2
Stop and Wait Algorithm at receiver(node B) (with initial condition RNEO) 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
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
Efficiency of stop and wait Let s= total time between the transmission of a packet and reception of its ACK DTD transmission time of the packet Efficiency(no errors)=Dp/S S=DTp 2Dp+ DTa A cket B TE Dp TA DTAACKtrans.Time E=DIP/(DTP 2D dTA) DTP= pack ket trans time
Efficiency of stop and wait Let S = total time between the transmission of a packet and reception of its ACK DTP = transmission time of the packet Efficiency (no errors) = DTP/S A B DP = prop delay packet ACK S DTP DP DTA DP S = DTP + 2D P + DTA DTA = ACK trans. Time E = D DTP = packet trans. time TP/(DTP + 2D P + DTA )
Stop and wait in the presence of errors Let p the probability of an error in the transmission of a packet or in its acknowledgment S=Dr+2D。+D TA 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 E凶]=S+TOP/(1-P), Eficiency=Dp/E凶] Where TO= DTp in a full duplex system To= Sin a half duplex system
Stop and wait in the presence of errors Let P = the probability of an error in the transmission of a packet or in its acknowledgment S = DTP + 2D P + 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 E[X] = S + TO*P/(1-P), Efficiency = DTP/E[X] Where, TO = DTP in a full duplex system TO = S in a half duplex system
Go Back N ARQ (Sliding Window) Stop and Wait is inefficient when propagation delay is larger than the packet transmission time Can only send one packet per round-trip time Go Back n allows the transmission of new packets before earlier ones are acknowledged Go back n uses a window mechanism where the sender can send packets that are within a"window(range)of packets The window advances as acknowledgements for earlier packets are received WINDOW WINDOW WINDOW WINDOW PKT-o PKT-2 PKT-3 PKT-4 PKT-5PKT-6 PKT-7 PKT- PKT-9 入 AcK-olAcK-1 ACK-2 ACK-3 ACK-4ACK-5lACK-6 ACK-7AcK-8I
Go Back N ARQ (Sliding Window) • Stop and Wait is inefficient when propagation delay is larger than the packet transmission time – Can only send one packet per round-trip time • Go Back N allows the transmission of new packets before earlier ones are acknowledged • Go back N uses a window mechanism where the sender can send packets that are within a “window” (range) of packets – The window advances as acknowledgements for earlier packets are received PKT-0 PKT-1 PKT-2 PKT-3 PKT-4 PKT-5 PKT-6 PKT-7 PKT-8 PKT-9 ACK-0 ACK-1 ACK-2 ACK-3 ACK-4 ACK-5 ACK-6 ACK-7 ACK-8 WINDOW WINDOW WINDOW WINDOW
Features of go back N Window size= n Sender cannot send packet i+N until it has received the ACK for packet i Receiver operates just like in Stop and Wait Receive 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 RN's are piggybacked on packets going in the other direction Each packet contains a SN field indicating that packet's sequence number and a RN field acknowledging packets in the other direction SN RN Packet CRC
Features of Go Back N • Window size = N – Sender cannot send packet i+N until it has received the ACK for packet i • Receiver operates just like in Stop and Wait – Receive 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 RN’s are piggybacked on packets going in the other direction Each packet contains a SN field indicating that packet’s sequence number and a RN field acknowledging packets in the other direction SN RN Packet CRC