Reliable Data Transfer
You want to send a friend a hundred-page document, one page at a time, through a post office that
sometimes loses letters, sometimes smudges them into gibberish, and
occasionally delivers them out of order — and you have no way to know which fate befell any
particular page. How do you guarantee your friend ends up with all hundred pages, correct and in order?
This is the central problem of transport. Underneath TCP sits an
unreliable channel that can
corrupt, drop, or reorder anything. On top, applications demand a channel that never does. The
set of techniques that bridge that gap is called reliable data transfer (rdt), and it
is built from a small, beautiful toolkit — checksums, acknowledgements, sequence numbers, timers and
retransmission — assembled with increasing cleverness until the pipe is both correct and fast.
The five tools of reliability
Every reliable protocol, from a 1970s modem link to modern TCP, is built from the same five ingredients.
Each one answers a specific failure of the channel:
- Checksum — detects corruption. Bits flipped in transit are caught so the
receiver can reject a damaged packet instead of trusting it.
- Acknowledgement (ACK) — the receiver tells the sender "I got it." Without feedback,
the sender is blind. A NAK ("I got something broken") is the explicit negative.
- Sequence number — a label on each packet so the receiver can spot
duplicates and restore order. This is the tool that makes the others safe.
- Timer + retransmission — handles outright loss. If no ACK arrives before
a timeout, the sender assumes the worst and sends again.
- Windowing / pipelining — lets many packets be in flight at once, which is what
turns a correct-but-crawling protocol into a fast one.
A subtle point about NAKs: most modern protocols (TCP included) drop explicit NAKs and instead use a
duplicate ACK. The receiver simply re-acknowledges the last good in-order packet; a
run of identical ACKs is itself the "something's missing" signal. Fewer message types, same
information.
Stop-and-wait, and its dreadful utilisation
The simplest correct protocol is stop-and-wait: send one packet, then stop
and wait for its ACK before sending the next. Lose a packet? The timer fires and you resend. It works —
and it is agonisingly slow, because the link sits idle for an entire round trip on every single packet.
The damage is easy to quantify. Let the link have bandwidth R, a packet be
L bits, and the round-trip time be \text{RTT}.
The sender is busy transmitting for only L/R seconds, then waits about a
whole RTT for the ACK. The fraction of time the link is actually working — the
utilisation — is:
U_{\text{stop-and-wait}} = \frac{L/R}{\text{RTT} + L/R}
Plug in a fast, long link — say 1 Gbps, a 1 KB packet, 30 ms RTT — and you get a utilisation of well
under one percent. You bought a gigabit pipe and are using it like a trickle. The cure is to stop
waiting: keep the pipe full.
Pipelining: keep the pipe full
Pipelining means launching several packets before waiting for the first one's ACK.
Instead of one packet per RTT, you keep a window of N packets in
flight. Utilisation multiplies by roughly N (until you saturate the link),
turning that sub-1% into full throughput. The demo makes the contrast vivid:
// Compare link utilisation: stop-and-wait vs an N-packet pipelined window.
const R = 1_000_000_000; // 1 Gbps link
const L = 8_000; // 8000-bit (1 KB) packet
const RTT = 0.030; // 30 ms round trip
const txTime = L / R; // time to push one packet onto the wire
const cycle = RTT + txTime; // one send-then-wait cycle
const uStopWait = txTime / cycle;
console.log("Transmit time per packet:", (txTime * 1e6).toFixed(2), "microseconds");
console.log("Round-trip time: ", (RTT * 1e3).toFixed(1), "ms");
console.log("\nStop-and-wait utilisation:", (uStopWait * 100).toFixed(4) + "%");
// With a window of N packets we send N per cycle instead of 1 (capped at 100%).
for (const N of [1, 3, 10, 100, 1000]) {
const u = Math.min(1, (N * txTime) / cycle);
const bar = "#".repeat(Math.round(u * 40));
console.log(` window N=${String(N).padStart(4)} U = ${(u * 100).toFixed(2).padStart(6)}% ${bar}`);
}
console.log("\nOnce N*txTime reaches a full cycle, the pipe is full — 100% utilised.");
Pipelining creates a new problem, though: with many packets in flight, some may be lost or reordered
mid-window. How the protocol reacts to a gap defines the two great families of
Automatic Repeat reQuest (ARQ).
Go-Back-N vs Selective Repeat
Both keep a sliding window of unacknowledged packets; they differ entirely in how they recover from
a loss in the middle of that window.
-
Go-Back-N (GBN). The receiver is simple: it accepts packets strictly in
order and discards anything out of order, sending only cumulative ACKs ("I have
everything up through n"). When a packet is lost, everything after it is
thrown away, and on timeout the sender re-sends the whole window from the lost
packet onward. Cheap receiver, wasteful on loss — a single drop forces a flurry of retransmissions.
-
Selective Repeat (SR). The receiver is smart: it buffers
out-of-order packets and ACKs each one individually. When a packet is lost, the
sender retransmits only that one, and the receiver slots it into the gap it was
holding open. More memory and bookkeeping at the receiver, far less wasted bandwidth on loss.
The trade-off is the classic one: GBN spends bandwidth to keep the receiver dumb; SR spends receiver
memory to save bandwidth. Real TCP is a pragmatic hybrid — cumulative ACKs like GBN, but with
selective acknowledgement (SACK) options and fast retransmit that give it much of SR's
efficiency, retransmitting a single lost segment rather than the whole window.
- Go-Back-N: cumulative ACKs, receiver discards out-of-order packets, sender
re-sends from the loss onward. Simple receiver, more retransmission.
- Selective Repeat: individual ACKs, receiver buffers out-of-order packets, sender
resends only the lost one. Complex receiver, minimal retransmission.
Sequence numbers do more than count
It is tempting to think sequence numbers exist merely to put packets back in order. Their subtler and
more important job is to detect duplicates — and duplicates arise even on a channel
that never truly loses anything.
Here is the case that breaks naïve protocols. The sender transmits packet 1. It arrives fine, and the
receiver sends ACK 1 — but that ACK is lost or merely slow. The sender's
timer fires (a premature timeout), so it retransmits packet 1. Now the
receiver has two copies of packet 1. Without sequence numbers it would deliver the same page
to the application twice, silently corrupting the stream.
The sequence number saves the day: the receiver sees the duplicate's number, recognises "I already
have this one," discards the copy, and re-sends the ACK. This is exactly why ACKs
themselves carry the number they acknowledge, and why a run of
duplicate ACKs is meaningful. The lesson: a packet arriving twice is normal,
not exotic — timeouts fire early, ACKs get lost — and a correct protocol must treat "I've seen this
before" as a first-class event, not an error. Reliability is as much about tolerating
duplicates as it is about recovering losses.
You don't need a number per packet forever — you can reuse them, as long as you have enough
that an old straggler can't be mistaken for a fresh packet. For stop-and-wait, astonishingly, a
single bit suffices: alternating 0, 1, 0, 1… (the "alternating-bit protocol"),
because only one packet is ever in flight. For a window of size
N, Go-Back-N needs at least N+1 distinct
numbers, while Selective Repeat needs at least 2N — the SR receiver's
buffer makes it easier to confuse a new packet with an old one, so it needs a bigger number space to
stay unambiguous.