Medium Access Control

Medium Access Control Overview

When several stations share the same broadcast channel — the bus topology of traditional Ethernet, or a wireless LAN — the question of who may use the channel arises. Medium access control (MAC) is the mechanism that answers it.

Medium access control protocols fall into three categories:

1. Channel partitioning protocols: the channel resource is divided into fixed pieces assigned to each station (FDM, TDM, WDM, CDM)
2. Random access protocols: stations access the channel at random, collisions may occur, and they are handled by collision detection or avoidance (ALOHA, CSMA/CD, CSMA/CA)
3. Polling access protocols: access is coordinated through a central controller or token passing (Token Ring, polling)

Channel Partitioning Protocols

Frequency Division Multiplexing (FDM)

The total bandwidth of the channel is split into several non-overlapping sub-bands, and each station permanently occupies one of them for communication. All stations can transmit at the same time without interfering with each other.

• Advantages: no collisions, and all stations can transmit simultaneously
• Disadvantages: low channel utilization (a sub-band sits idle while its station is silent), and inflexible (a new station needs a new sub-band)
• Applications: radio broadcasting, cable television, ADSL

Time Division Multiplexing (TDM)

Time is divided into frames of fixed length, each frame is further divided into slots, and each station permanently occupies one slot. The stations take turns using the full bandwidth of the channel in time order.

• Advantages: no collisions, and the stations are treated fairly
• Disadvantages: a slot is wasted while its station is silent, and the scheme is inflexible
• Applications: E1/T1 digital carriers, ISDN

Wavelength Division Multiplexing (WDM)

In fiber-optic communication, different wavelengths (colors) of light carry different signals, and a prism or diffraction grating multiplexes and demultiplexes them. It is essentially frequency division multiplexing in the optical domain.

• Applications: fiber-optic backbone networks, where a single fiber can carry dozens or even hundreds of wavelengths simultaneously

Code Division Multiplexing (CDM)

Each station uses a unique chip sequence, and all stations may transmit at the same time using the same frequency. The sender exclusive-ORs the data bits with the chip sequence, and the receiver recovers the original data using the orthogonality of the chip sequences.

• Advantages: all stations can transmit simultaneously, with strong interference resistance
• Disadvantages: chip synchronization is required, which makes the implementation complex
• Applications: 3G mobile communications (CDMA)

Random Access Protocols

The ALOHA Protocol

ALOHA was the earliest random access protocol, proposed by Norman Abramson at the University of Hawaii in 1970.

Pure ALOHA

• A station transmits immediately when it has data, without listening to the channel
• If a collision occurs (two or more stations transmit at the same time), all colliding frames are corrupted
• If the sender receives no acknowledgment within a period of time, it waits for a random interval and then retransmits
• Channel utilization (throughput): $S = G \cdot e^{-2G}$, with a maximum of about 18.4% (when $G=0.5$)

Here $G$ is the total number of frames transmitted by all stations per unit time, counting both new frames and retransmissions.

Slotted ALOHA

• Time is divided into slots of fixed length, and a station may only transmit at the start of a slot
• Collisions can only occur within the same slot, so the collision window is halved
• Channel utilization: $S = G \cdot e^{-G}$, with a maximum of about 36.8% (when $G=1$)

The throughput of slotted ALOHA is twice that of pure ALOHA.

The CSMA Protocol

CSMA (Carrier Sense Multiple Access) is based on a single idea: listen to the channel before transmitting, and transmit only if the channel is idle.

According to how the protocol behaves when the channel is busy and how it handles collisions after transmitting, CSMA comes in several variants:

1-Persistent CSMA

• Channel idle: transmit immediately
• Channel busy: keep listening and transmit as soon as it becomes idle (persistent)
• High collision probability (several stations waiting transmit simultaneously the moment the channel becomes idle)

Non-Persistent CSMA

• Channel idle: transmit immediately
• Channel busy: wait for a random interval and then listen again (non-persistent)
• Low collision probability, but the channel utilization may be lower (the channel may be idle during the waiting period)

p-Persistent CSMA

• Channel idle: transmit with probability $p$, or defer to the next slot with probability $1-p$
• Channel busy: keep listening
• Balances the collision probability against the channel utilization

The CSMA/CD Protocol

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) is the medium access control protocol used by traditional Ethernet.

How It Works

The operation of CSMA/CD is summarized as “listen before transmitting, listen while transmitting, stop on collision, retransmit at random”:

1. Carrier sense: listen to the channel before transmitting; wait if the channel is busy
2. Transmit data: begin transmitting when the channel is idle
3. Collision detection: keep listening while transmitting to detect whether a collision occurs
4. Collision handling: on detecting a collision, stop transmitting immediately and send a jamming signal to notify all stations that a collision occurred
5. Random retransmission: wait for a random interval and then try again

Contention Period and Minimum Frame Length

The key question in collision detection is: how long does the sender need before it can detect a collision?

Let the one-way propagation delay of the signal on the channel be $\tau$. In the worst case the sender detects a collision $2\tau$ after starting (the round-trip propagation delay). This $2\tau$ is called the contention period or collision window.

Therefore the minimum frame length must satisfy:

$L_{\min} = R \times 2\tau$

