vault

Congestion Control Fundamentals and AIMD

20 min read

Congestion Control Fundamentals and AIMD

A Transmission Control Protocol (TCP) sender may not simply blast data at line rate: two independent limits bound how much unacknowledged data it keeps “in flight.” The first is the advertised (receive) window the receiver announces to protect its own buffer — that is flow control, and it is the subject of TCP Flow Control and the Sliding Window. The second is the congestion window (cwnd), a limit the sender imposes on itself to protect the network from overload; managing it is congestion control. A sender may transmit no more than min(cwnd, rwnd) bytes of unacknowledged data (RFC 5681 §2). The canonical algorithm for moving cwnd — grow it gently while packets get through, cut it sharply the instant one is lost — is Additive-Increase / Multiplicative-Decrease (AIMD), and the reason AIMD (rather than any other increase/decrease pairing) is the right choice is a small, beautiful piece of control theory due to Chiu and Jain (Chiu & Jain 1989). This note is the protocol/algorithm view — the RFC-level mechanism and the theory behind it. The Linux kernel implementation of these same ideas — the pluggable tcp_congestion_ops framework, the code paths, the sysctls — lives in the sibling note TCP Congestion Control; this note owns the specification, that one owns the machinery.

Why Congestion Control Exists — the Collapse of 1986

The Internet learned about congestion the hard way. In October 1986 the throughput between Lawrence Berkeley Laboratory and UC Berkeley — two sites 400 yards apart connected by a path with a nominal capacity of 32 kbit/s — collapsed to 40 bit/s, a factor of a thousand (Jacobson 1988, “Congestion Avoidance and Control”). The cause was a positive feedback loop: when a router’s queue overflows, packets are dropped; TCP interprets the missing acknowledgement (ACK) as a signal to retransmit; the retransmissions add yet more load to the already-saturated router, causing more drops, causing more retransmissions. The network spends all its capacity carrying copies of packets that will be dropped again — a state called congestion collapse. Van Jacobson’s response, implemented in the 4.3BSD “Tahoe” release, was a set of algorithms — slow start, congestion avoidance, and a better retransmission timer — that make a TCP sender probe for the available capacity and back off the moment it sees loss. Those algorithms, refined over three decades of RFCs, are what every TCP still runs today.

The key reframing Jacobson introduced is the conservation of packets principle: a connection “in equilibrium” should be self-clocking — it injects a new packet into the network only when an ACK signals that an old packet has left the network (Jacobson 1988). The stream of returning ACKs is, in effect, a clock that paces the sender at exactly the bottleneck’s drain rate. Congestion control is the discipline of setting the size of that in-flight window correctly, and of starting the clock when a connection has no ACKs yet to pace it.

Mental Model — Two Windows, One Sawtooth

The single most important distinction to internalise is that a sender is throttled by the minimum of two windows that mean completely different things:

  • rwnd (receive window) — set by the receiver, advertised in every TCP segment’s window field. It says “I have this much free buffer space; do not overrun me.” This is flow control, a receiver-vs-sender concern. See TCP Flow Control and the Sliding Window.
  • cwnd (congestion window) — set by the sender, never transmitted on the wire, invisible to the peer. It says “I believe the network can absorb this much; I will not exceed it.” This is congestion control, a sender-vs-network concern.

The sender’s ceiling on unacknowledged data is min(cwnd, rwnd). A connection can therefore be limited by either — and diagnosing which is the first question in any throughput investigation.

cwnd itself moves through two growth regimes separated by a threshold called ssthresh (the slow-start threshold), and it collapses on loss. Plotting cwnd over time produces the signature AIMD sawtooth: an exponential ramp, a linear climb, a sharp cut, repeat.

flowchart TB
  START["Connection opens<br/>cwnd = IW (~10 segments)<br/>ssthresh = very large"] --> SS
  SS["SLOW START<br/>cwnd &lt; ssthresh<br/>+1 segment per ACK<br/>= doubles per RTT (exponential)"]
  SS -->|"cwnd reaches ssthresh"| CA["CONGESTION AVOIDANCE<br/>cwnd &gt;= ssthresh<br/>+1 segment per RTT<br/>(additive increase, linear)"]
  SS -->|"3 dup-ACKs"| FR
  CA -->|"3 dup-ACKs<br/>(fast retransmit)"| FR["FAST RECOVERY<br/>ssthresh = FlightSize/2<br/>cwnd = ssthresh + 3 (mild cut)"]
  FR -->|"recovery ACK"| CA
  CA -->|"RTO timeout<br/>(no ACKs at all)"| RTO["TIMEOUT<br/>ssthresh = FlightSize/2<br/>cwnd = 1 segment<br/>(restart slow start)"]
  RTO --> SS

