Sliding Window Protocol - Learning Module

Loading content...

0/228

Sequence Number Space

The Mathematics of Sequence Numbers

Sequence numbers are the identifiers that distinguish one frame from another. They enable the receiver to detect duplicates, identify missing frames, and maintain correct ordering. They allow the sender to correlate acknowledgments with specific transmissions.

But sequence numbers come from a finite set. With n bits, we have 2ⁿ possible values. Eventually, sequence numbers wrap around, returning to previously-used values. This creates a fundamental challenge:

How do we ensure that old frames are never confused with new frames, even when sequence numbers repeat?

This page addresses this question rigorously, deriving the mathematical constraints that govern sequence number space design.

What You Will Learn

By the end of this page, you will understand modular arithmetic in sequence number spaces, the circular nature of sequence comparisons, formal derivation of sequence number requirements for Go-Back-N and Selective Repeat, practical implications for protocol design, and common pitfalls that lead to protocol failures.

Modular Arithmetic Fundamentals

Sequence numbers operate in a modular arithmetic space. With n bits, sequence numbers range from 0 to 2ⁿ - 1, and incrementing beyond the maximum wraps to 0.

Formal Definition:

For sequence space size S = 2ⁿ:

seq' = (seq + 1) mod S

The Circular Model:

Think of sequence numbers as positions on a clock with S positions. Moving forward always wraps around; there's no 'end.'

        0
    7       1
  6           2
    5       3
        4
        
  (3-bit sequence space, S = 8)

Comparison Challenges:

In linear arithmetic, 5 > 3 is always true. But in circular space, 'greater than' depends on perspective:

If we're at position 2, is 6 'ahead' or 'behind'?
Distance from 2 to 6 going forward: 4
Distance from 2 to 6 going backward: 4

Both distances equal S/2, so 6 is ambiguous. This ambiguity is at the heart of sequence number constraints.

Modular Sequence Number Arithmetic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
Modular Sequence Number Arithmetic
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Given: n-bit sequence numbers, S = 2ⁿ
 
Basic Operations:
──────────────────────────────────────────────────────────────────────────────
    MASK = S - 1 = 2ⁿ - 1    // Bitmask for modular reduction
 
    inc(seq)     = (seq + 1) & MASK           // Increment
    add(seq, k)  = (seq + k) & MASK           // Add offset
    sub(a, b)    = (a - b + S) & MASK         // Difference (always positive)
    distance(a, b) = sub(b, a)                // How far from a to b (forward)
 
Comparison Functions (Signed Interpretation):
──────────────────────────────────────────────────────────────────────────────
The key insight: treat forward distance < S/2 as "ahead"
                  treat forward distance > S/2 as "behind"
 
    // Is 'a' less than 'b' in circular order?
    seq_lt(a, b):
        diff = (b - a) & MASK
        return 0 < diff < (S / 2)
 
    // Is 'a' less than or equal to 'b'?
    seq_le(a, b):
        return (a == b) or seq_lt(a, b)
 
    // Is sequence 'seq' within window [base, base + size)?
    in_window(seq, base, size):
        diff = (seq - base) & MASK
        return diff < size
 
Example (3-bit, S = 8, MASK = 7):
──────────────────────────────────────────────────────────────────────────────
    Sequence space: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, ...
    
    sub(2, 5) = (2 - 5 + 8) & 7 = 5          // 5 is 3 steps behind 2
    sub(5, 2) = (5 - 2 + 8) & 7 = 3          // 5 is 3 steps ahead of 2
    
    seq_lt(2, 5): diff = 3, 0 < 3 < 4 → TRUE  (5 is ahead of 2)
    seq_lt(5, 2): diff = 5, 0 < 5 < 4 → FALSE (2 is not ahead of 5)
    
    in_window(3, 2, 4): diff = 1, 1 < 4 → TRUE
    in_window(7, 2, 4): diff = 5, 5 < 4 → FALSE
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Critical Assumption: Window size never exceeds S/2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
If window size ≥ S/2, the comparison functions become ambiguous.
This is why Selective Repeat requires Wₛ + Wᵣ ≤ S.

The Half-Space Rule

In circular sequence space, we can only reliably distinguish 'ahead' from 'behind' if the difference is less than S/2. This is analogous to signed integer interpretation: in an 8-bit signed byte, values 0-127 are positive, 128-255 are negative. The same bit pattern means different things depending on interpretation.

Go-Back-N Sequence Number Requirements

For Go-Back-N, the sequence number requirement is relatively lenient because the receiver only buffers the expected frame (Wᵣ = 1).

The Constraint:

For Go-Back-N: Wₛ < S

Equivalently: Wₛ ≤ S - 1, where S = 2ⁿ

With n bits: Wₛ ≤ 2ⁿ - 1

Why This Works:

Let's prove that Wₛ ≤ S - 1 is sufficient for correct operation.

Go-Back-N Sequence Number Proof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Go-Back-N: Proof of Sequence Number Requirement
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Claim: For Go-Back-N with receive window Wᵣ = 1:
       Wₛ ≤ S - 1 is necessary and sufficient for correctness.
 
