Medium Access Control: ALOHA, CSMA and CSMA/CD

When many stations share one broadcast channel (a coaxial cable, a hub, a radio frequency), two frames sent at overlapping times destroy each other: a collision. The medium access control (MAC) sublayer of the data link layer decides who may transmit when.

There are three families. Channel partitioning (TDMA, FDMA) gives each station a fixed share; it is collision-free but wastes the share of idle stations. Taking turns (polling, token passing) passes the right to send around; it is collision-free but has overhead and a single point of failure. Random access lets any station send when it has data and recovers from collisions; it is simple and efficient at light load. ALOHA, slotted ALOHA, CSMA and CSMA/CD are random-access protocols, and classic Ethernet is CSMA/CD.

The quantities are throughput formulas and their maxima ($1/(2e)$ and $1/e$), vulnerable periods, the minimum frame size for collision detection, binary exponential backoff probabilities, and CSMA/CD efficiency.

Measure time in frame times $T$ (the transmission time of one frame, all frames of equal length). Let $G$ be the offered load: the mean number of transmission attempts (new frames and retransmissions) per frame time. Let $S$ be the throughput: the mean number of successful frames per frame time, so $0 \le S \le 1$. Attempts are modelled as a Poisson process.

A station sends whenever it has a frame. If it collides, it waits a random time and sends again. A frame sent at time $t_0$ survives only if no other frame starts in $(t_0 - T, t_0 + T)$: any frame starting in the previous $T$ is still on the channel, and any frame starting in the next $T$ overlaps its tail. The vulnerable period is $2T$, so

Time is divided into slots of length $T$; a frame may start only at a slot boundary. Two frames collide only if they choose the same slot, so the vulnerable period is $T$:

With $N$ stations each transmitting in a slot with probability $p$, a slot succeeds if exactly one transmits:

The slotted expression is largest at $p = 1/N$, where it equals $(1 - 1/N)^{N-1}$, which falls to $1/e$ as $N \to \infty$. The pure expression is largest at $p = 1/(2N - 1)$ and tends to $1/(2e)$.

Carrier sense multiple access stations sense the channel and do not start while another transmission is heard. Collisions remain possible because a signal needs time $T_p$ to reach the other stations: the vulnerable period becomes the propagation delay.

1-persistent has the least delay at light load but collides whenever two stations are waiting for the same frame to end. Non-persistent wastes idle time but collides less at heavy load.

With collision detection a station listens while it sends. On detecting a collision it stops at once, sends a short jam signal so every station notices, and backs off. This saves the rest of the frame time that ALOHA and plain CSMA waste on a doomed frame.

Minimum frame size. A sender can only know that a collision happened if it is still transmitting when the collision noise reaches it. In the worst case, station A at one end starts at time 0; just before A's first bit reaches the far end at $T_p$, station B starts; B's signal reaches A at almost $2T_p$. So

Classic 10 Mbps Ethernet fixes the slot time at 512 bit times (51.2 µs) and the minimum frame at 64 bytes, which bounds the network diameter.

After the $n$-th consecutive collision of a frame, the station picks $K$ uniformly from $\{0, 1, \ldots, 2^{m} - 1\}$ with $m = \min(n, 10)$ and waits $K$ slot times (512 bit times) before sensing again. After 16 failed attempts the frame is dropped and an error is reported. The range doubles with each collision, so the expected wait adapts to the number of contending stations.

Throughput of pure ALOHA. A given attempt succeeds if no other attempt occurs in a window of $2T$, which for Poisson attempts at rate $G$ per frame time has probability $e^{-2G}$. Attempts occur at rate $G$, so $S = G e^{-2G}$. Setting $dS/dG = e^{-2G}(1 - 2G) = 0$ gives $G = 1/2$ and $S = 1/(2e)$. For slotted ALOHA the window is one slot, $S = Ge^{-G}$, maximum at $G = 1$, $S = 1/e$.

CSMA/CD efficiency. Two standard models give approximations of the same shape:

with $a = T_p/T_t$ and $T_p$ the maximum end-to-end propagation delay. In the Tanenbaum model each contention slot has length $2T_p$ and, with optimal persistence among many stations, a slot is won with probability $1/e$, so on average $e$ slots of $2T_p$ precede each frame. Both formulas give $\eta \to 1$ as $a \to 0$ (long frames, short cable) and $\eta \to 0$ as $a$ grows.

