ARQ Protocol Comparison: Stop-and-Wait, Go-Back-N, and Selective Repeat

Understanding ARQ protocol behavior is essential, but engineers need numbers. How much faster is Go-Back-N than Stop-and-Wait on a satellite link? At what error rate does Selective Repeat's complexity become worthwhile? When does pipelining stop helping?

This page develops the mathematical framework for answering these questions rigorously. We'll derive utilization formulas, analyze their behavior across different channel conditions, and establish quantitative guidelines for protocol selection.

Before diving into formulas, we must establish precise definitions. Several related but distinct metrics quantify protocol performance.

Channel Utilization (η):

The fraction of time the channel is used for transmitting useful (non-retransmitted) data:

$$\eta = \frac{\text{Time spent sending useful data}}{\text{Total time}}$$

Throughput (S):

The rate at which useful data is successfully delivered. Throughput equals channel capacity multiplied by utilization:

$$S = \eta \times C$$

where C is the channel capacity in bits per second.

Key Parameters:

To analyze efficiency, we need these fundamental quantities:

The Critical Parameter: a (Bandwidth-Delay Product Ratio)

The parameter a = t_p / t_f is the most important single number for protocol comparison. It represents how many frames could be "in flight" if we could transmit continuously:

• a << 1: Frame transmission time dominates. The channel is nearly done sending the frame before propagation begins. Stop-and-Wait works fine.
• a ≈ 1: Transmission and propagation are comparable. Pipelining helps significantly.
• a >> 1: Propagation dominates. The frame arrives at the receiver long after transmission completes. Without pipelining, utilization is terrible.

The bandwidth-delay product itself is C × t_p (bits), representing the "capacity" of the pipe. The ratio a normalizes this by frame size.

Error-Free Channel:

In the ideal case with no errors, Stop-and-Wait's efficiency depends only on the relationship between transmission time and round-trip time.

Timeline for one frame cycle:

1. Sender transmits frame: t_f time units
2. Frame propagates to receiver: t_p time units
3. Receiver processes and sends ACK: ~0 (negligible)
4. ACK propagates back: t_p time units
5. Sender ready for next frame

Total cycle time: t_f + 2·t_p = t_f + RTT

Useful transmission time: t_f

Utilization (error-free):

$$\eta_{SW} = \frac{t_f}{t_f + 2 \cdot t_p} = \frac{1}{1 + 2a}$$

where a = t_p / t_f

With Frame Errors (Probability p):

When frames can be lost or corrupted with probability p, efficiency decreases further. Each frame may require multiple transmission attempts.

Expected transmissions per successful delivery: 1/(1-p)

Modified utilization:

$$\eta_{SW} = \frac{1 - p}{1 + 2a}$$

This assumes ACKs are never lost. With ACK loss probability q:

$$\eta_{SW} = \frac{(1 - p)(1 - q)}{1 + 2a}$$

Numerical Example:

Channel capacity: 1 Mbps = 10⁶ bps Frame size: 1000 bits Propagation delay: 50 ms Frame error rate: 0.1% (p = 0.001)

Step 1: Calculate t_f $$t_f = \frac{1000 \text{ bits}}{10^6 \text{ bps}} = 0.001 \text{ s} = 1 \text{ ms}$$

Step 2: Calculate a $$a = \frac{t_p}{t_f} = \frac{50 \text{ ms}}{1 \text{ ms}} = 50$$

Step 3: Calculate utilization $$\eta_{SW} = \frac{1 - 0.001}{1 + 2(50)} = \frac{0.999}{101} \approx 0.0099 = 0.99%$$

Step 4: Calculate throughput $$S = \eta \times C = 0.0099 \times 10^6 = 9,900 \text{ bps} \approx 10 \text{ Kbps}$$

Despite a 1 Mbps channel, effective throughput is only 10 Kbps—a 99% waste!

Go-Back-N dramatically improves efficiency by allowing up to N frames to be outstanding. If N is chosen correctly, the sender can transmit continuously, filling the pipeline.

Error-Free Channel:

