Weekly Paper Notes — the Seminal Paper of the Week for the 2026-10-03 digest. Area: Networking / Systems.
Authors: Van Jacobson (Lawrence Berkeley Laboratory), with Michael J. Karels (UC Berkeley) on the revised version Published: Proceedings of ACM SIGCOMM ‘88, Stanford, August 1988; Computer Communication Review 18(4), pp. 314–329. DOI: 10.1145/52324.52356
Why the paper still matters
In October 1986 the link between Lawrence Berkeley Laboratory and UC Berkeley, about 400 yards apart and three gateway hops, went from 32 kbit/s to 40 bit/s. Nothing was broken. Every host was running a TCP that followed the specification, and the network had settled into a state where nearly all the bandwidth carried retransmissions of packets that would be dropped again. That was the first of a series of Internet congestion collapses.
This paper is the diagnosis and the fix. The fix lives entirely in TCP senders, needed no change to the wire protocol, and no change to any router, and it shipped in 4.3BSD Tahoe. Almost every TCP stack since has descended from it, and it’s why the Internet scaled from tens of thousands of hosts to billions without falling over again in the same way.
It’s worth rereading now for two reasons. The mechanisms are still running in every TCP connection and in QUIC’s default controller, and in datacenter variants they’re being reworked again for AI training fabrics. The way Jacobson argues is also unusual for a systems paper. He starts from a physical principle, asks where real implementations violate it, and fixes each violation separately. The paper is better known for its results than for its reasoning, and the reasoning is the more transferable part.
The setup
TCP in 1986 already had flow control: the receiver advertises a window, and the sender keeps no more than that many bytes unacknowledged. What it lacked was any idea of the network’s capacity. A sender that opened a connection would immediately send a full receiver window into the path. When a gateway queue overflowed and dropped packets, the sender’s retransmit timer, set from a fixed multiple of a smoothed RTT estimate, would fire, and it would resend into the same overloaded queue. Under load, queueing delay pushed RTT up faster than the estimator could follow, so timers fired early and the network filled with duplicate copies of packets that were still in flight. Every host behaved correctly by the spec, and together they produced collapse.
The abstract lists seven algorithms added to 4BSD TCP: RTT variance estimation, exponential retransmit timer backoff, slow start, a more aggressive receiver ACK policy, dynamic window sizing on congestion, Karn’s clamped retransmit backoff, and fast retransmit. The body organises most of them around one principle.
The principle: conservation of packets
Jacobson’s starting point is a physical analogy. A connection running stably with a full window in flight should be conservative: a new packet doesn’t enter the network until an old one leaves. A network where every flow obeys this should be very hard to push into collapse, because you can’t create congestion by replacing one packet with another.
So the question becomes how a real implementation breaks conservation. The paper identifies three ways:
- The connection never reaches equilibrium.
- The sender injects a new packet before an old one has left.
- Equilibrium can’t be reached because of resource limits along the path.
Each failure has its own mechanism, and that’s the structure of the paper.
The three fixes
Figure: The window dynamics the paper introduced. Original diagram for this post; the halve-and-continue sawtooth on the right is the later Reno refinement, and 1988 Tahoe restarts from one packet on every timeout.
Getting to equilibrium: slow start and the ACK clock
The key observation is that ACKs come back spaced at the bottleneck link’s packet rate. A packet that crossed a slow link arrives stretched out in time, and the receiver’s ACKs keep that spacing on the way back. A sender that transmits one packet per ACK is therefore automatically clocked at the bottleneck rate without knowing what that rate is. Jacobson calls this self-clocking. It’s the reason TCP works at all over paths whose capacity no endpoint knows.
Self-clocking only works once packets are in flight, which leaves the problem of starting. The answer is slow start. Add a congestion window, cwnd, start it at one packet, and add one packet to it for every ACK received. Each RTT the window doubles, so it reaches the right size in about log₂(window) round trips, while the ACK clock spaces the transmissions properly from the start. The name was always slightly ironic, since the growth is exponential. What’s slow is the start, compared with dumping a whole receiver window into the network at once.
Conservation at equilibrium: a timer that understands variance
Once the flow is stable, the main way to break conservation is a spurious retransmission, where the sender assumes a packet is lost while it’s still queued. RFC 793 set the timeout to β times a smoothed RTT with β = 2. Jacobson shows from queueing theory that RTT variance grows sharply with load, and that a fixed β = 2 only tolerates about 30% utilisation before timers start firing on packets that are just late.
The fix is to estimate the variation as well as the mean, using mean deviation because it’s cheap with integer arithmetic and tracks the standard deviation closely enough, and to set the timeout from both. The paper’s appendix gives the shift-and-add code. Modern TCP uses RTO = SRTT + 4·RTTVAR (RFC 6298), which comes directly from this work. Combined with Karn’s rule (don’t sample RTT from retransmitted segments) and exponential backoff of the timer on repeated losses, the retransmit timer stops being a source of congestion.
Adapting to the path: AIMD
The third failure is a resource limit: other flows arrive, and the share that used to be available isn’t any more. The sender needs a congestion signal and a response to it.
For the signal, Jacobson argues that packet loss is good enough. Fewer than 1% of packets were lost to corruption on the networks of the day, so a timeout almost always meant a queue had overflowed somewhere. That needed no new protocol fields and no router changes.
For the response he borrows from control theory, and from Jain, Ramakrishnan and Chiu’s DECbit work. When the network is congested, queue length grows exponentially, so the sender has to back off at least as fast: on loss, cut the window multiplicatively (halve it). When there’s no loss, probe for spare capacity slowly: add about one packet per RTT. Increasing quickly would push the network straight back into overload, and the cost of overshooting is far larger than the cost of being slightly under. That’s additive increase, multiplicative decrease, the sawtooth in the diagram. The next year, Chiu and Jain’s analysis showed it’s the linear policy that converges to both efficiency and fairness among competing flows, which explains why it worked.
In Tahoe, a timeout records half the current window as a threshold, ssthresh, resets cwnd to one, and slow-starts up to the threshold before switching to linear growth. Reno (1990) added fast recovery, which halves on three duplicate ACKs and continues without dropping back to one. Both come straight from this paper’s framework.
The other half: gateways
The paper ends on a section about what gateways should do, and it’s candid that endpoint control alone isn’t enough. Hosts can only infer congestion after a queue has overflowed, and a gateway that drops from the tail of a full queue does nothing to keep flows fair. Jacobson sketches gateways that signal congestion earlier and drop fairly. Five years later that became Random Early Detection (Floyd and Jacobson, 1993), and the same line of work leads through ECN to the AQM schemes, such as CoDel, that are deployed today.
Why this design has outlasted everything around it
The central decision is the one most often criticised: treating loss as the congestion signal. It needed nothing from the network, so it could be deployed one host at a time in 1988, and it put congestion control in the end hosts, which is where the end-to-end argument (an earlier seminal pick) says that kind of function belongs. It’s also where the design has strained. Wireless links lose packets without congestion and get treated as overloaded. Deep buffers let loss arrive late, after queues have built seconds of delay (bufferbloat). Very high bandwidth-delay paths take a long time to grow back linearly after a halving. Each of these produced a successor: CUBIC replaced linear growth with a cubic function of time since the last loss and is the Linux default, DCTCP uses ECN marks in datacenters, and BBR drops loss as the primary signal and models bottleneck bandwidth and RTT directly.
What none of them dropped is the structure: ACK clocking, slow start to find the operating point, a variance-aware timer, and multiplicative backoff when the network says stop. The same arguments are still running in places the 1988 paper never anticipated. This week’s digest includes an analysis of meta-stability in exponential backoff (arXiv:2609.37073), the same backoff discipline studied as implicit admission control. And the incast problems in MoE all-to-all traffic, covered in an earlier note on MoE rate scheduling, are congestion collapse in a different setting: many synchronised senders, one bottleneck, no ACK clock to slow them down.
Jacobson’s method is still the useful part. He named a conservation law, asked where implementations violate it, and fixed each violation with the smallest mechanism that would deploy. The result has kept a shared, uncoordinated, global network working for close to forty years.
Read alongside
- Nagle, “Congestion Control in IP/TCP Internetworks” (RFC 896, 1984): the earlier description of congestion collapse, before it happened at scale.
- Jain, Ramakrishnan, Chiu, “Congestion Avoidance in Computer Networks with a Connectionless Network Layer” (DEC-TR-506, 1988): the DECbit scheme and the source of the additive-increase / multiplicative-decrease policy.
- Chiu and Jain, “Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks” (1989): the proof that AIMD converges to fairness.
- Karn and Partridge, “Improving Round-Trip Time Estimates in Reliable Transport Protocols” (SIGCOMM ‘87): the retransmission ambiguity rule the paper adopts.
- Floyd and Jacobson, “Random Early Detection Gateways for Congestion Avoidance” (1993): the gateway half the paper calls for.
- Cardwell et al., “BBR: Congestion-Based Congestion Control” (ACM Queue, 2016): the clearest modern departure from loss-based control, and a good test of which parts of 1988 survived.
Links
📄 ACM Digital Library (SIGCOMM ‘88) · 📄 Revised version with Karels (LBL, 1988) · 📄 RFC 6298: Computing TCP’s Retransmission Timer
Part of the Weekly CS Paper Digest series. Seminal picks are written from background knowledge and a reread of the original; diagram is original work.