The Math of Congestion: Why TCP Uses Additive Increase, Multiplicative Decrease
In packet-switched networks, thousands of independent applications inject data into shared intermediate routers without centralized coordination.
If end hosts transmit too aggressively, router memory buffers overflow, causing packet drops, retransmission storms, and Congestive Collapse (a phenomenon that nearly brought down the nascent Internet in 1986).
To stabilize global communications, Van Jacobson introduced the TCP Congestion Control Algorithm, built upon the mathematical principle of Additive Increase, Multiplicative Decrease (AIMD).
1. The Two Windows: Flow Control vs Congestion Control
A TCP sender's in-flight data is bounded by two distinct constraints:
Effective Window = min(rwnd, cwnd)
-
rwnd(Receive Window): Advertised by the receiver to prevent overflowing receiver RAM buffers (Flow Control). -
cwnd(Congestion Window): Dynamically calculated by the sender to prevent overflowing intermediate network routers (Congestion Control).
2. The Phases of TCP Congestion Control
Phase 1: Slow Start
Despite its name, Slow Start increases transmission speed exponentially:
- Initial
cwnd = 1 MSS. - For every incoming ACK,
cwndincreases by1 MSS. - Over one Round-Trip Time (RTT),
cwnddoubles:1 → 2 → 4 → 8 → 16. - Terminates when
cwnd ≥ ssthresh(Slow Start Threshold).
Phase 2: Congestion Avoidance (Additive Increase)
Once cwnd reaches ssthresh, exponential growth would quickly overwhelm router buffers.
The sender switches to linear probing:
cwnd = cwnd + 1 MSS per RTT
Phase 3: Multiplicative Decrease
When packet loss is detected via 3 Duplicate ACKs:
ssthresh = (cwnd / 2)
cwnd = ssthresh
The sender immediately slashes its transmission window by 50%.
3. The Chiu & Jain Vector Proof
Why Additive Increase and Multiplicative Decrease? Why not Additive Decrease?
In a seminal 1989 paper, Dah-Ming Chiu and Raj Jain modeled two users competing for a bottleneck link of capacity C.
They analyzed four combinations:
- AIAD (Additive Increase, Additive Decrease): Oscillates along a fixed trajectory; never converges to fairness.
- MIMD (Multiplicative Increase, Multiplicative Decrease): Unstable and non-convergent.
- AIMD (Additive Increase, Multiplicative Decrease): The only linear control law that monotonically converges competing flows toward both optimal efficiency and 50/50 fairness.
Explore interactive TCP congestion simulations at Binary Dose.
Top comments (0)