OneNoughtOne
0/240
Loading content...
Read aloud is unavailable in this browser.
In network protocol design, reliability doesn't come in one flavor. The three pillars of Automatic Repeat Request (ARQ)—Stop-and-Wait, Go-Back-N, and Selective Repeat—represent fundamentally different philosophies for achieving reliable data transfer over unreliable channels. Each makes distinct tradeoffs between simplicity, efficiency, and resource requirements.
A protocol that excels on a low-latency Ethernet LAN may perform catastrophically on a high-latency satellite link. A mechanism optimal for a resource-constrained embedded system may waste capacity on a modern server with gigabytes of available memory. Understanding these tradeoffs is not merely academic—it directly impacts the performance, cost, and reliability of the systems you design and deploy.
By the end of this page, you will understand the fundamental operational differences between Stop-and-Wait, Go-Back-N, and Selective Repeat ARQ. You'll be able to articulate their distinct approaches to acknowledgments, retransmission, buffering, and window management—establishing the foundation for deeper efficiency and complexity analysis.
Before diving into comparisons, let's establish the common foundation that unites all ARQ protocols. Despite their differences, Stop-and-Wait, Go-Back-N, and Selective Repeat share a fundamental objective: transform an unreliable channel into a reliable one through controlled redundancy and retransmission.
The Universal ARQ Mechanism:
Every ARQ protocol implements the same basic loop:
The protocols differ in how they execute each step—how many frames can be outstanding, how acknowledgments are structured, what happens after an error, and what resources are required at each endpoint.
The Evolutionary Progression:
The three protocols evolved to address increasingly sophisticated optimization goals:
Stop-and-Wait (SW) represents the simplest possible ARQ implementation. It prioritizes correctness and minimal complexity over efficiency. You can implement it with almost no state: just remember which sequence number you're expecting next.
Go-Back-N (GBN) introduces pipelining to dramatically improve efficiency. The sender can transmit multiple frames before waiting for acknowledgments, but error recovery remains simple: discard everything after an error and retransmit from the failure point.
Selective Repeat (SR) achieves maximum efficiency by retransmitting only the specific frames that failed. This requires significant receiver-side buffering and complexity, but minimizes wasted bandwidth on retransmissions.
Think of these protocols as points on a spectrum. At one end, Stop-and-Wait offers simplicity at the cost of efficiency. At the other, Selective Repeat offers efficiency at the cost of complexity. Go-Back-N sits in the middle, offering good efficiency with moderate complexity. No protocol is universally 'best'—the optimal choice depends on channel characteristics and system constraints.
Stop-and-Wait ARQ is the simplest reliable protocol. Its operation can be stated in one sentence: Send one frame, wait for its acknowledgment, then send the next frame. This simplicity makes it an excellent pedagogical starting point and a practical choice for extremely constrained systems.
Operational Mechanics:
Why Only Two Sequence Numbers?
Stop-and-Wait needs only 1 bit for sequence numbers (values 0 and 1). This suffices because only one frame can ever be outstanding. The receiver only needs to distinguish between:
With only one frame in-flight, there's no ambiguity that would require larger sequence numbers.
State Requirements:
| Entity | State Required | Memory Impact |
|---|---|---|
| Sender | Next sequence number to send (1 bit) | Negligible |
| Sender | Copy of current frame for retransmission | One frame buffer |
| Sender | Timer state for retransmission timeout | Minimal |
| Receiver | Expected sequence number (1 bit) | Negligible |
| Receiver | No buffering required | Zero overhead |
Stop-and-Wait can be implemented in a few dozen lines of code with minimal memory. This makes it ideal for embedded systems, bootloader protocols, and educational purposes. The protocol is also naturally self-clocking—each acknowledgment acts as implicit flow control, preventing buffer overflow at the receiver.
The Fundamental Limitation:
Stop-and-Wait's fatal flaw is its inability to utilize the channel during round-trip time. Consider the math:
$$\text{Utilization} = \frac{T_{frame}}{T_{frame} + 2 \times T_{prop}}$$
For a 1 Mbps link with 1000-bit frames and 100ms propagation delay:
The channel sits idle 99.5% of the time, waiting for acknowledgments. This inefficiency becomes catastrophic as the bandwidth-delay product increases.
Go-Back-N ARQ dramatically improves efficiency by allowing multiple frames to be in-flight simultaneously. The sender maintains a sliding window of frames that can be transmitted before waiting for acknowledgments. This pipelining fills the channel during round-trip time, approaching full utilization.
Operational Mechanics:
Go-Back-N permits up to N frames (the window size) to be outstanding simultaneously. However, its error recovery is aggressive: upon detecting an error, all frames from the error point onward are discarded and must be retransmitted, even if some were received correctly.
The "Go Back" in Go-Back-N:
The protocol's name reveals its error recovery strategy. If frame 3 is lost but frames 4, 5, 6 arrive correctly, the receiver discards frames 4, 5, 6 (they arrived out of order). The sender's timer for frame 3 expires, and it must "go back" to frame 3 and retransmit everything: 3, 4, 5, 6, and any subsequent frames.
This seems wasteful—and it is! The correctly-received frames 4, 5, 6 are thrown away and retransmitted. But this design choice enables a crucial simplification: the receiver needs no buffer for out-of-order frames.
Sequence Number Space:
Go-Back-N requires more sequence numbers than Stop-and-Wait. With window size N, we need at least N+1 sequence numbers. The constraint is:
$$\text{Sequence numbers} \geq N + 1$$
Or equivalently, with k-bit sequence numbers (values 0 to 2^k - 1):
$$N \leq 2^k - 1$$
This prevents ambiguity when the window wraps around. If sequence numbers 0-7 are used (k=3) and window size is 7, the sender could have frames 0,1,2,3,4,5,6 outstanding. When the receiver ACKs frame 6 and expects frame 7 next, new frame 0 from the next cycle is distinguishable from old frame 0.
| Entity | State Required | Memory Impact |
|---|---|---|
| Sender | Window bounds: send_base, next_seqnum | Two integers |
| Sender | Buffer for all frames in window | N frame buffers |
| Sender | Timer for oldest unacknowledged frame | One timer |
| Receiver | Expected sequence number | One integer |
| Receiver | No buffering required | Zero overhead |
Go-Back-N trades bandwidth for receiver simplicity. The receiver needs almost no memory or state—it just tracks which sequence number comes next and discards anything else. This was crucial in early networks where receivers (e.g., terminals) had extremely limited resources. The cost is paid in retransmission bandwidth, which is acceptable when error rates are low.
Selective Repeat ARQ achieves the highest efficiency by retransmitting only the specific frames that were lost or corrupted. Unlike Go-Back-N, correctly received out-of-order frames are buffered at the receiver and delivered in order once the missing frames arrive.
Operational Mechanics:
Selective Repeat maintains sliding windows at both sender and receiver. The receiver window allows frames to arrive out of order and be held until gaps are filled. The sender retransmits only specific frames for which acknowledgments haven't arrived.
The Selective Advantage:
Imagine frame 3 is lost but frames 4, 5, 6 arrive correctly. With Selective Repeat:
Compare to Go-Back-N where frames 4, 5, 6 would be discarded and retransmitted unnecessarily.
Sequence Number Space Constraint:
Selective Repeat has a stricter sequence number requirement than Go-Back-N:
$$\text{Sequence numbers} \geq 2N$$
Or with k-bit sequence numbers:
$$N \leq 2^{k-1}$$
Why the stricter requirement? With both sender and receiver windows of size N, we must ensure that the sender's window and receiver's window never overlap in the sequence number space. If they could overlap, an old frame might be mistaken for a new frame (or vice versa) after sequence number wraparound.
| Entity | State Required | Memory Impact |
|---|---|---|
| Sender | Window bounds: send_base, next_seqnum | Two integers |
| Sender | Buffer for all frames in window | N frame buffers |
| Sender | Individual timer for each outstanding frame | N timers |
| Sender | ACK status for each frame in window | N bits/flags |
| Receiver | Window bounds: rcv_base | One integer |
| Receiver | Buffer for out-of-order frames | N frame buffers |
| Receiver | Received status for each position in window | N bits/flags |
Selective Repeat achieves efficiency by shifting complexity to the receiver. The receiver must buffer frames, track which positions have been filled, and manage reordering. This requires memory proportional to the window size—a significant cost in resource-constrained environments but negligible on modern systems with abundant RAM.
Let's consolidate the operational differences in a comprehensive comparison. Understanding these distinctions is fundamental to selecting the right protocol for a given scenario.
| Characteristic | Stop-and-Wait | Go-Back-N | Selective Repeat |
|---|---|---|---|
| Maximum Outstanding Frames | 1 | N (window size) | N (window size) |
| Sender Window Size | 1 | N | N |
| Receiver Window Size | 1 | 1 | N |
| Sequence Numbers Required | 2 (1 bit) | N+1 (⌈log₂(N+1)⌉ bits) | 2N (⌈log₂(2N)⌉ bits) |
| ACK Type | Individual | Cumulative | Individual |
| Out-of-Order Handling | N/A (only 1 frame) | Discard and re-ACK | Buffer and ACK |
| Retransmission Scope | Single frame | Frame + all subsequent | Single frame |
| Receiver Buffering | None | None | Up to N frames |
| Sender Timers | 1 | 1 (for oldest) | N (one per frame) |
| Reordering at Receiver | Not needed | Not needed | Required |
Acknowledgment Philosophy:
The three protocols take fundamentally different approaches to acknowledgments:
Stop-and-Wait: Simple ACK
Go-Back-N: Cumulative ACK
Selective Repeat: Individual (Selective) ACK
Real protocols often combine features. TCP uses cumulative ACKs (like GBN) but also supports Selective Acknowledgment (SACK) options that allow reporting out-of-order segments, combining Go-Back-N's simplicity with Selective Repeat's efficiency when the SACK option is negotiated.
The most illuminating way to understand protocol differences is to trace their behavior through specific error scenarios. Let's analyze how each protocol handles a lost frame.
Scenario: Frame 2 Lost, Window Size = 4
Assume the sender transmits frames 0, 1, 2, 3, 4, 5 and frame 2 is lost in transit.
Stop-and-Wait Recovery (Window = 1):
Time Event
──────────────────────────────────────────────
t1 Sender: Send frame 0
t2 Receiver: Receive frame 0, send ACK 0
t3 Sender: Receive ACK 0, send frame 1
t4 Receiver: Receive frame 1, send ACK 1
t5 Sender: Receive ACK 1, send frame 2
t6 [FRAME 2 LOST IN TRANSIT]
t7 Sender: Timer expires for frame 2
t8 Sender: Retransmit frame 2
t9 Receiver: Receive frame 2, send ACK 2
t10 Sender: Receive ACK 2, send frame 3
... continues normally ...
Analysis:
Stop-and-Wait has no 'wasted' retransmissions because there are never correctly-received frames waiting. The inefficiency is in the normal operation, not error recovery.
The difference between GBN and SR is dramatic when errors are frequent. If 10% of frames are lost, GBN might retransmit up to 4× the original data (each error triggers window-size retransmissions), while SR only retransmits ~10% extra. But if errors are rare (0.1%), GBN wastes little bandwidth and its simplicity wins.
The relationship between window size and sequence number space is a critical protocol design consideration. Getting it wrong causes catastrophic failures—frames accepted as valid that are actually duplicates from previous transmissions.
The Ambiguity Problem:
Sequence numbers are finite. After transmitting frame 7 (if using 3-bit sequence numbers), the next frame is frame 0 again. If windows are too large relative to sequence number space, old frames from previous windows become indistinguishable from new frames.
Derivation of Constraints:
| Sequence Bits (k) | Sequence Space (2^k) | Max Window (GBN) | Max Window (SR) |
|---|---|---|---|
| 1 | 2 | 1 | 1 |
| 2 | 4 | 3 | 2 |
| 3 | 8 | 7 | 4 |
| 4 | 16 | 15 | 8 |
| 5 | 32 | 31 | 16 |
| 8 | 256 | 255 | 128 |
| 16 | 65,536 | 65,535 | 32,768 |
| 32 | 4,294,967,296 | ~4.3 billion | ~2.1 billion |
Violating sequence number constraints doesn't cause obvious failures—it creates silent data corruption. The receiver might accept an old, retransmitted frame as a new frame, delivering duplicate data or data from the wrong position. These errors are extremely difficult to debug because they appear random and may only occur under specific loss patterns.
Practical Protocol Examples:
We've established the fundamental operational differences between the three ARQ protocols. Each represents a distinct philosophy for achieving reliable transmission:
What's Next:
With the operational fundamentals established, we'll quantify the efficiency differences. The next page derives and compares utilization formulas for all three protocols, showing mathematically when each protocol is optimal based on bandwidth-delay product and error rates.
You now understand the fundamental operational differences between Stop-and-Wait, Go-Back-N, and Selective Repeat ARQ protocols. You can articulate how each handles acknowledgments, error recovery, buffering, and window management. Next, we'll put numbers to these differences with rigorous efficiency analysis.