Reliable delivery protocols
This is an optional deep dive. The transport layer has the short version. Here the mechanism is rebuilt from nothing, because every rule TCP follows is the fix for a specific failure.
The goal is a reliable channel on top of an unreliable one: no bits corrupted, nothing lost, everything in order. IP gives none of that.
One failure at a time
Section titled “One failure at a time”Start with a protocol for a perfect channel and break the channel one way at a time.
| Channel problem | What breaks | Fix added |
|---|---|---|
| None | Nothing. The sender sends, the receiver delivers | Nothing needed |
| Bit errors | Receiver gets damaged data | A checksum to detect it. ACK for good packets, NAK for bad ones. The sender retransmits on NAK (this family is called ARQ, automatic repeat request) |
| Damaged ACK or NAK | The sender cannot tell whether the data arrived. Resending may deliver a duplicate | A sequence number on each packet. The receiver drops duplicates and ACKs them again |
| No NAKs allowed | NAKs are an extra message type | The ACK carries the sequence number it confirms. A duplicate ACK for the old number means “the next packet was bad” |
| Packet loss | Nothing arrives, so no ACK or NAK ever returns | A timer. If no ACK comes in time, retransmit |
With a stop-and-wait design, one bit is enough for the sequence number, because only one packet is ever outstanding. It simply alternates 0, 1, 0, 1. That is why this final version is called the alternating-bit protocol.
Three details matter in practice:
- A timeout that is too short causes a retransmission while the original is still in flight. The receiver sees a duplicate and uses the sequence number to discard it. Correctness survives a bad timer. Only efficiency suffers.
- The sender ignores a damaged or unexpected ACK and lets the timer expire.
- Duplicate ACKs, introduced to remove NAKs, are what TCP uses later for fast retransmit.
Why stop-and-wait fails
Section titled “Why stop-and-wait fails”The sender transmits one packet and idles until the ACK returns. Utilization is the fraction of time the sender is actually sending:
U = (L / R) / (RTT + L / R)
L = packet size in bits, R = link rate in bit/sTake a 1 Gbit/s path with a 30 ms RTT and 1,000-byte packets:
- Transmit time
L / R= 8,000 bits / 1,000,000,000 bit/s = 0.008 ms U= 0.008 / (30 + 0.008) = 0.000267, or 0.027%- Effective throughput: about 267 kbit/s on a 1 Gbit/s link
To keep the link busy, the sender needs about RTT / (L / R) = 30 / 0.008 = 3,750 packets in flight. That number is the bandwidth-delay product expressed in packets. The cure is pipelining: send many packets before the first ACK returns.
Pipelining changes three requirements:
- Sequence numbers must be unique for every packet in flight, not just 0 and 1.
- The sender must buffer packets that are sent but not yet acknowledged.
- The receiver may need to buffer packets that arrive out of order.
Two designs solve this differently.
Go-Back-N
Section titled “Go-Back-N”Go-Back-N (GBN) allows at most N unacknowledged packets. The permitted sequence numbers form a window that slides forward as ACKs arrive.
acknowledged sent, waiting usable now not usable yet [0 ... base-1] [base ... next-1] [next ... base+N-1] [base+N ...]- The sender tracks
base(oldest unacknowledged) andnextseqnum(next to send). - ACKs are cumulative.
ACK nmeans everything up to and includingnarrived. - There is one timer, for the oldest unacknowledged packet.
- On a timeout the sender goes back and resends every unacknowledged packet in the window.
- The receiver accepts only the next expected packet. It discards anything out of order and repeats the last good ACK. It needs no buffer.
Trace with N = 4, packets 0 to 5, and packet 2 lost:
| Event | Sender | Receiver |
|---|---|---|
| Send 0, 1, 2, 3 | Window is full | 0 and 1 arrive, ACK 0 and ACK 1. 2 is lost |
| 3 arrives | Expected 2, so discard 3 and send ACK 1 again | |
| ACK 0 and ACK 1 arrive | base moves to 2, send 4 and 5 | 4 and 5 arrive, both discarded, ACK 1 sent twice more |
| Timer for packet 2 expires | Resend 2, 3, 4, 5 | Accept all four, ACK 2 to 5 |
Packets 3, 4, and 5 arrived intact the first time and were thrown away. With a large window on a lossy path, one drop wastes a whole window of transmissions. GBN is simple, but loss makes it expensive.
Selective Repeat
Section titled “Selective Repeat”Selective Repeat (SR) retransmits only what was lost.
- The receiver ACKs every correct packet individually, in order or not.
- The sender keeps a timer per packet and resends only the one that timed out.
- The receiver buffers out-of-order packets. When the gap fills, it delivers the run of consecutive packets to the application in one batch.
- The receiver must also re-ACK packets below its window. If an ACK was lost, the sender will resend that packet. Without a fresh ACK, the sender’s window never advances.
Same scenario, packet 2 lost: the receiver buffers 3, 4, and 5 and ACKs each. The timer for 2 expires, the sender resends only 2, and the receiver delivers 2, 3, 4, and 5 together. One retransmission instead of four.
| Go-Back-N | Selective Repeat | |
|---|---|---|
| ACKs | Cumulative | Individual |
| Timers | One | One per packet |
| On timeout | Resend whole window | Resend one packet |
| Receiver buffering | None | Required |
| Cost | Wasted bandwidth on loss | State and complexity |
The sender and receiver windows do not always line up. Delayed or lost ACKs mean the sender’s window can lag the receiver’s. This is the source of the next problem.
Window size vs sequence space
Section titled “Window size vs sequence space”Sequence numbers live in a fixed-width field, so they wrap. The window must be small enough that the receiver can tell a new packet from an old retransmission.
Suppose Selective Repeat uses 4 sequence numbers (0 to 3) with a window of 3:
- The sender sends 0, 1, 2. The receiver gets all three, ACKs them, and its window moves to expect 3, 0, 1.
- All three ACKs are lost.
- The sender times out and resends 0.
- The receiver sees 0, which is inside its new window, and accepts it as new data. It has delivered a duplicate as if it were fresh.
The rule that prevents this is:
Selective Repeat: N <= 2^(k-1) (window at most half the sequence space)Go-Back-N: N <= 2^k - 1There is a second constraint outside the protocol. On a real network, old copies of a packet can wander for a while and then show up late. A sequence number must not be reused until old copies are certain to be gone. TCP assumes a maximum segment lifetime of about two minutes, which is the reason for the TIME_WAIT state after a connection closes.
How TCP combines them
Section titled “How TCP combines them”TCP is neither pure GBN nor pure SR.
| TCP behavior | Resembles |
|---|---|
| Cumulative ACKs: the ACK number is the next byte expected | Go-Back-N |
| Receiver buffers out-of-order segments | Selective Repeat |
| One retransmission timer, for the oldest unacknowledged segment | Go-Back-N |
| On timeout, resend only the oldest segment, not the whole window | Selective Repeat |
| Three duplicate ACKs trigger a retransmit before the timer expires | The duplicate ACK trick from the NAK-free design |
| The SACK option reports exactly which ranges arrived | Selective Repeat |
TCP numbers bytes, not packets, in a 32-bit field. On a fast path the sequence space can wrap while old segments are still alive, so the timestamps option (PAWS, protection against wrapped sequence numbers) lets the receiver reject stale segments. Window scaling raises the window beyond 64 KB, which fast long paths need.
# Are the features that make TCP efficient on fast paths enabled?sysctl net.ipv4.tcp_sack net.ipv4.tcp_window_scaling net.ipv4.tcp_timestamps# net.ipv4.tcp_sack = 1# net.ipv4.tcp_window_scaling = 1# net.ipv4.tcp_timestamps = 1
# See SACK and window scale on a live connectionss -ti dst 198.51.100.20# cubic wscale:7,7 rto:204 rtt:23.5/4.2 mss:1448 cwnd:10 ... sackIn Wireshark, tcp.options.sack shows SACK blocks and tcp.analysis.retransmission shows resends. If SACK is disabled by a middlebox, a single loss in a large window falls back to slow, GBN-like recovery, and throughput on lossy links drops sharply.