Random Access Protocols · Slotted ALOHA and ALOHA · Computer Networking Interactive

Let every node transmit at the full rate whenever it likes, accept that frames will sometimes collide, and have each collided node wait a random time before trying again.

Words you will meet

Random access protocol — transmit at the full rate R, and back off after a collision.
Active node — a node that has frames waiting to send.
Slotted ALOHA — time is cut into slots and every node starts only at a slot boundary.
Successful slot — a slot in which exactly one node transmitted.
Efficiency — the long-run fraction of slots that are successful, when many nodes always have frames to send.
Pure ALOHA — the same idea with the slots taken away.

Why this matters

Section 6.3.1 built a list of four properties a good protocol should have, and channel partitioning failed the first one. A node was stuck at R/N even when nobody else wanted the channel.

Random access fixes exactly that. A node transmits at the full rate R, always. The price is collisions, and this page is about how expensive that price turns out to be.

The answer is a number worth remembering: at best, 37 per cent. It is the reason Ethernet does not use ALOHA, and the reason section 6.3.2-csma exists.

Transmit, collide, wait, try again

A random access protocol has no master and no schedule. Every transmitting node sends at the full channel rate R. When two nodes send at once, both frames are destroyed, and both nodes must send again.

The important detail is the word random. A node that has collided does not retransmit at once. It waits a delay it chooses itself, at random, independently of every other node. That independence is the whole mechanism.

In plain words

If two people start speaking together and both immediately start again, they collide again. And again. Waiting a random time each is what eventually lets one of them go first.

The book puts it exactly this way: one node may pick a delay small enough to “sneak its frame into the channel without a collision”.

There are hundreds of random access protocols in the research literature. This page covers the two oldest — the ALOHA protocols — and the next page covers the family that Ethernet actually uses, CSMA (Carrier Sense Multiple Access) .

Slotted ALOHA

The simplest of them all. It begins with five assumptions.

What slotted ALOHA assumes

Assumption	What it buys

Cells marked ⓘ have an explanation — click to read it.

Five assumptions, from book page 466. The first three describe the channel; the last two are what the nodes must be able to do.

Given those, the rules at each node are short.

Slotted ALOHA at one node

A fresh frame arrivesstep 1 of 4

The node waits for the start of the next slot, then transmits the whole frame inside that slot. It does not listen first, and it does not ask anyone.

Read all steps as text

A fresh frame arrives — The node waits for the start of the next slot, then transmits the whole frame inside that slot. It does not listen first, and it does not ask anyone.
No collision — The frame is through. Nothing more is needed, and the node can pick up the next frame if it has one.
A collision — Someone else transmitted in the same slot. The node knows before the slot ends, and both frames are gone.
Toss a biased coin — In each following slot the node retransmits with probability p, and stays quiet with probability 1 − p. It keeps tossing until the frame gets through.

Notice what slotted ALOHA already does well, measured against section 6.3.1’s list. A single active node transmits continuously at the full rate R. The protocol is fully decentralized, because each node detects its own collisions and decides for itself when to retry. And it is extremely simple.

It fails only the fourth property, and only a little: the slots have to be synchronized across all the nodes.

Watching the slots

Here is the book’s own figure. Three nodes, nine slots.

Figure 6.10 — three nodes, nine slots

slot 9 of 9

Slots so far: 9	Counted	Fraction
S — Successful	3	33.3%
E — Empty	3	33.3%
C — Collision	3	33.3%

Press "Next slot" and watch it unfold. All three nodes transmit in the first slot, so all three frames are destroyed. Each node then retries with probability p. Node 2 gets through in slot 4, node 1 in slot 8, node 3 in slot 9 — and each stops as soon as it succeeds.

Every slot is one of three things, and the letters under the axis name them. C is a collision, E is an empty slot, and S is a successful slot. Only the S slots do any work.

The two ways a slot is wasted are worth separating. A collision wastes the slot because too many nodes transmitted. An empty slot wastes it because none did — every node tossed its coin and every coin said “skip”. The probability that saves you from the first problem causes the second.

The same protocol, run for longer

slot 40 of 40

p (each node tries, each slot)0.13

