Backoff
One wire, many machines, and nobody in charge of who speaks. The rule that sorts it out is a guess at a number nobody is ever told.
New to networks? Start here
A message that takes time and may not arrive
Two computers in one room are far apart by a processor's standards. A message crossing between them takes time you cannot argue with, and across a continent that floor is set by the speed of light in glass.
Worse, it may arrive after a message sent later, or arrive twice, or never arrive at all, and the sender is not told which. There is no moment at which both ends know the same thing. Every machine in this topic is a way of getting useful work done anyway, without that guarantee, and the ones that look overcomplicated are usually the ones that stopped pretending.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
The machine for this idea on its own is Race, if you would rather press it than read about it.
The wire
slots 166collisions 27idle 107delivered 32 of 32dropped 0worst tries 7
All 32 frames got through in 166 slots, 19.3% of them carrying one, against a ceiling of 37.4% for any scheme where the stations guess.
1 Listen: the wire is quiet, so send
2 Collide: someone else thought so too, and both signals are ruined
3 Wait: a random number of slot times, from a window that doubles each try
4 Give up: at sixteen attempts the frame is dropped and the layer above is told
The same wire, three policies, right now
Where a fixed window stops working
Checked when this page loaded: 6 combinations of station count and transmit probability, each measured over 40,000 slots and compared with N p (1-p) to the N-1 computed separately. 6 of 6 agreed to within 0.02; the widest gap was 0.0027.
Nobody is in charge, and that is the design
There is no arbiter on this wire. No station is granted a turn, no station asks permission, and no station knows how many others exist. Metcalfe and Boggs called it statistical arbitration
, and were plain about the shape of it: control is completely distributed among stations
, and a transmission that runs into another is aborted and rescheduled by whoever sent it.
Everything hard about that is in the word rescheduled.
The ceiling, which is worse than you would guess
Suppose every station tosses a coin each slot and transmits with probability p. Exactly one wins the slot with probability N p (1−p) to the N−1. That is largest when p is one over N, and at that point it is (1−1/N) to the N−1, which settles down to about 0.368 as N grows.
So a contention slot, played as well as it can possibly be played, ends with exactly one winner about 37 times in a hundred. The other 63 are empty or ruined. That is not a flaw in anyone's algorithm; it is the price of nobody being in charge, and no choice of p gets past it.
It is not a ceiling on what the wire carries, and this page used to say it was. Metcalfe and Boggs separate the two in the paper cited below: section 6.1 computes exactly this quantity and calls it the acquisition probability, and once a station has acquired the ether it transmits a whole packet, which is very much longer than the slot it takes to detect a collision. Their efficiency calculation is a different expression, and they say plainly that “with carrier detection, Ether efficiency increases with increasing packet length”. Slots are the unit here because this page has no frames and no time; 37 per cent is the lottery, not the throughput.
The number nobody knows
The best p is one over the number of stations, and that is exactly the thing a station cannot see. Nothing tells it how many others are on the wire, and the answer changes every time a machine is switched on.
A retry window is a guess at that number. Pick one and freeze it and you have hard-coded an assumption about how busy the wire will ever get. Doubling the window after each collision is the same guess made at run time, by each station, using the only evidence it has: how many times it has just failed. Metcalfe and Boggs put the rule in one sentence — a mean retransmission interval of one slot to begin with, and on each collision an interval of random length with a mean twice that of the previous interval
.
It does not fail by getting slower
The machine above measures both policies at several loads, and the result is not the tidy one. A fixed window of sixteen is faster than doubling at moderate load, sometimes twice as fast, because doubling backs off further than it needs to and leaves the wire idle.
Then the load rises past what the fixed window assumed, and it does not slow down. It starts throwing frames away. Every station keeps colliding, keeps hitting the sixteen-attempt limit, and keeps dropping the frame, and nothing on the wire reports an error because from the wire's point of view nothing went wrong. The doubling window is slower and loses nothing at any load tested.
That is the trade in this finite burst, and it is worth stating plainly because the usual summary gets it backwards: exponential backoff does not make a shared wire fast. It makes it survive. What is shown here is a fixed number of stations all wanting the wire at once, which is not a stability proof for indefinite arrivals: Aldous showed in 1987 that binary exponential backoff can be unstable in an idealised infinite-user model at any positive arrival rate.
Two dates and an unsettled claim
Robert Metcalfe wrote the memo at Xerox PARC on 22 May 1973 that proposed dropping the name ALTO ALOHA Network in favour of the ether, and that date is the one usually given as Ethernet's birthday. The mechanism was not published until Metcalfe and Boggs wrote it up for Communications of the ACM in July 1976, which is where every quotation on this page comes from.
There is also a prior claim. Simon Lam is credited with adaptive backoff driven by a station's own collision count, work dated to 1973 and published with Leonard Kleinrock in 1975. The scanned paper has no text layer and could not be read here, so this page repeats the claim without having checked it, and says so rather than dropping it.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| 6 of 6 station-and-probability combinations match the closed form to within 0.02, worst gap 0.0027 | yes | each measured over 40,000 slots and compared with N p (1-p)^(N-1) computed separately; if they disagreed the simulator would be the thing that is wrong |
| played perfectly the wire is idle or ruined about 63% of the time, approaching 1 - 1/e | yes | 1/e is 0.3679 against a computed 0.3681; this is the ceiling and no policy beats it |
| with 12 stations no transmit probability out of 199 beats 1/N | yes | the optimum is derived in the prose and searched for here, which are two different routes to the same number |
| of 192 stations, doubling gets all 192 through, a fixed window loses 21 and retrying at once delivers 0 | yes | the fixed window occupies a larger share of its slots (21.9% against 15.4%) and that is not a virtue: it finishes sooner because it gave up |
| a fixed window drops 55 stations at 64 and 0 at 8, where doubling drops 0 | yes | 802.3 gives up after 16 attempts, and a window that does not widen runs out of them |
What is real here, and what is not
There is no wire
No cable, no volts, no propagation delay, no carrier to detect, no frames of any actual size, and no time. Slots are counted, not measured, and a slot here is a turn rather than the round-trip interval the paper defines. What is modelled is the decision about when to try again, because that part is arithmetic.
The jam signal is described and not shown
A real station that detects a collision jams the wire briefly, so that every other station in the collision is forced to notice it too. The 1976 paper calls this collision consensus enforcement and gives the reason: without it, the station that would otherwise be last to detect the collision might not detect it at all, and would send something that looks like a good packet and is not. Nothing above simulates that, because there is no signal here to jam.
Everyone arrives at once, which is the worst case and not the usual one
Every station starts with one frame ready in the first slot. Real traffic arrives spread out, mostly finds a quiet wire, and never gets near this. The worst case is the interesting one for a backoff rule, but do not read these numbers as what a network does on a Tuesday.
The constants are from the standard, and the paper is not the standard
Giving up after sixteen attempts, and the window ceasing to double after ten, are IEEE 802.3, which arrived in 1983. The experimental Ethernet Metcalfe and Boggs describe in 1976 ran at 2.94 megabits on a kilometre of coaxial cable and is not the same thing. This page uses the standard's numbers with the paper's rule, which is a blend, and that is the sort of thing a ledger exists to say.
The fixed window of sixteen is a choice, and it moves the cliff
A larger fixed window survives more stations and wastes more slots at low load; a smaller one is quicker when the wire is quiet and falls over sooner. Nothing about sixteen is special. That is the argument, in fact: any fixed number is right for one load and wrong for the others.
The randomness is a seed, so the page can be argued with
The generator is deterministic and seeded, so the numbers printed here are the numbers a test gets. The reseed button moves the seed on by one rather than reaching for the clock. The claim that the model itself is sound is checked separately, against a closed form nothing here simulates.
Sources
- Metcalfe and Boggs, Ethernet: Distributed Packet Switching for Local Computer Networks, CACM, July 1976
- Computer History Museum on the memo of 22 May 1973
- Secondary, and used as such: Exponential backoff, for the IEEE 802.3 constants and the Lam attribution. The constants belong to the standard, which names the sixteen-attempt limit and the truncation at ten. IEEE sells 802.3 rather than publishing it, so what is cited here is a secondary account of a document this page has not read, and that is a debt rather than a decision.