How do you get millions of independent, uncoordinated senders to fairly share limited network capacity, without any central authority dictating allocations? This is one of the most remarkable achievements in distributed systems: emergent global fairness from purely local decisions.

The answer is a deceptively simple strategy called AIMD: Additive Increase, Multiplicative Decrease. Each sender independently increases its rate slowly, additively—and when it detects congestion, it decreases its rate sharply, multiplicatively.

This asymmetric response—cautious when increasing, aggressive when decreasing—is the secret sauce that makes TCP congestion control work. It's not just an engineering hack; there's deep mathematical beauty underlying why AIMD achieves both efficiency (using all available capacity) and fairness (dividing that capacity reasonably among competing flows).

AIMD defines how TCP adjusts its congestion window (cwnd) in response to network feedback. The algorithm has two phases:

Additive Increase:

When no congestion is detected (ACKs arriving normally, no loss or ECN marks):

cwnd = cwnd + α

Typically α = 1 MSS (Maximum Segment Size) per round-trip time.

More precisely, TCP increases cwnd by 1/cwnd for each ACK received, so that over one RTT (approximately cwnd/MSS ACKs), the total increase is:

cwnd = cwnd + (1/cwnd) × (cwnd/MSS) × MSS = cwnd + MSS

This results in linear growth of the congestion window over time.

Multiplicative Decrease:

When congestion is detected (packet loss or ECN marks):

cwnd = cwnd × β

Typically β = 0.5 (halve the window).

This is a proportional cut—the sender immediately reduces its rate by a fixed fraction, regardless of current window size.

The Sawtooth Pattern:

AIMD's behavior over time produces the characteristic "sawtooth" pattern in cwnd:

1. cwnd grows linearly (additive increase)
2. Loss detected → cwnd cuts in half (multiplicative decrease)
3. cwnd grows linearly again
4. Loss detected → cwnd cuts in half again
5. Pattern repeats indefinitely

This oscillation is not a flaw—it's the mechanism by which TCP continually probes for available capacity while avoiding prolonged congestion. The network is always explored at the boundary of its capacity.

One of the most remarkable properties of AIMD is that it causes competing flows to converge toward equal bandwidth shares, even though each flow operates independently with no knowledge of others.

The Setup:

Consider two flows sharing a bottleneck link with capacity C. Let:

• x₁, x₂ = current sending rates of flows 1 and 2
• Fairness = both flows equally share: x₁ = x₂ = C/2

We can visualize this in a 2D state space where the x-axis is flow 1's rate and the y-axis is flow 2's rate.

Key Lines:

• Efficiency Line: x₁ + x₂ = C (total rate = capacity, full utilization)
• Fairness Line: x₁ = x₂ (both flows get equal share)
• Optimal Point: intersection at (C/2, C/2)

AIMD Dynamics:

During Additive Increase: Both flows increase by the same absolute amount (α). In state space, this is movement along a 45° line (both coordinates increase equally).

During Multiplicative Decrease: Both flows decrease by the same factor (β). In state space, this is movement toward the origin along a line through the current point.

The Convergence Proof:

Here's the elegant argument for why AIMD converges to fairness:

Phase 1: Additive Increase

• Both flows increase by +α
• Movement in state space: parallel to fairness line (x₁ = x₂)
• Vertical distance from fairness line: unchanged
• Eventually hits efficiency line (x₁ + x₂ = C)

Phase 2: Multiplicative Decrease

• Both flows multiply by β < 1
• x₁_new = β × x₁, x₂_new = β × x₂
• Movement: toward origin along line through current point
• Both coordinates shrink by same factor
• Ratio x₁/x₂ preserved, but absolute difference reduced
• Moves CLOSER to fairness line!

Result: Each AI/MD cycle maintains direction toward efficiency but moves closer to fairness. Over repeated cycles, the system oscillates around the optimal point (C/2, C/2).

Why Other Combinations Fail:

Understanding AIMD's behavior allows us to derive formulas for TCP throughput in terms of network parameters.

The Sawtooth Window:

In steady state, cwnd oscillates between W_max (just before loss) and W_max/2 (just after loss), where W_max is the window size that fills the network and causes congestion.

Average Window:

Since growth is linear from W_max/2 to W_max:

W_avg = (W_max/2 + W_max) / 2 = 3W_max/4

Average Throughput:

Throughput_avg = W_avg / RTT = 3W_max / (4 × RTT)

Relating to Loss:

