Multiple Access: Channel Partitioning, Random Access, and Taking Turns

The Multiple Access Problem

There are two kinds of links: a point-to-point link connects exactly one pair of nodes, while a broadcast link lets many nodes attach to one shared channel, so a frame sent by any node is received by all the others. When two or more nodes transmit at the same time, their signals overlap on the channel and the receivers cannot make sense of any frame; this is a collision. The rules that coordinate how nodes use the shared channel are called multiple access protocols, also known as medium access control (MAC) protocols.

For a broadcast channel of rate $R$, an ideal multiple access protocol would let a single active node send at rate $R$; give each of $M$ active nodes an average rate of $R/M$; be decentralized, with no special node whose failure brings down the network; and be simple and cheap to implement.

Multiple access protocols fall broadly into three classes: channel partitioning protocols, random access protocols, and taking-turns protocols.

Shared-Medium Networks

As the name suggests, a shared-medium network is one in which several devices use the same communication medium. It is a half-duplex design: data can travel in both directions on a channel, but not at the same time.

The main types of shared-medium networks are Ethernet and the Fiber Distributed Data Interface (FDDI).

Since several devices share one channel, more than one transmission may reach the same medium and contend for it. Shared-medium networks therefore use one of two medium access control methods: contention and token passing (token-passing protocols).

Channel Partitioning Protocols

Channel partitioning protocols cut the channel into pieces in advance, and each node owns one piece, so collisions never happen:

Channel partitioning is efficient under heavy load but wasteful under light load, which is the problem random access protocols address.

Random Access Protocols

In a random access protocol, a node always transmits at the full channel rate $R$. After a collision, each node waits a random time before retransmitting; the randomness makes it likely that they will not collide again.

ALOHA and Slotted ALOHA

Slotted ALOHA divides time into slots of one frame time, and nodes transmit only at the start of a slot. After a collision, a node retransmits in each later slot with probability $p$. With $N$ active nodes, a slot succeeds only when exactly one node transmits:

So with many nodes, at most about 37% of the slots carry useful data. Pure ALOHA has no slots, so a frame collides with anything sent within one frame time before or after it, and its maximum efficiency is only $1/(2e) \approx 0.18$.

Contention

Contention is the access method used by carrier sense multiple access (CSMA). With this method, the stations on the network occupy the carrier channel on a first-come, first-served basis. If several stations send frames at the same time, collisions are inevitable, degrading performance and congesting the network.

Suppose A wants to send data to C. A first makes sure that no other station is sending, then sends the data to C. In doing so, A actually sends the data to every station on the channel; each station that receives A's data extracts the MAC address from A's frame. If the data is not addressed to it, the station discards it.

In CSMA, a station first listens to the carrier channel. If no data is present, it sends; if the channel is busy, it waits for a while before sending.

CSMA with Collision Detection (CSMA/CD)

Listening before talking cannot eliminate collisions: signals need time to propagate along the bus, so a distant node still thinks the channel is idle until the signal reaches it. CSMA/CD adds "listening while talking": a node keeps sensing the channel while it transmits, stops as soon as it detects a collision, sends a short jam signal to alert every node, and then backs off for a random time before retrying. Colliding frames are no longer sent in full, which greatly reduces the wasted channel time.

Let $d_{prop}$ be the maximum propagation delay between the two farthest nodes and $d_{trans}$ the time to transmit a maximum-size frame. The efficiency of CSMA/CD is approximately:

The smaller the propagation delay and the longer the frames, the closer the efficiency gets to 1.

Taking-Turns Protocols

Random access protocols do well under light load but suffer frequent collisions under heavy load. Taking-turns protocols let nodes transmit in some order. Two are common:

• Polling: a master node asks each node in turn whether it has data to send. This eliminates collisions but adds polling delay, and if the master fails, the whole channel stops working.
• Token passing: a special frame called the token is passed among the nodes in a fixed order; the token ring is the classic example.

Token Ring

As the name suggests, a token ring has a token that is passed around a ring, and only the station holding the token may transmit data.

This approach has two advantages:

1. Only the station holding the token can transmit, which guarantees that frames never collide.
2. Every station has an equal chance to get the token, which ensures that performance does not degrade even when the network is congested.

The token ring has costs too: even a lone sender must wait for the token to reach it, and if the token is lost through an error or the station holding it crashes, a dedicated recovery mechanism is needed (for example, a monitor station regenerates the token).