AIMD Congestion Control and the Collapse It Prevented

In October 1986 throughput on a path between two ARPANET sites collapsed by roughly three orders of magnitude and recovered only when the traffic stopped. The cause was not a hardware failure. Hosts were retransmitting on timeout into a network whose queues were already full, so each retransmission added load to a path that had no capacity to absorb it, and the effective throughput collapsed while the offered load stayed constant. Van Jacobson’s diagnosis, published with Michael Karels in 1988, identified the missing component: the endpoints had no model of the path, so they could not tell the difference between a path that was slow and a path that was saturated.

Congestion control is the mechanism that supplies that model. It is not flow control, which protects the receiver from a sender that is too fast; it protects the network from the aggregate of senders that are individually reasonable. The distinction matters because the two operate on different signals and fail in different ways. Flow control uses a window advertised by the receiver; congestion control uses a window inferred by the sender from the path’s response.

The signals available without measurement

A sender cannot ask a router how loaded it is. There is no field in the IPv4 header that reports queue occupancy, and the ICMP message that once served that purpose, Source Quench, was a router’s local opinion at a single moment and was never trustworthy enough to act on. The sender’s only reliable signal is time.

Three observable events carry information. An acknowledgement arrives, which means a byte reached the receiver. An acknowledgement does not arrive within the retransmission timeout, which means either the byte was lost or the path is slower than the timer assumed. And acknowledgements arrive in a pattern: a stream of acks with increasing spacing implies the receiver’s window is being filled more slowly than the sender is offering, which usually means a queue somewhere on the path is growing.

The third signal is the subtle one and the basis of the whole design. If a sender injects a burst and measures the round trip of the last byte of the burst, the increase over the idle-path round trip is the queueing delay at the bottleneck. A growing round trip with a growing window is the signature of a queue filling, and the queue is the buffer whose overflow will cause the loss that the sender will then have to recover from. Reacting to the delay increase avoids the loss entirely; reacting only to the loss reacts after the damage. The queue itself is not a defect of the network: it is the same buffer that makes statistical multiplexing work, as described in Statistical Multiplexing and the Case Against Reserved Circuits, and the control loop is what keeps it from becoming the thing that breaks the path.

Early implementations used loss as the sole signal because measuring delay required a timestamp option that not every path preserved. Modern implementations have the option, but the option can be stripped or zeroed by middleboxes, so delay-based control is deployed alongside loss-based control rather than replacing it.

Why the increase is additive and the decrease multiplicative

The window $W$ is the number of unacknowledged bytes a sender may have in flight. The control law that Jacobson and Karels described, and that RFC 5681 codifies, is:

$$W \leftarrow W + \frac{1}{W} \quad \text{per acknowledgement, and} \quad W \leftarrow \frac{W}{2} \quad \text{per loss event.}$$

In practice the first rule increments the window by one segment per round trip, because an acknowledgement covering one segment adds $1/W$ of a window and there are $W$ acknowledgements per round trip. The aggregate is additive increase: one segment per round trip, regardless of the current window.

The choice of additive increase is a stability argument. Suppose two connections share one bottleneck and both increase additively. The one with the larger window gains the same absolute amount as the smaller one, so the difference between them stays constant while the sum grows; they converge to equal shares only through the decrease step. Now suppose both increase multiplicatively. The larger window grows by more than the smaller, the gap widens, and one connection takes the link. Additive increase is the only increase rule under which two flows starting at different rates approach equality rather than diverging.

The decrease must be multiplicative because the amount by which a sender must back off depends on how far over capacity it is, and that distance is proportional to its own window. Halving is the smallest decrease that reliably clears a queue built during one round trip, and it is the largest decrease that does not waste most of the discovered capacity. The pair, additive increase and multiplicative decrease, is the AIMD that gives the scheme its name.

class AimdWindow:
    """Congestion window in segments, with the RFC 5681 rules in slow start
    and congestion avoidance, and the halving on a loss event."""

    def __init__(self, initial=1, smss=1460):
        self.cwnd = initial * smss
        self.ssthresh = float("inf")
        self.smss = smss
        self.in_slow_start = True

    def on_ack(self, newly_acked):
        if self.in_slow_start:
            self.cwnd += newly_acked           # exponential: doubles per RTT
            if self.cwnd >= self.ssthresh:
                self.in_slow_start = False
        else:
            # Additive: one SMSS per RTT, apportioned over the acks in that RTT.
            self.cwnd += self.smss * newly_acked / self.cwnd

    def on_loss(self):
        self.ssthresh = max(self.cwnd / 2, 2 * self.smss)
        self.cwnd = self.ssthresh
        self.in_slow_start = False

Slow start is the exception to additive increase, and it exists because a new connection has no estimate at all. Starting at one segment and increasing by one per acknowledgement doubles the window each round trip, which reaches a working window in a handful of round trips rather than the tens that additive increase would need. The transition to congestion avoidance happens at the threshold recorded when the last loss occurred, so the exponential phase does not repeat the overshoot that caused the loss.

