Window Size Limit

Every protocol has hidden constraints that, if violated, lead to subtle but catastrophic failures. For Go-Back-N ARQ, one such critical constraint governs the relationship between the window size N and the sequence number space size 2^k (for k-bit sequence numbers).

At first glance, a larger window seems purely beneficial—more outstanding frames, better channel utilization, higher throughput. Why not set the window as large as possible? The answer lies in a delicate interaction between the finite sequence number space, cumulative acknowledgments, and the protocol's need to distinguish new frames from retransmissions.

This page rigorously derives the Go-Back-N window size constraint, demonstrates failure scenarios when the constraint is violated, and connects this seemingly abstract limit to the practical design of networking protocols.

Sequence numbers serve a critical purpose: they allow the receiver to distinguish different frames and detect duplicates, reordering, and gaps. However, with finite bit fields, sequence numbers must eventually wrap around and be reused.

The Question:

How do we ensure that when a sequence number is reused, the receiver can distinguish between:

• A new frame with that sequence number (first use in a new cycle)
• A retransmitted frame from a previous transmission attempt
• A duplicate frame that should be discarded

The Constraint:

For Go-Back-N with k-bit sequence numbers (space = 2^k), the window size must satisfy:

N ≤ 2^k - 1

Equivalently: Window size must be strictly less than the sequence number space.

This leaves at least one sequence number outside any possible window configuration, enabling disambiguation.

Intuition via Modular Arithmetic:

With k-bit sequence numbers, we work in modular arithmetic modulo 2^k. The sender's window occupies sequence numbers [send_base, send_base + N - 1] mod 2^k.

The receiver, after acknowledging frames up to some point, expects sequence numbers starting from expectedseqnum. For the protocol to work correctly:

1. The receiver must be able to identify if an arriving frame is within the current expected range (accept) or outside it (reject as duplicate or premature)

2. When the window wraps around, new sequence numbers used must not overlap with sequence numbers from potentially still-in-flight retransmissions

With N = 2^k, the window would span all sequence numbers, making these distinctions impossible.

Let's derive the window size constraint formally, considering the interaction between sender and receiver state.

Setup:

• Sequence number space: S = {0, 1, 2, ..., 2^k - 1}
• Window size: N
• Sender state: send_base, nextseqnum with send_base ≤ nextseqnum < send_base + N (mod 2^k)
• Receiver state: expectedseqnum

Sender Window Set:

At any time, the sender may have outstanding frames with sequence numbers:

W_sender = {send_base, send_base + 1, ..., send_base + N - 1} mod 2^k

This is a contiguous block of N sequence numbers.

Receiver Expectation:

The receiver, having acknowledged frames up to send_base - 1, expects:

W_receiver = {expectedseqnum} = {send_base}

But crucially, if the ACKs are lost or delayed, the receiver might have moved ahead to:

W_receiver' = {send_base + m} for some 0 ≤ m ≤ N

The Conflict Scenario:

Suppose the receiver has advanced (received all N frames successfully) while ACKs are in transit. The receiver now expects sequence number (send_base + N) mod 2^k.

Meanwhile, the sender hasn't received ACKs and times out, retransmitting from send_base.

Question: Can the receiver distinguish retransmitted frame send_base from new frame (send_base + N) mod 2^k?

Proof by Contradiction:

Assume N = 2^k (window equals sequence space).

1. Sender transmits frames 0, 1, 2, ..., 2^k - 1 (filling the entire window)
2. All frames arrive correctly at the receiver
3. Receiver delivers all frames and sends ACK(2^k - 1)
4. ACK is lost in transit
5. Receiver now expects sequence number (2^k - 1 + 1) mod 2^k = 0
6. Sender times out and retransmits frame 0

The Problem:

• Sender's frame 0 is a retransmission (already delivered)
• Receiver expects frame 0 as a NEW frame (start of next batch)
• Receiver cannot distinguish these cases!

If N = 2^k:

• Retransmitted frame 0 has sequence number 0
• Expected new frame also has sequence number 0
• Duplicate frame is accepted as new, violating correctness

With N = 2^k - 1:

1. Sender transmits frames 0, 1, ..., 2^k - 2 (window of N = 2^k - 1)
2. All frames arrive, receiver sends ACK(2^k - 2)
3. ACK is lost
4. Receiver expects sequence number (2^k - 2 + 1) mod 2^k = 2^k - 1
5. Sender times out and retransmits frame 0

Now:

• Retransmitted frame has sequence number 0
• Expected frame has sequence number 2^k - 1
• 0 ≠ 2^k - 1, so receiver correctly rejects the retransmission

The constraint N ≤ 2^k - 1 ensures there's always at least one sequence number separating the sender's window from the receiver's next expected frame, enabling correct disambiguation.

To fully appreciate the constraint, let's trace through a complete failure scenario with 2-bit sequence numbers (space = 4) and window size N = 4.

Setup:

• Sequence numbers: 0, 1, 2, 3
• Window size: N = 4 (violates N ≤ 3)
• Data to send: A, B, C, D, E, F, G, H

Correct Operation with N = 3:

Now let's trace the same scenario with N = 3 (satisfying N ≤ 2^k - 1 = 3).

