A study in motion
What converges
in AIMD?
Two senders have to discover how much a network can carry—and how to share it. A small asymmetry in their rules makes fairness emerge while their windows keep rising and falling.
Find your place in this lesson
The path: a sender's predicament → a complete two-flow cycle → two views of the same motion → what actually converges → a rule that fails.
How much should a sender send?
Imagine starting a large download while another download is already using the same bottleneck link. Yours could send cautiously and leave available bandwidth unused. It could send aggressively and help build a queue that eventually overflows. It would be convenient if the network simply told both senders their fair rates. For this lesson, it gives them much less: acknowledgments as data arrives, and a congestion signal when they have collectively pushed too far.
That leaves two problems tangled together. The senders must discover how much traffic the path can sustain. They must also divide that opportunity: an older, larger flow should not keep its head start forever merely because it arrived first. A rule that solves the first problem need not solve the second.
A sender controls its congestion window: roughly, how much data it permits to remain outstanding before acknowledgments make room for more. Picture a window of twenty packets as permission to keep about twenty packets in flight. If acknowledgments come back after a round-trip time, or RTT, the rough sustained sending rate is window divided by RTT. The window counts packets; the rate counts packets per unit time. We will hold RTT fixed so that we can study the window without simultaneously modeling queues and changing feedback delays.
The sender still does not know where to set that window. One reasonable strategy is to keep probing: increase while delivery appears to be going well, then back off when congestion appears. This produces a rise-and-fall pattern. But saying “increase, then decrease” leaves the central design choice open. Increase by the same amount, or by the same proportion? And which kind of decrease?
AIMD chooses additive increase, multiplicative decrease. Before proving anything about it, we will watch those two operations act on a pair of unequal flows. The question is whether a common rule can erase an unequal starting position without either sender knowing the other's window.
Give the rule something concrete to do
Call the flows A and B. A begins with a window of 4 packets; B begins at 20. Both always have more data to send, and both have the same, fixed RTT. During each RTT of uncongested operation, each adds one packet to its window. When their combined window reaches 48 packets, both immediately halve their windows.
These are chosen teaching parameters. The threshold of 48 is in packets, not a link capacity in packets per second. We are deliberately replacing packet arrivals, queues, loss detection, and feedback delay with one shared threshold event. Fractional window values are allowed. This simplified system lets us isolate the increase/decrease mechanism; later we will identify what it leaves out.
Start with the increase. After one RTT, the windows are 5 and 21. After two, they are 6 and 22. B's lead remains sixteen packets. Adding the same amount to two numbers cannot change their difference. At first this seems unpromising: the smaller flow is making progress, but it is not closing the absolute gap.
After twelve RTTs the windows reach 16 and 32. Their sum is 48, so the congestion event fires. Halving leaves 8 and 16. Now B's lead is eight packets. The same proportional cut took sixteen packets from the larger window but only eight from the smaller one.
| Moment | A | B | Total | B's lead |
|---|---|---|---|---|
| Start | 4 | 20 | 24 | 16 |
| After 1 RTT | 5 | 21 | 26 | 16 |
| Before the cut | 16 | 32 | 48 | 16 |
| After the cut | 8 | 16 | 24 | 8 |
Compare the first and last rows. The total has returned to exactly the same value, twenty-four. The allocation has changed: A has gained four packets of window, and B has lost four. Neither sender explicitly transferred anything to the other. Equal additions followed by proportional cuts produced that redistribution.
There is a subtlety here. Halving did not change the ratio at the instant of the cut: 16:32 and 8:16 are both 1:2. Additive growth had already improved A's relative share, taking it from one sixth of the total to one third. The cut shrank the absolute gap and made room for another round of equal additions. The two operations cooperate; neither observation by itself explains a complete cycle.
Watch the motion in two different spaces
A time plot shows the familiar teeth: slow growth, sudden cuts. It is good for seeing that the senders keep moving. It is less direct about how they divide the total. For that, put A's window on a horizontal axis and B's on a vertical axis. One point now describes the entire allocation.
In this second picture, equal windows lie on the diagonal B = A. The congestion threshold lies on the descending line A + B = 48. An additive step moves one packet right and one packet up. A halving step moves halfway toward the origin. These directions follow straight from the update rules; the geometry is another way to execute the same arithmetic.
First inspect the completed first cycle below. The allocation moves from (4, 20) to (16, 32), then inward to (8, 16). Reset and step through it if needed. Next, use “Next cut” a few times. Watch the path approach the equal-window diagonal while the time plot keeps its full-height total-window teeth. Both plots use fixed scales.
After the second cut, the windows are 10 and 14. After the third, 11 and 13. The first post-cut point was (8, 16); these later points move toward (12, 12). The upper endpoints move toward (24, 24). The zigzag narrows toward the fairness diagonal, but its journey up and down that diagonal does not disappear.
This is the source of the apparent paradox in “AIMD converges.” Looking at the allocation, something is clearly getting closer to equal sharing. Looking at the time plot, the process is clearly not settling at a single pair of windows. We need a more precise statement than “the algorithm converges.”
Choose quantities that separate the two questions
So far we have tracked A and B because those are what the senders control. For the proof, it helps to track the two things we care about instead: how much window exists in total, and how unequally it is divided. Write the individual windows as wA and wB, and define:
d = |wB − wA| (absolute gap)
This change of variables is useful because the rules treat the two quantities differently. During one additive step, the total gets both new packets. In the difference, the equal additions cancel:
d′ = |(wB + 1) − (wA + 1)| = d
During a shared halving, both quantities halve:
d′ = |wB/2 − wA/2| = d/2
Now follow a whole cycle. Growth replenishes the total that the previous cut removed. It never replenishes the gap. Every cut therefore removes half the remaining gap, with nothing in between undoing that progress.
The initial gap is sixteen. After m shared cuts:
The half is not essential to this reasoning. If every shared decrease multiplies both windows by a fixed factor β between zero and one, the gap is multiplied by β each time. Equal additive increments still preserve it. With indefinitely repeated events, dm = βmd0 tends to zero. Equal increments and a common shrinking factor are the assumptions doing the work.
Notice what information the proof uses and what the implementation uses. We, as observers, calculate a total and a gap. The modeled sender does not need to know either one. It adds to its own window and responds to a congestion signal. A global property can emerge from local updates even when the variables that make the proof easy are not locally available.
Fairness can converge while the system keeps cycling
In this example, every cut returns the total from 48 to 24. Every increase phase takes it from 24 back to 48. No matter how many cycles have passed, the total will still visit both values. It cannot have a single limit in time.
The gap behaves differently. It is constant between cuts and halves at each cut, so it tends to zero even when we look throughout the whole trajectory. Sample the windows immediately after cuts and their sum is always 24; combine that with a vanishing gap and the pair tends to (12, 12). Sample immediately before cuts and the pair tends to (24, 24).
Equal windows also mean equal approximate rates here because the RTTs are equal and fixed. That qualification matters. We have not proved that arbitrary real connections obtain equal throughput, or that the link has some universal utilization percentage. Inferring utilization from our window threshold alone would require a queue and service model we have not supplied.
The continuing oscillation makes sense given the original predicament. This rule has no instruction saying “you found the final allocation; stop.” Without a congestion event it keeps probing, even when the flows are already equal. Fairness corrects the imbalance between senders; it does not switch off their search for available capacity.
Why not increase proportionally too?
Return to the original windows, 4 and 20. Increasing by the same percentage might seem equally reasonable. Both senders would follow the same rule, and a larger sender could expand faster in absolute terms. Keep the shared halving, but replace equal additions with common multiplicative growth.
Watch one excursion to the same threshold. To grow a total of 24 to 48, common multiplicative growth must double both windows. The allocation moves from (4, 20) to (8, 40). Halving sends it straight back to (4, 20). However many smaller proportional steps make up that outward trip, B keeps five times A's window.
Scale, then halve: (4, 20) → (8, 40) → (4, 20)
On the allocation plot, proportional growth would go outward along the ray from the origin through the current point. Proportional backoff comes inward along that same ray. It never changes direction toward the fairness diagonal. In algebra, any common positive factor k cancels from the ratio:
The flaw in a tempting proof is now visible. “Each congestion event halves the gap” remains true, but the growth phase doubles it again in this excursion. A shrinking error at one operation does not establish convergence over repeated cycles. You must account for the operations between the snapshots.
That is the useful asymmetry of AIMD: equal additions improve the smaller flow's relative position, and proportional cuts reduce the absolute disparity while opening room to repeat. Merely treating both senders by an identical rule is insufficient. The mathematical form of that rule decides whether their unequal starting positions persist.
Change the clock, and find the broken step
We made the RTTs equal so that “one packet per RTT” meant the same growth over the same interval for both flows. Suppose A's RTT is now 50 ms and B's is 100 ms. Continue to idealize each as adding one packet per its own RTT, and begin an interval with B's window larger.
Over 100 ms, which equality in the gap proof stops being true? Try naming the failed cancellation before predicting who benefits. This is more informative than memorizing that real networks are complicated.
Follow the changed clock
Over 100 ms, A adds two packets while B adds one. The signed lead of B changes from wB − wA to (wB + 1) − (wA + 2) = wB − wA − 1. Equal additions no longer cancel over equal wall-clock time. The absolute gap is not generally constant during growth.
There is another change: equal windows would no longer imply equal rates. With these fixed RTTs, an equal window corresponds to twice the approximate rate for A. The earlier argument therefore cannot establish equal-throughput fairness. Deriving a new allocation requires a model of the unequal growth and congestion events; changing this assumption does not entitle us to guess one from the old proof.
Real TCP adds further state and timing: acknowledgments arrive asynchronously, queues affect RTT, losses need not reach both flows together, and timeout recovery differs from our single shared cut. The example earns a narrower but valuable result: it shows how two different update operations can contract an allocation imbalance without eliminating persistent motion.
When another congestion-control algorithm claims convergence, you now have a way in. Identify what each sender changes, trace a whole feedback cycle, and ask which error contracts across that cycle. Then separate the allocation claim from the claim about the trajectory in time. The sawtooth alone cannot answer either question.