Sliding Window Protocol

How the window slides

Imagine mailing 1,000 letters but refusing to send letter two until the recipient mails back a postcard confirming letter one. Each confirmation takes a week round trip. At that rate 1,000 letters takes 1,000 weeks. That's stop-and-wait — one frame on the wire, then a full round-trip of dead air. The sliding window protocol fixes it by letting you keep a whole batch of letters in transit at once.

The sender keeps a window — a contiguous range of sequence numbers it is allowed to send without waiting. Say the window size is W = 4 and the window currently covers frames [3, 4, 5, 6]. The sender fires all four into the network back-to-back. As acknowledgements come back, the window's left edge advances:

           window (W=4)
          ┌───────────────┐
... 0 1 2 │ 3  4  5  6 │ 7  8  9 ...
          └───────────────┘
   sent &       sent,        not yet
   ACKed     awaiting ACK    allowed

ACK 3 arrives  →  slide right by 1:

... 0 1 2 3 │ 4  5  6  7 │ 8  9 ...
            └───────────────┘
                          ↑ 7 now sendable

Three pointers describe the sender's state at any moment:

• send_base — the oldest frame sent but not yet acknowledged (the window's left edge).
• next_seq — the next sequence number to hand to the network.
• send_base + W — the right edge; next_seq may never cross it.

The window can hold at most W outstanding (in-flight) frames. When an ACK confirms the oldest one, send_base moves up, a slot opens at the right edge, and one more frame becomes sendable. The window "slides" along the infinite stream of sequence numbers, never wider than W, always moving forward. The receiver mirrors this with its own window of acceptable incoming sequence numbers.

The throughput math: filling the pipe

The whole point of windowing is link utilisation. With stop-and-wait, utilisation is:

U_stop-and-wait = T_frame / (T_frame + RTT)

where T_frame = frame_bits / bandwidth is the time to clock one frame onto the wire and RTT is the round-trip time. On a 100 Mbps link with 30 ms RTT and 12,000-bit (1,500-byte) frames, T_frame = 120 µs, so utilisation is 120 µs / (120 µs + 30,000 µs) ≈ 0.4%. You're throwing away 99.6% of a fast link.

A window of W frames raises that to:

U_window = min(1, W · T_frame / (T_frame + RTT))

To reach 100% utilisation you need the window to cover the entire bandwidth-delay product (BDP) — the amount of data that fits "in the pipe" at one time:

BDP        = bandwidth × RTT
W_optimal  = ⌈ (bandwidth × RTT) / frame_size ⌉ + 1
           = ⌈ (T_frame + RTT) / T_frame ⌉

For the link above, BDP = 100 Mbps × 30 ms = 3 Mbit = 375 KB, so you need W ≈ 250 frames in flight to saturate it. The window size is the throughput knob: too small and you cap below line rate, just right and the wire never goes idle.

When to use it (and when not to)

• Long fat networks. High bandwidth × high latency = huge BDP. Satellite links (600 ms RTT), transcontinental fibre, anything where one round trip wastes megabytes — windowing is mandatory.
• Reliable, ordered delivery. When the application needs every byte in order (file transfer, TCP streams), the window plus ACKs gives you reliability and pipelining together.
• Flow control. The receiver advertises its window; a slow receiver shrinks W and the sender automatically backs off. This stops a fast sender from drowning a slow consumer.

Skip it when latency dominates over volume. A request-response RPC with one small message per round trip gains nothing from a window — there's only ever one frame outstanding. And on a lossless local bus, the ACK machinery is pure overhead; raw streaming is simpler. Real-time media (voice, gaming) often prefers UDP with no retransmission at all, because a late-but-correct frame is useless.

Go-Back-N vs Selective Repeat vs stop-and-wait

	Stop-and-wait	Go-Back-N (GBN)	Selective Repeat (SR)
Sender window	1	W	W
Receiver window	1	1	W
Sequence numbers needed	2	W + 1	2W
On a single loss	resend that frame	resend that frame + all after it	resend only the lost frame
Out-of-order frames	n/a	discarded	buffered until gap fills
ACK style	per frame	cumulative	individual (selective)
Receiver buffering	none	none	up to W frames
Best for	teaching, lossless short links	low-loss links, simple receivers	lossy links, bandwidth-precious

The headline trade is loss-recovery cost versus receiver complexity. Go-Back-N keeps the receiver trivial — it accepts frames strictly in order and throws away anything out of sequence — but a single drop near the start of a full window forces the sender to retransmit the entire window. Selective Repeat keeps a buffer at the receiver and re-sends only the gaps, which is far cheaper on a lossy link but needs more memory and a richer ACK format. TCP is essentially Selective Repeat with selective acknowledgements (SACK) layered on top of cumulative ACKs.

What the numbers actually say

• Stop-and-wait on a fast link is catastrophic. 100 Mbps, 30 ms RTT, 1,500-byte frames → 0.4% utilisation. Effective throughput ≈ 400 Kbps on a 100 Mbps link. A window of 250 fixes it.
• The window must scale with the BDP. 1 Gbps × 80 ms RTT = 10 MB in flight. With 1,500-byte frames that's ≈ 6,700 frames; with 9,000-byte jumbo frames, ≈ 1,100. This is exactly why TCP needed the window scale option (RFC 7323): the original 16-bit window maxes at 65,535 bytes, which caps a 100 ms link to ≈ 5 Mbps without scaling.
• Go-Back-N's penalty is the window itself. On a link with frame-loss probability p, GBN re-sends roughly W frames per loss event, so its goodput falls off as the window grows on a lossy path — the opposite of what you want. SR's penalty is just the one lost frame.
• Sequence-number wraparound is real. A 3-bit field gives 8 numbers, so GBN can run W = 7 and SR can run W = 4. Use a larger field than the math demands and you waste header bits on every frame; use a smaller one and ACK aliasing corrupts the stream.

JavaScript implementation (Go-Back-N sender)

A Go-Back-N sender driven by ACK and timeout events. Sequence numbers wrap modulo 2^k; the window holds at most W = 2^k − 1 frames.

class GoBackN {
  constructor({ windowSize, seqBits, send, timeoutMs }) {
    this.W = windowSize;                 // e.g. 7
    this.MOD = 1 << seqBits;             // e.g. 8 for 3 bits
    this.send = send;                    // (seq, payload) => void  (puts frame on wire)
    this.timeoutMs = timeoutMs;
    this.base = 0;                       // oldest unACKed seq
    this.nextSeq = 0;                    // next seq to send
    this.buffer = new Map();             // seq -> payload, for retransmit
    this.timer = null;
  }

  // Application hands down a new frame.
  push(payload) {
    const inFlight = (this.nextSeq - this.base + this.MOD) % this.MOD;
    if (inFlight >= this.W) return false;   // window full — apply back-pressure
    this.buffer.set(this.nextSeq, payload);
    this.send(this.nextSeq, payload);
    if (this.base === this.nextSeq) this.startTimer();  // first frame in window
    this.nextSeq = (this.nextSeq + 1) % this.MOD;
    return true;
  }

  // Cumulative ACK: ackNum acknowledges every frame up to (ackNum - 1).
  onAck(ackNum) {
    // Advance base past everything ackNum confirms.
    while (this.base !== ackNum) {
      this.buffer.delete(this.base);
      this.base = (this.base + 1) % this.MOD;
    }
    if (this.base === this.nextSeq) this.stopTimer();   // window empty
    else this.startTimer();                             // restart for the new oldest
  }

  // Timer fired: resend the whole outstanding window — the "go back N".
  onTimeout() {
    let seq = this.base;
    while (seq !== this.nextSeq) {
      this.send(seq, this.buffer.get(seq));
      seq = (seq + 1) % this.MOD;
    }
    this.startTimer();
  }

  startTimer() { this.stopTimer(); this.timer = setTimeout(() => this.onTimeout(), this.timeoutMs); }
  stopTimer()  { if (this.timer) { clearTimeout(this.timer); this.timer = null; } }
}

Two details that bite real implementations. First, inFlight must be computed modulo MOD so a wrapped nextSeq still reports the right window occupancy. Second, there is exactly one timer for the whole window (the oldest frame), not one per frame — that's the defining simplification of Go-Back-N over Selective Repeat, which needs a timer per outstanding frame.

Python implementation (Selective Repeat receiver)

The receiver is where Selective Repeat differs most: it buffers out-of-order frames inside its own window and only delivers a contiguous prefix to the application.

class SelectiveRepeatReceiver:
    def __init__(self, window_size, seq_bits, deliver, send_ack):
        self.W = window_size            # SR receive window == send window
        self.MOD = 1 << seq_bits        # need MOD >= 2 * W
        self.deliver = deliver          # callback: hand ordered payload up
        self.send_ack = send_ack        # callback: ACK a specific seq
        self.rcv_base = 0               # left edge of receive window
        self.buf = {}                   # seq -> payload, out-of-order holding area

    def _in_window(self, seq, base):
        # Is seq within [base, base + W) on the modular ring?
        return (seq - base) % self.MOD < self.W

    def on_frame(self, seq, payload):
        # Always ACK frames in the *previous* window too: the sender may have
        # missed an ACK, so re-acking keeps it from stalling.
        if self._in_window(seq, (self.rcv_base - self.W) % self.MOD):
            self.send_ack(seq)

        if not self._in_window(seq, self.rcv_base):
            return                       # outside both windows — drop

        self.send_ack(seq)               # selective ACK for this exact frame
        if seq not in self.buf:
            self.buf[seq] = payload

        # Slide: deliver every frame starting at rcv_base that we now hold.
        while self.rcv_base in self.buf:
            self.deliver(self.buf.pop(self.rcv_base))
            self.rcv_base = (self.rcv_base + 1) % self.MOD

The subtle line is the first ACK check. If the receiver advanced its window because frames 0–3 arrived, but the ACK for frame 0 was lost, the sender will time out and resend frame 0 — now below the receive window. The receiver must re-ACK it anyway, or the sender stalls forever. This is why Selective Repeat needs MOD ≥ 2W: the window and the just-vacated window must use disjoint sequence numbers so a stale frame can never be mistaken for a fresh one.

Variants worth knowing

Cumulative ACKs (Go-Back-N). One ACK number means "I have everything below this." Robust to lost ACKs — the next ACK covers the gap — but uninformative about which specific frame is missing.

Selective ACKs (TCP SACK, RFC 2018). The receiver reports the exact byte ranges it holds, so the sender retransmits only the holes. This is cumulative-plus-selective: the base ACK still advances, and SACK blocks describe islands above it.

Negative ACKs (NAK). Instead of waiting for a timeout, the receiver immediately signals "I expected frame 5, got frame 7 — send 5." Speeds up recovery on reordering at the cost of extra signalling. TCP's fast retransmit approximates this with three duplicate ACKs.

Adaptive / dynamic windows. TCP doesn't use a fixed W. The advertised receive window handles flow control, while a separate congestion window grows and shrinks with network feedback; TCP sends the minimum of the two. The "window" still slides — it just breathes in size every round trip.

Per-frame timers vs single timer. Go-Back-N runs one timer for the whole window. Selective Repeat logically needs a timer per outstanding frame; production stacks fake this with one timer scanning a sorted list of send times to avoid thousands of OS timers.

Common bugs and edge cases

• Window larger than the sequence space. Go-Back-N needs W ≤ MOD − 1 and Selective Repeat needs W ≤ MOD / 2. Violate it and a stale frame from the old window aliases onto a fresh sequence number — silent data corruption that only shows up under loss.
• Computing in-flight count without the modulo. nextSeq - base goes negative the instant nextSeq wraps. Always use (nextSeq - base + MOD) % MOD.
• Resetting the timer on the wrong frame. Go-Back-N's timer tracks the oldest unacknowledged frame. On a cumulative ACK that advances the base, restart the timer for the new oldest, don't leave it pointing at a frame that's already gone.
• Receiver not re-ACKing below its window. A lost ACK leaves the sender retransmitting a frame the receiver already delivered. If the receiver silently drops it instead of re-ACKing, the sender deadlocks.
• Window stuck closed (silly window syndrome). A receiver that advertises tiny window updates (a few bytes at a time) makes the sender ship tiny frames forever, all header and no payload. Nagle's algorithm and Clark's solution exist precisely to coalesce these.
• Ignoring the BDP. A 65 KB window on a 1 Gbps × 80 ms path caps you at ~6.5 Mbps no matter how fast the link is. The fix is window scaling, not a faster NIC.