In Go-Back-N ARQ: Why the Window Size Must Be $< 2^n$

In Go-Back-N ARQ, the sender uses $n$-bit sequence numbers, so sequence numbers live in a finite space of size $2^n$. This implies sequence numbers are reused modulo $2^n$, i.e., $0,1,\dots,2^n-1$ repeat cyclically. To ensure that the receiver (and acknowledgments) can unambiguously distinguish “new” from “old” frames after wrap-around, the sender’s window size must satisfy the key constraint: $W < 2^n.$

This constraint prevents ambiguity in the receiver’s acceptance rule for a frame with sequence number $s$, especially when the sender’s sequence numbers wrap around after enough transmissions. The core intuition is:

• The receiver’s acceptance depends on whether the incoming sequence number lies within the receiver’s current expected window.
• If the sender’s window were $\ge 2^n$, then after wrap-around, a sequence number that should be treated as “old/retransmitted” could look “in-window” as if it were “new,” causing incorrect ACK behavior and breaking reliable delivery.

We’ll formalize this using the sliding window structure and modulo arithmetic.

Key terms:

• ARQ
• Go-Back-N
• Sequence Number
• Sliding Window

Precise model (modulo $2^n$) and the ambiguity problem

Let the sender transmit frames with sequence numbers modulo $M$, where: $M = 2^n.$

Let $W$ be the sender’s window size (number of outstanding/unacknowledged frames allowed). In a standard sliding-window ARQ, the receiver maintains an “expected” interval for acceptable new frames. For Go-Back-N, the receiver typically buffers nothing beyond the “expected” frame; it only advances in-order when it receives the correct expected sequence number, otherwise it discards out-of-order frames and sends an ACK for the last correctly received in-order frame (or equivalently an ACK indicating the next expected frame).

The receiver’s behavior relies on the assumption that there is no overlap between the set of sequence numbers representing “new frames for the current cycle” and those representing “old frames from the previous cycle.” Overlap would make the receiver unable to determine whether a wrapped sequence number corresponds to:

• a genuinely new frame that falls within the current expected range, or
• an old (possibly retransmitted) frame whose sequence number has wrapped into the current numeric range.

When sequence numbers wrap modulo $M$, the only way to avoid that overlap is to ensure the distance between “start points” of consecutive windows is large enough that numeric wrap doesn’t cause aliasing. With a window size $W$, the receiver’s expected set for new frames spans $W$ distinct sequence numbers. If $W \ge M$, then in modular arithmetic those spans can cover (or exceed) the entire residue class space, guaranteeing overlap/aliasing between consecutive cycles.

This leads directly to the necessary condition: $W < M = 2^n.$

Relationship to common textbook results

Many analyses of sliding-window ARQ protocols state that with $n$-bit sequence numbers, the maximum usable sender window size is $2^n - 1$, which is equivalent to $W < 2^n$. This condition is the same “no overlap/aliasing” requirement: the sender must keep enough slack so that wrap-around cannot cause a sequence number from a different cycle to be mistaken for an in-cycle frame.

Key terms:

• Modulo Arithmetic
• ACK (Acknowledgment)
• Wrap-around
• Ambiguity