The sequence number space can be visualized as a circular ring (since sequence numbers wrap around). The window size constraint can be understood geometrically:

The Ring Model:

Imagine sequence numbers 0, 1, 2, ..., 2^k - 1 arranged in a circle. The sender's window occupies an arc of N positions on this ring.

Constraint Visualization:

• With N = 2^k, the sender's window covers the entire ring

• When the window "slides" (after all ACKs received), it wraps around to... the same starting position

• No gap exists between where the window was and where it is now

• With N = 2^k - 1, the sender's window covers all but one position

• There's always a gap of at least 1 sequence number between the old window and the new window

• This gap "protects" against confusion between old and new frames

Color-Coded Window States:

Let's visualize with 3-bit sequence numbers (0-7) and window N = 7:

Initial Window (send_base = 0):
  Seq#:   [0] [1] [2] [3] [4] [5] [6]  7
  Status:  W   W   W   W   W   W   W   -
  
After all ACKed, Window slides (send_base = 7):
  Seq#:    0   1   2   3   4   5   6  [7]
  Status:  -   -   -   -   -   -   -   W
  
Note: Previous position 0-6 is now outside window
      New position 7 (and wrapping to 0-5) is inside window

Key Insight: When N = 7 and space = 8, after the window slides by N = 7 positions, only 1 position from the old window could potentially overlap with the new window when frames are retransmitted. But the receiver has moved expectedseqnum such that it no longer accepts the old sequence numbers.

Contrast with N = 8:

Initial Window (send_base = 0):
  Seq#:   [0] [1] [2] [3] [4] [5] [6] [7]
  Status:  W   W   W   W   W   W   W   W
  
After all ACKed, Window slides (send_base = 8 mod 8 = 0):
  Seq#:   [0] [1] [2] [3] [4] [5] [6] [7]
  Status:  W   W   W   W   W   W   W   W
  
Window is IDENTICAL! No way to distinguish old from new frames.

The window size constraint has direct implications for protocol design and performance optimization.

Sequence Number Sizing:

When designing a protocol, engineers choose k (sequence number bits) based on desired window size:

• Required window N ← determined by bandwidth-delay product and efficiency goals
• Minimum k = ⌈log₂(N + 1)⌉

Example:

• Desired window: N = 100 frames
• N + 1 = 101
• log₂(101) ≈ 6.66
• Minimum k = 7 bits (sequence space = 128)
• Maximum N = 127

Real Protocol Examples:

Trade-off: Larger k vs. Overhead:

Using more bits for sequence numbers provides:

• Larger maximum window → better efficiency on high bandwidth-delay products
• More protection against delayed duplicates → safer protocol operation

But also incurs:

• Higher header overhead → more bits per frame for sequence numbers
• More complex arithmetic → especially for embedded/simple devices

The HDLC Case Study:

HDLC (High-Level Data Link Control) offers two modes:

1. Normal mode: 3-bit sequence numbers, max window = 7

   • Suitable for low-latency, low-speed links
   • Simple implementation
   • Limited throughput on high-delay links

2. Extended mode: 7-bit sequence numbers, max window = 127

   • Suitable for satellite links, high-speed connections
   • More complex but much higher throughput potential
   • Standard for most modern HDLC deployments

It's illuminating to compare Go-Back-N's window constraint with Selective Repeat ARQ, as they differ significantly.

Selective Repeat Constraint:

For Selective Repeat with k-bit sequence numbers:

N ≤ 2^(k-1) or equivalently N ≤ (sequence space) / 2

This is more restrictive than Go-Back-N's N ≤ 2^k - 1.

Why the Difference?

In Selective Repeat:

• The receiver accepts and buffers out-of-order frames
• The sender and receiver windows can be "out of sync" by up to N positions
• In the worst case, the sender's window and receiver's window could be completely disjoint

To prevent ambiguity:

• Sender window: [send_base, send_base + N - 1]
• Receiver window: [rcv_base, rcv_base + N - 1]
• These could differ by up to N

For no overlap when windows are maximally apart: send_base + N - 1 < rcv_base + sequence_space (unwrapped)

This requires N + N ≤ sequence_space, i.e., N ≤ 2^k / 2.

Why GBN Allows Larger Windows:

The key insight is that in Go-Back-N, the receiver's "window" is effectively size 1—it only accepts the single expected sequence number. When the sender retransmits, the receiver is guaranteed to reject any retransmission of a previously accepted frame because:

• Receiver's expectedseqnum has advanced past the retransmitted frame's sequence number
• The gap of at least 1 sequence number (ensured by N ≤ 2^k - 1) provides disambiguation

In Selective Repeat, both sender and receiver have actual windows of size N, creating more potential for sequence number confusion—hence the stricter constraint.

The window size constraint is a fundamental correctness requirement for Go-Back-N ARQ. Let's consolidate the essential insights:

What's Next:

With window size constraints understood, we're ready to examine retransmission behavior in depth—the "go back" mechanism that defines the protocol. The next page explores how timeouts trigger retransmission, the impact of retransmitting already-received frames, and strategies to minimize redundant retransmission while maintaining protocol correctness.