The idea: many stations, one medium, no referee
When several computers share one wire or one radio channel, only one of them can talk at a time. If two talk at once, their signals mix and both frames are lost: a collision. A multiple access protocol is the rule every station follows to decide when to send. There is no central referee, so the rule must work with what each station can see on its own.
The page has four stations A, B, C, D on one cable. Pick a protocol and a traffic pattern, and the same frames play out on the cable (top) and on a timeline (bottom). A frame lasts 10 ticks; one tick is 64 bit times, so a frame is 640 bits = 80 bytes.
Pure ALOHA: just send
ALOHA was built at the University of Hawaii in 1971 to link islands by radio. Its rule is as simple as it gets: send a frame as soon as you have it. If it collides (no acknowledgement comes back), wait a random time and send it again. On this page a sender retries with probability 1/2 in each frame time, so it waits K frame times with K = 0, 1, 2 … less and less likely.
A collision needs only a small overlap. In Demo 1, A sends at t = 0 and B at t = 7. They overlap for 3 ticks, and both 10-tick frames are lost: 20 ticks of channel time are wasted for 3 ticks of overlap. A frame is safe only if no one else starts in the frame time before it or during it, a vulnerable period of 2 frame times.
Slotted ALOHA: send only at a slot boundary
Slotted ALOHA cuts time into slots of one frame time, and a station may start only at the beginning of a slot. Frames then overlap completely or not at all, and only frames from the same slot can collide, so the vulnerable period is 1 frame time. In Demo 2 the same arrivals as Demo 1 cause no collision: B arrives at t = 7, waits for the slot at t = 10, and both frames get through. In Demo 3 A arrives at 2 and B at 7: both wait for the slot at 10 and collide there. The price is a short wait and a shared clock.
Why 18 % and 37 %
Let G be the number of frames (new and retried) that try to start per frame time, and assume they arrive at random (a Poisson process). A frame gets through if no other frame starts in its vulnerable period. The chance of that is e−2G for pure ALOHA and e−G for slotted ALOHA, so the useful throughput S (good frames per frame time) is:
| Protocol | Throughput S | Best load G | Best S |
|---|---|---|---|
| pure ALOHA | G · e−2G | 0.5 | 1/(2e) ≈ 0.184 = 18.4 % |
| slotted ALOHA | G · e−G | 1 | 1/e ≈ 0.368 = 36.8 % |
Past the peak, more traffic means more collisions, more retries and less useful work. Even at best, two thirds of a slotted ALOHA channel is wasted on collisions and empty slots. The demos are small, so their own numbers (the "useful" line under the timeline) are not these averages.
Listen first: CSMA
On a cable, a station can hear whether someone else is sending. CSMA (carrier sense multiple access) adds one rule: do not start while the cable is busy. Classic Ethernet is 1-persistent: keep listening and start the moment the cable goes quiet. In Demo 4, A sends at 0. C gets a frame at 5, hears A's signal and waits. A stops at 10, but its last bit needs 3 ticks to reach C, so C starts at 13. No collision, and the channel is 87 % useful.
Listening cannot prevent every collision, because a signal takes time to travel. Here the cable is τ = 4 ticks long from A to D. D can start at t = 3 even though A started at 0, because A's first bit only reaches D at t = 4.
CSMA/CD: detect, jam, back off
CSMA/CD (with collision detection) is what shared Ethernet did. A station listens while it sends. If it hears another signal, it stops at once, sends a short jam signal (32 bits) so that every station notices, and backs off. In Demo 5, D hears A at t = 4 and A hears D at t = 7: instead of two full frames, the collision wastes 8 ticks of A and 2 of D.
The wait uses binary exponential backoff. The unit is the slot time, 512 bit times (8 ticks here). After the n-th collision of the same frame, the station picks K at random from 0 to 2min(n, 10) − 1 and waits K slot times:
| Collision n | 1 | 2 | 3 | 4 | … | 10–15 | 16 |
|---|---|---|---|---|---|---|---|
| K from | 0..1 | 0..3 | 0..7 | 0..15 | … | 0..1023 | give up |
Two stations that picked the same K collide again, but the window doubles each time, so a tie gets less likely. In Demo 6, B and D both wait for C, both start as soon as C's signal has passed, and collide. Both pick K = 1, collide again, and then B picks 3 from 0..3 while D picks 0, so D goes first. The window adapts to the load without anyone knowing how many stations there are.
With collision detection the waste per collision is short (at most a round trip plus the jam), so CSMA/CD can use most of the cable. A common estimate of its efficiency is 1 / (1 + 5a), where a is the propagation delay divided by the frame time: short cables and long frames come close to 100 %.
Why Ethernet needs 64-byte frames
A sender can only notice a collision while it is still sending. In the worst case the other station is at the far end and starts just before the first bit reaches it. Its signal then needs another τ to come back. So the sender must still be sending 2τ after it started: a frame must last at least 2τ.
Ethernet fixed 2τ at 512 bit times (51.2 µs at 10 Mb/s), which limits the cable length (about 2.5 km with repeaters), and made 512 bits = 64 bytes the minimum frame. Shorter data is padded. In Demo 5 the 80-byte frame lasts 10 ticks, longer than 2τ = 8, and A hears the collision at 7. In Demo 7 the same timing with a 48-byte frame (6 ticks) ends at 6: A hears nothing, counts the frame as sent, and never retries, but D's signal garbled it at B, C and D. At 100 Mb/s the slot stays 512 bits, so the cable got 10 times shorter; half-duplex Gigabit Ethernet stretched short frames to 512 bytes (carrier extension).
| pure ALOHA | slotted ALOHA | CSMA/CD | |
|---|---|---|---|
| Starts | at once | at the next slot | when the cable is quiet |
| Collision found | no ACK, after the frame | no ACK, after the slot | while sending |
| Wasted per collision | up to 2 frame times | 1 slot | ≤ 2τ + jam |
| Best throughput | 18.4 % | 36.8 % | close to 100 % for long frames |
Today: switches and full duplex
Modern Ethernet has no shared cable. Each computer has its own full-duplex link to a switch port, so nothing can collide and CSMA/CD is switched off; see Hub vs Switch vs Router for collision domains and How Ethernet Switches Forward Frames. Radio still shares the air, but a radio cannot hear while it sends, so Wi-Fi avoids collisions instead of detecting them: see Wi-Fi CSMA/CA. Slotted ALOHA lives on in the random access channel that phones use to ask a cell tower for a first connection.
What the page leaves out
- Real frame sizes (up to 1518 bytes), the preamble, the 96-bit gap between frames and the exact jam length: times are rounded to ticks of 64 bit times.
- The ALOHA acknowledgement and its timeout: here a sender simply knows at the end of its frame.
- Propagation delay in ALOHA mode, and the Poisson load model behind the 18 % / 37 % curves; the demos use a few fixed frames.
- Non-persistent and p-persistent CSMA, and the capture effect (one station winning many backoffs in a row).
- Hubs and repeaters, the 5-4-3 rule, and the signal-level way a transceiver detects a collision.