Sliding Window Sizing: Why Go-Back-N and Selective Repeat Limit Window Sizes

Sliding window protocols allow transmitters to pipeline multiple unacknowledged frames, saturating links governed by the Bandwidth-Delay Product.

However, sequence numbers cannot grow indefinitely; they are encoded in an m-bit header field, providing a finite sequence space of 2^m unique IDs (modulo 2^m).

A fundamental question arises: Why can't we size the sender window W_s to match the full sequence space 2^m?

---

1. Go-Back-N ARQ: W_s ≤ 2^m - 1

In Go-Back-N, the receiver maintains a window of size W_r = 1. It accepts only the exact next in-order frame and discards any out-of-order packets.

The Ambiguity Proof (Why W_s = 2^m Fails):

Assume m = 2, giving sequence numbers \0, 1, 2, 3\. Suppose we set W_s = 4:

1. Sender transmits frames 0, 1, 2, 3.
2. The receiver successfully receives all four frames, slides its expected sequence counter from 0 → 1 → 2 → 3 → 0, and sends acknowledgments.
3. Disaster Scenario: Every ACK is lost in transit.
4. The sender's retransmission timer fires for frame $0$ and retransmits it.
5. The receiver is currently expecting sequence number $0$ (from the next cycle). It accepts the duplicate frame $0$ as fresh data!

To eliminate this ambiguity, the window size must leave at least one sequence number unallocated:

W_s ≤ 2^m - 1

---

2. Selective Repeat ARQ: W_s + W_r ≤ 2^m

In Selective Repeat, the receiver independently acknowledges frames and buffers out-of-order packets. To maximize symmetrical pipelining, W_s = W_r.

The Ambiguity Constraint:

When all ACKs are lost, the sender retransmits its oldest unacknowledged window. For the receiver to distinguish between a retransmitted old packet and a legitimate new packet across the modular boundary:

W_s + W_r ≤ 2^m

Since W_s = W_r:

2 · W_s ≤ 2^m implies W_s ≤ 2^m-1

The maximum sender window size in Selective Repeat is half the total sequence number space.

Explore interactive space-time protocol ladders at Binary Dose.