Channel allocation and multiple access: ALOHA, CSMA, CSMA/CD

The original Ethernet, Wi-Fi and satellite links share a common problem: many nodes share a single broadcast channel. If two nodes send at the same time, the signals overlap and both are corrupted. This is called a collision. A multiple access protocol is a set of rules that decides who sends when, without a central authority.

On the exam this topic hits in two places: ALOHA efficiency calculation and the minimum frame size in CSMA/CD. Golden rules:

1. Slotted ALOHA is $1/e$, pure ALOHA is $1/(2e)$. In pure ALOHA the vulnerable period is two frame times.
2. N nodes, probability $p$: success $= Np(1-p)^{N-1}$.
3. $L_{min} = 2 d_{prop} R$. You must hear the collision before the transmission ends.
4. The backoff range doubles with every collision.

The channel allocation problem

An ideal shared channel (rate $R$) should provide:

1. If only one node is sending, it can use the whole $R$.
2. If $M$ nodes are sending, each gets $R/M$ on average.
3. There is no central coordinator (no single point of failure).
4. It is simple and cheap.

Why is static allocation bad?

The simplest solution is to divide the channel into fixed parts: FDMA (frequency) or TDMA (time). Each node uses its own slice. The problem: when a node is silent its slice is wasted, and a node that is talking gets only $R/N$. A simple model from queueing theory gives the mean delay:

$T = \frac{1}{\mu C - \lambda}$

Here $C$ is the channel capacity (bps), $1/\mu$ is the mean frame length (bits), and $\lambda$ is the arrival rate (frames/s).

C = 100 Mbps, frame 10,000 bit, lambda = 5000 frames/s
mu C = 10^8 / 10^4 = 10,000 frames/s
Single channel  : T = 1 / (10,000 - 5,000) = 0.2 ms
10 subchannels  : each has C/10 and lambda/10
                  T = 1 / (1,000 - 500)    = 2 ms  (10 times)

With static division the delay is multiplied by $N$. Because computer traffic is bursty, dynamic sharing is needed.

Protocol families

ALOHA

It was developed at the University of Hawaii for a radio network between the islands. It is the ancestor of random access.

Pure ALOHA

When a node has a frame it sends it immediately. If it collides, the node waits a random time and tries again. Let the duration of a frame be $T$ and let our frame start at $t_0$.

     t0 - T           t0            t0 + T
       |--------------|---------------|
       a frame starting  a frame starting
       in this interval  in this interval
       collides          collides
       vulnerable period = 2T

Let $G$ be the average number of attempts (new + retransmissions) per frame time. If the attempts are assumed to follow a Poisson distribution, the probability that there is no other attempt in the $2T$ interval is $e^{-2G}$:

$S_{pure} = G\,e^{-2G}, \qquad S_{max} = \frac{1}{2e} \approx 0.184 \text{ (at G = 0.5)}$

Slotted ALOHA

Time is divided into slots the length of one frame time. Nodes can send only at the start of a slot. A collision happens only among nodes that choose the same slot, and the vulnerable period drops to $T$:

$S_{slotted} = G\,e^{-G}, \qquad S_{max} = \frac{1}{e} \approx 0.368 \text{ (at G = 1)}$

The other model in textbooks has $N$ nodes, each sending in every slot with probability $p$:

$P(\text{successful slot}) = N p (1-p)^{N-1}$

The best $p$ is $1/N$. As $N \to \infty$ this converges to $1/e$.

Worked example

$N = 5$, $p = 0.2$:

success   : 5 x 0.2 x 0.8^4         = 0.4096
idle slot : 0.8^5                   = 0.32768
collision : 1 - 0.32768 - 0.4096    = 0.26272
pure ALOHA same N, p : N p (1-p)^(2(N-1)) = 0.8^8 = 0.1678

On a 1 Mbps slotted ALOHA channel, the useful throughput in the best case is $10^6/e \approx 368$ kbps.