Case 1: N ≥ 1 + 2a (Window large enough to fill the pipe)

The sender can always have a frame in transmission. During the time it takes for a frame and ACK to round-trip (t_f + 2t_p), the sender transmits (1 + 2a) frames. If window size N ≥ 1 + 2a, transmission is continuous.

$$\eta_{GBN} = 1 \quad \text{when } N \geq 1 + 2a$$

Case 2: N < 1 + 2a (Window too small)

The sender must pause after transmitting N frames, waiting for the first ACK. Utilization is limited by the window.

$$\eta_{GBN} = \frac{N}{1 + 2a} \quad \text{when } N < 1 + 2a$$

With Frame Errors:

Errors hurt Go-Back-N more than they hurt Selective Repeat, because GBN retransmits not just the error frame but all subsequent frames too.

When a frame is lost, the sender eventually times out and retransmits the lost frame plus all frames that were sent after it (up to N-1 additional frames). On average, N/2 frames are retransmitted per error.

Approximate efficiency with errors:

$$\eta_{GBN} \approx \frac{1 - p}{1 + 2a \cdot p \cdot N} \quad \text{when } N \geq 1 + 2a$$

Simplified approximation for high N and moderate errors:

$$\eta_{GBN} \approx \frac{1 - p}{1 + Np}$$

This captures the key insight: each error wastes approximately N frame transmissions.

Numerical Example:

Channel capacity: 1 Mbps Frame size: 1000 bits Propagation delay: 5 ms (t_p) Window size: N = 15 Frame error rate: p = 0.02 (2%)

Step 1: Calculate t_f and a $$t_f = 1 \text{ ms}, \quad a = 5$$

Step 2: Check window adequacy $$1 + 2a = 1 + 10 = 11$$ $$N = 15 \geq 11 \quad \checkmark \text{ (window sufficient)}$$

Step 3: Error-free efficiency $$\eta_{GBN,\text{no error}} = 1 = 100%$$

Step 4: With errors $$\eta_{GBN} \approx \frac{1 - 0.02}{1 + 15 \times 0.02} = \frac{0.98}{1.30} \approx 0.754 = 75.4%$$

Compare to Stop-and-Wait on the same channel: $$\eta_{SW} = \frac{0.98}{11} \approx 8.9%$$

Go-Back-N with N=15 provides 8.5× better throughput than Stop-and-Wait!

Selective Repeat achieves maximum possible efficiency by retransmitting only the frames that fail. This eliminates the N-factor penalty that plagues Go-Back-N under errors.

Error-Free Channel:

Identical to Go-Back-N:

$$\eta_{SR} = \begin{cases} 1 & \text{if } N \geq 1 + 2a \ \frac{N}{1 + 2a} & \text{if } N < 1 + 2a \end{cases}$$

With Frame Errors:

Each frame has probability p of failure. A failed frame is retransmitted once, with probability p of failure again, and so on. The expected number of transmissions per frame is:

$$E[\text{transmissions}] = 1 + p + p^2 + \cdots = \frac{1}{1-p}$$

Utilization with errors:

$$\eta_{SR} = (1 - p) \quad \text{when } N \geq 1 + 2a$$

For the window-limited case:

$$\eta_{SR} = \frac{N(1-p)}{1 + 2a} \quad \text{when } N < 1 + 2a$$

The Selective Repeat Advantage:

Comparing the error-case formulas reveals Selective Repeat's advantage:

Selective Repeat's efficiency is independent of the window size N. Whether N=7 or N=1000, SR's efficiency under errors is simply (1-p). This is optimal—you can't do better than only retransmitting failed frames.

Numerical Example (Comparing All Three):

Channel capacity: 1 Mbps Frame size: 1000 bits Propagation delay: 50 ms Window size: N = 127 Frame error rate: p = 0.05 (5%)

Parameters: $$t_f = 1 \text{ ms}, \quad a = 50, \quad 1 + 2a = 101$$

N = 127 ≥ 101, so window is sufficient.

