Random Access Protocols · CSMA and CSMA/CD · Computer Networking Interactive

Listen to the channel before you transmit, and keep listening while you transmit, so that a collision is both rarer and cheaper than it was under ALOHA.

Words you will meet

Carrier sensing — listen before speaking, and wait if somebody else is transmitting.
Collision detection — keep listening while speaking, and stop the moment you hear interference.
Channel propagation delay — how long a signal takes to travel from one node to another.
Space-time diagram — a picture whose across-axis is position and whose down-axis is time.
Binary exponential backoff — after each collision, draw the wait from a set twice as large.
Bit time — how long one bit takes on this link, so 512 bit times is a different delay on a faster one.

Why this matters

Section 6.3.2 ended with a hard number. Slotted ALOHA cannot get past 37 per cent of the channel, and pure ALOHA cannot get past 18.

The reason is that neither protocol pays any attention to the channel. A node transmits without checking, and carries on transmitting even after its frame has already been destroyed.

This page fixes both halves of that, and the payoff is large: a real Ethernet runs at around 98 per cent.

It is also where section 6.1 earns its point about the link layer living in hardware. An adapter that transmits and listens at the same time is not something software can fake.

Two rules from polite conversation

The book gets both ideas from human beings, and states them as two rules for polite conversation.

Listen before speaking. If someone else is speaking, wait until they are finished. · If someone else begins talking at the same time, stop talking.

The first is carrier sensing: a node listens to the channel before transmitting. If another node’s frame is on the channel, it waits until it detects no transmissions for a short time, and then begins.

The second is collision detection: a transmitting node listens to the channel while it is transmitting. If it detects another node interfering, it stops, waits a random time, and repeats the sense-and-transmit-when-idle cycle.

Together they name the two protocols. CSMA (Carrier Sense Multiple Access) has the first rule. CSMA/CD (Carrier Sense Multiple Access with Collision Detection) has both.

So why do collisions still happen?

Here is the obvious objection. If every node listens first, and refuses to transmit whenever it hears somebody, how can two frames ever collide?

The answer needs a different kind of picture. In a space-time diagram the across-axis is not time but position along the wire, and time runs downwards. A transmission is then a cone, spreading out from its sender in both directions at the speed of the medium.

Figure 6.12 — two CSMA nodes with colliding transmissions

propagation delay across the bus0.250collision detection (Figure 6.12)

Node	Started	Sensed another signal	Stopped	Frame time used
B	0.060	0.265	0.480	100%
D	0.140	0.185	0.560	100%

D sensed an idle channel and began, but a signal was already on the way and had not yet arrived. Carrier sensing was not wrong — it was out of date.

B begins at t₀ and its signal spreads both ways at a finite speed. At t₁ node D listens, hears nothing, and begins — because B’s signal has not reached D yet. Tick the box to turn on collision detection and get Figure 6.13. Then drag the propagation delay down and watch the collision become impossible.

Positions and start times are chosen to match the book’s figure; the shape of every cone is then computed from the propagation delay, not drawn. Both figures come from one simulation, so the only difference between them really is the collision-detection setting.

Follow node B. It senses the channel at t₀, hears nothing, and starts. Its bits begin travelling both ways along the cable, but they travel at a finite speed.

Now follow node D. At t₁ it senses the channel — and the channel at D really is idle, because B’s signal has not arrived there yet. So D obeys the protocol exactly, and transmits. A moment later B’s signal reaches D, and the two interfere.

In plain words

D did nothing wrong. Carrier sensing was not disobeyed and it did not malfunction. It simply answered a question about the past.

A node can only sense the channel where it is standing. “Idle here” is always older news than “idle everywhere”, by exactly the time the signal needs to arrive.

This is why the book says the channel propagation delay plays a crucial role. Drag the slider down and the collision disappears entirely: with a short enough delay, B’s signal reaches D before D senses, so D hears a busy channel and waits. Drag it up and the danger returns.

The longer this propagation delay, the larger the chance that a carrier-sensing node is not yet able to sense a transmission that has already begun at another node in the network.

