The Additive Increase/Multiplicative Decrease Algorithm: How TCP Congestion Control Mathematically Trades Efficiency for Fairness

Highway traffic networks prevent gridlock through central controllers—ramp meters and centralized dispatchers that monitor the entire system and dictate who enters and when. The Internet, by contrast, operates with no central authority, yet it manages a vastly larger volume of traffic without collapsing. The single respect in which the Internet differs from a physical highway is that its traffic control is entirely decentralized, relying on a mathematical rule embedded in every connected device: the Additive Increase/Multiplicative Decrease (AIMD) algorithm.[6]

We argue that AIMD is the most successful distributed algorithm in human history, but its success relies on a transparent, structural trade-off. It mathematically sacrifices absolute network efficiency to guarantee a specific definition of fairness. However, as our analysis of heterogeneous network latencies shows, that definition of fairness inherently punishes users who are physically further from the server.[2][7]

To understand why this trade-off is necessary, one must look at the alternative. In October 1986, the early Internet experienced a catastrophic congestion collapse. As the network became saturated, routers began dropping packets. Endpoints, assuming the packets were lost in transit, immediately retransmitted them, pouring more data into an already overwhelmed network. Throughput on a 32-kilobit-per-second link between the Lawrence Berkeley Laboratory and UC Berkeley plummeted to just 40 bits per second—a 99.8 percent drop.[4]

The solution, introduced by researcher Van Jacobson in 1988, was to make the endpoints responsive to the network's state without requiring the network to explicitly communicate that state. Jacobson's implementation of TCP congestion control relied on packet loss as an implicit signal of congestion. When a packet is dropped, the sender assumes the network is full and slows down.[4][6]

The mechanism governing this acceleration and deceleration is AIMD. The Additive Increase phase is the algorithm's exploratory function. For every round-trip time (RTT) that passes without a dropped packet, the sender increases its transmission window by exactly 1 maximum segment size. This results in a slow, linear increase in bandwidth utilization, gently probing the network for available capacity.[4]

The Multiplicative Decrease phase is the algorithm's emergency brake. The moment a packet is lost, the sender does not merely subtract a segment from its window; it cuts its transmission rate by exactly 50 percent. This aggressive, non-linear reaction is what prevents the cascading failures of 1986, instantly draining the congested router queues.[4][6]

The choice of AIMD over other mathematical combinations—such as Additive Increase/Additive Decrease (AIAD) or Multiplicative Increase/Multiplicative Decrease (MIMD)—was not arbitrary. In a seminal 1989 paper, researchers Dah-Ming Chiu and Raj Jain used phase-space plots to prove that AIMD is the only control function that mathematically guarantees convergence to both efficiency and fairness across competing data flows.[3]

Efficiency, in this context, means the network's total capacity is fully utilized. Fairness means that 2 endpoints sharing the same bottleneck link will eventually converge to an equal share of the bandwidth, regardless of their starting speeds. As RFC 2914, the Internet Engineering Task Force's foundational document on congestion control, notes: "Congestion control is a necessary prerequisite for the stable operation of the Internet."[1]

However, the strongest counter-argument to AIMD's brilliance lies in its definition of fairness. The algorithm measures time in RTTs—the time it takes for a packet to reach its destination and an acknowledgment to return. Because Additive Increase adds 1 segment per RTT, a flow with a shorter RTT will increase its speed much faster than a flow with a longer RTT.[2][4]

This creates a structural geographic penalty. According to research published by the École Polytechnique Fédérale de Lausanne (EPFL), when 2 flows with heterogeneous RTTs compete for the same bottleneck, the AIMD algorithm allocates bandwidth in inverse proportion to their latencies. A user 5,000 miles away connecting to a server in New York will mathematically be starved of bandwidth by a local user connecting to the same server.[2]

"The fairness of AIMD is highly sensitive to the round-trip time," the EPFL researchers note, demonstrating that the algorithm's theoretical convergence only holds true when all competing flows share identical geographic distances. In the real world, this means the protocol structurally favors local traffic over global traffic.[2]

This latency bias has profound implications for modern network architecture. As the Internet has scaled to support high-definition video and real-time cloud computing, the limitations of AIMD have become a bottleneck. RFC 6077, which outlines open research issues in Internet congestion control, explicitly highlights the challenge of maintaining fairness in high-speed, high-latency environments.[5]

To compensate for AIMD's geographic penalty, the tech industry has spent billions of dollars deploying Content Delivery Networks (CDNs). By caching data physically closer to the end user, CDNs artificially reduce the RTT, allowing the Additive Increase phase to ramp up faster and bypass the algorithm's structural bias.[6][7]

AI

Furthermore, network engineers are increasingly abandoning pure AIMD in favor of delay-based algorithms. Google's BBR (Bottleneck Bandwidth and Round-trip propagation time), introduced in 2016, attempts to model the network's actual capacity rather than relying on packet loss as a proxy for congestion. By measuring the exact delivery rate, BBR can maintain high throughput even on long-distance links.[6]

Yet, despite these innovations, AIMD remains the default congestion control mechanism for the vast majority of the Internet's infrastructure. Its simplicity—requiring no complex calculations or centralized coordination—makes it incredibly robust. It is a testament to the power of distributed algorithms that a few lines of code written in 1988 still prevent the collapse of a global communications network today.[4][6]

The story of AIMD is a lesson in the mathematics of compromise. It proves that in a decentralized system, you cannot optimize for everything. By choosing to prioritize network survival over absolute geographic fairness, the architects of the Internet built a system resilient enough to scale from a few thousand academic computers to billions of global devices.[1][7]