Stop-and-Wait: $$\eta_{SW} = \frac{1 - 0.05}{1 + 100} = \frac{0.95}{101} = 0.94%$$ $$S_{SW} = 0.0094 \times 10^6 = 9,400 \text{ bps}$$

Go-Back-N: $$\eta_{GBN} = \frac{1 - 0.05}{1 + 127 \times 0.05} = \frac{0.95}{7.35} = 12.9%$$ $$S_{GBN} = 0.129 \times 10^6 = 129,000 \text{ bps}$$

Selective Repeat: $$\eta_{SR} = 1 - 0.05 = 95%$$ $$S_{SR} = 0.95 \times 10^6 = 950,000 \text{ bps}$$

Summary:

The bandwidth-delay product (BDP) quantifies how much data can be "in flight" on a channel. It's perhaps the most important factor in protocol selection.

$$\text{BDP} = C \times RTT = C \times 2t_p \quad \text{(bits)}$$

Alternatively, in terms of frames:

$$\text{BDP (frames)} = \frac{C \times 2t_p}{L} = 2a$$

High BDP Channels:

Channels with large BDP require large windows to achieve good efficiency:

• Satellite links: 500ms RTT × 100 Mbps = 50 Mbit = 50,000 frames of 1000 bits
• Transoceanic fiber: 150ms RTT × 10 Gbps = 1.5 Gbit = 1.5 million frames
• Long-distance WAN: 100ms RTT × 1 Gbps = 100 Mbit = 100,000 frames

Low BDP Channels:

Channels with small BDP need minimal protocol sophistication:

• Local Ethernet: 0.1ms RTT × 1 Gbps = 100 Kbit = 100 frames
• USB connection: 1μs RTT × 480 Mbps = 480 bits < 1 frame
• Embedded bus: ~negligible RTT

The Long Fat Network (LFN) Challenge:

Networks with high bandwidth AND high delay are called "long fat networks" (LFNs) or "fat pipes." These are the most demanding for protocol design:

• Require enormous window sizes
• Require many more sequence number bits
• Require substantial buffer memory
• Selective ACKs become essential
• Single packet loss can be catastrophic to throughput

Example: A Challenging Scenario

10 Gbps link, 100ms RTT (cross-country datacenter):

• BDP = 10 × 10⁹ × 0.1 = 1 Gbit = 125 MB
• With 1500-byte packets: ~83,000 packets in flight
• Sequence numbers: need at least 17 bits for GBN, 18 bits for SR
• Buffer requirement: 125 MB at sender (GBN) and receiver (SR)

This is why TCP's 32-bit sequence numbers (counting bytes) and window scaling are essential for modern high-speed networks.

Visual representations help build intuition about protocol behavior across parameter ranges.

Efficiency vs. 'a' (Error-Free):

Key Observations:

1. Stop-and-Wait degrades immediately as 'a' increases beyond 0
2. GBN and SR are identical when error-free—both achieve full efficiency when N ≥ 1+2a
3. The cliff at N = 1+2a: When a exceeds (N-1)/2, pipelined protocols hit their window limit
4. Linear degradation after the cliff: Efficiency = N/(1+2a) decreases inversely with 'a'

Efficiency vs. Error Rate (a=50, N=127):

Optimal Window Size Selection:

Given the efficiency formulas, we can derive optimal window sizes:

Minimum window for full efficiency (error-free): $$N_{optimal} = \lceil 1 + 2a \rceil$$

For SR with sequence number constraint (k bits): $$N_{max} = 2^{k-1}$$

Rule of thumb:

• Use Stop-and-Wait only if a < 0.1 (transmission time >> propagation time)
• Use Go-Back-N if errors are rare (p < 0.001) and complexity must be low
• Use Selective Repeat if errors are non-trivial (p > 0.001) or on high-value links

This section consolidates all efficiency formulas for quick reference.

What's Next:

Efficiency isn't everything. The next page analyzes the complexity tradeoffs—the implementation cost, state management, memory requirements, and computational overhead that balance against the efficiency gains we've quantified here.