Sliding Window Protocol: Reliable Delivery, Ordering, and Flow Control

Why windowing matters

Stop-and-wait sends one frame and waits for an ACK before sending the next. On a 100ms RTT link at 1 Gbps, stop-and-wait achieves:

Efficiency = frame_size / (frame_size + RTT × bandwidth)
           = 1500 bytes / (1500 bytes + 0.1s × 1,000,000,000 bps / 8)
           = 1500 / (1500 + 12,500,000)
           ≈ 0.012% utilization

Sliding window keeps W frames in flight simultaneously, improving utilization to:

Efficiency = min(1, W × frame_size / (RTT × bandwidth))

With W=1000 frames, the same link achieves reasonable utilization.

Sender and receiver state

// Sender state
SwpSeqno LAR;  // sequence number of last ACK received
SwpSeqno LFS;  // last frame sent

// Constraint: LFS - LAR <= SWS (send window size)
// Window of unacknowledged frames: [LAR+1 ... LFS]

// Receiver state
SwpSeqno NFE;  // next frame expected (= highest in-order seq + 1)

// Constraint: frames accepted: [NFE ... NFE+RWS-1]
// (receive window size RWS allows buffering out-of-order frames)

When the sender receives an ACK for sequence number N, it advances LAR to N and cancels all retransmit timers for frames with seqno ≤ N. This frees send window slots for new frames.

When the receiver gets frame N:

• If N == NFE: deliver to application, advance NFE, check if buffered frames can also be delivered
• If NFE < N ≤ NFE+RWS-1: buffer the frame (out of order), send ACK for NFE-1 (last in-order received)
• Otherwise: drop (outside window)

if (hdr.SeqNum == state->NFE) {
    // In-order delivery: deliver and advance
    while (slot->received) {
        deliver(HLP, &slot->msg);
        slot->received = FALSE;
        slot = &state->recvQ[++state->NFE % RWS];
    }
    // ACK the highest in-order received frame
    prepare_ack(&m, state->NFE - 1);
    send(LINK, &m);
}

The ACK piggybacked in the response is cumulative: ACK=N means "I have received all frames through N in order."

Sequence number space must be larger than send window + receive window combined — otherwise old and new frames are ambiguous

ConceptNetworking Protocols

With k-bit sequence numbers, there are 2^k distinct sequence numbers. If the send window is SWS and receive window is RWS, the sequence space must satisfy SWS + RWS ≤ 2^k. If this constraint is violated, the receiver can't distinguish a retransmit of an old frame from a new frame with the same sequence number. For Go-Back-N (RWS=1), the sender window must be ≤ 2^k - 1. For Selective Repeat (RWS = SWS), each window must be ≤ 2^(k-1) — half the sequence space.

Prerequisites

• Sequence numbers
• ACK mechanisms
• Retransmission timers

Key Points

• Go-Back-N: RWS=1, SWS ≤ 2^k - 1. On loss, sender retransmits from the lost frame forward.
• Selective Repeat: SWS = RWS ≤ 2^(k-1). Receiver buffers out-of-order frames, sender only retransmits the lost frame.
• TCP uses a hybrid: cumulative ACKs (Go-Back-N style) + SACK (Selective Acknowledgment) option for selective retransmit.
• Sequence number wraparound: TCP 32-bit seqno wraps at 4GB. On high-speed links, PAWS (Protection Against Wrapped Sequences) uses timestamps to disambiguate.

Three roles of sliding window

The sliding window algorithm serves three distinct purposes simultaneously:

1. Reliable delivery: Retransmit timers detect lost frames. Each sent frame has a timer; if no ACK arrives before timeout, the frame is retransmitted.

2. Ordering: Frames outside the receive window are dropped. The NFE tracker ensures the application layer receives frames in sequence, even if the network delivers them out of order.

3. Flow control: The receiver controls the sender's window size. If the application is slow to consume data, the receiver shrinks its advertised window, slowing the sender. TCP's rwnd (receive window) field in ACK packets implements this.

📝TCP congestion control vs flow control

TCP has two window mechanisms:

Flow control (receiver-driven): The receiver's rwnd in the ACK packet limits how much the sender can transmit. This prevents the sender from overwhelming the receiver's buffer.

Congestion control (network-driven): The sender maintains cwnd (congestion window). The effective window is min(rwnd, cwnd). Congestion control algorithms (slow start, AIMD, CUBIC, BBR) probe available bandwidth and back off on loss or delay signals.

• Slow start: cwnd starts at 1 MSS, doubles each RTT until reaching ssthresh
• Congestion avoidance: after ssthresh, cwnd grows by 1 MSS per RTT (additive increase)
• On loss (packet drop): ssthresh = cwnd/2, cwnd drops to 1 MSS (multiplicative decrease)
• BBR: estimates bandwidth and RTT to set cwnd without relying on packet loss as a signal

QUIC implements its own congestion control (typically CUBIC or BBR) in user space, allowing faster iteration than waiting for OS kernel updates.

A sliding window protocol uses 3-bit sequence numbers (8 values: 0-7) with Go-Back-N (receive window = 1). What is the maximum send window size?

medium

Go-Back-N uses receive window size = 1. The sequence number space has 2^3 = 8 values. The constraint is SWS + RWS ≤ 2^k.

• A8 — use all sequence numbers

  Incorrect.If SWS=8 and RWS=1, SWS + RWS = 9 > 2^3 = 8. The constraint is violated. A sender could have frames 0-7 all unacknowledged, and when it sends frame 0 again (wraparound), the receiver can't tell if it's a new frame or a retransmit.
• B7 — send window must be at most 2^k - 1 with Go-Back-N

  Correct!With 3-bit sequence numbers (2^3 = 8 values) and Go-Back-N (RWS=1): SWS + RWS ≤ 2^k → SWS + 1 ≤ 8 → SWS ≤ 7. If the sender has frames 0-6 unacknowledged (7 frames) and sends 7, the receiver might think frame 0 (the same sequence number as the first unacknowledged frame) has arrived — ambiguous. With SWS=7, the next new frame would be seqno 7, which the receiver can distinguish from the outstanding frames 0-6.
• C4 — half the sequence space, same rule as Selective Repeat

  Incorrect.The half-sequence-space limit applies to Selective Repeat (where RWS = SWS). Go-Back-N has RWS=1, so the constraint allows SWS up to 2^k - 1.
• DAny size — the receiver window of 1 means no ambiguity is possible

  Incorrect.RWS=1 doesn't prevent sequence number ambiguity. The ambiguity occurs when the sender wraps sequence numbers while some frames are still unacknowledged. The window size limit exists precisely to prevent this.

Hint:Go-Back-N constraint: SWS + RWS ≤ 2^k. With RWS=1 and 2^k=8, what's the maximum SWS?