PITFALL · $G$ versus $S$. $G$ is the attempted load (including collided frames), $S$ is the fraction of successful frames. $G$ can exceed 1, $S$ never can. If $G$ is very large, almost every slot collides and $S \to 0$.

CSMA: listen before you send

ALOHA is crude: it sends even when the channel is busy. CSMA (carrier sense multiple access) listens to the channel first.

• 1-persistent: if the channel is idle, send immediately; if busy, wait for it to become idle and send immediately. Two nodes that were waiting will certainly collide when it frees up.
• Non-persistent: if the channel is busy, wait a random time, then listen again.
• p-persistent: (slotted) if the channel is idle, send with probability $p$, and with probability $1-p$ defer by one slot.

Listening does not eliminate collisions. Because of propagation delay, B may think the channel is idle and send, since A’s signal has not reached it yet. The longer the propagation (the longer the cable), the more likely a collision.

CSMA/CD: listen while sending too

This is the protocol of classic Ethernet. CD (collision detection): the node keeps listening to the channel while it sends. If it hears something different from its own signal:

1. It stops sending immediately (there is no point in sending the corrupted frame to the end).
2. It sends a 48-bit jam signal so that everyone notices.
3. It waits a random time with binary exponential backoff, then starts over.

Minimum frame size

Worst case: A and B are at the two ends of the cable. A starts to send. Just before its signal reaches B, B starts too. News of the collision returns to A after $2 d_{prop}$. A must still be sending at that moment, otherwise it cannot attribute the collision to its own frame:

$\frac{L}{R} \ge 2 d_{prop} \quad\Longrightarrow\quad L_{min} = 2\,d_{prop}\,R$

R = 10 Mbps, cable 2500 m, s = 2 x 10^8 m/s
dprop = 2500 / 2e8 = 12.5 us
Lmin  = 2 x 12.5e-6 x 1e7 = 250 bit

Real Ethernet also accounted for repeater delays and chose 512 bits (64 bytes). When the speed is multiplied by 10, the allowed distance for the same 512 bits shrinks 10 times: 5120 m at 10 Mbps, 512 m at 100 Mbps (with the propagation calculation alone).

Binary exponential backoff

After the $n$-th consecutive collision, the node chooses $K$ at random:

$K \in \{0, 1, \ldots, 2^{\min(n,10)} - 1\}, \qquad \text{wait} = K \times 512 \text{ bit times}$

After 16 attempts the frame is dropped and an error is reported to the upper layer. The idea: collisions mean heavy load; by enlarging the range you spread everyone out more as the load grows.

Ethernet efficiency

When many nodes always have a frame to send, approximately:

$\text{efficiency} = \frac{1}{1 + 5\,d_{prop}/d_{trans}}$

dprop = 12.5 us
1500-byte frame @10 Mbps : dtrans = 1200 us -> 1/(1 + 0.052) = 0.950
64-byte frame   @10 Mbps : dtrans = 51.2 us -> 1/(1 + 1.22)  = 0.450

When the frame is long and the cable short, the efficiency approaches 1.

Taking-turns protocols

• Polling: a master node asks each node in turn “do you have anything to send?”. There are no collisions, but there is polling delay, and if the master crashes the network stops. Bluetooth works this way.
• Token passing: a special token frame circulates from node to node; only the node holding the token sends. There are no collisions, but there is trouble if the token is lost or a node does not release it.

Wireless: why no CD?

In Wi-Fi, a sending node’s own strong signal drowns out the weak signal coming from afar; it cannot hear the collision. There is also the hidden terminal problem: A and C cannot hear each other but both send to B. So 802.11 tries to avoid collisions rather than detect them (CSMA/CA): a random countdown, an ACK for every frame, and optional RTS/CTS reservation.

TIP · the security connection. On a shared medium every node sees every frame; the card passes only what is addressed to it to the upper layer. Someone who puts the card in “promiscuous mode” can read all the traffic. On shared and wireless networks, what provides confidentiality is not the medium but encryption.

Common mistakes