Proof of Sufficiency:
──────────────────────────────────────────────────────────────────────────────
 
At any time, the receiver expects exactly one sequence number: Rₙ.
 
The sender's window is [Sᵦ, Sᵦ + Wₛ), containing at most Wₛ values.
 
Question: Can an older, retransmitted frame be confused with a new frame?
 
Consider the worst case:
  - All Wₛ frames in sender window transmitted and received.
  - All ACKs lost.
  - Receiver has advanced: Rₙ = Sᵦ + Wₛ (received all Wₛ frames)
  
Now, sender times out and retransmits frame with seq = Sᵦ.
 
For correctness, the receiver must recognize Sᵦ as OLD (already delivered).
 
Receiver's expected frame: Rₙ = Sᵦ + Wₛ (mod S)
 
  - The retransmitted frame has seq = Sᵦ
  - Currently expected: Rₙ = Sᵦ + Wₛ
  - Difference: (Sᵦ - Rₙ) mod S = (Sᵦ - Sᵦ - Wₛ) mod S = (S - Wₛ) mod S
 
Since Wₛ ≤ S - 1:
  - S - Wₛ ≥ 1
  - The difference (S - Wₛ) ≥ 1, so Sᵦ ≠ Rₙ
  
The receiver will see seq = Sᵦ ≠ Rₙ, recognize it as out-of-order, and discard.
 
Proof of Necessity:
──────────────────────────────────────────────────────────────────────────────
 
If Wₛ = S (full sequence space):
 
After transmitting S frames (0 through S-1), all received:
  - Rₙ = S mod S = 0
 
If all ACKs lost, sender retransmits frame 0.
  - Receiver expects seq = 0 (since Rₙ = 0)
  - Retransmission has seq = 0
  
The old retransmission is ACCEPTED as expected frame! ← FAILURE
 
Therefore, Wₛ must be < S.
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Conclusion: Go-Back-N requires Wₛ ≤ S - 1
            With n-bit sequence numbers: Wₛ ≤ 2ⁿ - 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Go-Back-N: Maximum Window Size by Sequence Bits
Sequence Bits (n)	Space S	Maximum Wₛ	Example Protocol
1	2	1	Stop-and-Wait (trivial)
3	8	7	Simple data link
7	128	127	HDLC (standard)
8	256	255	HDLC (extended)
16	65,536	65,535	Large windows

The Stop-and-Wait Special Case

Stop-and-Wait is Go-Back-N with Wₛ = 1. With 1-bit sequence numbers (S = 2), we can have Wₛ ≤ 1. This confirms our earlier observation that Stop-and-Wait uses only sequence numbers 0 and 1, alternating between them.

Selective Repeat Sequence Number Requirements

Selective Repeat has stricter sequence number requirements because both sender and receiver maintain windows that might overlap after wrap-around.

The Constraint:

For Selective Repeat: Wₛ + Wᵣ ≤ S

With equal windows (Wₛ = Wᵣ = W): W ≤ S/2

With n bits: W ≤ 2ⁿ⁻¹

Intuition:

The sender window and receiver window must never overlap in the sequence space, even after wrap-around. If they overlap, retransmissions could be confused with new frames.

Selective Repeat Sequence Number Proof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
Selective Repeat: Proof of Sequence Number Requirement
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Claim: For Selective Repeat with Wₛ = Wᵣ = W:
       W ≤ S/2 is necessary and sufficient.
 
More generally: Wₛ + Wᵣ ≤ S
 
Proof of Necessity (Why Wₛ + Wᵣ > S Fails):
──────────────────────────────────────────────────────────────────────────────
 
Consider S = 6 (sequence numbers 0-5), Wₛ = Wᵣ = 4 (violation: 4+4=8 > 6)
 
Initial state:
  - Sender window: [0, 1, 2, 3]
  - Receiver window: [0, 1, 2, 3]
 
Best-case scenario (all frames received, all ACKs received):
  - After sending 0,1,2,3 and receiving ACKs:
  - Sender window slides to: [4, 5, 0, 1]  ← wraps!
  - Receiver window slides to: [4, 5, 0, 1]
  - Protocol works correctly.
 
Worst-case scenario (all frames received, ALL ACKs lost):
  - Sender: never gets ACKs, window stuck at [0, 1, 2, 3]
  - Receiver: received all, window slides to [4, 5, 0, 1]
  
  Notice: Sender window [0,1,2,3] and Receiver window [4,5,0,1]
          OVERLAP at sequence numbers 0 and 1!
 
  Sender times out, retransmits frame with seq = 0.
  
  Receiver check: Is seq = 0 in window [4, 5, 0, 1]?
  
                  ┌─ Window start: 4
                  │   ┌─ 0 is "2 positions forward" from 4 (mod 6)
                  │   │
            YES! 0 is in the window.
  
  Receiver thinks: "Frame 0 is expected (second wrap-around)."
  Receiver buffers/delivers as NEW data. ← CATASTROPHIC!
  
  The OLD retransmission is confused with a NEW frame.
 
