Selective Repeat ARQ

The intuition: don't punish the survivors

Imagine mailing 64 numbered pages of a manuscript. One page — say number 17 — gets lost in transit. You have two ways to recover. The crude way: tell the recipient to throw away everything from page 17 onward and you re-send pages 17 through 64. The surgical way: the recipient quietly files pages 18 through 64 in a drawer, tells you "I'm only missing 17," and you re-send a single page. Selective Repeat is the surgical way.

Automatic Repeat reQuest (ARQ) is the family of protocols that turn an unreliable, packet-dropping channel into a reliable byte stream using only three tools: sequence numbers, acknowledgements, and timeouts. The three classic members are Stop-and-Wait (window of 1), Go-Back-N (a sender window but a receiver that refuses anything out of order), and Selective Repeat — the most efficient and the most complex of the three. Selective Repeat earns its complexity by being the only one of the three that never wastes the network's time re-sending data that already arrived safely.

The key design decision is that the receiver gets a window too. In Go-Back-N the receiver window is exactly 1: it accepts only the next in-order packet and drops everything else. In Selective Repeat both sides keep a window of size W, and the receiver is allowed to accept, buffer, and acknowledge any packet whose sequence number lands inside its window — even far ahead of the next byte it owes the application.

How the two windows move

Both sender and receiver maintain a base pointer and a window of W sequence numbers. Sequence numbers come from a finite space of 2m values (an m-bit field) and wrap around modulo 2m.

The sender keeps a buffer slot, a per-packet "acked?" flag, and a per-packet timer for every sequence number in [sendBase, sendBase + W). It transmits as many unsent packets as the window allows. When an individual ACK for sequence n arrives, it marks n acked and stops n's timer. If n == sendBase, the window slides forward past every consecutively-acked packet, freeing slots so new packets can launch. If any timer fires, only that one packet is re-sent and its timer restarts.

The receiver keeps recvBase and a buffer for [recvBase, recvBase + W). For an arriving packet with sequence n:

• If n is inside the receive window: buffer it, mark it received, and send an individual ACK for n. If n == recvBase, deliver the now-contiguous run of buffered packets to the application and slide the window forward.
• If n is in the window just below the receive window — i.e. [recvBase − W, recvBase) — it is a duplicate of something already delivered. The receiver re-sends its ACK (the original ACK was lost, which is why the sender retried) but does not re-deliver.
• Otherwise the packet is ignored.

That second bullet is the subtle heart of the protocol, and it's why the window bound exists.

The window-size bound: W ≤ 2^m−1

This is the single most-tested fact about Selective Repeat, and the place every textbook problem set tries to trip you up. The window may be no larger than half the sequence-number space. With m bits you have 2m sequence numbers, so the maximum window is W = 2m−1.

Here's the failure it prevents. Suppose m = 2 (sequence numbers 0,1,2,3) and someone foolishly sets W = 3. The sender ships packets 0,1,2. All three arrive; the receiver delivers them and slides its window to [3,0,1]. But all three ACKs are lost. The sender times out and re-sends packet 0. The receiver sees sequence 0 — which is now inside its new window — and cannot tell whether this is the old packet 0 (a duplicate it should discard) or a fresh packet 0 from the next round (real data it must accept). It guesses wrong, and the stream silently corrupts.

With W = 2m−1 the old window and the worst-case new window never overlap modulo 2m, so a retransmitted old sequence number always lands in the "just below" duplicate band and is correctly rejected. Note the contrast: Go-Back-N only needs W ≤ 2m − 1, because its receiver window of 1 leaves no ambiguity. Selective Repeat pays for its bigger receive buffer with a tighter sequence-number budget.

When to choose Selective Repeat

• Long fat networks (high bandwidth-delay product). A satellite or transcontinental link with a 600 ms round trip and gigabit capacity has thousands of packets in flight. Re-sending the whole window on every loss (Go-Back-N) is catastrophic; Selective Repeat is mandatory.
• Lossy links with non-trivial loss rate. Wi-Fi, cellular, and lossy mesh links drop packets often enough that the difference between "resend 1" and "resend W" dominates goodput.
• Anywhere you already pay for a receive buffer. If the receiver buffers for reordering anyway (and almost every transport does), the marginal cost of Selective Repeat is small.

Reach for Go-Back-N only when the receiver is genuinely memory-starved (a tiny embedded sensor), or when the link is so clean and short that losses are rare and the wasted retransmissions never matter. Stop-and-Wait is for when you can afford only one outstanding packet at a time — the original 1970s modem world.

Selective Repeat vs the other ARQ schemes

	Stop-and-Wait	Go-Back-N	Selective Repeat
Sender window	1	W	W
Receiver window	1	1	W
Out-of-order packets	n/a	discarded	buffered
ACK style	per packet	cumulative	individual
Retransmits per loss	1	up to W	≈ 1
Sequence-number bound	≥ 1 bit (0/1)	W ≤ 2m−1	W ≤ 2m−1
Receiver buffer	none	none	O(W) packets
Timers	1	1 (oldest)	1 per packet
Best for	tiny / legacy links	clean, short links	lossy or high-BDP links

