Additive Increase, Multiplicative Decrease, and the Fairness of the Sawtooth

Two flows share a bottleneck link. Each runs the same algorithm, each sees the same round trip, and neither knows the other exists. Within a few hundred round trips they end up with nearly equal shares, and they stay there. That convergence is not a coincidence and it is not a property of TCP specifically. It follows from the arithmetic of the update rule, and it fails when the arithmetic changes.

The rule is: on every acknowledgement, increase the window by a small fixed amount; on every loss indication, multiply the window by a constant less than one. Additive increase, multiplicative decrease. The interesting part is why that particular pairing, out of the four combinations available, is the one that produces a stable and fair equilibrium.

The rule in bytes

In congestion avoidance, the sender credits itself roughly one segment per round trip. Since acknowledgements arrive one per segment, the per-ACK increment is one segment divided by the current window in segments:

/* Congestion avoidance: roughly +1 SMSS per RTT, credited per ACK. */
cwnd += (smss * smss) / cwnd;

The division is what makes the growth additive in time rather than in packets. With a window of W segments, W acknowledgements arrive per round trip, each adding 1/W of a segment, so the window grows by exactly one segment per round trip regardless of W. Growth is linear in round trips, which is a slow ramp: a flow starting at 10 segments needs 90 round trips to reach 100.

On a loss indication the sender multiplies. For a single loss detected by duplicate acknowledgements, RFC 5681 halves the window, with a floor of two segments:

/* Multiplicative decrease: halve, but never below two segments. */
cwnd = cwnd / 2;
if (cwnd < 2 * smss)
    cwnd = 2 * smss;

The floor matters on short flows and on paths with tiny windows, where halving repeatedly would collapse the window to zero and stall the sender permanently. Two segments is the smallest window from which a sender can still make progress against delayed acknowledgements.

The window therefore traces a sawtooth: a linear climb from W/2 to W, a halving, another climb. The period is W/2 round trips and the mean window is 3W/4.

Why the two directions differ

Four combinations of increase and decrease are conceivable, and only one of them converges.

Consider two flows with windows x and y sharing a link. Fairness is the diagonal x = y; efficiency is the line x + y = C for the capacity C. A control law moves the pair through this plane, and the question is where repeated application sends it.

Multiplicative increase, multiplicative decrease. Both windows scale by the same factor on every step, so the ratio x/y is invariant. A pair starting at (3C/4, C/4) stays at a ratio of three forever. Convergence to the diagonal never happens; the equilibrium is whatever the starting point was.

Additive increase, additive decrease. Both windows move by the same amount, and the increase and decrease steps are opposite motions along the same line of slope one, so x - y is invariant and the pair can only oscillate along the line it started on. Starting at (3C/4, C/4), the difference of C/2 persists forever while the sum oscillates around capacity: the link stays busy, but the split is fixed by where the two flows started and never converges to the diagonal.

Multiplicative increase, additive decrease. The increase scales both windows by the same factor, so the ratio is preserved, while the decrease subtracts the same amount from both, which the smaller flow feels proportionally more sharply: 0.75 and 0.25 become 0.70 and 0.20 after a decrease of 0.05, and the ratio widens from three to three and a half. Every cycle moves the pair further from the diagonal.

Additive increase, multiplicative decrease. The increase moves the pair along a line of slope one, so the difference x - y is unchanged and the sum rises. The decrease moves the pair toward the origin along a ray, so the ratio is unchanged and the difference is halved. Alternating the two makes the sum return to capacity after every cycle while the difference falls by half per cycle, so the pair spirals onto the diagonal. This is the only combination of the four that both converges to fairness and keeps the link utilized, which is the result Chiu and Jain derived in 1989 by treating the pair as a vector and asking which control laws have the diagonal as an attractor.

The intuition for why halving is proportional is worth stating separately, because it is often described as an arbitrary choice. It is not. The multiplicative decrease is what preserves the relative position of the two flows, so the decrease step alone cannot fix unfairness, and the additive increase is what supplies the correcting force. If the decrease were subtractive, a flow with a small window would lose the same absolute amount as a large one, which is punitive to the small flow and would let the large flow dominate. Proportional reduction is the only decrease that treats flows according to their current size.

From sawtooth to throughput

The sawtooth converts a loss rate into a throughput, and the conversion is the most quoted result in the field. It is worth deriving rather than reciting, because the assumptions are the interesting part.

Let the peak window be W segments. The window climbs from W/2 to W, one segment per round trip, so the climb takes W/2 round trips. The number of segments sent during the cycle is the area under the window over that time, in units of round trips:

window at round trip k:   W/2 + k,   k = 0 … W/2 - 1
segments per cycle:       sum over k of (W/2 + k) = 3W²/8 - W/4  ≈ 3W²/8