The sawtooth and what it costs

A single connection under AIMD traces a sawtooth: the window climbs linearly until a loss, halves, climbs again. The amplitude of the sawtooth is proportional to the window at the moment of loss, and the period is the time to climb from half the window back to the loss point, which is roughly $W/2$ round trips. The average window is therefore about three quarters of the peak, and the utilization oscillates around the path’s capacity rather than sitting at it.

That oscillation is the price of not knowing the capacity. A sender that knew the bottleneck rate could hold the window exactly at the bandwidth-delay product and never lose a packet. AIMD discovers the rate by probing past it and backing off, and the probing is what generates the sawtooth. The loss rate needed to sustain a given window scales as $W^{-2}$: doubling the window requires roughly a quarter of the loss rate, which is why high-throughput paths tolerate very low loss and why a loss rate that looks negligible can cap throughput far below the link rate.

The other cost is that the sawtooth is synchronized. Connections sharing a bottleneck all lose packets at approximately the same moment, all halve together, and all climb together, so the aggregate oscillates with a larger amplitude than any individual flow. The classic remedy is to randomise the moment of loss so that different flows back off at different times, which is what random early detection does by dropping a fraction of packets before the queue is full. The drop probability rises with the average queue length, so a flow is likely to be hit slightly before the buffer overflows and the choice of victim is random rather than last-in-first-out.

Recovery without waiting for a timeout

A lost segment is detected two ways. The retransmission timer expiring is unambiguous but slow: the timeout must be at least the estimated round trip plus several times its variation, and after a loss the estimate is stale, so the sender waits far longer than necessary. Fast retransmit avoids the wait by using duplicate acknowledgements. When a receiver gets a segment out of order, it re-acknowledges the last in-order byte, and each duplicate tells the sender that a segment after that point arrived. Three duplicates is enough evidence to retransmit without waiting, because a path that reorders three positions and also loses the segment is unlikely enough to be worth the risk of a spurious retransmission.

Fast recovery then keeps the pipe full. Instead of dropping the window to one segment and re-entering slow start, the sender halves the window, inflates it by the number of segments known to have left the network, and retransmits the missing one. The inflation accounts for the data the receiver has buffered, so the sender does not stall while waiting for the recovery acknowledgement. When the recovery acknowledgement finally arrives, the window is deflated back to the halved value.

The timer estimate itself is part of the design. The retransmission timeout is computed from a smoothed round-trip estimate and its mean deviation, with the deviation scaled up so that the timeout adapts quickly to a path whose delay is variable. A fixed timeout cannot work: too short and it fires on a path that is merely slow, causing a spurious retransmission that adds load to a congested network; too long and a real loss goes unrepaired for seconds.

Where the loop breaks

The first failure is the path that carries no signal. A sender whose loss is caused by a corrupt link rather than a full queue halves its window for a condition that reducing the window cannot fix, and the throughput settles at the level where the corruption rate and the window balance. The control loop assumes loss means congestion, and a wireless link violates the assumption continuously.

The second is the path whose capacity changes faster than the loop can track. A cellular link that drops from high rate to low rate in a few milliseconds leaves the sender with a window far above the new capacity, and the queue that forms takes many round trips to drain. The bufferbloat problem is the same phenomenon at a longer timescale: a buffer sized in seconds of link time turns every congestion episode into a delay episode, and the sender’s delay-based signal reads a full buffer as a saturated path long after the queue should have been dropped.

The third is the flow that does not back off. A sender that ignores loss, whether by design or by a bug, takes capacity from every sender that does back off, and the equilibrium moves toward the aggressive flow. This is why the fairness property of AIMD holds only among flows that implement it, and why the response to non-conforming senders is enforcement in the network rather than a stronger control law. Where the enforcement lives is itself a design question raised by the placement argument in The TCP/IP Split and the End-to-End Argument.

The fourth is the interaction with the receiver’s window. Congestion control computes a window from the path’s behaviour, flow control computes one from the receiver’s buffer, and the sender transmits the smaller of the two. On a path with a large bandwidth-delay product and a receiver with a small buffer, the flow-control window binds and the congestion window never grows, so the path is underused and the sender’s model of it is never tested. The window scale option exists to lift the 16-bit limit on the advertised window, which on a long path would otherwise cap throughput regardless of the congestion window.

The fifth is the one the original design did not anticipate: the sender’s estimate of the path is per-connection, and the path is shared. Each connection independently discovers the bottleneck, and the sum of their windows is what the bottleneck actually sees. The control loop is stable because the aggregate response to a loss event is proportional to the aggregate window, but the allocation among connections is determined by their relative round trips rather than by any fairness criterion. A connection with a shorter round trip opens its window faster and holds a larger share, and no part of the protocol corrects for it. That bias, and the queueing model that produces it, are the reason later work moved from end-to-end inference toward signals carried in the packets themselves.