The headline trade-off: Go-Back-N moves all complexity to the sender and keeps the receiver dumb (one timer, no buffer, cumulative ACKs), at the cost of bandwidth on every loss. Selective Repeat splits the bookkeeping across both ends — buffer, per-packet flags, individual ACKs, per-packet timers — to buy near-perfect bandwidth efficiency.

What the numbers actually say

• Retransmissions per loss: ~W for Go-Back-N, ~1 for Selective Repeat. With a window of 64 packets, a single drop costs Go-Back-N up to 64 retransmissions; Selective Repeat costs 1. At 1% loss that is roughly a 64× difference in wasted transmissions on loss events.
• Window to fill the pipe = bandwidth × RTT ÷ packet size. A 1 Gbps link with 600 ms RTT and 1500-byte packets needs about (10⁹ × 0.6 / 8 / 1500) ≈ 50,000 packets in flight. Go-Back-N at that window is unusable; this BDP regime is what made Selective Repeat (via TCP SACK) the default.
• Sequence-number budget. The W ≤ 2^m−1 rule means a 50,000-packet window needs at least a 17-bit sequence field (2¹⁶ = 65,536 ≥ 2·50,000 is not quite enough → 2¹⁷). TCP sidesteps this entirely by counting bytes in a 32-bit field.
• Receiver memory: O(W) packets. A 64-packet window of 1500-byte packets is about 96 KB of buffer — trivial on a server, possibly real on a microcontroller.

JavaScript implementation

A self-contained simulation of both endpoints over a lossy channel. The sender keeps per-packet acked flags and timers; the receiver buffers out-of-order packets and only delivers contiguous runs.

const M = 4;                 // sequence-number bits
const SEQ = 1 << M;           // 16 sequence numbers
const W = SEQ >> 1;           // window = 8  (the W ≤ 2^(m-1) bound)
const TIMEOUT = 3;           // ticks before a packet retransmits

class Sender {
  constructor(data, channel) {
    this.data = data;                 // array of payloads to send
    this.channel = channel;
    this.base = 0;                    // oldest unacked seq
    this.next = 0;                    // next seq to send
    this.acked = new Array(data.length).fill(false);
    this.timer = new Array(data.length).fill(-1); // tick when sent, -1 = idle
  }

  tick(now) {
    // Launch new packets while the window has room and data remains
    while (this.next < this.data.length && this.next < this.base + W) {
      this.send(this.next, now);
      this.next++;
    }
    // Retransmit only the packets whose timers expired — one each
    for (let i = this.base; i < this.next; i++) {
      if (!this.acked[i] && this.timer[i] >= 0 && now - this.timer[i] >= TIMEOUT) {
        this.send(i, now);            // resend just this packet
      }
    }
  }

  send(i, now) {
    this.timer[i] = now;
    this.channel.toReceiver({ seq: i % SEQ, idx: i, payload: this.data[i] });
  }

  onAck(seq) {
    // Map the m-bit seq back to the absolute index inside the window
    for (let i = this.base; i < this.next; i++) {
      if (i % SEQ === seq && !this.acked[i]) {
        this.acked[i] = true;
        this.timer[i] = -1;
        break;
      }
    }
    while (this.acked[this.base]) this.base++; // slide past acked prefix
  }

  done() { return this.base >= this.data.length; }
}

class Receiver {
  constructor(channel) {
    this.channel = channel;
    this.base = 0;                    // next index owed to the app
    this.buf = new Map();             // idx -> payload (out-of-order store)
    this.delivered = [];
  }

  onPacket(pkt) {
    const i = pkt.idx;
    if (i >= this.base && i < this.base + W) {       // inside receive window
      this.buf.set(i, pkt.payload);
      this.channel.toSender(pkt.seq);              // individual ACK
      while (this.buf.has(this.base)) {            // deliver contiguous run
        this.delivered.push(this.buf.get(this.base));
        this.buf.delete(this.base);
        this.base++;
      }
    } else if (i >= this.base - W && i < this.base) { // already delivered
      this.channel.toSender(pkt.seq);              // re-ACK, do NOT re-deliver
    } // else: outside both windows → ignore
  }
}

Two details mirror the textbook protocol exactly. First, onAck walks the window to map a wrapped m-bit sequence number back to an absolute index — the sequence space is finite, indices are not. Second, the receiver's already-delivered branch re-acknowledges without re-delivering, because a lost ACK (not a lost data packet) is the reason the sender retried.

Python implementation

The same logic with a tiny lossy channel and an event loop, so you can watch the window slide.

import random
from collections import deque

M, SEQ = 4, 1 << 4            # 4 bits, 16 sequence numbers
W = SEQ // 2                  # window = 8  (W ≤ 2**(m-1))
TIMEOUT = 3

