Multiple access links and protocols

A multiple access link (or broadcast link) is a link that connects multiple nodes through a shared communication channel.

On a shared channel, a broadcast occurs when one node transmits a frame and every other node attached to the link receives a copy (e.g., Ethernet and wireless LANs).

A shared channel is like a conversation in a classroom:

• everyone shares the same communication medium (the air)
• if multiple people speak at once, communication breaks down
• to avoid this, people follow rules about who talks and when (e.g., raise your hand to speak, don't interrupt, etc.)

In computer networks, if two or more nodes transmit at the same time, their signals interfere, causing a collision. As a result:

• none of the transmitted frames can be decoded
• all colliding frames are lost
• the channel is wasted for the duration of the collision

A multiple access protocol coordinates transmissions from active nodes on the shared channel to avoid collisions. They are commonly grouped into three categories:

1. channel partitioning protocols
2. random access protocols
3. taking-turns protocols

Ideal properties

Ideally, a multiple access protocol for a broadcast channel with transmission rate R bits/s should satisfy the following properties:

1. maximum throughput: if only one node has data to send, it should have a throughput of R bits/s
2. fairness: if M active nodes have data to send, each should have an average throughput of R/M bits/s
3. decentralized: the protocol should not rely on a master node, avoiding a single point of failure
4. simple: the protocol should be inexpensive to implement

In the following examples, we assume that a channel supports N nodes and has a transmission rate of R bits/s.

Channel partitioning protocols

Channel partitioning protocols divide a broadcast channel's bandwidth among all nodes that share it and collisions are structurally prevented.

TDM (time-division multiplexing)

TDM divides a broadcast channel in time:

• time is divided into frames
• each frame is divided into N time slots
• each time slot is assigned to one of the N nodes
• when a node has a packet, it transmits during its assigned slot in each frame

In the classroom analogy:

• each person speaks in turn for a fixed time
• then the next person speaks for the same duration
• once everyone has spoken, the cycle repeats

TDM eliminates collisions and is perfectly fair: each node gets a dedicated throughput of R/N bits/s per frame.

However, it has two main drawbacks, even when only one node has data to send:

1. it's limited to an average rate of R/N bits/s
2. a node must wait for its turn, even if the channel is idle

FDM (frequency-division multiplexing)

FDM divides a broadcast channel in frequency:

• the channel of rate R bits/s is split into N frequency bands
• each band has bandwidth R/N
• each band is assigned to one of the N nodes

Like TDM, FDM:

• avoids collisions and fairly divides bandwidth among the N nodes
• limits each node to R/N bandwidth, even if it is the only one sending

CDMA (code division multiple access)

CDMA assigns a unique code to each node:

• each node encodes its data using its assigned code
• if codes are chosen carefully:
  • multiple nodes can transmit simultaneously
  • each receiver can correctly decode its intended signal (if it knows the sender's code)
  • even in the presence of interference from other transmissions

CDMA is widely used in cellular networks. It's tightly tied to wireless channels.

Random access protocols

In a random access protocol, all nodes share the same channel and transmit whenever they have data, which can lead to collisions.

If a collision occurs:

• the involved nodes detect (or infer) the collision
• each node waits a random amount of time before retransmitting
• they keep retrying until the frame is sent successfully without collision

There are many random access protocols, such as:

• ALOHA protocols (ALOHA = Additive Links On-line Hawaii Area)
• CSMA protocols (CSMA = Carrier Sense Multiple Access)
• Ethernet

Slotted ALOHA

In slotted ALOHA:

• time is divided into equal time slots
• each slot can carry one frame
• nodes are synchronized and can only send at the beginnings of slots

Each node decides randomly whether to transmit in a given slot:

• if exactly one node sends → successful
• if more than one sends → collision (each node keeps retrying randomly in future slots)
• if nobody sends → wasted slot

As more nodes join, the chance that two or more choose the same time slot increases very quickly.

The efficiency is the fraction of successful slots, assuming many active nodes where each always has data to send:

• mathematically, it turns out that even under optimal conditions, only about 37% of slots are successful
• this means that the effective throughput is at most about 0.37 R bits/s, rather than R

ALOHA

In the first ALOHA protocol, packets are transmitted at any time without waiting for slot boundaries.

This means that transmissions can overlap in time, so collisions are more likely.

To understand its efficiency, we make the following assumptions:

• there are \( N \) active nodes
• each node transmits independently without slot synchronization (i.e., at any time)
• each frame has a fixed transmission duration

For a transmission to be successful:

• no other node must start transmitting during the vulnerable period of a frame
• this includes both:
  • the time just before the transmission starts
  • the time during the transmission itself

This is because even a slightly overlapping transmission causes a collision:

So, compared to slotted ALOHA, the vulnerable period is effectively twice as large, since transmissions are not aligned to slots (collisions can happen from both past and future overlaps).

As a result, the probability of a successful transmission is reduced.

Mathematically, it turns out that the maximum efficiency of pure ALOHA is exactly half that of slotted ALOHA.

CSMA (carrier sense multiple access)

ALOHA is like a rude student who keeps talking without checking if anyone else is already speaking. This often causes people to talk over each other.

In human protocols, there are two important rules in conversation:

1. listen before speaking:
   • if someone else is talking, wait until they finish
   • in networking, this is called carrier sensing
   • before sending data, a node listens to the network
   • if another node is already transmitting, it waits
   • once the network has been quiet for a short time, it starts transmitting
2. stop if someone starts talking at the same time:
   • if two people begin speaking together, they usually stop and let one person continue
   • in networking, this is called collision detection
   • while transmitting, a node keeps listening to the network
   • if it detects another transmission at the same time (a collision), it:
     • stops transmitting
     • waits for a random amount of time
     • then tries again by listening before transmitting

These ideas form the basis of two networking protocols:

• CSMA (carrier sense multiple access): nodes listen before transmitting
• CSMA/CD (CSMA with collision detection): nodes also detect collisions and retransmit later

If all nodes perform carrier sensing, why do collisions still happen?

• the reason is signal propagation delay
• signals take a small amount of time to travel across the network: they do not reach every node instantly

This is easier to understand with a space-time diagram:

Time	Events	Image
At time \( t_{0} \)	node 1 senses the channel is idle it begins transmitting its signal travels in both directions along the broadcast medium although the signal travels very fast, it still takes a short time to reach the other nodes
At time \( t_{1} \)	node 2 also wants to transmit 1 is already transmitting 1's signal has not yet reached 2 node 2 cannot hear 1, so it believes the channel is idle 2 begins transmitting
A short time later	the signals from 1 and 2 meet somewhere on the shared medium a collision occurs because the signals overlap eventually, both 1 and 2 detect the collision

Carrier sensing cannot completely prevent collisions because network signals need time to travel.

The longer the propagation delay (the time for a signal to travel from one node to another), the greater the chance that two nodes will both think the network is idle and begin transmitting at the same time.

CSMA/CD (carrier sense multiple access with collision detection)

In CSMA/CD, an adapter in a node follows these rules:

Step	Description
1	get a datagram from the network layer and build a link-layer frame
2	sense the channel: if idle (no signal energy entering the adapter from the channel) → start transmitting if busy → wait until it becomes idle, then send
3	while transmitting, continue to sense the channel
4	stop immediately if a collision is detected
5	wait a random time after aborting, then try again

Stopping early improves performance because the nodes do not finish sending a corrupted frame.

If devices always waited the same fixed amount of time after a collision, they would continue colliding forever.

Random waiting reduces this chance, but:

• if the wait time is too large, the channel is underused
• if the wait time is too small, devices are likely to choose similar wait times and collide again

So the best waiting time adapts to congestion:

• small when few nodes collide
• large when many collide

Ethernet uses binary exponential backoff to choose the random delay.

After \( n \) collisions, a node picks:

• \( K \) randomly from \( \{ 0, 1, 2, …, 2^{n} - 1 \} \)
• so, the more collisions experienced by a frame, the larger the interval from which \( K \) is chosen
• the actual amount of time a node waits is \( K \times 512 \) bit times
• the maximum value that \( n \) can take is capped at 10

The size of the sets from which \( K \) is chosen grows exponentially with the number of collisions:

• after 1 collision: \( K \in \{0,1\} \)
• after 2 collisions: \( K \in \{0,1,2,3\} \)
• after 3 collisions: \( K \in \{0, 1, 2, 3, 4, 5, 6, 7\} \)
• after 10 collisions: \( K \in \{0, 1, 2, …, 1023\} \)

Each new frame is treated independently by CSMA/CD and may transmit immediately if the channel is idle, while other nodes may still be in exponential backoff from earlier collisions.

Mathematically, it turns out that CSMA/CD efficiency works best when frames are long and propagation delay is small, allowing the channel to be used productively most of the time.

Taking-turns protocols

In taking-turns protocols, nodes share the channel by taking turns transmitting.

They often approximate fairness, unlike random-access protocols such as ALOHA and CSMA, where collisions and contention can lead to uneven access and throughput between nodes.

Polling protocols

A polling protocol requires one of the nodes to be designated as a master node:

• the master node polls each node in a cyclic manner (round-robin)
• when a node is polled, it is allowed to transmit up to a maximum number of frames
• the master then polls the next node, and the process repeats

Advantages:

• eliminates collisions
• achieves higher efficiency than random access protocols

Drawbacks:

1. polling delay:
   • each node must wait until the master polls it
   • if only one node is active, it still has to wait while the master polls inactive nodes
   • as a result, the active node cannot achieve the full rate of R bits/s
2. single point of failure:
   • if the master node fails, the entire network stops working

Historically used in systems such as Bluetooth piconets.

Token-passing protocols

Instead of a master node, a small control frame called a token is passed between nodes in a fixed order:

• node 1 might always send the token to node 2
• node 2 might always send the token to node 3
• node N might always send the token to node 1

When a node receives the token:

• if it has data to send: it transmits up to a maximum number of frames, then passes the token to the next node
• if it has no data to send: it immediately forwards the token

Advantages:

• highly efficient
• decentralised (no central controller is required)

Drawbacks:

• the failure of one node can disrupt token circulation
• recovery procedures are required if the token is lost or circulation is disrupted

E.g., IEEE 802.5 Token Ring.

DOCSIS

A cable access network connects thousands of residential cable modems to a Cable Modem Termination System (CMTS).

DOCSIS (Data Over Cable Service Interface Specifications):

• specifies the cable data network architecture
• and its protocols

DOCSIS is an excellent case study because it combines all three classes of multiple access protocols.

Frequency-division multiplexing

DOCSIS uses FDM to divide the cable spectrum into multiple upstream and downstream channels:

• each downstream channel (CMTS → modem):
  • is between 24 MHz and 192 MHz wide
  • supports up to approximately 1.6 Gbps
• each upstream channel (modem → CMTS):
  • is between 6.4 MHz and 96 MHz wide
  • supports up to approximately 1 Gbps

Downstream transmission

A downstream channel:

• is a broadcast channel
• frames are received by all cable modems receiving that channel
• only the intended modem processes each frame
• there is no multiple-access problem because only the CMTS transmits on the downstream channel

Upstream transmission

An upstream channel:

• is shared by many cable modems
• therefore transmissions must be coordinated to avoid collisions

Each upstream channel is divided into intervals of time (TDM-like) containing mini-slots during which cable modems can transmit to the CMTS.

The CMTS centrally grants permission to individual cable modems to transmit during specific mini-slots by sending MAP messages on the downstream channel that specify:

• which cable modem may transmit
• during which mini-slots

Since the CMTS allocates mini-slots, it can prevent collisions during data transmission.

Requesting transmission opportunities

How does the CMTS know which cable modems have data to send?

• cable modems transmit mini-slot-request frames to the CMTS
• these are sent during dedicated request mini-slots
• because multiple cable modems may transmit requests simultaneously, these request messages use random access and may collide

A cable modem:

• cannot sense whether the upstream channel is busy
• cannot detect collisions directly
• instead infers that its request collided if it does not receive a transmission grant in a subsequent MAP message
• retransmits the request using binary exponential backoff

Summary

DOCSIS combines all three classes of multiple access protocols:

1. channel partitioning:
   • FDM partitions the cable spectrum into upstream and downstream channels
   • TDM-like scheduling divides each upstream channel into mini-slots
2. random access:
   • mini-slot-request frames are transmitted using random access and may collide
3. taking turns:
   • the CMTS centrally allocates mini-slots, allowing cable modems to take turns transmitting without collisions