A third family of protocols gives each node a turn, so that collisions become impossible and no slot is wasted on a node that has nothing to say.
Words you will meet
-
Taking-turns protocol taking-turns protocol Simple Everyone speaks in an agreed order. Precise A class of multiple access protocol that gives nodes the channel in turn. The book covers polling, where a master node invites each node to transmit, and token passing, where a special frame circulates and only its holder may send. introduced in ch. 6 — open in glossary — nodes transmit in an agreed order, never at once.
-
Polling protocol polling protocol Simple A master node invites each node to speak in turn. Precise One node is designated master and polls the others in round-robin order, telling each that it may transmit up to some maximum number of frames. It eliminates collisions and empty slots, at the cost of a polling delay and a single point of failure. Bluetooth is an example. introduced in ch. 6 — open in glossary — a master node master node Simple The node that tells the others when they may transmit. Precise In a polling protocol, the one node designated to poll the others in round-robin order. It removes collisions entirely, but it is a single point of failure: if the master node fails, the entire channel becomes inoperative. introduced in ch. 6 — open in glossary invites each node to transmit in turn.
-
Polling delay polling delay Simple The time it takes to be told you may transmit. Precise The amount of time required to notify a node that it can transmit. It is why a polling protocol does not give a single active node the full rate R: the master must still poll each inactive node in turn between that node's turns. introduced in ch. 6 — open in glossary — the time it takes to be told you may transmit.
-
Token-passing protocol token-passing protocol Simple Hold the token to speak, then pass it on. Precise A small special-purpose frame, the token, is exchanged among the nodes in a fixed order, and only the node holding it may transmit. There is no master, but the failure of one node, or the loss of the token, can break the channel. introduced in ch. 6 — open in glossary — a token token Simple A small special frame that gives its holder permission to transmit. Precise A small, special-purpose frame exchanged among the nodes in a fixed order. A node holds on to the token only if it has frames to transmit, and otherwise forwards it immediately. If a node neglects to release it, a recovery procedure must put it back in circulation. introduced in ch. 6 — open in glossary circulates, and only its holder may transmit.
-
CMTS (Cable Modem Termination System) Cable Modem Termination System The head-end device that turns the analog signals of many cable modems back into digital data. introduced in ch. 1 — the box at the cable head end that every cable modem cable modem Simple The device in a home that connects it to the cable network. Precise The device at a residence that attaches it to a cable access network. Several thousand cable modems typically share a path to one cable modem termination system at the cable headend. They share the upstream channel, so their transmissions can collide; the downstream channel has a single sender and therefore no multiple access problem. introduced in ch. 6 — open in glossary talks to.
-
Mini-slot minislot Simple A small unit of upstream time that the CMTS hands out. Precise In DOCSIS, each upstream channel is divided into intervals of time, each containing a sequence of mini-slots during which cable modems may transmit. Most are explicitly assigned to one modem so no collision is possible; a dedicated set is left for mini-slot-request frames and is contended for by random access. introduced in ch. 6 — open in glossary — a small unit of upstream time, handed out by a MAP message map message Simple The CMTS control message saying who may transmit when. Precise A control message the CMTS sends on a downstream channel specifying which cable modem may transmit during which mini-slot, for the interval of time named in the message. Because the assignment is explicit, the CMTS can guarantee there are no colliding transmissions in an assigned mini-slot. introduced in ch. 6 — open in glossary .
Why this matters
Two properties, from section 6.3.1. One active node should get the full rate R. And M active nodes should each get about R/M.
Channel partitioning has the second but not the first. ALOHA and CSMA (Carrier Sense Multiple Access) Carrier Sense Multiple Access Listen before you speak: a node senses the channel and transmits only when it is idle. Collisions still happen, because propagation takes time. introduced in ch. 6 have the first but not the second — see section 6.3.2-csma. This page is the third attempt, aiming at both.
Then section 6.3.4 does something better than summarise. It takes one real network — cable Internet access — and shows all three families working inside it at once.
Polling
One node is designated the master node. It polls each of the others in round-robin order, telling each in turn that it may transmit up to some maximum number of frames. The master knows a node has finished by observing the lack of a signal on the channel.
No collisions and no empty slots. This is polling at its best, and it is why the efficiency beats any random access protocol.
Click any arrow to see what that message says and why it is sent.
Switch between the two runs. The first shows why polling is efficient; the second shows the price. A single active node does not get the full rate R, because the master keeps asking everybody else.
Read this diagram as text
- Master sends you may send up to 2 frames to Node 1. The master node polls each node in round-robin order, telling it a maximum number of frames.
- Node 1 sends frame to Master.
- Node 1 sends frame to Master.
- Master sends you may send up to 2 frames to Node 2. The master knows node 1 has finished by observing the lack of a signal on the channel.
- Node 2 sends frame to Master.
- Node 2 sends frame to Master.
- Master sends you may send up to 2 frames to Node 3.
- Node 3 sends frame to Master.
Lifelines, left to right: Master (server), Node 1 (host), Node 2 (host), Node 3 (host).
Polling eliminates the collisions and empty slots that plague random access, and that alone lifts the efficiency well past ALOHA’s ceiling. But it has two drawbacks, and the second is serious.
In plain words
The polling delay. Being told you may transmit takes time. If only one node is active it still does not get the full rate R, because the master must poll every inactive node in turn between that node’s turns. Switch the diagram to the second run and count the wasted messages.
The master node is a single point of failure. If it fails, the entire channel becomes inoperative. Not degraded — inoperative.
A wrong cross-reference in the book
Page 475 says: “The Bluetooth protocol, which we will study in Section 6.3, is an example of a polling protocol.”
The claim about Bluetooth is right, but the section number is not. Bluetooth is section 7.3.6, “Personal Area Networks: Bluetooth”, on book page 560. Section 6.3 is the section this sentence is already inside, so as printed it points at itself.
Token passing
The second taking-turns protocol has no master node at all.
A small, special-purpose frame called a token is exchanged among the nodes in a fixed order. Node 1 always sends it to node 2, node 2 to node 3, and node N back to node 1.
When a node receives the token it holds on to it only if it has frames to transmit. Otherwise it forwards the token immediately. A node that does have frames sends up to a maximum number and then passes the token on.
Node 1 always sends the token to node 2, node 2 to node 3, and node N back to node 1. Only the holder may transmit.
Click any arrow to see what that message says and why it is sent.
Token passing is decentralized and highly efficient. Its failure modes are the price: one broken node, or one token that is never released, and the channel stops.
Read this diagram as text
- Node 1 sends token to Node 2. A small, special-purpose frame. Holding it is permission to transmit.
- Node 2 sends token to Node 3. Node 2 has nothing to send, so it forwards the token immediately.
- Node 3 sends token to Node 4.
- Node 4 sends token to Node 1. Node N always sends the token back to node 1, closing the circle.
Lifelines, left to right: Node 1 (host), Node 2 (host), Node 3 (host), Node 4 (host).
Token passing is decentralized and highly efficient. Its problems are failures rather than inefficiency. The failure of one node can crash the entire channel. And if a node neglects to release the token, some recovery procedure must be invoked to get a token back into circulation.
Many token-passing protocols have been built, including FDDI (Fiber Distributed Data Interface) Fiber Distributed Data Interface A token-passing standard for a fibre ring, named by the book alongside IEEE 802.5 token ring as one of the many token-passing protocols built — each of which had to solve the same failure and token-loss problems. introduced in ch. 6 and the IEEE (Institute of Electrical and Electronics Engineers) Institute of Electrical and Electronics Engineers The body whose 802 committee standardises Ethernet and WiFi. introduced in ch. 1 802.5 token ring protocol. Each had to solve these problems, and others.
The three families, side by side
| Channel partitioningTDM, FDM, CDMA | Random accessALOHA, CSMA/CD | Taking turnspolling, token passing | |
|---|---|---|---|
| One active node gets the full rate RProperty 1 | |||
| M active nodes each get about R/MProperty 2 | |||
| Decentralized — no single point of failureProperty 3 | |||
| SimpleProperty 4 | |||
| Are collisions possible? |
Cells marked ⓘ have a reason behind them — click to read it.
The whole of section 6.3 in one grid. Click any cell for the reasoning. Notice that no column is all good — this is a set of trade-offs, not a ranking.
No column is all good. That is the honest summary of section 6.3: three families, each buying one property by giving up another.
Cable access: all three families in one network
Now for something better than a summary. A cable access network uses aspects of every one of the three classes at the same time.
Recall from section 1.2.1 that a cable access network connects several thousand residential cable modems to a CMTS (Cable Modem Termination System) Cable Modem Termination System The head-end device that turns the analog signals of many cable modems back into digital data. introduced in ch. 1 at the cable network headend. DOCSIS (Data-Over-Cable Service Interface Specifications) Data-Over-Cable Service Interface Specifications The link-layer protocol of cable Internet access; version 3.0 defines 1.2 Gbps downstream. introduced in ch. 1 specifies the architecture and its protocols.
DOCSIS uses frequency-division multiplexing to separate downstream, from the CMTS to the modems, from upstream, from the modems back. Each direction is a broadcast channel.
The book’s Figure 6.14, walked through one idea at a time. The mini-slots are drawn schematically — a real interval holds far more of them than will fit here.
Read all steps as text
- Two channels, split by frequency — DOCSIS uses frequency-division multiplexing to separate downstream, from the CMTS to the modems, from upstream, from the modems back. Each direction is a broadcast channel.
- Downstream has no multiple access problem — Only the CMTS transmits into the downstream channel, so nothing can collide there. Every modem on that channel receives every frame.
- Upstream is the interesting one — Several thousand cable modems share one upstream channel, so their transmissions can collide. The rest of this page is about how DOCSIS stops that.
- The upstream channel is cut into mini-slots — Each upstream channel is divided into intervals of time, each holding a sequence of mini-slots. This part is TDM-like, and it is the third family showing up inside a cable network.
- The MAP message hands out the assignments — The CMTS sends a MAP message down the downstream channel naming which modem may transmit in which mini-slot, for the interval it covers. Because the assignment is explicit, an assigned mini-slot cannot collide.
The asymmetry is the key to the whole design. Downstream there is exactly one sender, the CMTS, so there is no multiple access problem at all. Upstream, several thousand modems share one channel, and collisions can happen.
Granting turns, and asking for one
The CMTS explicitly grants permission to individual modems to transmit during specific mini-slots, using a MAP message sent downstream. Since mini-slots are explicitly allocated, the CMTS can ensure there are no colliding transmissions in one.
But that raises a question the book asks directly: how does the CMTS know which modems have data to send in the first place?
Modem A asks for room in a request mini-slot, the CMTS grants it in the next MAP message, and A sends its data in a mini-slot nobody else may use.
Click any arrow to see what that message says and why it is sent.
The second run is the part worth dwelling on. Ethernet detects a collision by listening; a cable modem cannot listen at all, so it deduces the collision from a message that never mentions it.
Read this diagram as text
- Modem A sends mini-slot request to CMTS. Sent in one of the mini-slots dedicated to requests. These are contended for — this part of DOCSIS is a random access protocol.
- CMTS sends MAP: A may use mini-slot 7 to Modem A. Broadcast on the downstream channel. Every modem receives it, and each acts only on its own assignment.
- Modem A sends upstream data frame to CMTS. Sent in the assigned mini-slot. No other modem is permitted there, so no collision is possible.
Lifelines, left to right: Modem A (host), Modem B (host), CMTS (server).
Modems send mini-slot-request frames in a special set of mini-slots reserved for that purpose. Those requests are transmitted in a random access manner, so they may collide with each other.
In plain words
Here is the part worth dwelling on. A cable modem can neither sense whether the upstream channel is busy nor detect collisions. It has neither of the abilities the previous page was about.
So it infers. If the next downstream control message contains no response to its requested allocation, the modem concludes that its request collided. Then it backs off, using the same binary exponential algorithm as Ethernet.
Ethernet learns about a collision by listening. A cable modem learns about one from a message that never mentions it.
When there is little traffic on the upstream channel, a modem may simply send data frames in slots nominally assigned for requests, and skip the wait for an assignment altogether.
Every family, in one network
Read the list below slowly. 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 separates the channels and 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 divides each upstream channel into mini-slots — both from section 6.3.1. The MAP messages are a taking-turns mechanism. And the requests that ask for them are contended for, which is random access.
| Mechanism | Which family | What it does here |
|---|---|---|
| When the upstream channel is quiet, a modem may skip the request step entirely and send data in slots nominally reserved for requests. | ||
Cells marked ⓘ have an explanation — click to read it.
The book’s closing point: FDM, TDM, random access, and centrally allocated time slots, all inside one network. Click a cell for the numbers.
A cable access network thus serves as a terrific example of multiple access protocols in action — FDM, TDM, random access, and centrally allocated time slots all within one network!
Check yourself
Check yourself
0 of 7 answered1.Which property do taking-turns protocols have that ALOHA and CSMA do not?
2.predictIn a polling network of 20 nodes, only one node has frames to send. Does it get the full rate R?
3.A node in a token-passing network receives the token and has nothing to send. What does it do?
4.Both polling and token passing avoid collisions. What do they each risk instead?
5.Why does the downstream direction of a cable network have no multiple access problem?
6.predictTwo cable modems send mini-slot-request frames in the same request mini-slot. How does either one find out?
7.Which multiple access families does a cable access network use?
What to remember
- Taking turns aims at both of the first two properties: a turn at the full rate R, and a fair share when many nodes are busy. Neither polling nor token passing can collide, because only one node has permission at a time.
- Polling has a master node, so it costs a polling delay and stops if the master fails. Token passing has no master, but one broken node or one unreleased token stops the channel just as completely.
- DOCSIS uses all three families at once: FDM for the channels, TDM-like mini-slots, MAP messages granting turns, and random access for the requests. A cable modem cannot sense the channel, so it infers a collision from a grant that never arrives.