One loss occurs per cycle, so the loss probability per segment is p ≈ 1 / ((3/8)W²), giving W ≈ sqrt(8/(3p)). Average throughput is the mean window divided by the round trip:

throughput ≈ (3/4) * sqrt(8/(3p)) * MSS/RTT ≈ 1.22 * MSS / (RTT * sqrt(p))

The constant 1.22 is the familiar one from the Mathis et al. analysis of Reno. The important content is the exponent: throughput falls as the inverse square root of loss probability. Halving the loss rate raises throughput by only about 41 percent. Quadrupling throughput requires a sixteenfold reduction in loss. This square-root law explains why loss-based control struggles on paths where the achievable loss rate cannot be driven low enough, and why high-bandwidth long-delay paths pushed the field toward algorithms that do not depend on loss at all, a direction taken up in model-based congestion control.

The derivation also shows what the sawtooth amplitude costs. The window swings by a factor of two, so the sending rate swings by a factor of two within every cycle, and the queue at the bottleneck swings by the corresponding amount. For a flow with a 10 MB window, the swing is 5 MB of queue, which on a link serving at 1 Gbit/s is 40 ms of standing delay. The peak-to-trough variation is not a detail; it is the dominant source of jitter on a congested path.

A deterministic two-flow model

The convergence claim is easy to check with a fluid model. Two windows share a capacity of one unit, each grows additively, and each is halved when the sum exceeds capacity. The fairness ratio is the quantity to watch.

def simulate(steps=400, cap=1.0, step=0.01, x=0.9, y=0.1):
    """Two AIMD flows; halve both whenever the sum overshoots capacity."""
    for _ in range(steps):
        x += step
        y += step
        if x + y > cap:
            x *= 0.5
            y *= 0.5
    return x, y

x, y = simulate()
print(f"{x:.3f} {y:.3f} ratio={x / y:.2f}")

The starting split of nine to one closes quickly. Each overshoot halves both windows, so the difference x - y halves per cycle while the sum returns to capacity, and ten cycles reduce a gap of 0.8 to under 0.001. Convergence is geometric in the number of loss events rather than linear, and the rate depends only on the decrease factor: with a decrease factor β, the gap shrinks by β per cycle, so a gentler decrease converges more slowly.

The model is deliberately unfair to the algorithm in one respect and generous in another. It is generous because both flows reduce at exactly the same instant, which no real pair of flows does; the simultaneity is what makes the gap halve cleanly instead of random-walking. It is unfair because real decreases are triggered by losses that arrive at different times for different flows, so the convergence is noisy and the equilibrium is a distribution around the diagonal rather than a point. What survives in both cases is the direction of the motion: additive increase always pushes the pair apart along the diagonal’s parallel, and multiplicative decrease always pulls it toward the origin along a ray, and those two motions together cannot avoid the diagonal.

Where the argument breaks

The convergence proof assumes that all flows see the same capacity and the same round trip, and that loss is the only signal. Each assumption has a failure mode with a name.

Different round trips. A flow with a shorter round trip increases its window more often per unit time, so it captures a larger share. The equilibrium is proportional to 1/RTT, not equal. This is the RTT bias, treated in RTT fairness among competing flows.

Timeouts. A halving is a mild event: throughput drops by half for one round trip and recovers over the next W/2. A retransmission timeout is a severe one: the window collapses to one segment and the recovery is a full slow start. The sender is also forced to wait out the retransmission timer, which RFC 6298 recommends rounding up to at least one second, so the stall lasts far longer than the loss that triggered it. The sawtooth model assumes all losses are duplicate-ACK losses, which is the case examined in duplicate ACK recovery.

Multiple losses per window. Reno halves once per window regardless of how many segments were lost. If a window loses five segments, the sender halves, retransmits one, and then waits for a timeout for the rest. The result is a throughput collapse out of proportion to the loss rate, and it is why selective acknowledgement changed the recovery mechanics rather than the control law.

Small windows and the floor. The two-segment floor breaks the multiplicative decrease on paths where the window is small, so a flow that repeatedly hits the floor does not halve at all and behaves like a constant-rate source. On a lossy link with a short round trip this can make a flow far more aggressive than the model predicts.

Compressed ACKs and bursty returns. The model counts acknowledgements as a smooth stream. A receiver that acknowledges every second segment halves the clock rate, and a sender that credits per ACK rather than per byte grows at half the intended rate, which is a silent factor-of-two error in the control loop.

The sawtooth also has a consequence for the network rather than the sender: because the amplitude is proportional to the window, and windows grow with bandwidth-delay product, the queue variation that the network must absorb grows with the path’s capacity. That is the argument for queue management that reacts earlier than overflow, and for buffers sized to the product rather than to a fixed number of packets.