Loading learning content...
The previous pages covered the components of error control: detection techniques, correction codes, and retransmission mechanisms. Now we assemble these components into complete protocols—systematic procedures that transform unreliable physical channels into reliable data links.
Automatic Repeat Request (ARQ) is the protocol family that uses error detection and retransmission to achieve reliable delivery. Unlike Forward Error Correction which corrects errors without feedback, ARQ protocols explicitly request retransmission when errors occur.
Three fundamental ARQ protocols form the basis of virtually all reliable communication systems:
Understanding these protocols deeply—their operation, efficiency, tradeoffs, and implementation—is essential for network engineers.
This page covers the three fundamental ARQ protocols in depth: their operation under normal and error conditions, efficiency analysis, sequence number requirements, implementation considerations, and comparisons. You'll understand when to use each and why.
Stop-and-Wait is the simplest reliable protocol. The sender transmits one frame and waits for acknowledgment before sending the next. Despite its simplicity, it correctly handles all error scenarios.
Basic Operation:
Sequence Number Requirement:
Only 1 bit (values 0 and 1) is needed:
NORMAL OPERATION (No Errors): Sender Receiver────── ────────Send Frame 0 ─────────────────→ Receive, deliverStart timer Send ACK 0 ←───────────────── Stop timer, advance Send Frame 1 ─────────────────→ Receive, deliverStart timer Send ACK 1 ←─────────────────Stop timer, advanceSend Frame 0 ─────────────────→ ... LOST FRAME: Sender Receiver────── ────────Send Frame 0 ─────────X (never arrives)Start timer (waiting...) (nothing to receive)TIMEOUT!Retransmit 0 ─────────────────→ Receive, deliverStart timer Send ACK 0 ←─────────────────Stop timer, advance LOST ACK: Sender Receiver────── ────────Send Frame 0 ─────────────────→ Receive, deliverStart timer expect = 1 Send ACK 0 ←─────────X (ACK lost)TIMEOUT!Retransmit 0 ─────────────────→ Receive Frame 0Start timer seq=0 ≠ expect=1 DUPLICATE! Discard Re-send ACK 0 ←─────────────────Stop timer, advanceSend Frame 1 ─────────────────→ ...Stop-and-Wait's correctness comes from its simplicity: only one frame is ever 'in flight'. The sender knows exactly which frame the receiver is expecting. If anything goes wrong (frame lost, ACK lost, corruption), the timeout triggers retransmission of the one outstanding frame. Sequence numbers distinguish new frames from duplicates.
Stop-and-Wait is simple but potentially very inefficient. The sender idles while waiting for acknowledgment, wasting channel capacity on high-latency links.
Efficiency Derivation:
Consider a link with:
Transmission time: T_tx = L / B Total cycle time: T_cycle = T_tx + RTT = L/B + RTT
Efficiency (utilization): $$U = \frac{T_{tx}}{T_{cycle}} = \frac{L/B}{L/B + RTT} = \frac{1}{1 + \frac{B \times RTT}{L}} = \frac{1}{1 + 2a}$$
where a = propagation delay / transmission time = (RTT/2) × B / L
| Link Type | Bandwidth | RTT | Frame Size | a | Utilization |
|---|---|---|---|---|---|
| LAN Ethernet | 1 Gbps | 0.1 ms | 1500 B | 4.2 | 10.7% |
| Metro fiber | 10 Gbps | 1 ms | 1500 B | 417 | 0.12% |
| Satellite | 10 Mbps | 500 ms | 1500 B | 208 | 0.24% |
| 10Base2 Ethernet (classic) | 10 Mbps | 0.05 ms | 1500 B | 0.02 | 96% |
The Bandwidth-Delay Product Problem:
The term B × RTT is called the bandwidth-delay product (BDP)—the amount of data 'in flight' to fill the pipe. Stop-and-Wait only keeps L bits in flight, so:
Numerical Example:
1 Gbps link, 100 km fiber (RTT ≈ 1 ms), 1500-byte frames:
The sender is idle 98.8% of the time. This is why pipelining (sliding window protocols) is essential for high-speed, long-distance links.
Stop-and-Wait works well when RTT is very short relative to transmission time—legacy low-speed links where a >> 1. It's also acceptable for very low-bandwidth requirements where efficiency doesn't matter. Its simplicity makes it ideal for teaching and for protocols where reliability matters more than throughput (e.g., TFTP).
To overcome Stop-and-Wait's efficiency problem, we allow multiple frames to be outstanding simultaneously. The sliding window mechanism controls how many unacknowledged frames can be in flight.
Window Concept:
A window is a range of sequence numbers that the sender is allowed to transmit without waiting for acknowledgment. As ACKs arrive, the window 'slides' forward, allowing more frames to be sent.
Window Size (W):
Optimal Window Size:
To fully utilize the link, window must cover the bandwidth-delay product: $$W_{optimal} = \lceil BDP / L \rceil + 1 = \lceil \frac{B \times RTT}{L} \rceil + 1$$
Sliding Window with W=4, sequence numbers 0-7: Initial State:Sequence: 0 1 2 3 4 5 6 7 ┌───┬───┬───┬───┬───────────────┐Sender: │ ← S E N D → │ cannot send │ └───┴───┴───┴───┴───────────────┘ ↑ ↑ base=0 base+W-1=3 After sending 0,1,2,3 and receiving ACK for 0,1: Sequence: 0 1 2 3 4 5 6 7 ┌───────┬───────────────┬───────┐Sender: │ ACKed │ ← S E N D → │ can't │ └───────┴───────────────┴───────┘ ↑ ↑ base=2 base+W-1=5 Key State Variables:- base: First unacknowledged frame (left edge of window)- nextseqnum: Next frame to send- Window: [base, base + W - 1] Send Condition: nextseqnum < base + WAdvance Condition: ACK(n) received → base = n + 1 (cumulative ACK) or base = n (individual ACK)With window size W: Utilization = W / (1 + 2a) for W ≤ 1 + 2a, or 100% for W > 1 + 2a. With optimal window size, we achieve full link utilization. The window essentially keeps the pipe full of data, eliminating idle time.
Go-Back-N (GBN) is a sliding window protocol where the sender can transmit multiple frames, but the receiver only accepts frames in order. On detecting a lost or corrupted frame, the sender must 'go back' and retransmit that frame and all subsequent frames.
Key Characteristics:
Sender Behavior:
Receiver Behavior:
Go-Back-N with Window Size 4: Normal Operation (no errors):Sender Receiver (expects next only)────── ────────Send 0 ───────────────────────────→ Rcv 0, deliver, ACK 0Send 1 ───────────────────────────→ Rcv 1, deliver, ACK 1Send 2 ───────────────────────────→ Rcv 2, deliver, ACK 2Send 3 ───────────────────────────→ Rcv 3, deliver, ACK 3 ←─────────────────────────── ACK 3 (cumulative)Send 4,5,6,7 ... Error Recovery (frame 2 lost):Sender Receiver (expects 2)────── ────────Send 0 ───────────────────────────→ Rcv 0, ACK 0, expect 1Send 1 ───────────────────────────→ Rcv 1, ACK 1, expect 2Send 2 ─────────────X (lost - never arrives)Send 3 ───────────────────────────→ Rcv 3, but expect 2! DISCARD! Re-send ACK 1Send 4 ───────────────────────────→ Rcv 4, but expect 2! DISCARD! Re-send ACK 1Send 5 ───────────────────────────→ Rcv 5, but expect 2! DISCARD! Re-send ACK 1 ←─────────────────────────── (duplicate ACK 1s arrive)TIMEOUT on frame 2!GO BACK to 2, retransmit 2,3,4,5...Send 2 ───────────────────────────→ Rcv 2, ACK 2, expect 3Send 3 ───────────────────────────→ Rcv 3, ACK 3, expect 4Send 4 ───────────────────────────→ Rcv 4, ACK 4, expect 5Send 5 ───────────────────────────→ Rcv 5, ACK 5, expect 6... Wasted bandwidth: frames 3,4,5 were transmitted and received correctly but had to be retransmitted!When frame N is lost, frames N+1, N+2, ..., N+W-1 are sent but discarded by the receiver. Then ALL must be retransmitted. With window size 127 and one lost frame, up to 126 correctly received frames are thrown away. GBN works well with low error rates but degrades significantly on noisy links.
Implementing Go-Back-N requires careful handling of timers, buffers, and sequence number management. Here's a complete implementation:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134
import threadingimport timefrom typing import Callable, Optional, List class GoBackNSender: """ Go-Back-N ARQ sender implementation. """ def __init__(self, window_size: int, seq_bits: int, timeout_sec: float, send_func: Callable): self.window_size = window_size self.seq_modulo = 1 << seq_bits # 2^seq_bits self.timeout = timeout_sec self.send_func = send_func # State variables self.base = 0 # Oldest unACKed sequence number self.nextseqnum = 0 # Next sequence number to use self.buffer = {} # seq -> frame data (for retransmission) # Synchronization self.lock = threading.Lock() self.timer = None self.timer_running = False def send(self, data: bytes) -> bool: """ Send a frame with the given data. Returns True if sent, False if window full. """ with self.lock: # Check if window allows sending if self._in_window(self.nextseqnum): seq = self.nextseqnum self.buffer[seq] = data self.nextseqnum = (self.nextseqnum + 1) % self.seq_modulo # Transmit frame self.send_func(seq, data) # Start timer if this is the first frame in window if self.base == seq: self._start_timer() return True else: return False # Window full, caller should wait def receive_ack(self, ack_seq: int): """ Process incoming cumulative ACK. ACK(n) means all frames up to n have been received. """ with self.lock: # Cumulative ACK: acknowledge all frames up to ack_seq while self.base != (ack_seq + 1) % self.seq_modulo: if self.base in self.buffer: del self.buffer[self.base] self.base = (self.base + 1) % self.seq_modulo # Restart timer if frames still outstanding self._stop_timer() if self.base != self.nextseqnum: self._start_timer() def _timeout_handler(self): """Handle timeout: retransmit all outstanding frames.""" with self.lock: self.timer_running = False print(f"TIMEOUT! Go back to {self.base}") # Retransmit all frames from base to nextseqnum-1 seq = self.base while seq != self.nextseqnum: if seq in self.buffer: print(f" Retransmit frame {seq}") self.send_func(seq, self.buffer[seq]) seq = (seq + 1) % self.seq_modulo # Restart timer self._start_timer() def _in_window(self, seq: int) -> bool: """Check if sequence number is within current window.""" # Window: [base, base + window_size - 1] (modulo) distance = (seq - self.base) % self.seq_modulo return distance < self.window_size def _start_timer(self): if self.timer_running: self._stop_timer() self.timer = threading.Timer(self.timeout, self._timeout_handler) self.timer.start() self.timer_running = True def _stop_timer(self): if self.timer and self.timer_running: self.timer.cancel() self.timer_running = False class GoBackNReceiver: """ Go-Back-N ARQ receiver implementation. Accepts only in-order frames. """ def __init__(self, seq_bits: int, deliver_func: Callable, ack_func: Callable): self.seq_modulo = 1 << seq_bits self.deliver_func = deliver_func # Callback to deliver data self.ack_func = ack_func # Callback to send ACK self.expected_seq = 0 def receive(self, seq: int, data: bytes, is_valid: bool): """ Process incoming frame. is_valid indicates whether CRC check passed. """ if not is_valid: # Corrupted frame: send duplicate ACK for last good frame ack_seq = (self.expected_seq - 1) % self.seq_modulo self.ack_func(ack_seq) return if seq == self.expected_seq: # Correct frame: deliver and advance self.deliver_func(data) self.ack_func(seq) self.expected_seq = (self.expected_seq + 1) % self.seq_modulo else: # Out-of-order: discard, resend last ACK ack_seq = (self.expected_seq - 1) % self.seq_modulo self.ack_func(ack_seq)Selective Repeat (SR) improves on Go-Back-N by retransmitting only the frames that are actually lost, not all frames from the loss point. This requires a more complex receiver that buffers out-of-order frames.
Key Characteristics:
Sender Behavior:
Receiver Behavior:
Selective Repeat with Window Size 4: Frame 2 Lost Scenario:Sender Receiver (buffers out-of-order)────── ────────Send 0 ───────────────────────────→ Rcv 0, deliver, ACK 0 expect [1,2,3,4]Send 1 ───────────────────────────→ Rcv 1, deliver, ACK 1 expect [2,3,4,5]Send 2 ─────────────X (lost)Send 3 ───────────────────────────→ Rcv 3, BUFFER (2 missing) ACK 3 (individual) ←─────────────────────────── ACK 3Mark 3 as ACKed expect [2,3,4,5], have 3 bufferedSend 4 ───────────────────────────→ Rcv 4, BUFFER ACK 4 ←─────────────────────────── ACK 4Mark 4 as ACKedSend 5 ───────────────────────────→ Rcv 5, BUFFER ACK 5 ←─────────────────────────── ACK 5Mark 5 as ACKed TIMEOUT on frame 2 only!Retransmit 2 only ─────────────────→ Rcv 2! Deliver 2, then buffered 3,4,5 ACK 2 ←─────────────────────────── ACK 2Window advances to [6,7,0,1] HUGE savings: Only 1 retransmission instead of 4! Comparison:- GBN: Lost frame 2 → retransmit 2,3,4,5 (4 frames)- SR: Lost frame 2 → retransmit 2 only (1 frame)| Scenario | Problem If Violation |
|---|---|
| W > 2^k / 2 | Sender window [0..W-1] and receiver window [W..2W-1] can OVERLAP after ACKs lost, causing ambiguity |
| W ≤ 2^(k-1) | Sender and receiver windows cannot overlap—old frame 0 vs new frame 0 always distinguishable |
| Example: 3-bit seq (0-7), W=4 | Safe: max windows [0,1,2,3] and [4,5,6,7] don't overlap |
| Example: 3-bit seq (0-7), W=5 | UNSAFE: [0,1,2,3,4] and [5,6,7,0,1] overlap at 0 and 1! |
Selective Repeat shines on lossy channels: each lost frame costs one retransmission, not W. But SR is more complex: receiver needs buffering and out-of-order assembly, sender needs per-frame timers and individual ACK tracking. For low-loss channels (wired links), GBN's simplicity may be preferable. For wireless or satellite, SR's efficiency is essential.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130
import threadingfrom typing import Callable, Dict, Optional class SelectiveRepeatSender: """ Selective Repeat ARQ sender implementation. Uses per-frame timers and individual ACKs. """ def __init__(self, window_size: int, seq_bits: int, timeout_sec: float, send_func: Callable): self.window_size = window_size self.seq_modulo = 1 << seq_bits self.timeout = timeout_sec self.send_func = send_func # State self.base = 0 self.nextseqnum = 0 self.buffer: Dict[int, bytes] = {} # seq -> data self.acked: Dict[int, bool] = {} # seq -> acknowledged? self.timers: Dict[int, threading.Timer] = {} self.lock = threading.Lock() def send(self, data: bytes) -> bool: """Send a frame. Returns False if window full.""" with self.lock: if not self._in_window(self.nextseqnum): return False seq = self.nextseqnum self.buffer[seq] = data self.acked[seq] = False self.nextseqnum = (self.nextseqnum + 1) % self.seq_modulo self.send_func(seq, data) self._start_timer(seq) return True def receive_ack(self, ack_seq: int): """Process individual ACK for frame ack_seq.""" with self.lock: if not self._in_window(ack_seq): return # Duplicate or stale ACK self.acked[ack_seq] = True self._stop_timer(ack_seq) # Advance base over consecutively ACKed frames while self.base in self.acked and self.acked[self.base]: del self.buffer[self.base] del self.acked[self.base] self.base = (self.base + 1) % self.seq_modulo def _timeout_handler(self, seq: int): """Timeout for specific frame: retransmit only that frame.""" with self.lock: if seq in self.buffer and not self.acked.get(seq, True): print(f"Timeout frame {seq}, retransmitting") self.send_func(seq, self.buffer[seq]) self._start_timer(seq) def _in_window(self, seq: int) -> bool: distance = (seq - self.base) % self.seq_modulo return distance < self.window_size def _start_timer(self, seq: int): self._stop_timer(seq) timer = threading.Timer(self.timeout, self._timeout_handler, args=[seq]) timer.start() self.timers[seq] = timer def _stop_timer(self, seq: int): if seq in self.timers: self.timers[seq].cancel() del self.timers[seq] class SelectiveRepeatReceiver: """ Selective Repeat ARQ receiver implementation. Buffers out-of-order frames and delivers in sequence. """ def __init__(self, window_size: int, seq_bits: int, deliver_func: Callable, ack_func: Callable): self.window_size = window_size self.seq_modulo = 1 << seq_bits self.deliver_func = deliver_func self.ack_func = ack_func self.rcv_base = 0 self.buffer: Dict[int, bytes] = {} # Buffered out-of-order frames self.received: Dict[int, bool] = {} # Track what we have def receive(self, seq: int, data: bytes, is_valid: bool): """Process incoming frame.""" if not is_valid: return # Corrupted, don't ACK, let sender timeout # Check if in current window if self._in_window(seq): if seq not in self.received or not self.received[seq]: self.buffer[seq] = data self.received[seq] = True # Always ACK frames in window self.ack_func(seq) # Deliver consecutive frames from rcv_base while self.rcv_base in self.received and self.received[self.rcv_base]: self.deliver_func(self.buffer[self.rcv_base]) del self.buffer[self.rcv_base] del self.received[self.rcv_base] self.rcv_base = (self.rcv_base + 1) % self.seq_modulo elif self._in_prev_window(seq): # Old frame (duplicate from retransmission due to lost ACK) # Re-ACK to let sender know self.ack_func(seq) # Else: frame too far ahead, discard silently def _in_window(self, seq: int) -> bool: distance = (seq - self.rcv_base) % self.seq_modulo return distance < self.window_size def _in_prev_window(self, seq: int) -> bool: # Previous window: [rcv_base - W, rcv_base - 1] distance = (self.rcv_base - seq) % self.seq_modulo return 0 < distance <= self.window_size| Feature | Stop-and-Wait | Go-Back-N | Selective Repeat |
|---|---|---|---|
| Sender window | 1 | N | N |
| Receiver window | 1 | 1 | N |
| Sequence space | ≥ 2 | ≥ N + 1 | ≥ 2N |
| ACK type | Individual | Cumulative | Individual |
| Timers needed | 1 | 1 | N |
| Receiver buffering | No | No | Yes (W frames) |
| Retransmit on loss | 1 frame | All from loss | Only lost frame |
| Implementation | Trivial | Moderate | Complex |
| Efficiency (no loss) | 1/(1+2a) | N/(1+2a) | N/(1+2a) |
| Efficiency (high loss) | Very poor | Poor | Good |
Efficiency Under Errors:
Consider frame error probability P_e:
Stop-and-Wait: Each frame requires on average 1/(1-P_e) transmissions
Go-Back-N: Lost frame triggers W retransmissions on average
Selective Repeat: Each lost frame requires only 1 retransmission
The High-level Data Link Control (HDLC) protocol family implements these ARQ variants: Normal Response Mode (NRM) uses variations of GBN; Asynchronous Balanced Mode (ABM) supports both. PPP (Point-to-Point Protocol) uses HDLC framing with optional ARQ. These real-world protocols add features like piggybacking, connection management, and flow control on top of basic ARQ.
We've completed our comprehensive study of Automatic Repeat Request protocols—the cornerstone of reliable communication at the Data Link Layer and beyond.
Module Complete:
You have now mastered Error Control at the Data Link Layer—from the fundamental need for error management, through detection and correction techniques, to the complete ARQ protocols that implement reliable communication. These concepts form the foundation for understanding reliability throughout the protocol stack.
Congratulations! You've completed the Error Control module. You now understand: why error control is essential (physical channels are noisy), how to detect errors (CRC, checksums), how to correct errors (Hamming, Reed-Solomon, LDPC), retransmission mechanics (ACKs, timeouts, sequence numbers), and complete ARQ protocols (Stop-and-Wait, Go-Back-N, Selective Repeat). This knowledge is fundamental to computer networks and will serve you throughout your networking career.