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.
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 wire shared this way, played as well as it can possibly be played, carries a frame in about 37 slots out of 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 amount of cleverness gets past it.
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, 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.
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.
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.