where $R$ is the data rate and $2\tau$ is the contention period.

For traditional Ethernet (10 Mbps, maximum cable length 2500 m, signal propagation speed about $2 \times 10^8$ m/s):

• $\tau = \frac{2500}{2 \times 10^8} = 12.5 \mu s$
• contention period $2\tau = 25.6 \mu s$
• minimum frame length $L_{\min} = 10 \times 10^6 \times 25.6 \times 10^{-6} = 256$ bit = 64 bytes

This is where the Ethernet minimum frame length of 64 bytes comes from.

Binary Exponential Backoff

After a collision the sender must wait a random interval before retransmitting. CSMA/CD uses the binary exponential backoff algorithm:

1. Determine the basic backoff time $T_0 = 2\tau$ (the contention period)
2. After the $k$-th collision, pick a random number $r$ from the integer set $\{0, 1, 2, \ldots, 2^k - 1\}$ and wait $r \times T_0$
3. $k = \min(\text{number of retransmissions}, 10)$, that is, at most $2^{10}-1 = 1023$ contention periods
4. After 16 failed retransmissions, give up and report an error

The characteristic of this algorithm is that the more collisions occur, the wider the range of waiting times becomes (the backoff), which lowers the probability of colliding again. It is an adaptive backoff strategy.

The CSMA/CA Protocol

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) is the medium access control protocol used by wireless LANs (IEEE 802.11 / Wi-Fi).

Why Wireless Networks Cannot Use CSMA/CD

1. The hidden terminal problem: A and C are both within B’s range, but A and C cannot hear each other. When A transmits to B, C senses the channel as idle and also transmits to B, causing a collision. Neither A nor C can detect it.
2. Large differences in signal strength: wireless signals attenuate quickly, so the transmitter’s signal is far stronger than the receiver’s, and the transmitter cannot listen for collisions while transmitting (the “near-far” problem).
3. A high bit error rate on wireless channels: collision detection is expensive, so it is better to avoid collisions in the first place.

Wireless networks therefore use CSMA/CA, which tries to avoid collisions before transmission rather than detecting them afterwards.

How It Works

The core mechanisms of CSMA/CA are:

1. Carrier sense: listen to the channel before transmitting and wait if it is busy
2. IFS (InterFrame Space):
   • DIFS (DCF IFS): the longest, used for data frames and management frames. A frame may be sent only after the channel has been idle for a DIFS
   • SIFS (Short IFS): the shortest, used for response frames such as ACK and CTS. The receiver waits only a SIFS before replying with an ACK, which gives response frames priority
3. Random backoff: if the channel is still busy after the DIFS, or if several stations were waiting, a station picks a random backoff time (a number of slots) and transmits only if the channel stays idle for that long. The backoff timer counts down and is paused while the channel is busy
4. The RTS/CTS mechanism (optional):
   • The sender first sends a short RTS (Request To Send) frame carrying the length of the data frame
   • The receiver replies with a CTS (Clear To Send) frame, also carrying the length
   • Every station that hears the RTS or the CTS knows that a transmission is coming and stays silent for the specified period (NAV, the Network Allocation Vector)
   • RTS/CTS solves the hidden terminal problem

Polling Access Protocols

Token Ring

• A special frame (the token) circulates around a ring topology
• Only the station holding the token may transmit data
• After the sender transmits, the data frame travels around the ring, the receiver copies the data and sets the response bit, and the frame eventually returns to the sender and is removed
• The sender then releases the token and passes it to the next station
• Advantages: no collisions, fair, and predictable (the maximum wait can be computed)
• Disadvantages: a lost or corrupted token brings the network down, and token management is complex; a ring topology is less reliable
• Applications: IEEE 802.5 Token Ring (largely obsolete)

Polling

• A primary station takes turns asking each secondary station whether it has data to send
• A secondary station may transmit only when it is polled
• Advantages: no collisions and simple control
• Disadvantages: high polling overhead and high latency (a secondary station must wait to be polled), and a failure of the primary station brings down the whole network
• Applications: IBM 3270 terminal networks, Bluetooth (master/slave mode)

Worked Examples

Example 1: Computing the Minimum Ethernet Frame Length

On a 100 Mbps Ethernet with a maximum cable length of 200 m and a signal propagation speed in the cable of $2 \times 10^8$ m/s, find the contention period and the minimum frame length.

Example 2: Collision Detection Time in CSMA/CD

In a CSMA/CD network, stations A and B are 1 km apart and the signal propagation speed is $2 \times 10^8$ m/s. A starts transmitting a frame at $t=0$, and B also starts transmitting a frame at $t=2 \mu s$. (1) At what time does A detect the collision? (2) At what time does B detect the collision?

Example 3: ALOHA Throughput

In a pure ALOHA network, the total number of frames transmitted by all stations per unit time (counting both new frames and retransmissions) is $G=1$. Find the throughput of the network. What is the throughput if slotted ALOHA is used instead?

---

Exercises

Exercise 1

What are the main differences between CSMA/CD and CSMA/CA? Why do wireless networks use CSMA/CA instead of CSMA/CD?

Exercise 2

Describe how the binary exponential backoff algorithm works, and explain why an exponential backoff is used instead of a fixed one.

---

Glossary