The AIMD state machine of a TCP sender. What it shows: a fresh connection starts in slow start with an initial window of about ten segments and effectively-infinite ssthresh, so it doubles its window every round-trip time (RTT) until it hits ssthresh; it then switches to the cautious additive-increase climb of congestion avoidance; a mild loss (three duplicate ACKs) triggers a multiplicative decrease into fast recovery, halving ssthresh and continuing; a severe loss (a retransmission timeout, meaning the ACK clock has stopped entirely) collapses cwnd to a single segment and restarts slow start. The insight to take: the two motions that give the sawtooth its shape — the additive +1/RTT climb and the multiplicative ÷2 cut — are exactly the AIMD pairing that Chiu and Jain proved converges to fair, efficient sharing. Everything else (when a loss is declared, how recovery is timed) is bookkeeping around those two motions.

Slow Start — The Exponential Ramp

When a connection opens, the sender has no idea how much capacity the path offers, and it has no ACK clock yet. Blasting a full receiver-window of data immediately is what caused the 1986 collapse. Slow start instead begins with a small Initial Window (IW) and lets it grow exponentially until the first sign of trouble (RFC 5681 §3.1).

The initial window is sized by the sender’s maximum segment size (SMSS — the largest payload the sender will put in one segment, excluding TCP/IP headers): IW = 4×SMSS if SMSS ≤ 1095 bytes, 3×SMSS if 1095 < SMSS ≤ 2190, and 2×SMSS above that (RFC 5681 §3.1). Modern stacks use the larger IW10 of RFC 6928 (ten segments), so a typical web response of a few tens of kilobytes can complete in one or two round trips.

Slow start runs whenever cwnd < ssthresh. On every ACK that acknowledges new data the sender increases the window by

cwnd += min(N, SMSS)

where N is the number of previously-unacknowledged bytes the ACK covers (RFC 5681 §3.1). The classic form was simply cwnd += SMSS per ACK; the min(N, SMSS) cap is Appropriate Byte Counting, which defends against an “ACK division” attack where a malicious receiver sends many tiny ACKs to inflate the window faster than data was actually delivered. Because a full window’s worth of ACKs returns each RTT, cwnd roughly doubles every RTT — the growth is exponential, not linear. The name “slow start” is one of networking’s great misnomers: it is slow only relative to the pre-1988 behaviour of sending a whole window at once. The genuinely slow phase is the next one.

Congestion Avoidance — Additive Increase

Once cwnd reaches ssthresh, the sender believes it is near the network’s capacity and switches to congestion avoidance, whose increase is linear: roughly one extra segment per RTT regardless of how large the window already is (RFC 5681 §3.1). The RFC’s recommended per-ACK formula is

cwnd += SMSS * SMSS / cwnd

Walking this symbol by symbol: each ACK adds a fraction of a segment, and that fraction is SMSS/cwnd of a full segment (the SMSS×SMSS/cwnd byte increment divided by SMSS bytes-per-segment). Since one RTT delivers about cwnd/SMSS ACKs, summing the fractional increments over a full RTT yields exactly +1 SMSS. The RFC is emphatic that a sender MUST NOT increment cwnd by more than one SMSS per RTT — this bound is the “additive increase” of AIMD. The constant additive step, independent of the current window size, is what makes congestion avoidance a cautious probe: the closer to capacity you are, the more the fixed +1 step is a smaller and smaller relative nudge.

Multiplicative Decrease — The Cut on Loss

The other half of AIMD is the response to a congestion signal. In classic loss-based TCP the signal is a dropped packet, inferred either from duplicate ACKs or from a retransmission timeout (RTO). On loss the sender sets

ssthresh = max(FlightSize / 2, 2*SMSS)

where FlightSize is the amount of data sent but not yet cumulatively acknowledged (RFC 5681 §3.1). The window is roughly halved — that factor of ½ is the “multiplicative decrease.” A duplicate-ACK-detected loss triggers a mild cut via fast recovery (below); an RTO — which means no ACKs are arriving and the self-clock has died — is treated as a far worse signal, collapsing cwnd all the way to the Loss Window of one full-sized segment and restarting slow start toward the new (halved) ssthresh.

