Go-Back-N ARQ: the Window Size must be Less than $2^n$

Setup

With $n$ sequence-number bits the frame numbers are $0, 1, \dots, 2^n - 1$ and then wrap around modulo $2^n$. In Go-Back-N the receiver keeps track only of the next expected frame number and sends a cumulative ACK with that number; any frame that is not the expected one is discarded (no buffering).

Claim

$$W \le 2^n - 1$$

i.e. the sender window must be strictly less than $2^n$.

Proof by counter-example (contradiction)

Assume $W = 2^n$. Take $n = 3$, so frames are numbered $0 \dots 7$ and $W = 8$:

1. The sender fills its whole window and transmits frames 0, 1, 2, 3, 4, 5, 6, 7.
2. All eight frames arrive correctly; the receiver delivers all of them. Its next expected number is $8 \bmod 8 =$ 0, so it is now waiting for a new frame numbered 0.
3. All ACKs are lost. The sender's timer for frame 0 expires and it retransmits frame 0, believing it was never received.
4. The receiver is waiting for exactly number 0, so it accepts the retransmission as a brand-new frame and delivers a duplicate copy of the data to the network layer.

The protocol has failed: the receiver cannot distinguish a retransmission of the old frame 0 from a new frame 0, because the window has consumed every number in the sequence space, leaving no free number to signal that a wrap-around occurred.

 n = 3,  W = 8 (illegal)

 Sender                                  Receiver   (expects next = 0)
   | -- frame 0 -->|                      expects 0
   | -- frame 1 -->|                      expects 1
   |      ...      |                       ...
   | -- frame 7 -->|                      expects 8 mod 8 = 0
   |                                    
   |  ACKs lost, timeout on frame 0
   | -- frame 0 -->|  (retransmission)    ACCEPTED AS NEW frame 0  <-- DUPLICATE

 n = 3,  W = 7 (legal)

 Sender                                  Receiver   (expects next = 7)
   | -- frame 0..6 -->|                   expects 7
   |  ACKs lost, timeout on frame 0
   | -- frame 0 -->|  (retransmission)    0 != 7  -->  discarded, re-ACK 7  <-- CORRECT

Why $W \le 2^n - 1$ repairs the problem

If $W = 2^n - 1$, at least one sequence number is always unused at any instant. When the sender retransmits a frame numbered $s$, the receiver's expected number has not yet wrapped all the way around to $s$ (in the example above it expects 7, not 0), so the incoming frame $s$ is recognised as old, discarded, and the ACK is simply re-sent. Duplicates can never be delivered.

General statement

$$\text{Window size } W \le 2^n - 1 \quad \Longleftrightarrow \quad \text{number of distinct frame numbers} \ge W + 1$$

The extra, unused sequence number acts as the marker that separates the current window from the previous one. The same reasoning applied to Selective Repeat — where the sender and receiver windows slide independently — gives the tighter bound $W \le 2^{n-1}$, so that the two windows can never overlap ambiguously.