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.

Two time lines. Pure ALOHA: a frame from t0 to t0 plus T is hit by any other frame that starts between t0 minus T and t0 plus T, a vulnerable period of 2T. Slotted ALOHA: frames start only at slot boundaries, so only a frame in the same slot can hit it, a vulnerable period of T.
Pure ALOHA: any frame that starts within one frame time on either side hits yours. Slots cut that window in half.

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:

ProtocolThroughput SBest load GBest S
pure ALOHAG · e−2G0.51/(2e) ≈ 0.184 = 18.4 %
slotted ALOHAG · e−G11/e ≈ 0.368 = 36.8 %
Graph of throughput S against offered load G from 0 to 3. The slotted ALOHA curve G times e to the minus G peaks at 0.368 when G is 1. The pure ALOHA curve G times e to the minus 2G peaks at 0.184 when G is 0.5. Both fall towards 0 as the load grows.
More traffic helps only up to a point; past the peak, collisions eat the channel.

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 n1234…10–1516
K from0..10..30..70..15…0..1023give 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τ.

Space-time diagram with A on the left, D on the right and time going down. A starts at 0; its signal reaches D at 4. D starts at 3, just before; D's signal reaches A at 7. Left: an 80-byte frame lasts until 10, so A is still sending at 7 and detects the collision. Right: a 48-byte frame ends at 6, before D's signal arrives at 7, so A never detects the collision.
The collision comes back to A at 2τ. A frame shorter than that has already ended, so its sender never hears it.

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 ALOHAslotted ALOHACSMA/CD
Startsat onceat the next slotwhen the cable is quiet
Collision foundno ACK, after the frameno ACK, after the slotwhile sending
Wasted per collisionup to 2 frame times1 slot≤ 2τ + jam
Best throughput18.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.

On the mind map

Open the Networking mind mapNetworkingLayers & links: frames on one local networkLayers & linksIP & routing: packets hop between networksIP & routingCore services: address, name and timeCore servicesTCP, UDP & sockets: end to end between two portsTCP, UDP & socketsHTTP & TLS: what a browser does per requestHTTP & TLSAPIs & push: how apps talk to serversAPIs & pushProxies & edge: boxes in the middle of the pathProxies & edgeContainers: virtual networks from Linux partsContainersReal-time media: voice and video over UDPReal-time mediaSecurity at the edge: filter traffic at the borderSecurity at the edgeProtocol layersProtocol layerseach layer wraps the one above in a headerHub vs switch vs routerHub vs switch vs routerL1 repeats, L2 learns MACs, L3 routes IPVLANsVLANs802.1Q tag splits one switch into LANsARPARPbroadcast who-has IP, reply with the MACCRCCRCXOR division remainder catches bit errorsInternet ChecksumInternet ChecksumSum + NOT sum = 0xFFFF; blind to swapsWi-Fi CSMA/CAWi-Fi CSMA/CAlisten, random backoff, wait for the ACKALOHA and CSMA/CDFrame must last 2τ to hear a collisionCellular Reuse and HandoverCellular Reuse and HandoverMargin + timer: no ping-pong, no dropOpen the Networking mind mapNetworkingframes on one local networkLayers & linksProtocol layersProtocol layerseach layer wraps the one above in a headerHub vs switch vs routerHub vs switch vs routerL1 repeats, L2 learns MACs, L3 routes IPVLANsVLANs802.1Q tag splits one switch into LANsARPARPbroadcast who-has IP, reply with the MACCRCCRCXOR division remainder catches bit errorsInternet ChecksumInternet ChecksumSum + NOT sum = 0xFFFF; blind to swapsWi-Fi CSMA/CAWi-Fi CSMA/CAlisten, random backoff, wait for the ACKALOHA and CSMA/CDFrame must last 2τ to hear a collisionCellular Reuse and HandoverCellular Reuse and HandoverMargin + timer: no ping-pong, no drop
This page on the Networking mind map · 62 pages in 10 branches · open it to see the whole map and test yourself in recall mode.