Why AIMD? — The Chiu–Jain Convergence Argument

The deep question is: why halve on loss and add one on success, rather than any other combination? The answer is a 1989 result by Dah-Ming Chiu and Raj Jain that analyses increase/decrease control laws as a dynamical system and shows AIMD is the unique linear rule that drives a distributed set of senders toward both full efficiency and fairness (Chiu & Jain 1989; course slides).

Model the system as n users sharing one bottleneck. User i sends at rate x_i(t). After each round the network returns one bit of binary feedback y(t): 0 means “underloaded, increase,” 1 means “overloaded, decrease” — this is exactly what a packet drop is, a one-bit “you have overshot” signal (slide “Feedback”). Each user adjusts with a linear control law:

x_i(t+1) = a_I + b_I * x_i(t)     when feedback says increase
x_i(t+1) = a_D + b_D * x_i(t)     when feedback says decrease

The four constants define the family of possible controls: a_I, a_D are the additive components, b_I, b_D the multiplicative components. The four classic schemes are the corners of this space — Additive-Increase/Additive-Decrease, Additive-Increase/Multiplicative-Decrease, Multiplicative-Increase/Additive-Decrease, and Multiplicative-Increase/Multiplicative-Decrease.

Chiu and Jain visualise the two-user case (n = 2) as a point moving in a plane whose axes are x_1 and x_2:

  • The efficiency line is x_1 + x_2 = X_goal (the total the bottleneck can carry). Points below it waste capacity; points above it are overloaded.
  • The fairness line is x_1 = x_2 (equal shares), the 45° diagonal. The ideal operating point is the intersection of the two lines — full utilisation, split evenly.
  • Fairness is measured by the Jain fairness index, F(x) = (Σx_i)² / (n · Σx_i²), which is 1 when all shares are equal and drops toward 1/n as they diverge (slide “Criteria”).

Now watch how each motion moves the point:

  • Additive change (x_i += a) shifts the point along a 45° line — both users’ rates change by the same absolute amount. A 45° move toward the efficiency line does not change the ratio x_1:x_2 in absolute terms but does move the point closer to the fairness diagonal (adding a constant to both makes them relatively more equal). Crucially, additive increase nudges the system toward fairness.
  • Multiplicative change (x_i *= b) moves the point along a ray through the origin — it scales both rates by the same factor, so it preserves the ratio x_1:x_2 exactly, i.e. it moves along a line of constant fairness. Multiplicative decrease pulls the overloaded system back below the efficiency line without making it any less fair.
flowchart LR
  subgraph AI["Additive Increase"]
    A1["overshoot? no<br/>x_i += a_I<br/>move along 45 deg line<br/>-> toward fairness diagonal"]
  end
  subgraph MD["Multiplicative Decrease"]
    M1["overshoot? yes<br/>x_i *= b_D (b_D &lt; 1)<br/>move along ray to origin<br/>-> preserves fairness ratio"]
  end
  AI -->|"repeatedly alternating"| OPT["converges to<br/>efficiency AND fairness<br/>(the sawtooth homes in on x1=x2)"]
  MD --> OPT

The geometric heart of the Chiu–Jain argument. What it shows: additive increase steps the operating point up a 45° line, which nudges two unequal flows toward the equal-share diagonal; multiplicative decrease steps it down a ray through the origin, which preserves the current fairness ratio while shedding load. The insight to take: because only additive increase improves fairness and only multiplicative decrease avoids destroying it, the alternation of the two — AIMD — is the sole combination whose sawtooth spirals inward onto the fair, efficient operating point. Additive-decrease or multiplicative-increase schemes fail to converge to fairness; multiplicative-increase also over-reacts and oscillates.

The formal result: for the control to be efficient and distributed (each user reacting only to the shared one-bit signal, knowing nothing about the others), Chiu and Jain derive a_I > 0, b_I ≥ 1, a_D = 0, 0 ≤ b_D < 1 (slide “Constraints: Efficiency + Distributedness”). Layering the fairness requirement on top forces b_I = 1 (increase must be purely additive — any multiplicative increase component hurts fairness convergence) and forces the decrease to be purely multiplicative (a_D = 0). What remains is exactly:

Additive increase:        a_I > 0,  b_I = 1     ->  cwnd += constant
Multiplicative decrease:  a_D = 0,  0 < b_D < 1 ->  cwnd  = cwnd * factor