Collision detection: stop wasting the rest of the frame

In Figure 6.12 nobody performs collision detection. B and D both keep going and transmit their frames in full, even though both frames were destroyed within the first moments.

Tick the collision-detection box on the diagram above to get Figure 6.13. It is the same scenario in every other respect, and the difference is easy to see: a short time after each node detects the interference, it aborts.

Notice which node finds out first. D detects before B does, even though D started later. B’s signal was already most of the way to D when D began, while D’s signal still has the whole distance to travel back.

The table under the diagram prints how much of each frame time was actually used. With detection off it is 100 per cent for both nodes, all of it wasted.

The adapter’s five steps

The book summarizes CSMA/CD (Carrier Sense Multiple Access with Collision Detection) from the point of view of the adapter — the hardware on the node, from section 6.1.

CSMA/CD from the adapter’s point of view

1 · Take the datagram, build a framestep 1 of 5

The adapter gets a datagram from the network layer, prepares a link-layer frame, and puts the frame in its buffer.

Read all steps as text

1 · Take the datagram, build a frame — The adapter gets a datagram from the network layer, prepares a link-layer frame, and puts the frame in its buffer.
2 · Sense, then send — If the adapter senses no signal energy entering from the channel, it starts transmitting. If it senses the channel busy, it waits until the energy stops, and then transmits.
3 · Keep listening while sending — While it transmits, the adapter monitors the channel for signal energy coming from other adapters. This is the part ALOHA never did.
4 · Finish, or abort — If the whole frame goes out with no other energy detected, the adapter is done. If it does detect energy from another adapter, it aborts — it stops transmitting immediately.
5 · Wait a random time, then go back to step 2 — After aborting, the adapter waits a random amount of time and returns to sensing. How long it waits is the subject of the rest of this page.

Step 5 says random, and the reason is worth stating plainly. If two nodes collided and then both waited the same fixed time, they would collide again, and again, forever.

Choosing how long to wait

So the wait must be random. But drawn from what interval?

In plain words

The book states the dilemma as a pair of failures:

If the interval is large and few nodes collided, they all wait a long time while the channel sits idle.
If the interval is small and many nodes collided, their random choices are likely to be nearly the same, so they collide again.

What we want is an interval that is short when few nodes are colliding and long when many are. But no node knows how many others collided.

Binary exponential backoff solves this without anyone counting anything. A node does not need to know how many others are competing — it uses its own collision count as the estimate. Colliding repeatedly is itself the evidence that the channel is crowded.

Binary exponential backoff — the set K is drawn from

Collisions so far	K is drawn from	Choices	Longest wait at 100 Mbps






The exponent is capped at 10, so the set stops growing. Without the cap an unlucky frame could be made to wait for hours.

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

After n collisions, K is picked at random from {0, …, 2ⁿ − 1}, and the node waits K × 512 bit times. The set doubles each time, which is what "binary exponential" names. Click any cell for the reasoning.

How long does a node wait?

What each symbol means

n — collisions this frame has already suffered (collisions)
K — the random number drawn from the set (none — a count)
512 bit times — the time to put 512 bits on this link (seconds)

Read aloud: Pick a random number from a set that doubles after every collision, and wait that many blocks of 512 bits.

Collisions so farcollisionsLink rateMbps

Longest possible wait5.12 µs

after 1 collision, K comes from {0, ..., 2^1 - 1} = {0, ..., 1}
one bit time on this link = 1 / 100 Mbps, so 512 bit times = 5.12 µs
longest wait = K x 512 bit times = 1 x 5.12 µs = 5.12 µs
mean wait = 2.56 µs, since K is uniform over the set

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

Push the collision count past 10 and the answer stops growing — that is the cap. Change the link rate and the same rule gives a different real delay, because a bit time is shorter on a faster link.

Two details are easy to miss.

The cap at ten collisions stops the interval growing forever. And the count belongs to the frame, not the node: each time a node prepares a new frame it runs the algorithm afresh, ignoring any collisions in the recent past. So a node with a new frame can sneak in a successful transmission while several other nodes are still waiting out their backoff.