class Sender:
    def __init__(self, data):
        self.data = data
        self.base = self.nxt = 0
        self.acked = [False] * len(data)
        self.timer = [-1] * len(data)

    def tick(self, now, link):
        while self.nxt < len(self.data) and self.nxt < self.base + W:
            self._send(self.nxt, now, link); self.nxt += 1
        for i in range(self.base, self.nxt):          # per-packet timers
            if not self.acked[i] and self.timer[i] >= 0 \
               and now - self.timer[i] >= TIMEOUT:
                self._send(i, now, link)              # resend only packet i

    def _send(self, i, now, link):
        self.timer[i] = now
        link.append(('data', i % SEQ, i, self.data[i]))

    def on_ack(self, seq):
        for i in range(self.base, self.nxt):
            if i % SEQ == seq and not self.acked[i]:
                self.acked[i] = True; self.timer[i] = -1; break
        while self.base < len(self.acked) and self.acked[self.base]:
            self.base += 1                            # slide window

    def done(self): return self.base >= len(self.data)

class Receiver:
    def __init__(self):
        self.base = 0
        self.buf = {}                                 # idx -> payload
        self.out = []

    def on_packet(self, idx, seq, payload, back):
        if self.base <= idx < self.base + W:           # in window
            self.buf[idx] = payload
            back.append(('ack', seq))
            while self.base in self.buf:               # deliver contiguous run
                self.out.append(self.buf.pop(self.base)); self.base += 1
        elif self.base - W <= idx < self.base:         # duplicate
            back.append(('ack', seq))                  # re-ACK only

def simulate(payloads, loss=0.2, seed=1):
    random.seed(seed)
    s, r = Sender(payloads), Receiver()
    to_r, to_s, now = deque(), deque(), 0
    while not s.done() and now < 1000:
        s.tick(now, to_r)
        for _, seq, idx, p in list(to_r):             # forward over lossy link
            if random.random() >= loss: r.on_packet(idx, seq, p, to_s)
        to_r.clear()
        for _, seq in list(to_s):
            if random.random() >= loss: s.on_ack(seq)
        to_s.clear()
        now += 1
    return r.out

print(simulate(list(range(20))) == list(range(20)))   # True — stream intact

Run it with loss=0.2 and the receiver still reconstructs the exact stream, while a Go-Back-N version of the same loop would re-transmit floods of already-delivered packets to get there.

Variants worth knowing

TCP Selective Acknowledgement (SACK, RFC 2018, 1996). Classic TCP uses cumulative ACKs, so it is Go-Back-N-flavoured. SACK adds an option carrying up to three or four byte ranges the receiver already holds. The sender then retransmits only the holes — pure Selective Repeat behaviour grafted onto a cumulative-ACK protocol. Negotiated by default in essentially every modern stack.

QUIC's explicit gap encoding. QUIC (RFC 9000) makes Selective Repeat native: every packet has a monotonically increasing packet number that is never reused on retransmission, and ACK frames carry ranges of received packet numbers. This removes the retransmission ambiguity that forces the W ≤ 2^m−1 rule, because a retransmitted chunk rides a brand-new packet number.

Negative ACKs (NAK / SNACK). Some link-layer and multicast protocols (e.g. parts of the Space Data Link protocols and NORM) have the receiver explicitly request the missing sequence numbers instead of individually ACKing everything received — better when losses are rare and ACK traffic would otherwise dominate.

SR with delayed/coalesced ACKs. To cut ACK overhead, real implementations batch acknowledgements (one ACK per few packets or per timer tick). This keeps the Selective-Repeat semantics but reduces the reverse-channel load — at the price of slightly slower loss detection.

Common bugs and edge cases

• Setting the window larger than 2^m−1. The classic exam trap and a real corruption bug: with an oversized window the receiver cannot distinguish a retransmitted old packet from a fresh one. Always enforce W ≤ 2m−1.
• Forgetting the "below the window" re-ACK. If the receiver ignores duplicates of already-delivered packets instead of re-acknowledging them, a single lost ACK wedges the sender forever — it keeps retransmitting a packet the receiver silently drops.
• Sliding the sender window on a non-base ACK. The window advances only past a contiguous acked prefix starting at base. Acking packet base+5 while base itself is still missing must not move the window.
• One shared timer instead of per-packet timers. Copying Go-Back-N's single timer means a timeout retransmits the wrong packet (or the whole window), defeating the entire point. Each in-flight packet times out independently.
• Sequence-number wrap arithmetic. Comparisons like "is n inside the window?" must be done modulo 2m, not with naive </>, or the window check breaks exactly at the wrap boundary.
• Unbounded receive buffer. A misbehaving or malicious sender that floods sequence numbers far ahead can balloon the receive buffer if the in-window check is missing — always reject packets outside [recvBase, recvBase + W).