Multiple access protocols
A point-to-point link has one sender and one receiver, so it needs no rules. A broadcast link has many nodes on the same medium: a shared cable, a radio channel, a cable-TV line. If two nodes transmit at once, the signals overlap and both frames are lost. That is a collision. A multiple access protocol decides who may transmit and when.
An ideal protocol has four properties, and no real one has all four:
- A single active node can use the full channel rate
R. - When
Mnodes are active, each gets aboutR/M. - No central coordinator is required, and no clock synchronization.
- It is simple.
Protocols fall into three families, each trading these properties differently.
| Family | Idea | Strength | Weakness |
|---|---|---|---|
| Channel partitioning | Give each node a fixed slice of time, frequency, or code | No collisions, predictable | One node can never use more than R/N, even when others are idle |
| Random access | Anyone transmits at full rate, and collisions are repaired | One active node gets all of R | Wasted capacity under load |
| Taking turns | Nodes transmit in an agreed order, or when granted permission | No collisions, high efficiency | Coordination overhead, a single point of failure |
Channel partitioning
Section titled “Channel partitioning”Time-division multiplexing (TDM) divides time into frames of N slots and gives each node one slot per frame. Frequency-division multiplexing (FDM) splits the channel into N frequency bands of R/N each. Code-division multiple access (CDMA) gives each node a distinct code, and receivers separate overlapping signals by applying the matching code. CDMA was central to 3G cellular and is mostly replaced by OFDM-based schemes in newer systems.
All three eliminate collisions and share fairly under full load. All three waste capacity when traffic is bursty: an idle node’s slot or band goes unused, and a lone busy node is limited to R/N. They suit traffic with steady rates, such as voice circuits and broadcast TV, and appear inside many larger systems rather than as the only mechanism.
Random access
Section titled “Random access”A node with a frame sends it at the full rate R. If a collision occurs, each involved node waits a random delay before retrying, so they are unlikely to collide again.
Slotted ALOHA assumes time is divided into frame-sized slots and all nodes are synchronized. A node transmits a new frame at the start of the next slot. After a collision it retransmits in each following slot with probability p. Pure ALOHA drops the slots and transmits immediately, at the cost of a doubled vulnerability window: any transmission starting within one frame time before or after overlaps.
| Protocol | Best-case efficiency | Why |
|---|---|---|
| Slotted ALOHA | about 37% | Many slots are empty or collided |
| Pure ALOHA | about 18% | The vulnerable window is twice as long |
The derivation is in the deep dive. The lesson for practice is that uncoordinated sharing tops out well below the channel rate.
CSMA and CSMA/CD
Section titled “CSMA and CSMA/CD”Carrier sense multiple access adds etiquette: listen before talking, and wait if the channel is busy. Collisions still happen, because a signal takes time to propagate. Two nodes far apart can each sense idle and start within the same short window, and the longer the cable, the wider that window.
CSMA/CD (collision detection) adds the second half: keep listening while sending, and abort immediately if another signal appears. This saves the time of finishing a doomed frame. After an abort the node waits using binary exponential backoff:
- After the nth collision on a frame, pick a random integer
Kfrom0to2^n - 1(withncapped at 10). - Wait
K x 512bit times, then sense again.
The window grows with every collision, which means light traffic recovers fast and heavy traffic spreads out. Classic Ethernet gave up on a frame after 16 attempts.
CSMA/CD was the access method for coax bus and hub-based Ethernet. Modern Ethernet uses full-duplex switched links with one sender per direction, so there is nothing to collide and CD is switched off. Wireless links cannot detect a collision while sending, so they use CSMA with collision avoidance instead.
What it means in practice
Section titled “What it means in practice”On a switched network, collisions should be absent. If counters show them, the cause is a configuration fault:
ethtool eth0 | grep -iE 'speed|duplex|auto'# Speed: 1000Mb/s# Duplex: Full# Auto-negotiation: on
ethtool -S eth0 | grep -iE 'collision'# tx_late_collisions: 0A non-zero late collision count means a duplex mismatch: one end believes it is half-duplex and transmits while the other end is sending. The usual cause is one side forced to a fixed speed and duplex while the peer tries to auto-negotiate. Set both ends to auto-negotiate, or both to the same fixed setting.
Taking turns
Section titled “Taking turns”Taking-turns protocols try to get the efficiency of coordination without the waste of collisions.
Polling. A controller asks each node in order whether it has data, and lets it send up to a limit. This removes collisions and empty slots, but a poll adds delay, a lone busy node cannot reach the full rate R because the controller still polls the idle nodes, and the controller is a single point of failure. Bluetooth works this way, with a master polling its piconet.
Token passing. A small frame called the token circulates among nodes in a fixed order. Only the holder may transmit, up to a limit, and then it passes the token on. There is no central controller, but a failed node or a lost token breaks the ring until recovery procedures regenerate it. Token Ring and FDDI used this approach. They lost to Ethernet on cost and simplicity.
Case study: cable internet
Section titled “Case study: cable internet”Cable access uses all three families in one system, which makes it a good example of how the pieces combine. A cable modem termination system (CMTS) at the provider headend connects to thousands of modems over a shared coaxial network. The standard is DOCSIS.
| Direction | Mechanism | Class |
|---|---|---|
| Downstream | The CMTS is the only sender on its channels, so nothing collides. Each channel is a separate frequency band | FDM, single sender |
| Upstream data | The upstream channel is divided into time mini-slots. The CMTS broadcasts a MAP message saying which modem may use which mini-slots next | TDM with central grants |
| Upstream requests | Modems that want bandwidth send small request frames in designated mini-slots, and may collide | Random access with backoff |
A modem cannot sense the upstream channel, so it infers a collision when its request is not granted in the next MAP, then backs off with binary exponential backoff and tries again.
sequenceDiagram
participant M as Cable modem
participant C as CMTS
M->>C: Request mini-slot (may collide)
Note over M: No grant in next MAP?<br/>Assume collision, back off
C->>M: MAP: modem may send in slots 40-47
M->>C: Data in the granted slots (no collision)
Summary
Section titled “Summary”| Single node rate | Fairness under load | Collisions | Needs | |
|---|---|---|---|---|
| Partitioning (TDM, FDM) | R/N | Equal | None | Fixed assignment |
| Random access (ALOHA, CSMA) | R | Degrades with load | Yes | Nothing central |
| Taking turns (polling, token) | A bit below R | Near R/M | None | Controller or token recovery |