Proof of Sufficiency (Why Wₛ + Wᵣ ≤ S Works):
──────────────────────────────────────────────────────────────────────────────
 
Consider any valid state:
  - Sender window: [Sᵦ, Sᵦ + Wₛ)
  - Receiver window: [Rₙ, Rₙ + Wᵣ)
 
All frames the sender might retransmit: {Sᵦ, Sᵦ+1, ..., Sᵦ+Wₛ-1}
 
All frames the receiver considers "new": {Rₙ, Rₙ+1, ..., Rₙ+Wᵣ-1}
 
For correctness, these sets must not overlap (after all corrections for modular arithmetic)
 
Worst case: Receiver has received all Wₛ frames, but sender knows nothing:
  - Rₙ = Sᵦ + Wₛ  (receiver advanced past entire sender window)
 
Sender window: [Sᵦ, Sᵦ + Wₛ)
Receiver window: [Sᵦ + Wₛ, Sᵦ + Wₛ + Wᵣ)
 
Non-overlap condition:
  Sender window ends at: Sᵦ + Wₛ - 1
  Receiver window starts at: Sᵦ + Wₛ
  These are adjacent: ✓
  
  But after wrap-around, receiver window end is: Sᵦ + Wₛ + Wᵣ - 1
  
  For no overlap with sender window start (Sᵦ):
    Sᵦ + Wₛ + Wᵣ - 1 < Sᵦ + S  (receiver window end before sender wraps back)
    Wₛ + Wᵣ ≤ S  ✓
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Conclusion: Selective Repeat requires Wₛ + Wᵣ ≤ S
            With equal windows: W ≤ S/2
            With n-bit sequence numbers: W ≤ 2ⁿ⁻¹
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Converting Mermaid diagram...

Half the Window Size

Selective Repeat uses only half the sequence space for its window compared to Go-Back-N. With 3 bits (S=8), GBN can have Wₛ=7, but SR can only have W=4. This is the price of receiver buffering—you need more sequence numbers to avoid ambiguity.

Visual Comparison of Window Requirements

Let's visualize the sequence space constraints for both protocols using a circular representation.

Sequence Space Utilization: GBN vs SR
Protocol	Constraint	3-bit (S=8)	7-bit (S=128)	Utilization
Go-Back-N	Wₛ ≤ S - 1	Wₛ ≤ 7	Wₛ ≤ 127	87.5% - 99.2%
Selective Repeat	W ≤ S/2	W ≤ 4	W ≤ 64	50%
Stop-and-Wait	W = 1	W = 1	W = 1	12.5% - 0.8%

