When many nodes share one channel, two of them speaking at once destroys both messages. So a protocol has to decide who transmits, and the simplest answer is to cut the channel into fixed shares.
Words you will meet
-
Multiple access problem multiple access problem Simple Deciding who gets to talk, and when. Precise The problem of coordinating the access of many sending and receiving nodes to a shared broadcast channel. Every multiple access protocol falls into one of three classes: channel partitioning, random access, or taking turns. introduced in ch. 6 — open in glossary — deciding who gets to talk, and when.
-
Collision collision Simple Two nodes transmit at once and both frames are ruined. Precise When more than one node transmits into a broadcast channel at the same time, the frames become inextricably tangled at every receiver. All the frames involved are lost and the channel is wasted for the duration. introduced in ch. 6 — open in glossary — two nodes transmit at once and every frame involved is destroyed.
-
Multiple access protocol — the rules that coordinate transmission into a shared channel.
-
Channel partitioning protocol channel partitioning protocol Simple Cut the channel into fixed shares, one per node. Precise A class of multiple access protocol that divides the channel among the nodes — by time (TDM), by frequency (FDM) or by code (CDMA). It eliminates collisions and is perfectly fair, but limits a node to R/N even when it is the only one with anything to send. introduced in ch. 6 — open in glossary — cut the channel into fixed shares, one per node.
-
TDM (Time-Division Multiplexing) Time-Division Multiplexing Gives each connection the whole link, but only during its own repeating time slot. introduced in ch. 1 , FDM (Frequency-Division Multiplexing) Frequency-Division Multiplexing Gives each connection its own frequency band on the link, all of the time. introduced in ch. 1 , CDMA (Code Division Multiple Access) Code Division Multiple Access A channel-partitioning protocol that gives each node a different code rather than a time slot or a frequency, so several may transmit at once. Chapter 7 covers it. introduced in ch. 6 — cut it by time, by frequency, or by code.
Why this matters
Section 6.1 divided every link into two kinds and said that coordinating access to a point-to-point link is trivial. This is the other kind.
The problem is not a networking curiosity. Any shared medium has it — a radio band, a cable running past a hundred houses, a room full of people. Forty years of research and thousands of papers have gone into it, and the answers all fall into three families.
This page covers the first family and the framework for judging all three. The framework is the part to keep: sections 6.3.2 and 6.3.3 are scored against exactly the four properties written down here.
The problem
When any node transmits a frame, the channel broadcasts it and each of the other nodes receives a copy. In practice hundreds or even thousands of nodes can communicate directly over one broadcast channel.
Four nodes, one channel. Nothing here is broken and nobody is at fault — the difficulty is built into sharing.
Read all steps as text
- One node transmits, and everybody hears it — When any node transmits a frame, the channel broadcasts it and each of the other nodes receives a copy. In practice hundreds or even thousands of nodes can communicate directly over one broadcast channel.
- Two transmit at once, and both are destroyed — The signals of the colliding frames become inextricably tangled together. Typically no receiver can make sense of any of them, so ALL the frames involved are lost — not just one — and the channel does no useful work for the whole collision interval.
- Which is the whole subject of section 6.3 — If many nodes want to transmit frequently, many transmissions collide and much of the channel is wasted. Coordinating the transmissions of the active nodes is the job of the multiple access protocol. Thousands of papers have been written on it over forty years, and every one of them fits into three categories.
Two symbols in this section mean something new
R is a link rate now. In section 6.2 R was the
CRC (Cyclic Redundancy Check) Cyclic Redundancy Check The error-detection code used in link-layer adapters. Sender and receiver agree on a generator G; the sender appends bits so the whole pattern divides by G with no remainder under modulo-2 arithmetic.
introduced in ch. 6 check bits — a bit pattern appended to data. From here on R is the rate of the
shared channel, in bits per second, and it turns up in ratios such as R/N.
The tell is the unit: if R is being divided, or measured in bits per second, it
is a rate.
N is a count again, and it is the fourth thing this book has called N. It
was the number of router ports in section 4.2.2, the number
of TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control.
introduced in ch. 1 flows in section 4.2.4, and the set
of nodes of a graph from section 5.2 onwards. Here it is the
number of nodes sharing a broadcast channel, an ordinary count that you divide
by.
Everyday picture
The book’s own analogy, and it uses two. A cocktail party, where many people gather in a large room and the air is the shared medium. Or a classroom, where a teacher and students share the same one.
Humans have evolved an elaborate protocol for it. The book lists some of the rules:
Give everyone a chance to speak · Don’t speak until you are spoken to · Don’t monopolize the conversation · Raise your hand if you have a question · Don’t interrupt when someone is speaking.
Every one of those is a multiple access protocol, and each one trades the same things off. “Raise your hand” is polling. “Don’t interrupt” is carrier sensing. “Give everyone a chance” is a taking-turns protocol.
Where the picture stops. Two people talking at once are merely hard to follow, and a listener can usually recover one of the voices. On a broadcast channel the signals become inextricably tangled and all the frames are lost, not just the quieter one.
What a good protocol would look like
| # | What is wanted |
|---|---|
Cells marked ⓘ have an explanation — click to read it.
Written down before any protocol is examined, so that every protocol in this section can be scored against them. Keep them: sections 6.3.2 and 6.3.3 are graded on exactly these.
In plain words
Properties 1 and 2 sound like the same thing and they are not.
Property 2 is about fairness when the channel is busy: with M nodes wanting to send, none should be starved.
Property 1 is about waste when it is quiet: if only one node has anything to say, it should get everything, because nobody else wants it.
A protocol can satisfy either one alone quite easily. The whole difficulty of this section is that satisfying both, without a central authority, is hard.
Channel partitioning
| Channel partitioning§6.3.1 — this page | Random access§6.3.2 | Taking turns§6.3.3 | |
|---|---|---|---|
| The idea | |||
| Property 1 · alone, a node gets R | |||
| Property 2 · M active nodes get R/M each | |||
| Collisions | |||
| Examples |
Cells marked ⓘ have a reason behind them — click to read it.
Dozens of protocols have been implemented across many link technologies, and just about any of them belongs to one of these three. This section covers the first column; the next two sections cover the others.
The first family is the one section 1.3.2 already built, for a
different purpose. Time-division multiplexing divides time into frames and
each frame into N slots, one per node. Frequency-division multiplexing divides
the channel into N bands of R/N each, one per node.
FDM: circuit 2 owns 4 kHz of the spectrum and uses it all the time — a thin slice, always.
TDM: circuit 2 owns the whole link — but only during 1 slot in every 4.
The same widget section 1.3.2 used for circuit switching, because these are the same two techniques. Press play: the FDM band is lit the whole time, and the TDM slot is lit one turn in four. Watch node 2 in particular — the book follows the same one.
”Frame” means two different things on this page
A TDM time frame is a repeating cycle of N slots. A link-layer frame is the unit of data an adapter sends, which section 6.1 defined and which this whole chapter otherwise means by the word.
The book notices the clash and handles it by saying “packet” for the link-layer unit throughout this subsection only. This page keeps the book’s own wording so that the two can be told apart, and returns to frame meaning the link-layer unit from section 6.3.2 onwards.
A third partitioning protocol is CDMA (Code Division Multiple Access) Code Division Multiple Access A channel-partitioning protocol that gives each node a different code rather than a time slot or a frequency, so several may transmit at once. Chapter 7 covers it. introduced in ch. 6 . Where TDM assigns time slots and FDM assigns frequencies, CDMA assigns a different code to each node, and each node encodes its data bits with its own code. If the codes are chosen carefully, several nodes can transmit at the same time and each receiver still recovers its sender’s bits correctly, despite the interference.
CDMA has been used in military systems for a long time, for its anti-jamming properties, and is now in widespread civilian use, particularly in cellular telephony. Because it is so tightly tied to wireless channels, the book saves the technical details for chapter 7.
What partitioning costs
TDM is appealing: it eliminates collisions and is perfectly fair. Each node
gets a dedicated rate of R/N during every frame time. FDM shares both that
advantage and the drawbacks below.
And there are two drawbacks, both of which are the same drawback seen from different sides.
A node is limited to R/N even when it is the only node with data to send.
A node must always wait for its turn, again even when it is the only one with anything to send.
At 12.0 (move the pointer over the plot to read it anywhere):
- R — the whole channel:10.0 Mbps
- what the book asks for: R/M:0.833 Mbps
- what partitioning gives: R/N:1.3 Mbps
The channel is shared by N nodes in total; M of them currently have something to send. Drag N and watch the gap at the left-hand edge — that gap is the whole objection to channel partitioning.
In plain words
Look at the left-hand edge of that plot, where M = 1.
The green line is what the book asked for: one active node, so it gets the whole
channel. The red line is what partitioning gives it: R/N, because its share was
decided in advance and the other N − 1 shares sit empty.
Drag N up and the gap widens. With 12 nodes sharing a 10 Mbps channel, a node that is alone still gets 833 kbps and watches 9.2 Mbps go unused.
The book’s version: imagine the partygoer who is the only one with anything to say — and imagine everyone wants to hear it. TDM would still make them wait their turn.
Check yourself
Check yourself
0 of 6 answered1.Two nodes on a broadcast channel transmit at the same instant. What happens to their frames?
2.The book lists four properties a good multiple access protocol should have. Which one does channel partitioning fail?
3.predictTwelve nodes share a 10 Mbps channel using TDM. Eleven of them have nothing to send. What rate does the twelfth get?
4.How does CDMA differ from TDM and FDM?
5.In this section the book writes "packet" where the rest of the chapter says "frame". Why?
6.In this section, what do R and N stand for?
What to remember
- Broadcast means every node hears every transmission, and can transmit too. When frames collide, all of them are lost, and the channel does no useful work for the whole interval.
- Four properties define a good multiple access protocol: full rate R when alone, about R/M when M are active, decentralized, and simple.
- Every multiple access protocol is one of three kinds: channel partitioning, random access, or taking turns. Partitioning eliminates collisions and is perfectly fair — and fails property 1, because a node gets R/N even when it is alone.