During one sawtooth cycle, TCP sends approximately:

• W_max/2 + (W_max/2 + 1) + ... + W_max segments
• This is roughly 3W_max²/8 segments

One loss occurs per cycle, so:

Loss probability p ≈ 8 / (3W_max²)

Solving for W_max:

W_max ≈ √(8/(3p)) ≈ 1.22/√p

The Mathis Equation:

Combining these insights, Mathis et al. (1997) derived the famous TCP throughput formula:

Throughput ≈ (MSS / RTT) × (C / √p)

Where C is a constant approximately 1.22 for standard TCP.

More refined versions account for timeout effects:

Throughput ≈ MSS / (RTT × √(2p/3) + RTO × 3√(3p/8) × p × (1 + 32p²))

Implications:

1. RTT Unfairness: Two flows with equal loss but different RTT get different throughput. The low-RTT flow gets proportionally more bandwidth.

2. Loss Sensitivity: Throughput drops as 1/√p. Doubling loss rate reduces throughput by ~30%. This is gentler than linear but still significant.

3. Efficiency Bound: To achieve high throughput on high-BDP paths, loss rate must be very low. For 10 Gbps on 100ms RTT (BDP = 125 MB), loss rate must be < 10⁻⁷ (one loss per 10 million packets!).

Pure AIMD would take too long to reach useful throughput from a cold start. TCP combines AIMD with additional phases for practicality:

Phase 1: Slow Start (Multiplicative Increase)

At connection start or after timeout, TCP uses exponential increase instead of additive:

cwnd = cwnd + MSS for each ACK (doubles each RTT)

This quickly probes for available capacity. "Slow" refers to comparison with the original TCP's immediate full-rate start, not to actual slow growth.

Exit Condition: cwnd reaches ssthresh (slow start threshold), or loss detected.

Phase 2: Congestion Avoidance (AIMD)

Once cwnd ≥ ssthresh, TCP switches to conservative additive increase:

cwnd = cwnd + MSS × MSS / cwnd for each ACK

This gives approximately +1 MSS per RTT—the "A" in AIMD.

On Loss: cwnd halved (or more severely for timeout), ssthresh set to new cwnd. This is the "MD" in AIMD.

Phase 3: Fast Retransmit & Fast Recovery

To avoid dropping to slow start on every loss:

