Sliding Window Protocol - Learning Module

Loading content...

0/228

Receiver Window

The Receiver's Role

While the sender manages the complex orchestration of transmission, buffering, and retransmission, the receiver plays an equally critical role. The receiver must:

Accept correctly-received frames and deliver data to the upper layer
Detect and handle out-of-order arrivals (depending on protocol variant)
Generate acknowledgments that inform the sender of progress
Manage its own window to control what frames it will accept

The receiver's design choices fundamentally distinguish different sliding window protocols. A receiver that accepts only in-order frames yields Go-Back-N behavior. A receiver that buffers out-of-order frames yields Selective Repeat behavior.

This page examines the receiver window in complete detail.

What You Will Learn

By the end of this page, you will understand receiver state variables and their semantics, frame acceptance criteria and the receiver window, the distinction between in-order-only and out-of-order-buffering receivers, acknowledgment generation strategies (cumulative vs. selective), and the complete receiver state machine.

Receiver State Variables

The receiver maintains state that mirrors and complements the sender's state:

Core Receiver Variables:

Variable	Description	Meaning
Rₙ (Receive Next)	Next expected sequence number	Frame the receiver is waiting for
Wᵣ (Receive Window)	Size of the acceptance window	How many frames beyond Rₙ to accept

Receive Window Interpretation:

The receive window defines which sequence numbers the receiver will accept:

Acceptable sequence numbers: [Rₙ, Rₙ + Wᵣ)

Wᵣ = 1: Only the next expected frame is acceptable (Go-Back-N receiver)
Wᵣ > 1: Out-of-order frames within the window are buffered (Selective Repeat receiver)

Converting Mermaid diagram...

Frame Classification at Receiver:

When a frame with sequence number seq arrives, the receiver classifies it:

seq < Rₙ (Before window): Already delivered frame—duplicate. Discard or re-ACK.
seq = Rₙ (At window base): Expected frame—accept, deliver to upper layer, advance Rₙ.
Rₙ < seq < Rₙ + Wᵣ (Inside window, not at base):
- If Wᵣ = 1 (GBN): Discard (out of order)
- If Wᵣ > 1 (SR): Buffer for later delivery
seq ≥ Rₙ + Wᵣ (Beyond window): Too far ahead—discard. Sender is misbehaving or severe reordering occurred.

The Critical Distinction

The receive window size Wᵣ is the key parameter distinguishing Go-Back-N (Wᵣ = 1) from Selective Repeat (Wᵣ = Wₛ). This single parameter change dramatically alters protocol behavior, buffering requirements, and retransmission efficiency.

Go-Back-N Receiver (Wᵣ = 1)

The Go-Back-N receiver is elegantly simple. It maintains a single expectation: the next in-order frame. Anything else is discarded.

Go-Back-N Receiver Behavior:

Receive window size: Wᵣ = 1
State: Only Rₙ (the next expected sequence number)
Buffering: None for data frames (only buffer the current frame during delivery)
ACK generation: Always ACK the last correctly received in-order frame

Algorithm:

On frame arrival (seq, data, checksum):
    if checksum_valid AND seq == Rₙ:
        deliver_to_upper_layer(data)
        Rₙ = Rₙ + 1
        send_ack(Rₙ)          // Cumulative: "I've received up to Rₙ-1"
    else:
        // Out of order or corrupted - discard
        send_ack(Rₙ)          // Re-send ACK for last in-order frame