Slots so far: 40	Counted	Fraction	Formula predicts
S — Successful	15	37.5%	39.3%
E — Empty	16	40.0%	34.4%
C — Collision	9	22.5%	26.4%

The formula column is the book’s N·p·(1−p)^N−1 for a success, (1−p)^N for an empty slot, and the rest for a collision. A short run wanders; press “New run” a few times and watch it settle.

Every node tosses its biased coin in every slot. Move p and watch the balance shift: too small and the channel sits empty, too large and almost every slot is a collision. The best value is p = 1/N, and the button sets it for you.

This is the simplified protocol the book derives its efficiency from, not the full one. Here a node transmits with probability p in every slot, whether the frame is fresh or has already collided. The real protocol sends a fresh frame immediately and only applies p after a collision.

How much of the channel does useful work

To get a number, the book simplifies the protocol a little. Assume every node always has a frame ready, and transmits in each slot with probability p — fresh frames and retransmissions alike.

Now count. A slot succeeds when exactly one node transmits:

one particular node transmits, with probability $p$
and the other $N-1$ nodes all stay quiet, with probability $(1-p)^{N-1}$
so that node succeeds with probability $p(1-p)^{N-1}$
and any of the $N$ nodes could be the lucky one, giving $Np(1-p)^{N-1}$

Efficiency against p

N — nodes sharing the channel20.0

At 0.400 (move the pointer over the plot to read it anywhere):

slotted ALOHA:0.000
pure ALOHA:0.000

The curve is the fraction of slots that carry exactly one frame. Move N and watch the peak slide left and settle at a height of 1/e. Slotted ALOHA peaks at 0.37; pure ALOHA, with no slots at all, peaks at exactly half that.

The curve has a clear peak. Push p too low and the nodes are too polite, so slots go empty. Push it too high and they all talk at once. The best value is $p^* = 1/N$ , and as N grows the height of that peak settles at $1/e = 0.37$ .

In plain words

Even when everything is tuned perfectly, only about 37 slots in every 100 carry a frame. The other 63 are thrown away.

And the split of those wasted slots is the surprising part: about 37 go empty and only about 26 are collisions. Idleness wastes more of the channel than collisions do.

Where the slots go

N — nodes sharing the channel20.0

At 0.300 (move the pointer over the plot to read it anywhere):

successful:0.007
empty:0.001
collision:0.992

The same channel, split three ways. At the best p the three curves cross close together: about 37 per cent of slots succeed, about 37 per cent go empty, and about 26 per cent are collisions. Two thirds of the channel does no work.

The disappointment

The book makes the cost concrete with a small story. A network administrator buys a 100 Mbps slotted ALOHA system for a large number of users and hopes to move, say, 80 Mbps through it.

The channel really can carry any single frame at 100 Mbps. But in the long run it will deliver less than 37 Mbps.

What the channel really carries

What each symbol means

R — the rate of the shared channel (bits per second)
N — the number of nodes sharing it (nodes)
p* — the best transmission probability, 1/N for slotted (none — a probability)

Read aloud: Multiply the link rate by the fraction of slots that succeed, and that fraction can never beat 37 per cent.

Channel rate RMbpsNodes Nnodes

Best case, slotted ALOHA36.9 Mbps

best p is p* = 1/N = 1/200 = 0.0050
efficiency = N x p* x (1 - p*)^(N-1) = 0.3688, which is 36.9%
throughput = R x efficiency = 100 Mbps x 0.3688 = 36.9 Mbps
and this is the BEST case — it needs every node to use exactly p*, and it tends to 1/e = 36.8% as N grows

Best case, pure ALOHA18.5 Mbps

best p is p* = 1/(2N-1) = 1/399 = 0.0025
efficiency = N x p* x (1 - p*)^2(N-1) = 0.1846, which is 18.5%
throughput = R x efficiency = 100 Mbps x 0.1846 = 18.5 Mbps
dropping the slots costs exactly half the throughput, because the vulnerable period doubles

Change any number above and the arithmetic re-runs, carrying the units through.

The book’s own warning, made adjustable. An administrator buys 100 Mbps and hopes for 80. Both answers are far below it, and the second is half the first.

Pure ALOHA: what the slots were worth

The first ALOHA protocol had no slots at all. It was fully decentralized, and the price of that is the point of this section.