Circular Sequence Space Visualization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Sequence Space Visualization (3-bit, S = 8)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Go-Back-N (Wₛ = 7, Wᵣ = 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
After sender transmits 0-6, receiver ACKs all:
 
        0                               0
    7       1                       7       1
              ←Sender─┐       ┌─Receiver→
  6           2       │       │ 6           2
              ←───────┘       └──→
    5       3                       5       3
        4                               4
        
Sender window: [0-6] (7 slots)     Receiver: expects 7 only (1 slot)
One slot (7) reserved             No overlap possible!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Selective Repeat (Wₛ = Wᵣ = 4):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
After sender transmits 0-3, all ACKs lost:
 
        0 ← overlap danger!          0 ← overlap danger!
    7       1                       7       1
              ←Sender─┐       ┌─Receiver→
  6           2       │       │ 6           2
              ←───────┘       └──→
    5       3                       5       3
        4 ← overlap danger!          4 ← window start
        
Sender window: [0,1,2,3]          Receiver window: [4,5,6,7]
ADJACENT but NOT overlapping!     If W were 5, would overlap at 0!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
FAILURE CASE: Selective Repeat with W = 5 (violation: 5+5=10 > 8):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Sender window: [0,1,2,3,4]        Receiver window: [5,6,7,0,1]
                │                               │
                └──── OVERLAP at 0 and 1! ──────┘
 
Retransmission of seq=0 is accepted as new frame ← DATA CORRUPTION!

Geometric Interpretation:

Imagine the sequence space as a circle. The sender and receiver each have a 'arc' covering their window:

Go-Back-N: Sender has large arc (S-1), receiver has tiny arc (just 1 point)
Selective Repeat: Both have arcs, and combined they must not exceed a full circle

The constraint Wₛ + Wᵣ ≤ S ensures the two arcs, even when maximally separated, fit within the circle without wrapping into each other.

Memory for Efficiency Trade-off

Selective Repeat's tighter constraint means you need more sequence bits for the same window size. To match GBN's Wₛ=127, SR needs 8 bits (256 values, W≤128) instead of 7 bits. The extra bit is the 'price' of receiver buffering.

Practical Implications for Protocol Design

The theoretical constraints translate directly into practical protocol decisions:

1. HDLC (High-Level Data Link Control):

Uses 3-bit sequence numbers (S = 8) in normal mode
Window size: 7 (Go-Back-N style)
Extended mode: 7-bit sequence numbers (S = 128), window 127

2. TCP:

Uses 32-bit sequence numbers (S = 2³²)
Sequence numbers count bytes, not segments
With SACK (Selective Repeat behavior), effective window can be up to 2³¹ bytes
But practical windows limited by receiver buffer, not sequence space

Protocol Sequence Number Choices
Protocol	Seq Bits	Space S	Mode	Max Window
HDLC Normal	3	8	GBN	7 frames
HDLC Extended	7	128	GBN	127 frames
HDLC Super	15	32,768	SR/GBN	16,383 (SR)
TCP	32	~4×10⁹	SR (SACK)	~2×10⁹ bytes
Bluetooth L2CAP	6	64	SR	32 frames
IEEE 802.11 (WiFi)	12	4096	GBN	4095 frames

Design Decisions:

1. How many bits for sequence numbers?

Start with required window size (from bandwidth-delay product), then:

For GBN: n = ⌈log₂(W + 1)⌉
For SR: n = ⌈log₂(2W)⌉ = ⌈log₂(W)⌉ + 1

2. Fixed vs. Variable Window Size:

Fixed: Simpler, predictable memory requirements
Variable: Adapts to receiver buffer availability (TCP's advertised window)

3. Handling High Bandwidth-Delay Products:

Modern networks may require huge windows:

10 Gbps × 100 ms = 1 Gbit = 125 MB

Solutions:

TCP window scaling (RFC 1323): Multiply advertised window by 2^scale
Large sequence number fields (TCP uses 32 bits, counting bytes)

TCP Window Scaling

TCP's original 16-bit window field limits to 64KB. For modern high-BDP paths, RFC 1323 introduced a scale factor (0-14), making effective window up to 64KB × 2¹⁴ = 1 GB. This was essential for long-distance, high-speed links.

Common Pitfalls and Debugging

Sequence number issues cause some of the most subtle protocol bugs. Here are common pitfalls:

1. Integer Overflow Without Masking:

// WRONG: Can overflow for large sequence numbers
SeqNum next = current + 1;

// CORRECT: Always mask
SeqNum next = (current + 1) & MASK;

2. Naive Comparison:

// WRONG: Fails near wrap-around
if (seq > base) { /* in window */ }

// CORRECT: Use modular comparison
if (((seq - base) & MASK) < window_size) { /* in window */ }

3. Window Size Exceeding Constraint:

// WRONG: Configured window too large
#define SEQ_BITS 3
#define WINDOW_SIZE 6  // For SR, max should be 4!

Debugging Symptoms of Sequence Number Bugs

•Duplicate data delivery: Retransmissions confused with new frames → SR window too large
•Missing data delivery: Correct frames rejected as out-of-order → comparison function bug
•Protocol freeze: Sender stopped, no ACKs processed → ACK comparison with stale base
•Infinite retransmission loops: Same frames retransmitted repeatedly → window never advancing
•Sporadic data corruption: Rare, hard to reproduce → happens only at wrap-around boundaries
•Works with small transfers, fails with large: Sequence space exhausted → window constraint violation

Debugging Sequence Number Issues
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Debugging Checklist for Sequence Number Issues
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
1. Verify window size vs. sequence space:
   
   GBN: assert(window_size <= MAX_SEQ);         // W ≤ S - 1
   SR:  assert(send_win + recv_win <= MAX_SEQ + 1);  // Wₛ + Wᵣ ≤ S
 
2. Check all sequence number operations are modular:
   
   grep for: seq + 1, seq - 1, seq++, seq--
   All must be: (seq + 1) & MASK, etc.
 
3. Check all sequence comparisons use window logic:
   
   Never: if (seq > base)
   Always: if (in_window(seq, base, size))
 
4. Test at wrap-around boundaries:
 
   Test with initial base near MAX_SEQ (e.g., MAX_SEQ - 2)
   Force window to wrap: base=7, next=2 for 3-bit sequences
 
5. Log sequence state at every event:
 
   ON_SEND:  "TX seq=%d, base=%d, next=%d"
   ON_ACK:   "RX ACK=%d, old_base=%d, new_base=%d"
   ON_RX:    "RX seq=%d, expected=%d, in_window=%s"
   ON_TIMER: "TIMEOUT base=%d, next=%d, outstanding=%d"
 
6. Simulate adversarial conditions:
 
   - All ACKs lost (causes maximal window advancement at receiver)
   - Extreme reordering (frame 0 arrives last)
   - Long bursts without reply (tests wrap-around under load)

Unit Testing Sequence Logic

Sequence number logic is pure math—perfect for unit testing in isolation. Test in_window(), seq_lt(), inc() with boundary cases: 0, 1, MAX_SEQ-1, MAX_SEQ, wrap-around scenarios. If these functions are correct, most protocol bugs are eliminated.

Summary: Sequence Number Space

We've explored the mathematics underlying sequence number design. Let's consolidate the key principles:

Key Takeaways

•Sequence numbers operate in modular arithmetic: With n bits, values wrap from 2ⁿ-1 to 0.
•Comparisons require distance-based logic: 'Greater than' has no meaning in circular space without a reference point.
•Go-Back-N requires Wₛ ≤ S - 1: The small receiver window (Wᵣ=1) allows nearly the full sequence space for sender.
•Selective Repeat requires Wₛ + Wᵣ ≤ S: Both windows together must fit within the sequence space.
•For SR with equal windows: W ≤ S/2, meaning an extra sequence bit is needed compared to GBN.
•Protocol design must match constraints: Window size, sequence bits, and protocol variant are interdependent.
•Wrap-around bugs are subtle: They manifest rarely, only when sequence numbers cycle, making them hard to catch without systematic testing.

What's Next:

With windows and sequence numbers understood, we'll examine pipelining in depth—how multiple frames in flight improves throughput, the timing analysis of pipelined transmission, and how different ARQ protocols (Go-Back-N, Selective Repeat) implement pipelining with their respective trade-offs.

Page Complete

You now understand sequence number space requirements—the mathematical constraints that ensure correct protocol operation even with finite sequence numbers. This knowledge is essential for implementing or debugging any sliding window protocol. Next, we explore pipelining mechanics in detail.

Sequence Number Space

The Mathematics of Sequence Numbers

How do we ensure that old frames are never confused with new frames, even when sequence numbers repeat?

This page addresses this question rigorously, deriving the mathematical constraints that govern sequence number space design.

What You Will Learn

Modular Arithmetic Fundamentals

Sequence numbers operate in a modular arithmetic space. With n bits, sequence numbers range from 0 to 2ⁿ - 1, and incrementing beyond the maximum wraps to 0.

Formal Definition:

For sequence space size S = 2ⁿ:

seq' = (seq + 1) mod S

The Circular Model:

Think of sequence numbers as positions on a clock with S positions. Moving forward always wraps around; there's no 'end.'

        0
    7       1
  6           2
    5       3
        4
        
  (3-bit sequence space, S = 8)

Comparison Challenges:

In linear arithmetic, 5 > 3 is always true. But in circular space, 'greater than' depends on perspective:

If we're at position 2, is 6 'ahead' or 'behind'?
Distance from 2 to 6 going forward: 4
Distance from 2 to 6 going backward: 4

Both distances equal S/2, so 6 is ambiguous. This ambiguity is at the heart of sequence number constraints.

Modular Sequence Number Arithmetic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
Modular Sequence Number Arithmetic
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Given: n-bit sequence numbers, S = 2ⁿ
 
Basic Operations:
──────────────────────────────────────────────────────────────────────────────
    MASK = S - 1 = 2ⁿ - 1    // Bitmask for modular reduction
 
    inc(seq)     = (seq + 1) & MASK           // Increment
    add(seq, k)  = (seq + k) & MASK           // Add offset
    sub(a, b)    = (a - b + S) & MASK         // Difference (always positive)
    distance(a, b) = sub(b, a)                // How far from a to b (forward)
 
Comparison Functions (Signed Interpretation):
──────────────────────────────────────────────────────────────────────────────
The key insight: treat forward distance < S/2 as "ahead"
                  treat forward distance > S/2 as "behind"
 
    // Is 'a' less than 'b' in circular order?
    seq_lt(a, b):
        diff = (b - a) & MASK
        return 0 < diff < (S / 2)
 
    // Is 'a' less than or equal to 'b'?
    seq_le(a, b):
        return (a == b) or seq_lt(a, b)
 
    // Is sequence 'seq' within window [base, base + size)?
    in_window(seq, base, size):
        diff = (seq - base) & MASK
        return diff < size
 
Example (3-bit, S = 8, MASK = 7):
──────────────────────────────────────────────────────────────────────────────
    Sequence space: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, ...
    
    sub(2, 5) = (2 - 5 + 8) & 7 = 5          // 5 is 3 steps behind 2
    sub(5, 2) = (5 - 2 + 8) & 7 = 3          // 5 is 3 steps ahead of 2
    
    seq_lt(2, 5): diff = 3, 0 < 3 < 4 → TRUE  (5 is ahead of 2)
    seq_lt(5, 2): diff = 5, 0 < 5 < 4 → FALSE (2 is not ahead of 5)
    
    in_window(3, 2, 4): diff = 1, 1 < 4 → TRUE
    in_window(7, 2, 4): diff = 5, 5 < 4 → FALSE
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Critical Assumption: Window size never exceeds S/2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
If window size ≥ S/2, the comparison functions become ambiguous.
This is why Selective Repeat requires Wₛ + Wᵣ ≤ S.

The Half-Space Rule

Go-Back-N Sequence Number Requirements

For Go-Back-N, the sequence number requirement is relatively lenient because the receiver only buffers the expected frame (Wᵣ = 1).

The Constraint:

For Go-Back-N: Wₛ < S

Equivalently: Wₛ ≤ S - 1, where S = 2ⁿ

With n bits: Wₛ ≤ 2ⁿ - 1

Why This Works:

Let's prove that Wₛ ≤ S - 1 is sufficient for correct operation.

Go-Back-N Sequence Number Proof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Go-Back-N: Proof of Sequence Number Requirement
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Claim: For Go-Back-N with receive window Wᵣ = 1:
       Wₛ ≤ S - 1 is necessary and sufficient for correctness.
 
Proof of Sufficiency:
──────────────────────────────────────────────────────────────────────────────
 
At any time, the receiver expects exactly one sequence number: Rₙ.
 
The sender's window is [Sᵦ, Sᵦ + Wₛ), containing at most Wₛ values.
 
Question: Can an older, retransmitted frame be confused with a new frame?
 
Consider the worst case:
  - All Wₛ frames in sender window transmitted and received.
  - All ACKs lost.
  - Receiver has advanced: Rₙ = Sᵦ + Wₛ (received all Wₛ frames)
  
Now, sender times out and retransmits frame with seq = Sᵦ.
 
For correctness, the receiver must recognize Sᵦ as OLD (already delivered).
 
Receiver's expected frame: Rₙ = Sᵦ + Wₛ (mod S)
 
  - The retransmitted frame has seq = Sᵦ
  - Currently expected: Rₙ = Sᵦ + Wₛ
  - Difference: (Sᵦ - Rₙ) mod S = (Sᵦ - Sᵦ - Wₛ) mod S = (S - Wₛ) mod S
 
Since Wₛ ≤ S - 1:
  - S - Wₛ ≥ 1
  - The difference (S - Wₛ) ≥ 1, so Sᵦ ≠ Rₙ
  
The receiver will see seq = Sᵦ ≠ Rₙ, recognize it as out-of-order, and discard.
 
Proof of Necessity:
──────────────────────────────────────────────────────────────────────────────
 
If Wₛ = S (full sequence space):
 
After transmitting S frames (0 through S-1), all received:
  - Rₙ = S mod S = 0
 
If all ACKs lost, sender retransmits frame 0.
  - Receiver expects seq = 0 (since Rₙ = 0)
  - Retransmission has seq = 0
  
The old retransmission is ACCEPTED as expected frame! ← FAILURE
 
Therefore, Wₛ must be < S.
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Conclusion: Go-Back-N requires Wₛ ≤ S - 1
            With n-bit sequence numbers: Wₛ ≤ 2ⁿ - 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Go-Back-N: Maximum Window Size by Sequence Bits
Sequence Bits (n)	Space S	Maximum Wₛ	Example Protocol
1	2	1	Stop-and-Wait (trivial)
3	8	7	Simple data link
7	128	127	HDLC (standard)
8	256	255	HDLC (extended)
16	65,536	65,535	Large windows

The Stop-and-Wait Special Case

Selective Repeat Sequence Number Requirements

Selective Repeat has stricter sequence number requirements because both sender and receiver maintain windows that might overlap after wrap-around.

The Constraint:

For Selective Repeat: Wₛ + Wᵣ ≤ S

With equal windows (Wₛ = Wᵣ = W): W ≤ S/2

With n bits: W ≤ 2ⁿ⁻¹

Intuition:

The sender window and receiver window must never overlap in the sequence space, even after wrap-around. If they overlap, retransmissions could be confused with new frames.

Selective Repeat Sequence Number Proof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
Selective Repeat: Proof of Sequence Number Requirement
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Claim: For Selective Repeat with Wₛ = Wᵣ = W:
       W ≤ S/2 is necessary and sufficient.
 
More generally: Wₛ + Wᵣ ≤ S
 
Proof of Necessity (Why Wₛ + Wᵣ > S Fails):
──────────────────────────────────────────────────────────────────────────────
 
Consider S = 6 (sequence numbers 0-5), Wₛ = Wᵣ = 4 (violation: 4+4=8 > 6)
 
Initial state:
  - Sender window: [0, 1, 2, 3]
  - Receiver window: [0, 1, 2, 3]
 
Best-case scenario (all frames received, all ACKs received):
  - After sending 0,1,2,3 and receiving ACKs:
  - Sender window slides to: [4, 5, 0, 1]  ← wraps!
  - Receiver window slides to: [4, 5, 0, 1]
  - Protocol works correctly.
 
Worst-case scenario (all frames received, ALL ACKs lost):
  - Sender: never gets ACKs, window stuck at [0, 1, 2, 3]
  - Receiver: received all, window slides to [4, 5, 0, 1]
  
  Notice: Sender window [0,1,2,3] and Receiver window [4,5,0,1]
          OVERLAP at sequence numbers 0 and 1!
 
  Sender times out, retransmits frame with seq = 0.
  
  Receiver check: Is seq = 0 in window [4, 5, 0, 1]?
  
                  ┌─ Window start: 4
                  │   ┌─ 0 is "2 positions forward" from 4 (mod 6)
                  │   │
            YES! 0 is in the window.
  
  Receiver thinks: "Frame 0 is expected (second wrap-around)."
  Receiver buffers/delivers as NEW data. ← CATASTROPHIC!
  
  The OLD retransmission is confused with a NEW frame.
 
Proof of Sufficiency (Why Wₛ + Wᵣ ≤ S Works):
──────────────────────────────────────────────────────────────────────────────
 
Consider any valid state:
  - Sender window: [Sᵦ, Sᵦ + Wₛ)
  - Receiver window: [Rₙ, Rₙ + Wᵣ)
 
All frames the sender might retransmit: {Sᵦ, Sᵦ+1, ..., Sᵦ+Wₛ-1}
 
All frames the receiver considers "new": {Rₙ, Rₙ+1, ..., Rₙ+Wᵣ-1}
 
For correctness, these sets must not overlap (after all corrections for modular arithmetic)
 
Worst case: Receiver has received all Wₛ frames, but sender knows nothing:
  - Rₙ = Sᵦ + Wₛ  (receiver advanced past entire sender window)
 
Sender window: [Sᵦ, Sᵦ + Wₛ)
Receiver window: [Sᵦ + Wₛ, Sᵦ + Wₛ + Wᵣ)
 
Non-overlap condition:
  Sender window ends at: Sᵦ + Wₛ - 1
  Receiver window starts at: Sᵦ + Wₛ
  These are adjacent: ✓
  
  But after wrap-around, receiver window end is: Sᵦ + Wₛ + Wᵣ - 1
  
  For no overlap with sender window start (Sᵦ):
    Sᵦ + Wₛ + Wᵣ - 1 < Sᵦ + S  (receiver window end before sender wraps back)
    Wₛ + Wᵣ ≤ S  ✓
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Conclusion: Selective Repeat requires Wₛ + Wᵣ ≤ S
            With equal windows: W ≤ S/2
            With n-bit sequence numbers: W ≤ 2ⁿ⁻¹
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Converting Mermaid diagram...

Half the Window Size

Visual Comparison of Window Requirements

Let's visualize the sequence space constraints for both protocols using a circular representation.

Sequence Space Utilization: GBN vs SR
Protocol	Constraint	3-bit (S=8)	7-bit (S=128)	Utilization
Go-Back-N	Wₛ ≤ S - 1	Wₛ ≤ 7	Wₛ ≤ 127	87.5% - 99.2%
Selective Repeat	W ≤ S/2	W ≤ 4	W ≤ 64	50%
Stop-and-Wait	W = 1	W = 1	W = 1	12.5% - 0.8%

Circular Sequence Space Visualization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Sequence Space Visualization (3-bit, S = 8)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Go-Back-N (Wₛ = 7, Wᵣ = 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
After sender transmits 0-6, receiver ACKs all:
 
        0                               0
    7       1                       7       1
              ←Sender─┐       ┌─Receiver→
  6           2       │       │ 6           2
              ←───────┘       └──→
    5       3                       5       3
        4                               4
        
Sender window: [0-6] (7 slots)     Receiver: expects 7 only (1 slot)
One slot (7) reserved             No overlap possible!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Selective Repeat (Wₛ = Wᵣ = 4):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
After sender transmits 0-3, all ACKs lost:
 
        0 ← overlap danger!          0 ← overlap danger!
    7       1                       7       1
              ←Sender─┐       ┌─Receiver→
  6           2       │       │ 6           2
              ←───────┘       └──→
    5       3                       5       3
        4 ← overlap danger!          4 ← window start
        
Sender window: [0,1,2,3]          Receiver window: [4,5,6,7]
ADJACENT but NOT overlapping!     If W were 5, would overlap at 0!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
FAILURE CASE: Selective Repeat with W = 5 (violation: 5+5=10 > 8):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Sender window: [0,1,2,3,4]        Receiver window: [5,6,7,0,1]
                │                               │
                └──── OVERLAP at 0 and 1! ──────┘
 
Retransmission of seq=0 is accepted as new frame ← DATA CORRUPTION!

Geometric Interpretation:

Imagine the sequence space as a circle. The sender and receiver each have a 'arc' covering their window:

Go-Back-N: Sender has large arc (S-1), receiver has tiny arc (just 1 point)
Selective Repeat: Both have arcs, and combined they must not exceed a full circle

The constraint Wₛ + Wᵣ ≤ S ensures the two arcs, even when maximally separated, fit within the circle without wrapping into each other.

Memory for Efficiency Trade-off

Practical Implications for Protocol Design

The theoretical constraints translate directly into practical protocol decisions:

1. HDLC (High-Level Data Link Control):

Uses 3-bit sequence numbers (S = 8) in normal mode
Window size: 7 (Go-Back-N style)
Extended mode: 7-bit sequence numbers (S = 128), window 127

2. TCP:

Uses 32-bit sequence numbers (S = 2³²)
Sequence numbers count bytes, not segments
With SACK (Selective Repeat behavior), effective window can be up to 2³¹ bytes
But practical windows limited by receiver buffer, not sequence space

Protocol Sequence Number Choices
Protocol	Seq Bits	Space S	Mode	Max Window
HDLC Normal	3	8	GBN	7 frames
HDLC Extended	7	128	GBN	127 frames
HDLC Super	15	32,768	SR/GBN	16,383 (SR)
TCP	32	~4×10⁹	SR (SACK)	~2×10⁹ bytes
Bluetooth L2CAP	6	64	SR	32 frames
IEEE 802.11 (WiFi)	12	4096	GBN	4095 frames

Design Decisions:

1. How many bits for sequence numbers?

Start with required window size (from bandwidth-delay product), then:

For GBN: n = ⌈log₂(W + 1)⌉
For SR: n = ⌈log₂(2W)⌉ = ⌈log₂(W)⌉ + 1

2. Fixed vs. Variable Window Size:

Fixed: Simpler, predictable memory requirements
Variable: Adapts to receiver buffer availability (TCP's advertised window)

3. Handling High Bandwidth-Delay Products:

Modern networks may require huge windows:

10 Gbps × 100 ms = 1 Gbit = 125 MB

Solutions:

TCP window scaling (RFC 1323): Multiply advertised window by 2^scale
Large sequence number fields (TCP uses 32 bits, counting bytes)

TCP Window Scaling

Common Pitfalls and Debugging

Sequence number issues cause some of the most subtle protocol bugs. Here are common pitfalls:

1. Integer Overflow Without Masking:

// WRONG: Can overflow for large sequence numbers
SeqNum next = current + 1;

// CORRECT: Always mask
SeqNum next = (current + 1) & MASK;

2. Naive Comparison:

// WRONG: Fails near wrap-around
if (seq > base) { /* in window */ }

// CORRECT: Use modular comparison
if (((seq - base) & MASK) < window_size) { /* in window */ }

3. Window Size Exceeding Constraint:

// WRONG: Configured window too large
#define SEQ_BITS 3
#define WINDOW_SIZE 6  // For SR, max should be 4!

Debugging Symptoms of Sequence Number Bugs

•Duplicate data delivery: Retransmissions confused with new frames → SR window too large
•Missing data delivery: Correct frames rejected as out-of-order → comparison function bug
•Protocol freeze: Sender stopped, no ACKs processed → ACK comparison with stale base
•Infinite retransmission loops: Same frames retransmitted repeatedly → window never advancing
•Sporadic data corruption: Rare, hard to reproduce → happens only at wrap-around boundaries
•Works with small transfers, fails with large: Sequence space exhausted → window constraint violation

Debugging Sequence Number Issues
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Debugging Checklist for Sequence Number Issues
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
1. Verify window size vs. sequence space:
   
   GBN: assert(window_size <= MAX_SEQ);         // W ≤ S - 1
   SR:  assert(send_win + recv_win <= MAX_SEQ + 1);  // Wₛ + Wᵣ ≤ S
 
2. Check all sequence number operations are modular:
   
   grep for: seq + 1, seq - 1, seq++, seq--
   All must be: (seq + 1) & MASK, etc.
 
3. Check all sequence comparisons use window logic:
   
   Never: if (seq > base)
   Always: if (in_window(seq, base, size))
 
4. Test at wrap-around boundaries:
 
   Test with initial base near MAX_SEQ (e.g., MAX_SEQ - 2)
   Force window to wrap: base=7, next=2 for 3-bit sequences
 
5. Log sequence state at every event:
 
   ON_SEND:  "TX seq=%d, base=%d, next=%d"
   ON_ACK:   "RX ACK=%d, old_base=%d, new_base=%d"
   ON_RX:    "RX seq=%d, expected=%d, in_window=%s"
   ON_TIMER: "TIMEOUT base=%d, next=%d, outstanding=%d"
 
6. Simulate adversarial conditions:
 
   - All ACKs lost (causes maximal window advancement at receiver)
   - Extreme reordering (frame 0 arrives last)
   - Long bursts without reply (tests wrap-around under load)

Unit Testing Sequence Logic

Summary: Sequence Number Space

We've explored the mathematics underlying sequence number design. Let's consolidate the key principles:

Key Takeaways

•Sequence numbers operate in modular arithmetic: With n bits, values wrap from 2ⁿ-1 to 0.
•Comparisons require distance-based logic: 'Greater than' has no meaning in circular space without a reference point.
•Go-Back-N requires Wₛ ≤ S - 1: The small receiver window (Wᵣ=1) allows nearly the full sequence space for sender.
•Selective Repeat requires Wₛ + Wᵣ ≤ S: Both windows together must fit within the sequence space.
•For SR with equal windows: W ≤ S/2, meaning an extra sequence bit is needed compared to GBN.
•Protocol design must match constraints: Window size, sequence bits, and protocol variant are interdependent.
•Wrap-around bugs are subtle: They manifest rarely, only when sequence numbers cycle, making them hard to catch without systematic testing.

What's Next:

Page Complete