Go-Back-N Receiver Trace
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
Go-Back-N Receiver Behavior (Wᵣ = 1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Scenario: Sender sends frames 0,1,2,3,4. Frame 2 is lost.
 
Time │ Arrival     │ Rₙ Before │ Action                │ Rₙ After │ ACK Sent
─────┼─────────────┼───────────┼───────────────────────┼──────────┼─────────
T1   │ Frame 0     │ 0         │ Accept, deliver       │ 1        │ ACK(1)
T2   │ Frame 1     │ 1         │ Accept, deliver       │ 2        │ ACK(2)
T3   │ Frame 2     │ 2         │ [LOST IN TRANSIT]     │ 2        │ —
T4   │ Frame 3     │ 2         │ seq≠Rₙ, DISCARD       │ 2        │ ACK(2)
T5   │ Frame 4     │ 2         │ seq≠Rₙ, DISCARD       │ 2        │ ACK(2)
T6   │ (Timeout)   │           │ Sender retransmits 2,3,4         │ 
T7   │ Frame 2     │ 2         │ Accept, deliver       │ 3        │ ACK(3)
T8   │ Frame 3     │ 3         │ Accept, deliver       │ 4        │ ACK(4)
T9   │ Frame 4     │ 4         │ Accept, deliver       │ 5        │ ACK(5)
 
Key Observations:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
• Frames 3 and 4 were correctly received but DISCARDED (not buffered)
• Receiver kept sending ACK(2) - the last in-order frame
• After retransmission, receiver had to re-receive frames 3 and 4
• Wasted effort: Frames 3,4 transmitted TWICE due to lack of buffering
 
Memory Usage: O(1) - no buffering!
Bandwidth Waste: O(W) frames retransmitted after single loss

Advantages of Go-Back-N Receiver:

Minimal memory: No receive buffer needed beyond frame-in-progress
Simple implementation: Just track one variable (Rₙ)
Guaranteed in-order delivery: Upper layer always gets data in sequence
No resequencing logic: Nothing to reassemble

Disadvantages:

Bandwidth waste: Correctly-received out-of-order frames are discarded
Sender burden: Sender must retransmit potentially many frames
High latency after loss: Recovery requires re-sending all frames from loss point

Why Discard Perfectly Good Frames?

At first, discarding correctly-received frames seems wasteful—and it is! But the GBN receiver trades bandwidth for memory and simplicity. In resource-constrained systems (early network equipment, embedded devices), this trade-off made sense. For modern systems with ample memory, Selective Repeat is usually preferred.

Selective Repeat Receiver (Wᵣ = Wₛ)

The Selective Repeat receiver buffers out-of-order frames, enabling more efficient recovery from losses. It's more complex but wastes far less bandwidth.

Selective Repeat Receiver Behavior:

Receive window size: Wᵣ = Wₛ (typically equal to sender window)
State: Rₙ plus buffer for out-of-order frames
Buffering: Buffer for up to Wᵣ frames
ACK generation: Individual ACK for each correctly received frame

Receiver Buffer States:

For each slot in the receive window [Rₙ, Rₙ + Wᵣ):

State	Meaning
EMPTY	Awaiting frame with this sequence number
RECEIVED	Frame buffered, waiting for gap to fill
(delivered)	Frame delivered; slot no longer in window

Selective Repeat Receiver Algorithm
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
Selective Repeat Receiver Algorithm
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
State:
    Rₙ          : SeqNum                    // Next expected (window base)
    Wᵣ          : int                       // Receive window size
    buffer[]    : Frame[Wᵣ]                 // Buffer for out-of-order frames
    received[]  : bool[Wᵣ]                  // Marks which slots are filled
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
On Frame Arrival (seq, data, checksum):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
function on_frame(seq, data, checksum):
    
    // Step 1: Validate checksum
    if not checksum_valid(data, checksum):
        return            // Corrupted frame - silently discard
    
    // Step 2: Check if in receive window
    if not in_window(seq, Rₙ, Wᵣ):
        // Outside window - could be old duplicate or too far ahead
        if in_window(seq, Rₙ - Wᵣ, Wᵣ):
            // Duplicate from already-delivered range - re-ACK
            send_ack(seq)
        return             // Otherwise ignore
    
    // Step 3: Frame is within window - buffer it
    idx = seq mod Wᵣ
    if not received[idx]:
        buffer[idx] = data
        received[idx] = true
        send_ack(seq)      // Individual ACK for this frame
    else:
        // Duplicate of already-buffered frame
        send_ack(seq)      // Re-ACK
        return
    
    // Step 4: Deliver contiguous frames starting from Rₙ
    while received[Rₙ mod Wᵣ]:
        deliver_to_upper_layer(buffer[Rₙ mod Wᵣ])
        received[Rₙ mod Wᵣ] = false   // Clear slot
        buffer[Rₙ mod Wᵣ] = null      // Free memory
        Rₙ = Rₙ + 1                   // Advance window
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Example Trace: Same scenario (Frame 2 lost)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Time │ Arrival  │ Rₙ │ Buffer Status [0][1][2][3] │ Action       │ Delivery
─────┼──────────┼────┼────────────────────────────┼──────────────┼──────────
T1   │ Frame 0  │ 0  │ [0][ ][ ][ ]              │ Buffer, ACK  │ Frame 0
T2   │ Frame 1  │ 1  │ [ ][1][ ][ ]              │ Buffer, ACK  │ Frame 1
T3   │ Frame 2  │ 2  │ [ ][ ][ ][ ]              │ [LOST]       │ —
T4   │ Frame 3  │ 2  │ [ ][ ][ ][3]              │ Buffer, ACK  │ —(gap)
T5   │ Frame 4  │ 2  │ [4][ ][ ][3]              │ Buffer, ACK  │ —(gap)
T6   │ Frame 2  │ 2  │ [4][ ][2][3]              │ Buffer, ACK  │ F2,F3,F4
     │ (retrans)│    │ → [ ][ ][ ][ ]            │ Gap filled!  │
 
Key Difference: Frames 3,4 were BUFFERED, not discarded.
Retransmission: Only frame 2 needed retransmission!
Bandwidth Saved: 2 frames (compared to GBN retransmitting 3 frames)

The Delivery Cascade:

When a missing frame arrives and fills a gap, multiple buffered frames may become deliverable in sequence. In the trace above, when frame 2 finally arrives:

Frame 2 is buffered (slot 2 now filled)
Rₙ = 2, and received[2] is true → deliver frame 2, Rₙ = 3
Rₙ = 3, and received[3] is true → deliver frame 3, Rₙ = 4
Rₙ = 4, and received[4] is true → deliver frame 4, Rₙ = 5
Rₙ = 5, received[5] is false → stop

This cascade delivers all buffered frames in sequence.

Memory Trade-off

Selective Repeat's efficiency comes at a cost: the receiver needs buffer space for Wᵣ frames. For a window of 127 frames at 1500 bytes, that's ~190 KB per connection. For a server with 10,000 connections, that's 1.9 GB of receive buffers alone. Memory-constrained systems may still prefer Go-Back-N.

Acknowledgment Generation Strategies

The receiver's acknowledgment strategy profoundly affects protocol behavior. Different acknowledgment styles serve different purposes:

1. Cumulative ACK (Go-Back-N style):

ACK(n) means: "I have received all frames with sequence numbers < n"

Simple for sender to process
Can acknowledge multiple frames with one ACK
Limitation: Doesn't tell sender which out-of-order frames were received

2. Individual/Selective ACK (Selective Repeat style):

ACK(n) means: "I have received frame with sequence number n specifically"

Allows sender to know exactly which frames need retransmission
Requires per-frame tracking at sender
More ACK traffic but more efficient retransmission

3. Negative Acknowledgment (NAK):

NAK(n) means: "I detected frame n is missing, please retransmit it"

Proactive loss notification
Speeds recovery (no timeout wait)
Requires gap detection at receiver

Acknowledgment Strategy Comparison
Strategy	Information Conveyed	Sender Action	Overhead
Cumulative ACK	Everything up to frame n received	Slide window to n	Low (1 ACK covers many frames)
Selective ACK	Specific frame n received	Mark frame n as ACKed	Medium (1 ACK per frame)
NAK	Frame n is missing	Retransmit frame n immediately	Low (only when loss detected)
SACK (combined)	Cumulative + ranges of received	Optimal retransmission	Variable (bitmap of received)

Selective ACK with Cumulative Base (SACK):

Modern protocols like TCP use a hybrid approach:

SACK(cum_ack=5, ranges=[(7,9), (12,15)])

This says: "I've received everything up to 4, plus frames 7-8, 12-14."

The sender knows exactly which frames are missing (5, 6, 9, 10, 11) and retransmits only those. This is the most bandwidth-efficient approach.

ACK Timing Considerations:

Immediate ACK: Send ACK as soon as frame received
- Fastest feedback
- More ACK traffic
Delayed ACK: Wait briefly before sending ACK
- Allows piggybacking on return data
- Reduces ACK count (one ACK per N frames)
- Trade-off: Delays sender's window advancement
ACK on Every Other Frame: Common compromise
- Reduces ACK traffic by 50%
- Still provides timely feedback

Duplicate ACKs

When the receiver gets an out-of-order frame (in cumulative ACK protocols), it re-sends the ACK for the last in-order frame. Multiple 'duplicate ACKs' signal to the sender that frames are being received but not the expected one. TCP uses 3 duplicate ACKs as a fast retransmit trigger—faster than waiting for timeout.

Receiver Window Size Constraints

The receive window size Wᵣ interacts critically with the sequence number space. Choosing Wᵣ incorrectly can cause protocol failure.

The Fundamental Constraint:

For a sequence number space of size S (i.e., sequence numbers 0 to S-1, where S = 2ⁿ for n-bit sequence numbers):

Go-Back-N (Wᵣ = 1):

Wₛ ≤ S - 1

The sender window can be at most S-1.

Selective Repeat (Wᵣ = Wₛ):

Wₛ + Wᵣ ≤ S

Since Wₛ = Wᵣ: Wᵣ ≤ S/2

The combined sender and receiver windows must fit within the sequence space.

Why the Constraint Exists - Selective Repeat Failure Mode
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
Selective Repeat: Why Wₛ + Wᵣ ≤ S is Necessary
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Consider: 3-bit sequence numbers (S = 8, sequences 0-7)
Violation: Using Wₛ = Wᵣ = 5 (5 + 5 = 10 > 8) ← INVALID!
 
Failure Scenario:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
1. Sender transmits frames 0, 1, 2, 3, 4
   - Sender window: [0, 1, 2, 3, 4]
   - Sender expecting ACKs for 0, 1, 2, 3, 4
 
2. Receiver correctly receives ALL five frames
   - Delivers frames 0, 1, 2, 3, 4 to upper layer
   - Advances Rₙ to 5
   - Sends ACK(0), ACK(1), ACK(2), ACK(3), ACK(4)
 
3. ALL ACKs are LOST in transit
 
4. Receiver's new window: [5, 6, 7, 0, 1]  (wrapping around!)
   - Receiver expecting frames 5, 6, 7, 0, 1
 
5. Sender times out and RETRANSMITS frame 0
 
6. Receiver gets frame with seq=0
   - Is seq=0 in current window [5, 6, 7, 0, 1]? YES!
   - Receiver thinks: "This is new frame 0 (after wrap-around)"
   - Receiver ACCEPTS IT AS NEW DATA
 
   ⚠️  CATASTROPHIC FAILURE!
   
   The retransmission of OLD frame 0 is mistaken for NEW frame 0!
   Receiver delivers DUPLICATE DATA, corrupting the stream.
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Correct Configuration: Wₛ = Wᵣ = 4 (4 + 4 = 8 = S) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
With Wₛ = Wᵣ = 4:
- Sender window after sending 0,1,2,3: [0, 1, 2, 3]
- After all ACKed, sender window: [4, 5, 6, 7]
- Receiver window after receiving 0,1,2,3: [4, 5, 6, 7]
 
Even if ACKs lost and sender retransmits 0:
- seq=0 is NOT in receiver window [4, 5, 6, 7]
- Receiver correctly identifies duplicate!
- Protocol remains correct.
 
The key: Sender and receiver windows must NEVER OVERLAP after wrap-around.

Maximum Window Sizes for Different Sequence Number Bits
Seq Bits (n)	Space S=2ⁿ	GBN Max Wₛ	SR Max Wₛ=Wᵣ
3	8	7	4
4	16	15	8
7 (HDLC)	128	127	64
16	65,536	65,535	32,768
32 (TCP)	~4 billion	~4 billion	~2 billion

Critical Design Rule

For Selective Repeat, the receive window must not extend so far that it overlaps with sequence numbers the sender might retransmit. The constraint Wₛ + Wᵣ ≤ S ensures non-overlapping windows even after wrap-around.

Complete Receiver State Machine

Let's formalize the complete receiver state machine, parameterized by window size to cover both GBN and SR variants.

Unified Receiver State Machine
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
80
81
82
83
Sliding Window Receiver: Unified State Machine
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Configuration:
    Wᵣ          : int            // Receive window size (1 = GBN, >1 = SR)
    MAX_SEQ     : int            // Maximum sequence number
 
State Variables:
    Rₙ          : SeqNum         // Next expected sequence number
    buffer[]    : Data[Wᵣ]       // Data buffer (unused if Wᵣ=1)
    received[]  : bool[Wᵣ]       // Received flags (unused if Wᵣ=1)
 
Helper Functions:
    inc(seq)         = (seq + 1) mod (MAX_SEQ + 1)
    in_window(s,b,w) = 0 ≤ (s-b) mod (MAX_SEQ+1) < w
    idx(seq)         = seq mod Wᵣ
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EVENT: Frame Arrival
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
procedure on_frame_arrival(frame):
    
    // Step 1: Error checking
    if not frame.checksum_valid():
        if Wᵣ == 1:
            send_ack(Rₙ)     // GBN: Re-ACK last good frame
        return                // Discard corrupted frame
    
    seq = frame.sequence_number
    
    // Step 2: Classify frame by position relative to window
    
    if in_window(seq, Rₙ, Wᵣ):
        // ──────────────────────────────────────────────
        // Case A: Frame is within receive window
        // ──────────────────────────────────────────────
        
        if Wᵣ == 1:
            // Go-Back-N behavior
            if seq == Rₙ:
                deliver_to_upper_layer(frame.data)
                Rₙ = inc(Rₙ)
            // else: out of order in GBN - implicitly discard
            send_ack(Rₙ)     // Always ACK the last in-order frame
            
        else:
            // Selective Repeat behavior
            i = idx(seq)
            if not received[i]:
                buffer[i] = frame.data
                received[i] = true
            send_ack(seq)    // Individual ACK for this frame
            
            // Deliver contiguous frames from window base
            while received[idx(Rₙ)]:
                deliver_to_upper_layer(buffer[idx(Rₙ)])
                received[idx(Rₙ)] = false
                buffer[idx(Rₙ)] = null
                Rₙ = inc(Rₙ)
    
    else if in_window(seq, Rₙ - Wᵣ, Wᵣ):
        // ──────────────────────────────────────────────
        // Case B: Frame is old (already delivered)
        // ──────────────────────────────────────────────
        // This is a duplicate - sender didn't get our ACK
        
        if Wᵣ == 1:
            send_ack(Rₙ)     // GBN: cumulative ACK
        else:
            send_ack(seq)    // SR: individual ACK for the duplicate
    
    else:
        // ──────────────────────────────────────────────
        // Case C: Frame is too far ahead or corrupted seq
        // ──────────────────────────────────────────────
        // Ignore - sender error or extreme reordering
        return
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Note: This unified algorithm handles both GBN (Wᵣ=1) and SR (Wᵣ>1)
      The conditional branches create protocol-appropriate behavior.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Parameterized Design

Notice how a single algorithm, parameterized by Wᵣ, elegantly captures both GBN and SR receiver behavior. This unified view helps understand that these aren't fundamentally different protocols—they're points on a spectrum defined by how much buffering the receiver is willing to do.

Summary: The Receiver Window

The receiver window complements the sender window, and together they define sliding window protocol behavior. Let's consolidate the key insights:

Key Takeaways

•The receive window size Wᵣ determines protocol behavior: Wᵣ = 1 yields Go-Back-N; Wᵣ > 1 yields Selective Repeat.
•GBN receiver is simple but wasteful: Discards out-of-order frames, requiring sender to retransmit everything after a loss.
•SR receiver buffers out-of-order frames: More complex but efficient—only lost frames need retransmission.
•ACK strategies vary: Cumulative ACKs (GBN) vs. individual ACKs (SR) vs. hybrid SACK (modern TCP).
•Sequence number constraint for SR: Wₛ + Wᵣ ≤ S to prevent wrap-around ambiguity.
•Frame classification: Each frame is either in-window (accept/buffer), before-window (duplicate), or beyond-window (discard).
•Delivery cascade: When a gap fills, multiple buffered frames may be delivered in sequence.

What's Next:

With both sender and receiver windows understood, we'll examine the sequence number space in detail. We'll derive the precise relationships between window sizes and sequence number requirements, understand modular arithmetic in sequence comparisons, and see why getting this wrong causes catastrophic failures.

Page Complete

You now understand the receiver window in depth—its state variables, frame classification logic, acknowledgment strategies, and the unified state machine that captures both GBN and SR behavior. The receiver's design choices directly determine protocol efficiency and correctness. Next, we explore sequence number space requirements.