Fast Retransmit: Upon receiving 3 duplicate ACKs, retransmit the lost segment immediately (don't wait for timeout).

Fast Recovery: After fast retransmit:

1. Set ssthresh = cwnd / 2
2. Set cwnd = ssthresh + 3 MSS (accounting for packets in flight)
3. For each additional duplicate ACK: cwnd += MSS (inflate window)
4. Upon new ACK (covering retransmitted data): cwnd = ssthresh, resume congestion avoidance

This allows TCP to maintain higher throughput during isolated losses—the window halves but doesn't reset to 1.

Timeout Handling:

Timeout indicates severe congestion (no ACKs at all):

1. ssthresh = cwnd / 2
2. cwnd = 1 MSS (or initial window)
3. Return to slow start

This is more drastic than fast recovery because timeout suggests major network disruption.

Classic AIMD's limitations—especially slow recovery on high-BDP paths and RTT unfairness—have motivated numerous improvements while preserving AIMD's core stability properties.

CUBIC (Linux Default):

CUBIC replaces linear increase with a cubic function centered on W_max (the window size before last loss):

W(t) = C × (t - K)³ + W_max

Where K = ∛(W_max × β / C)

Behavior:

• Far below W_max: grows quickly (catching up to previous level)
• Near W_max: grows slowly (cautious plateau)
• Above W_max: accelerates again (probing for new capacity)

This gives the "cubic" characteristic shape—fast when recovering, slow near congestion point, aggressive when discovering new capacity.

BBR's Departure from AIMD:

Google's BBR represents a more fundamental departure:

1. Model-based, not reactive: BBR explicitly estimates bottleneck bandwidth and minimum RTT, then paces at the calculated optimal rate.

2. No loss-driven decrease: BBR largely ignores loss as a congestion signal, except for safety bounds. It determines rate from its model.

3. Periodic probing: Instead of continuous exploration, BBR periodically probes for more bandwidth (raising rate briefly) and lower RTT (draining queues briefly).

Trade-offs: BBR can achieve higher throughput and lower latency than AIMD-based algorithms, but fairness between BBR and loss-based flows can be problematic. BBRv2 addresses some of these issues.

The AIMD Legacy:

Even as new algorithms emerge, AIMD principles persist:

• Cautious increase (even if not strictly additive)
• Strong decrease on congestion
• Multiplicative decrease for fairness convergence

These principles provide stability even when exact formulas differ.

AIMD deliberately oscillates—this is a feature, not a bug. But oscillation must be bounded and stable. Understanding the dynamics helps tune algorithm parameters.

Bounded Oscillation:

In steady state, cwnd oscillates between W_max/2 and W_max. The oscillation amplitude is W_max/2, which equals half the network's BDP when AIMD is correctly tracking capacity.

Why Oscillation is Necessary:

1. Capacity Probing: Without increasing past current rate, TCP can't discover if more bandwidth is available.

2. Fairness Adjustment: As flows come and go, AIMD's oscillations allow rebalancing.

3. Tracking Variable Capacity: Available bandwidth changes; oscillation provides ongoing exploration.

Stability Analysis:

From control theory, AIMD is stable when:

• Increase is slow relative to RTT (α/window small)
• Decrease is proportional, not additive
• All flows use compatible parameters

Synchronization Pathology:

A dangerous failure mode occurs when multiple flows become synchronized:

1. All flows increase together
2. All flows hit congestion simultaneously
3. All flows decrease together
4. Network oscillates violently between full and near-empty

This creates:

• High packet loss rates (buffer overflow when synchronized)
• Underutilization (all flows backing off together leaves capacity unused)
• Poor latency (periodic queue buildup)

Avoiding Synchronization:

Random Early Detection (RED): Router randomly drops packets before buffer is full. Different flows experience losses at different times, desynchronizing them.

ECN Spread: Marking packets probabilistically based on queue length achieves similar effect.

Initial Window Randomization: Starting flows with slightly random initial windows spreads their phases.

Timeout Randomization: Adding jitter to RTO prevents timeouts from clustering.

"Fairness" seems intuitive, but defining and measuring it precisely is subtle. Different metrics capture different fairness properties.

Jain's Fairness Index:

The most common metric, defined for n flows with throughputs x₁, x₂, ..., xₙ:

F = (Σxᵢ)² / (n × Σxᵢ²)

Properties:

• F = 1: Perfect fairness (all flows equal)
• F = 1/n: Maximum unfairness (one flow gets everything)
• F measures deviation from perfect equality

Example: Three flows with rates 5, 5, 5 Mbps: F = (15)² / (3 × 75) = 225/225 = 1.0 (perfect)

Three flows with rates 13, 1, 1 Mbps: F = (15)² / (3 × 171) = 225/513 = 0.44 (poor)

The RTT Unfairness Problem:

AIMD inherently favors low-RTT flows because:

1. Window increases by fixed amount per RTT
2. Low-RTT flow gets more RTTs per second
3. Low-RTT flow increases faster in absolute time

Quantitatively: Two flows with RTTs R₁ and R₂ sharing a bottleneck converge to:

x₁/x₂ ≈ R₂/R₁

The flow with 10ms RTT gets ~10× the throughput of a flow with 100ms RTT!

Addressing RTT Unfairness:

• CUBIC: Window growth based on real time, not RTT. Partially addresses unfairness.
• BBR: Estimates bandwidth directly, less RTT-dependent.
• Rate-based CC: Specifies rate, not window.

Fairness vs. Efficiency Trade-off:

Strict fairness may conflict with efficiency:

• Giving equal shares to a flow that's already buffer-limited wastes capacity
• Flows with different path bottlenecks shouldn't expect equal rates
• "Max-min" fairness gives smallest-demand flows priority

Practical fairness is always a compromise based on what "fair" means in context.

We've developed a comprehensive understanding of AIMD—the mathematical foundation of TCP congestion control. Let's consolidate the key insights:

Module Complete:

With this page, you've completed the Congestion Control Overview module. You now understand:

1. Why congestion is dangerous — The collapse problem and feedback loops
2. Network capacity concepts — BDP, pipelining, throughput limits
3. Sender-based control architecture — cwnd, ACK clocking, control loops
4. Congestion signals — Loss, delay, ECN, and their trade-offs
5. AIMD algorithm — The mathematical foundation enabling Internet-scale fairness

This foundational understanding prepares you for the next module, where we'll dive into Slow Start and Congestion Avoidance in detail—the specific algorithms that implement these principles in practice.