Backoff probabilities. If two stations pick $K$ independently and uniformly from ranges of sizes $r_1$ and $r_2$, they collide again with probability $\min(r_1, r_2)/(r_1 r_2)$; for equal ranges of size $r$, that is $1/r$.

200-bit frames on a 200 kbps channel, so $T = 1$ ms. Pure ALOHA:

Slotted ALOHA at $G = 1$ (1000 frames per second offered) gives $S = e^{-1} \approx 0.3679$, about 368 frames per second. Successful frames per second are $S/T$, that is $S$ times 1000 here; equivalently, the offered frames per second times the survival probability $e^{-2G}$ (for 500 frames per second, $500 \times e^{-1} \approx 184$). Multiplying $S$ by the offered frames per second counts the load twice and gives a wrong answer such as 92.

Ten stations, each sending in a slot with probability 0.1: $P = 10 \times 0.1 \times 0.9^9 \approx 0.3874$. This is the maximum over $p$ for $N = 10$, already close to $1/e \approx 0.3679$ from above.

A 1 km cable at 1 Gbps, $v = 2 \times 10^8$ m/s: $T_p = 5$ µs, so $L_{\min} = 2 \times 5 \times 10^{-6} \times 10^9 = 10{,}000$ bits (1250 bytes). At 10 Mbps over 2500 m: $T_p = 12.5$ µs and $L_{\min} = 250$ bits.

Reverse question: with 64-byte (512-bit) minimum frames at 100 Mbps, $T_t = 5.12$ µs, so $2T_p \le 5.12$ µs and the cable can be at most $2.56 \times 10^{-6} \times 2 \times 10^8 = 512$ m.

With $a = 0.1$: $1/(1 + 5 \times 0.1) \approx 0.667$ in the Kurose and Ross form, $1/(1 + 2e \times 0.1) \approx 0.648$ in the Tanenbaum form. With $a = 0.01$: 0.952 and 0.948.

Stations A and B collide. Each picks $K \in \{0, 1\}$: they collide again with probability $1/2$. After a second collision each picks from $\{0, 1, 2, 3\}$: probability $1/4$.

Now suppose A is on its first retry ($K_A \in \{0, 1\}$) and B on its second ($K_B \in \{0, 1, 2, 3\}$). A wins outright if $K_A < K_B$: if $K_A = 0$, B must pick 1, 2 or 3 (probability $3/4$); if $K_A = 1$, B must pick 2 or 3 ($1/2$). So $P(\text{A wins}) = \frac{1}{2}\left(\frac{3}{4} + \frac{1}{2}\right) = \frac{5}{8}$. B wins only if $K_A = 1$ and $K_B = 0$, probability $1/8$; they collide again ($K_A = K_B$) with probability $1/4$, which matches $\min(2, 4)/(2 \times 4)$.

A 2 km bus with $v = 2 \times 10^8$ m/s ($T_p = 10$ µs) at 10 Mbps. A starts sending at time 0. B, at the far end, starts at 6 µs, because A's first bit reaches B only at 10 µs and B still hears an idle channel. The two signals meet at 8 µs, 1600 m from A. B hears A at 10 µs, after sending for 4 µs (40 bits); A hears B at $6 + 10 = 16$ µs, after sending 160 bits. The later B starts, the later A finds out: if B starts just before 10 µs, A hears the collision just before $2T_p = 20$ µs. So A's frame must last at least 20 µs, which is 200 bits, the value $L_{\min} = 2T_pR$ gives.

Common misconceptions.

Polling (a master invites each station in turn) and token passing (a token circulates; only its holder sends) avoid collisions at the cost of polling or token-rotation delay.

Token-passing cycle. Let $N$ stations share a ring; a station holding the token sends one frame (time $T_t$) if it has data and passes the token on as soon as it has finished, and the token needs a total ring latency $\tau$ to travel once round the ring. With every station busy, one rotation takes $N T_t + \tau$, so the efficiency is $N T_t/(N T_t + \tau)$. For $N = 10$, $T_t = 100$ µs and $\tau = 50$ µs (5 µs per hop): a rotation takes 1050 µs, the efficiency is $1000/1050 \approx 0.952$, and a busy station waits 950 µs between the end of one of its frames and the start of its next. If only one station has data, it sends once every $T_t + \tau = 150$ µs and gets $100/150 = 2/3$ of the link. The ratio of $\tau$ to $T_t$ plays the part that $a$ plays in CSMA/CD.

Wi-Fi uses CSMA/CA: a station senses the channel, defers for a random backoff counted down only while the channel is idle, and relies on link-layer acknowledgements because it cannot detect collisions.