That is AIMD, and TCP’s +1 SMSS per RTT / cwnd ÷ 2 on loss is the concrete instantiation. This is the theoretical justification for the whole design: it is not an arbitrary heuristic but the provably-convergent control law for the problem TCP actually faces.

Loss Detection — Fast Retransmit and Fast Recovery

Multiplicative decrease needs a trigger, and waiting for the RTO timer to expire is wasteful — it can be hundreds of milliseconds, and it collapses the window to one segment. Fast retransmit detects a single loss far sooner using duplicate ACKs. A TCP receiver acknowledges the highest in-order byte it has, so a segment arriving out of order (because an earlier one was lost) makes the receiver re-send the same ACK number. RFC 5681 defines a duplicate ACK precisely: the receiver has outstanding data, the ACK carries no payload, SYN/FIN are clear, the ack number equals the previous greatest, and the advertised window is unchanged. On the third duplicate ACK the sender declares the segment lost and retransmits it immediately — without waiting for the timer (RFC 5681 §3.2).

Fast recovery then governs the window through the recovery period so the connection does not fall all the way back to slow start. The exact steps (RFC 5681 §3.2):

  1. On the third duplicate ACK, set ssthresh = max(FlightSize/2, 2*SMSS) — the multiplicative decrease.
  2. Retransmit the lost segment and set cwnd = ssthresh + 3*SMSS. The +3 “inflates” the window to account for the three segments that have left the network (each duplicate ACK is proof one more segment reached the receiver).
  3. For each additional duplicate ACK, cwnd += SMSS — keep inflating, because each dup-ACK means another segment has drained, so another may be sent.
  4. When an ACK finally acknowledges new data (the “recovery ACK”), deflate: set cwnd = ssthresh. The connection resumes congestion avoidance from the halved window, never having stopped its ACK clock.

The distinction from the RTO path is the whole point: three duplicate ACKs prove the clock is still running (packets are still arriving), so a mild halving suffices; an RTO proves the clock has stopped, which is a far more dangerous state and warrants collapse to cwnd = 1.

The Tahoe → Reno → NewReno Lineage

The names come from the 4.xBSD releases that shipped each refinement, and they mark distinct algorithmic generations:

  • TCP Tahoe (1988, Jacobson’s original) introduced slow start, congestion avoidance, and fast retransmit. But Tahoe’s response to any loss — including a fast-retransmit-detected one — was to drop cwnd to 1 and re-enter slow start. It had no fast recovery (Jacobson 1988).
  • TCP Reno added fast recovery: on a fast-retransmit event it halves the window and continues (the four steps above) rather than collapsing to slow start. This is the AIMD behaviour codified in RFC 5681. Reno’s weakness is multiple losses in one window — it recovers one loss per fast-recovery episode and often stalls into an RTO when a window loses several segments.
  • TCP NewReno (RFC 6582, April 2012, Standards Track, obsoleting RFC 3782) fixes exactly that without needing selective acknowledgements. It records recover, the highest sequence number outstanding when recovery began, and recognises a partial ACK — one that acknowledges some new data but not all of recover. On a partial ACK, NewReno stays in fast recovery, immediately retransmits the next unacknowledged segment, and repeats until the ACK finally covers recover (RFC 6582 §3). This lets one recovery episode repair a whole window’s worth of losses, at one retransmission per RTT, avoiding the timeout that would otherwise dominate. NewReno is the loss-recovery baseline that modern algorithms (including CUBIC Congestion Control) inherit, layering their own window-growth curve on top of the same detection-and-recovery skeleton. The finer-grained alternative — Selective Acknowledgement (SACK) — lets the receiver report exactly which non-contiguous blocks arrived, so the sender can repair several holes per RTT; see TCP Selective Acknowledgement. Retransmission timing itself is covered in TCP Retransmission Timers and Fast Retransmit.

Loss as a Signal — and ECN as the Alternative

Everything above treats packet loss as the congestion signal. That coupling has a cost: to find the congestion point, a loss-based sender must actually cause a loss — it fills the bottleneck queue until it overflows, then backs off. On a path with deep buffers this manifests as bufferbloat (huge standing queues and latency), and on a path with random non-congestive loss (wireless) it manifests as needless throughput cuts. See Bufferbloat and Active Queue Management.