In pure ALOHA a node transmits a fresh frame the moment it arrives, with no waiting for a boundary. If that frame collides, the node retransmits it with probability p as soon as it has finished sending the collided one. Otherwise it waits one frame time and tries again.

Now ask when a frame survives. Node i starts its frame at time $t_0$ and finishes at $t_0 + 1$ , taking one frame time as the unit.

Figure 6.11 — interfering transmissions in pure ALOHA

When the other node starts its framet₀ − 0.55

Both frames are lost. The other frame starts inside the window, so it overlaps the start of node i's frame.

Drag the slider to move the other node’s frame. Node i’s frame is safe only while the other frame starts outside the shaded stretch — and that stretch is two frame times long.

Two things must hold, not one:

no other node may start in $[t_0 - 1, t_0]$ , or it would still be transmitting when node i begins
no other node may start in $[t_0, t_0 + 1]$ , or it would begin while node i is still transmitting

Each has probability $(1-p)^{N-1}$ , so a frame survives with probability $p(1-p)^{2(N-1)}$ . The exponent doubles. Taking the same limits gives a maximum efficiency of $1/(2e)$ — about 18 per cent, exactly half of slotted ALOHA.

In plain words

Slots halve the danger. With slots, a frame is only in danger from nodes starting in its own slot — one frame time. Without them, it is in danger for two frame times: the one before it started, and the one while it is sending.

Double the danger, half the throughput. That is what synchronizing the nodes was worth.

Everyday picture

Two people agree to speak only on the minute. If they both start at 10:00, they clash — but someone starting at 10:00:30 cannot clash with either, because nobody is allowed to start then. That is slotted ALOHA.

Now take the clock away. Anyone may start at any moment, and your sentence is ruined by anyone who starts talking during it or who was already talking when you began.

Where the picture stops. A person can hear that someone else is already speaking and stop. Neither ALOHA protocol can: a node pays no attention to the channel before or during its own transmission. Listening first is the next page’s idea, and it is what CSMA (Carrier Sense Multiple Access) adds.

Where this came from

Norm Abramson was an engineer with a passion for surfing, which brought him to the University of Hawaii in 1969. Hawaii is many mountainous islands, so land-based networks were hard to install and operate.

When not surfing, he thought about doing packet switching over radio. His network had one central host and several secondary nodes scattered across the islands, on two frequency bands: one down from the host, one up to it. Collisions on the upstream channel were unavoidable, because the secondary hosts transmitted without coordination — and that observation produced pure ALOHA.

In 1970, funded by ARPA (Advanced Research Projects Agency) , he connected ALOHAnet to the ARPAnet. It was the first radio packet network. It also inspired Bob Metcalfe, who a few years later modified the protocol into CSMA/CD (Carrier Sense Multiple Access with Collision Detection) and the Ethernet LAN (Local Area Network) .

Check yourself

0 of 7 answered

1.What does a random access protocol give a node that channel partitioning could not?
2.Two nodes collide. Why does each wait a random delay rather than retransmitting at once?
3.predictIn slotted ALOHA with a large number of nodes, everything is tuned to the best p. What fraction of slots carry a frame?
4.predictAn administrator buys a 100 Mbps slotted ALOHA system for a large number of users and expects about 80 Mbps of aggregate throughput. What do they get?
5.Node i starts a frame at t₀ in pure ALOHA. Which other transmissions destroy it?
6.Pure ALOHA's maximum efficiency is exactly half of slotted ALOHA's. What is the reason?
7.What can neither ALOHA protocol do, that the next section's protocols add?

What to remember

A random access protocol lets every node transmit at the full rate R, and cleans up the collisions afterwards. After a collision each node waits a random, independently chosen delay, and that independence is what eventually lets one through.
Slotted ALOHA’s efficiency is $Np(1-p)^{N-1}$ , maximised at $p^* = 1/N$ , and its ceiling is 1/e ≈ 37 per cent. At that ceiling 37 per cent of slots are empty and 26 per cent are collisions — idleness wastes more than collisions do.
Pure ALOHA drops the slots and doubles the vulnerable period, so its ceiling is 1/(2e) ≈ 18 per cent, exactly half. Neither protocol listens to the channel, and that is what the next page fixes.