The same algorithm is used in Ethernet and in DOCSIS (Data-Over-Cable Service Interface Specifications) cable networks.

How much of the channel does this win back?

The book defines the efficiency of CSMA/CD (Carrier Sense Multiple Access with Collision Detection) as the long-run fraction of time during which frames are being transmitted without collisions, when many nodes each have many frames to send. It states an approximation without deriving it:

$\text{Efficiency} = \frac{1}{1 + 5\,d_{prop}/d_{trans}}$

CSMA/CD efficiency

What each symbol means

dprop — the longest time signal energy takes to travel between two adapters (seconds)
dtrans — the time to transmit a maximum-size frame (seconds)

Read aloud: The share of time the channel spends carrying frames that are not colliding, once many nodes are busy.

Propagation delay dpropµsFrame time dtransµsChannel rate RMbps

Efficiency98.0%

5 x dprop / dtrans = 5 x 5.00 µs / 1.20 ms = 0.0208
efficiency = 1 / (1 + 0.0208) = 0.9796, which is 98.0%
dprop is tiny next to dtrans, so almost nothing is wasted — this is the case Ethernet is designed for

Throughput9.80 Mbps

throughput = R x efficiency = 10.0 Mbps x 0.9796 = 9.80 Mbps
compare with slotted ALOHA on the same channel, which cannot beat 37% of R

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

The defaults are the book’s 10 Mbps Ethernet: a maximum-size frame takes about 1.2 ms, and the propagation delay across the cable is a few microseconds. Drag dprop up towards dtrans and watch the channel fall apart.

Both limits make sense on their own. As $d_{prop}$ approaches zero the efficiency approaches 1, because colliding nodes abort immediately and waste nothing. As $d_{trans}$ grows large it also approaches 1, because a frame that grabs the channel then holds it for a long time, doing productive work.

With the book’s own numbers — a few microseconds of propagation against a 1.2 ms frame — the answer is about 98 per cent. Compare that with slotted ALOHA’s ceiling of 37 per cent on the very same channel.

Everyday picture

A conversation across a large, echoing hall. You listen, hear silence, and start speaking — but someone at the far end started a moment ago and their voice has not reached you yet. You both keep going until you hear each other, then both stop.

Where the picture stops. Sound is slow enough that this really happens to people. On a hundred metres of Ethernet cable the delay is under a microsecond, so the equivalent almost never happens. That is exactly why the efficiency is 98 per cent and not 37. The picture explains the mechanism, but it badly overstates the scale.

Check yourself

0 of 8 answered

1.Every node performs carrier sensing and refuses to transmit when it hears another transmission. So why do collisions still happen?
2.predictOn the space-time diagram, you drag the propagation delay down towards zero. What happens to the collision?
3.What does adding collision detection to CSMA actually buy?
4.predictIn Figure 6.13, B starts first and D starts later. Which node detects the collision first?
5.After a node's frame has suffered 3 collisions, what set is K drawn from, and how long is the longest wait on 100 Mbps Ethernet?
6.Why is the backoff interval made to grow with the number of collisions, instead of being a fixed size?
7.predictA node has just suffered 6 collisions on one frame. It then prepares a completely new frame. What backoff does the new frame start with?
8.predictThe CSMA/CD efficiency is 1/(1 + 5·dprop/dtrans). What happens as dprop approaches zero?

What to remember

Carrier sensing is listening before transmitting. Collision detection is listening while transmitting. Collisions still happen because a node senses the channel only where it is, so “idle” is always slightly out of date.
Collision detection does not prevent collisions. It makes them cheaper, by not transmitting the rest of a frame that is already ruined.
Binary exponential backoff: after n collisions, draw K from {0, …, 2ⁿ − 1} and wait K × 512 bit times, with n capped at 10. Efficiency is $1/(1 + 5 d_{prop}/d_{trans})$ — about 98 per cent for a real Ethernet, against ALOHA’s 37.