Explicit Congestion Notification (ECN) decouples the signal from the drop (RFC 3168, September 2001, Standards Track). A router experiencing incipient congestion — a queue starting to build, detected by an Active Queue Management scheme — sets the Congestion Experienced (CE) codepoint in the IP header instead of dropping the packet. The two-bit ECN field in the IP header carries four codepoints: Not-ECT (00, not ECN-capable), ECT(0) (10) and ECT(1) (01) (sender marks the packet ECN-capable), and CE (11) (router marks congestion). The feedback loop runs through two TCP header flags: the receiver, on seeing CE, sets ECN-Echo (ECE) in its ACKs; the sender reacts by reducing cwnd and sets Congestion Window Reduced (CWR) on its next data segment so the receiver knows the signal was heard (RFC 3168 §6). Critically, RFC 3168 requires the reaction to be “essentially the same as the congestion control response to a single dropped packet” — one multiplicative decrease per window — so ECN is a drop-free loss signal, giving the sender the congestion information without the retransmission and without filling the queue. Data-centre variants such as DCTCP go further, reacting to the fraction of CE marks rather than treating any mark as a full loss, achieving very low queueing latency (at the cost of requiring ECN support on every hop).

Failure Modes and Common Misunderstandings

  • “Slow start is slow.” It is exponential — the window doubles each RTT. The linear phase (congestion avoidance) is the slow one. This is the single most common newcomer error.
  • Confusing cwnd with rwnd. cwnd protects the network and is invisible on the wire; rwnd protects the receiver’s buffer and is advertised in every segment. Throughput is capped by the minimum. If a transfer is slow but the path is uncongested, suspect a small advertised window (flow control) — go to TCP Flow Control and the Sliding Window and check window scaling.
  • cwnd is in segments/bytes, not packets-per-second. It is a quantity of in-flight data, not a rate. The rate that results is cwnd / RTT — which is why the bandwidth-delay product (bandwidth × RTT) is the window a connection needs to fill a pipe. An under-windowed sender on a long fat link is throughput-starved even with zero loss.
  • AIMD’s throughput is RTT-biased. Because the additive step is +1 per RTT, a short-RTT flow ramps faster and, sharing a bottleneck with a long-RTT flow, grabs a larger share — the classic RTT unfairness of Reno. This is one of the specific problems CUBIC Congestion Control was designed to reduce.
  • Reno stalls on multiple losses. A single window losing several segments often forces classic Reno into an RTO. NewReno’s partial-ACK handling (or SACK) is what makes multi-loss recovery graceful; a stack without them will show mysterious latency spikes on lossy paths.
  • A dropped packet is not always congestion. On wireless or dirty links, loss can be corruption, not queue overflow. Loss-based AIMD cannot tell the difference and cuts anyway — the motivation for model-based BBR and for ECN.

Alternatives and When to Choose Them

  • NewReno / Reno (pure AIMD) — the well-understood baseline; the universal fallback. Fine on low bandwidth-delay-product paths, but its +1/RTT climb is hopelessly slow to fill high-BDP links after a loss. Choose deliberately only for compatibility or teaching.
  • CUBIC — replaces the linear increase with a cubic function of real time since the last loss, so it fills large windows in seconds instead of minutes and is far less RTT-biased. The default on Linux, Windows, and Apple stacks; the sensible general-purpose choice.
  • BBR — abandons loss-as-signal entirely, modelling the bottleneck bandwidth and round-trip propagation delay directly and pacing to keep the pipe full without filling the queue. Strong on lossy or deeply-buffered paths; carries fairness caveats against loss-based flows.
  • DCTCP / ECN-based — for the data centre, where every hop supports ECN and ultra-low queueing latency matters more than open-Internet compatibility.

Production Notes

Congestion control is a sender-side choice — the receiver has no say beyond flow control and ECN echoing — so it is deployable unilaterally, which is why a single vendor (Google with BBR, or the Linux default of CUBIC) can shift the behaviour of a huge fraction of Internet traffic without any peer coordination. On Linux the algorithm is selected per-connection out of a pluggable framework and observed with ss -i, both covered in TCP Congestion Control. The one number worth committing to memory when reasoning about any of this: a connection can only be fast if its window reaches the bandwidth-delay product, and it can only stay fast if the algorithm’s increase can refill that window quickly after each multiplicative cut — which is precisely the arithmetic that made plain AIMD untenable on modern high-BDP links and motivated CUBIC and BBR.

See Also

Graph View