Loading learning content...
Imagine a post office that can only number packages from 0 to 7. If you send packages 0, 1, 2, 3, 4, 5, 6, 7 and then need to send more, you must reuse numbers: the next package is also numbered 0.
Now imagine package number 3 from the first batch gets severely delayed. Days later, it finally arrives—but by now you've sent a completely different package also numbered 3. How does the recipient know which package 3 they received?
This is the sequence number ambiguity problem, and it's the reason Selective Repeat has strict constraints on window size. Unlike Go-Back-N which can get away with W ≤ 2^n - 1, Selective Repeat requires the more restrictive W ≤ 2^n / 2. This page explains why, proves it mathematically, and demonstrates the disasters that occur when this constraint is violated.
By the end of this page, you will understand the mathematical basis for SR's window size constraint, see examples of what breaks when it's violated, and know how to correctly size windows for any sequence number space.
Every frame carries a sequence number for identification. With limited bits, sequence numbers must wrap around:
Sequence Number Space:
With n bits: sequence numbers range from 0 to 2^n - 1
n = 1 bit: 0, 1 (2 numbers)
n = 2 bits: 0, 1, 2, 3 (4 numbers)
n = 3 bits: 0, 1, 2, 3, 4, 5, 6, 7 (8 numbers)
n = 4 bits: 0 to 15 (16 numbers)
Wraparound:
After sending frame with sequence number 2^n - 1, the next frame uses sequence number 0:
... → 5 → 6 → 7 → 0 → 1 → 2 → ... (n=3 bits)
↑
Wraparound
The Problem:
If we send frames 0, 1, 2, 3 (first batch) and later send frames 0, 1, 2, 3 again (second batch after wraparound), how do we distinguish between old frame 2 (from first batch) and new frame 2 (from second batch)?
| Bits (n) | Max Sequence | Space Size (2^n) | Max Window (SR) | Max Window (GBN) |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 |
| 2 | 3 | 4 | 2 | 3 |
| 3 | 7 | 8 | 4 | 7 |
| 4 | 15 | 16 | 8 | 15 |
| 8 | 255 | 256 | 128 | 255 |
| 16 | 65535 | 65536 | 32768 | 65535 |
Selective Repeat's maximum window is half that of Go-Back-N for the same sequence number bits. This isn't inefficiency—it's a fundamental requirement for correctness with receiver buffering.
The fundamental constraint for Selective Repeat is:
Sender Window Size + Receiver Window Size ≤ Sequence Number Space
W_s + W_r ≤ 2^n
Since Selective Repeat uses equal sender and receiver windows (W_s = W_r = W):
2W ≤ 2^n
W ≤ 2^n / 2 = 2^(n-1)
In Plain Terms:
The window size must be at most half the sequence number space.
Examples:
| Sequence Bits | Space Size | Maximum Window Size |
|---|---|---|
| 3 bits | 8 | 4 |
| 4 bits | 16 | 8 |
| 8 bits | 256 | 128 |
| 16 bits | 65536 | 32768 |
Why This Constraint Exists:
The receiver must distinguish between two scenarios:
For this distinction to work, the current window and previous window must never overlap in sequence number space. Since each window occupies W numbers:
Current window: [recv_base, recv_base + W - 1]
Previous window: [recv_base - W, recv_base - 1]
For no overlap: These ranges must be disjoint
Requires: At least 2W sequence numbers
Therefore: 2W ≤ 2^n → W ≤ 2^(n-1)
Let's see exactly what goes wrong when we violate the W ≤ 2^(n-1) constraint. We'll use:
Disaster Scenario:
| Step | Event | Sender View | Receiver View | Problem |
|---|---|---|---|---|
| 1 | Send Frame 0,1,2,3,4 | send_base=0, next=5 | recv_base=0 | Window: 0-4 |
| 2 | All frames + ACKs delivered | send_base=5, next=5 | recv_base=5 | Window: 5-9→5,6,7,0,1 (wrap!) |
| 3 | Send Frame 5,6,7,0,1 (new!) | send_base=5, next=10→2 | recv_base=5 | Sending new 0,1 |
| 4 | Frame 5,6,7 delivered | send_base=5, next=2 | recv_base=8→0 | Receiver expects 0,1 |
| 5 | ACK 5,6,7 delivered | send_base=0, next=2 | Sender window: 0-4 | |
| 6 | OLD Frame 0 (delayed) arrives! | recv_base=0 | Receiver accepts it! | |
| 7 | CORRUPTION! | Old data delivered as new! |
The Fatal Confusion:
At step 6, the receiver's current window is [0, 4]. A frame with sequence number 0 arrives. The receiver cannot tell:
With no way to distinguish, the receiver does the only thing it can: accept it, buffer it, ACK it, and deliver the wrong data to the application.
The Root Cause:
With W=5 and space=8, the current and previous windows overlap:
At recv_base=5, window = [5,6,7,0,1] (wraps around)
Previous window would be [0,1,2,3,4]
Overlap: 0 and 1 appear in BOTH windows!
Violating the window constraint doesn't cause performance problems—it causes silent data corruption. The receiver delivers old data as if it were new, with no error indication. This is the worst possible failure mode.
Let's visualize why the constraint must hold. Think of sequence numbers as positions on a circle (due to wraparound).
Correct Case: W = 4, n = 3 (8 numbers)
7 0 1
╱ ╲
6 2
╲ ╱
5 4 3
If recv_base = 0:
Current window (accept + buffer): [0, 1, 2, 3] ← positions 0,1,2,3
Previous window (re-ACK only): [4, 5, 6, 7] ← positions 4,5,6,7
No overlap! Every sequence number belongs to exactly one window.
Incorrect Case: W = 5, n = 3 (8 numbers)
7 0 1
╱ ↑↑ ╲
6 ⚡ 2
╲ ↑↑ ╱
5 4 3
If recv_base = 4:
Current window: [4, 5, 6, 7, 0] ← 5 positions, WRAPS to 0
Previous window: [7, 0, 1, 2, 3] ← Would include 0, 7!
OVERLAP at 0 and 7! Ambiguity when these seq nums arrive.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
def check_window_constraint(seq_bits: int, window_size: int) -> dict: """ Verify if a window size satisfies the SR constraint. Args: seq_bits: Number of bits for sequence numbers window_size: Proposed window size Returns: Dictionary with constraint analysis """ space = 2 ** seq_bits max_valid_window = space // 2 is_valid = window_size <= max_valid_window result = { 'seq_bits': seq_bits, 'seq_space': space, 'window_size': window_size, 'max_valid_window': max_valid_window, 'is_valid': is_valid, 'overlap_positions': [], 'safety_margin': max_valid_window - window_size if is_valid else None } if not is_valid: # Calculate overlap positions for demonstration # With recv_base = 0: current_window = set(range(window_size)) # [0, W-1] previous_window = set((space - window_size + i) % space for i in range(window_size)) overlap = current_window & previous_window result['overlap_positions'] = sorted(overlap) result['overlap_count'] = len(overlap) return result def visualize_windows(seq_bits: int, window_size: int, recv_base: int = 0): """Create ASCII visualization of window positions.""" space = 2 ** seq_bits # Calculate windows current = [(recv_base + i) % space for i in range(window_size)] previous = [(recv_base - window_size + i) % space for i in range(window_size)] current_set = set(current) previous_set = set(previous) overlap = current_set & previous_set lines = [f"Sequence Space: 0 to {space-1} ({seq_bits} bits)"] lines.append(f"Window Size: {window_size}") lines.append(f"recv_base: {recv_base}") lines.append("") # Draw sequence numbers seq_line = "" marker_line = "" for i in range(space): if i in overlap: seq_line += f" {i}!" marker_line += " ⚡ " elif i in current_set: seq_line += f" {i}C" marker_line += " ↑ " elif i in previous_set: seq_line += f" {i}P" marker_line += " ↓ " else: seq_line += f" {i} " marker_line += " " lines.append(seq_line) lines.append(marker_line) lines.append("") lines.append(f"C=Current window, P=Previous window, !=OVERLAP (ERROR)") if overlap: lines.append(f"\n** CONSTRAINT VIOLATED! Overlap at: {sorted(overlap)} **") lines.append(" Old and new frames cannot be distinguished!") else: lines.append("\n✓ Constraint satisfied - windows do not overlap") return "\n".join(lines) # Demonstrationprint("=== VALID: W=4, n=3 ===")print(visualize_windows(3, 4, recv_base=0)) print("\n" + "="*50 + "\n") print("=== INVALID: W=5, n=3 ===")print(visualize_windows(3, 5, recv_base=0)) print("\n" + "="*50 + "\n") print("=== INVALID: W=5, n=3, different recv_base ===")print(visualize_windows(3, 5, recv_base=4))Go-Back-N has a less restrictive constraint: W ≤ 2^n - 1. Why can GBN use almost the entire sequence space while SR can only use half?
The Key Difference: Receiver Behavior
| Aspect | Go-Back-N | Selective Repeat |
|---|---|---|
| Out-of-order frames | Discarded | Buffered |
| Receiver window size | 1 (only expects next) | W (accepts window) |
| Frame acceptance | Only recv_base | Any in [recv_base, recv_base+W-1] |
Why GBN's Receiver Window = 1 Matters:
In GBN, the receiver only accepts frame with seq == recv_base. It ignores everything else. This means:
GBN Constraint Derivation:
At any time:
[send_base, send_base + W - 1] in flightrecv_baseFor correctness:
This requires: W < 2^n, i.e., W ≤ 2^n - 1
SR Constraint Derivation:
At any time:
[recv_base, recv_base + W - 1][recv_base - W, recv_base - 1]These two ranges of size W each must not overlap:
This requires: 2W ≤ 2^n, i.e., W ≤ 2^(n-1)
Given the constraint W ≤ 2^(n-1), how do we choose appropriate values for real systems?
Step 1: Determine Required Window Size
Window size is driven by the bandwidth-delay product:
W_required = (Bandwidth × RTT) / Frame_Size
= BDP / Frame_Size
Step 2: Calculate Required Sequence Bits
Given required W, need n bits where:
2^(n-1) ≥ W_required
n ≥ log₂(2 × W_required)
n = ceil(log₂(2 × W_required))
Step 3: Verify Memory Feasibility
Buffer memory = 2 × W × Frame_Size (sender + receiver)
If too much, may need to accept lower throughput with smaller W.
| Link | BDP | Required W | Min Bits (n) | Actual Max W | Memory per Conn |
|---|---|---|---|---|---|
| Ethernet LAN | 62.5 KB | 42 | 7 | 64 | 192 KB |
| Metro WAN | 625 KB | 417 | 10 | 512 | 1.5 MB |
| Cross-country | 1.25 MB | 833 | 11 | 1024 | 3 MB |
| Satellite | 750 KB | 500 | 10 | 512 | 1.5 MB |
| Datacenter 100G | 1.25 MB | 833 | 11 | 1024 | 3 MB |
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
import math def size_sr_window( bandwidth_bps: float, # Link bandwidth in bits per second rtt_seconds: float, # Round-trip time in seconds frame_size_bytes: int = 1500 # Maximum frame size) -> dict: """ Calculate appropriate window size and sequence number bits for SR. Returns recommended configuration ensuring protocol correctness. """ # Calculate bandwidth-delay product bdp_bytes = (bandwidth_bps / 8) * rtt_seconds # Required window to fill the pipe required_window = math.ceil(bdp_bytes / frame_size_bytes) # Calculate minimum sequence number bits # Constraint: W ≤ 2^(n-1), so 2^(n-1) ≥ W # Therefore: n ≥ 1 + log₂(W) min_bits = math.ceil(math.log2(2 * required_window)) if required_window > 0 else 1 min_bits = max(min_bits, 1) # At least 1 bit # Round up to common sizes (3, 4, 8, 16, 32 bits) practical_bits = min(b for b in [3, 4, 8, 16, 32] if b >= min_bits) # Calculate actual maximum window with chosen bits max_window = 2 ** (practical_bits - 1) # Effective window (minimum of required and maximum) effective_window = min(required_window, max_window) # Memory requirements sender_buffer_bytes = effective_window * frame_size_bytes receiver_buffer_bytes = effective_window * frame_size_bytes total_buffer_bytes = sender_buffer_bytes + receiver_buffer_bytes # Efficiency analysis achievable_throughput = (effective_window * frame_size_bytes * 8) / rtt_seconds efficiency = min(1.0, achievable_throughput / bandwidth_bps) * 100 return { 'input': { 'bandwidth_mbps': bandwidth_bps / 1e6, 'rtt_ms': rtt_seconds * 1000, 'frame_size': frame_size_bytes, }, 'sizing': { 'bdp_kb': bdp_bytes / 1024, 'required_window': required_window, 'sequence_bits': practical_bits, 'max_window_allowed': max_window, 'effective_window': effective_window, }, 'memory': { 'sender_buffer_kb': sender_buffer_bytes / 1024, 'receiver_buffer_kb': receiver_buffer_bytes / 1024, 'total_kb': total_buffer_bytes / 1024, }, 'performance': { 'theoretical_efficiency': efficiency, 'can_fill_pipe': required_window <= max_window, } } # Example calculationsprint("=== 1 Gbps Ethernet LAN (0.5ms RTT) ===")lan = size_sr_window(1e9, 0.0005)print(f"Window: {lan['sizing']['effective_window']} frames")print(f"Seq bits: {lan['sizing']['sequence_bits']}")print(f"Memory: {lan['memory']['total_kb']:.1f} KB") print("\n=== 100 Mbps WAN (50ms RTT) ===")wan = size_sr_window(100e6, 0.050)print(f"Window: {wan['sizing']['effective_window']} frames")print(f"Seq bits: {wan['sizing']['sequence_bits']}")print(f"Memory: {wan['memory']['total_kb']:.1f} KB") print("\n=== 10 Mbps Satellite (600ms RTT) ===")sat = size_sr_window(10e6, 0.600)print(f"Window: {sat['sizing']['effective_window']} frames")print(f"Seq bits: {sat['sizing']['sequence_bits']}")print(f"Memory: {sat['memory']['total_kb']:.1f} KB")TCP uses 32-bit sequence numbers but allows windows up to 2^30 bytes—seemingly violating our constraint. How?
TCP's Approach:
Why 32 Bits Seems To Work:
With 32-bit sequence numbers and byte-level sequencing:
At 1 Gbps:
Sending 1 billion bits/second = 125 million bytes/second
Time to exhaust 32-bit space: 4 billion / 125 million ≈ 34 seconds
If maximum segment lifetime (MSL) is 2 minutes:
Old segments could exist with same sequence number!
Solution: Timestamps (PAWS - Protection Against Wrapped Sequences)
Protection Against Wrapped Sequences (PAWS):
TCP segments carry timestamps:
1. Each segment includes sender's timestamp
2. Receiver remembers most recent timestamp accepted
3. Segments with "old" timestamps are rejected
4. Even if sequence number wraps, timestamp won't match
This effectively extends the sequence space using the timestamp as additional bits.
Lesson for SR:
For high-speed, long-delay links where sequence numbers might wrap during segment lifetime:
For most data link layer applications, 8-16 bit sequence numbers with W ≤ 2^(n-1) is sufficient.
When in doubt about sequence space sizing, err on the side of more bits. The memory overhead of tracking a few extra bits is negligible compared to the catastrophic failure of sequence number ambiguity.
We've thoroughly examined the critical window size constraint that ensures Selective Repeat correctness. Let's consolidate the essential concepts:
| Protocol | Constraint | Reason | Example (n=3) |
|---|---|---|---|
| Stop-and-Wait | W = 1 | Only one frame at a time | W = 1 |
| Go-Back-N | W ≤ 2^n - 1 | Sender window must fit in sequence space | W ≤ 7 |
| Selective Repeat | W ≤ 2^(n-1) | Current + previous windows must not overlap | W ≤ 4 |
Module Complete:
You have now completed the comprehensive study of Selective Repeat ARQ. You understand:
With this knowledge, you can analyze, implement, and troubleshoot Selective Repeat protocols in real-world networked systems.
Congratulations! You've mastered Selective Repeat ARQ—the most efficient sliding window protocol. You understand its operational mechanics, acknowledgment strategy, buffering requirements, and the critical window size constraints. Next, explore the Protocol Comparison module to see how SR compares with Stop-and-Wait and Go-Back-N across different network conditions.