Question 2 of 5: Medium Access Control — CSMA/CD, ALOHA and the Wireless Terminal Problems

Question 2: Medium Access Control — CSMA/CD, ALOHA and the Wireless Terminal Problems (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — CSMA/CD. Carrier Sense Multiple Access with Collision Detection is the access method of classical shared-medium Ethernet (IEEE 802.3). A station with a frame to send first listens to the medium (carrier sense). If it hears an ongoing transmission it defers; in the 1-persistent variant Ethernet uses, it transmits as soon as the medium goes idle and an inter-frame gap has elapsed. While transmitting, the station keeps listening and compares what it hears with what it is sending — that is the collision detection.

Collisions remain possible despite the carrier sense because the medium has a non-zero propagation delay. Two stations separated by a propagation time $\tau$ can both sense an idle cable and both begin to transmit within $\tau$ of each other, neither yet aware of the other. When the signals meet, the voltage on the cable no longer matches what either transmitter is sending, and both detect the collision.

Recovery has three parts. First, a station that detects a collision aborts immediately and transmits a short jam signal (32 bits), which guarantees that every other station on the segment also registers the collision rather than mistaking the truncated frame for a valid one. Second, it backs off for a random interval chosen by truncated binary exponential backoff: after the $n$-th consecutive collision the station waits $k$ slot times, where $k$ is drawn uniformly from $\{0, 1, \ldots, 2^{\min(n,10)}-1\}$, up to 16 attempts before the frame is discarded and the failure reported upward. Randomising the wait breaks the symmetry that caused the collision; doubling the range adapts the retry rate to the offered load, so the algorithm stabilises instead of collapsing as contention rises. Third, the minimum frame length (64 bytes) guarantees a station is still transmitting when the worst-case collision reaches it, so no collision goes undetected — the point quantified in part (e).

Part (b) — ALOHA compared with CSMA/CD. ALOHA does the opposite of carrier sense: a station transmits as soon as it has data, without listening to the channel at all, and infers success only from the absence of an acknowledgement. There is no collision detection either — in the original packet-radio setting a station could not hear the shared channel while its own transmitter was on — so a damaged frame is discovered only when the acknowledgement fails to arrive, after a full timeout rather than within a fraction of a frame.

Collisions are therefore not merely possible in ALOHA, they are the normal mode of operation, and they are more costly than in CSMA/CD in two ways: a colliding station wastes the entire frame time rather than aborting a few microseconds in, and it learns of the loss a timeout later. In pure ALOHA a frame of duration $T$ is destroyed by any transmission starting in a window of $2T$ around it, which caps throughput at $1/2e \approx 18\ \text{per cent}$ of the channel rate. Slotted ALOHA forces every transmission to begin on a common slot boundary, halving the vulnerable window to $T$ and doubling the peak to $1/e \approx 37\ \text{per cent}$. CSMA/CD, by sensing before and during transmission, avoids most collisions outright and truncates the rest, and so achieves throughput well above 90 per cent on a short LAN. The price is that CSMA/CD needs a medium on which every station can hear every other, which is precisely the assumption that fails in parts (c) and (d).

Part (c) — the hidden terminal problem. Radio range is limited and not transitive. In the figure, A and C are both within range of B but out of range of each other. A senses the channel, hears nothing (C is hidden from it), and transmits to B; C does the same at the same moment. Both frames arrive at B and collide there, yet neither sender's carrier sense could have predicted it. Carrier sense at the transmitter is the wrong test, because collisions happen at the receiver. Worse, the senders cannot detect the collision either: a radio cannot listen on the frequency it is transmitting on with anything like the dynamic range required, which is why 802.11 uses collision avoidance rather than collision detection.

The RTS-CTS-ACK exchange fixes this by moving the reservation to the receiver. A wanting to send first transmits a short Request To Send naming the intended recipient and the duration of the exchange. B replies with a Clear To Send carrying the same duration. Because the CTS comes from B, it reaches everything in B's range — including C, the hidden terminal. C sets its network allocation vector (a virtual carrier-sense timer) for that duration and stays silent, so A's data frame arrives at B uncontested. B finally returns an ACK, which both confirms delivery and tells the neighbourhood the medium is free again. Collisions are not eliminated, but they are confined to the short RTS frames, so the cost of a collision falls from a full data frame to a few tens of microseconds.

Part (d) — the exposed terminal problem. This is the complementary failure: carrier sense is too conservative rather than too permissive. In the figure B is transmitting to A, and C wishes to transmit to D. C is within range of B, so it hears B's carrier and defers — yet C's transmission would have been perfectly harmless, because C cannot reach A (where B's frame is being received) and B is not the receiver of C's frame. Two transmissions that could have proceeded in parallel are serialised, and capacity is wasted. The generic error is the same one as in (c): the station tests for activity at its own antenna when the question is whether its signal will corrupt somebody else's reception.

RTS-CTS helps here only partially, and it is worth being precise about why. C overhears B's RTS but never hears a CTS from A, because A is out of C's range. A station that hears an RTS but no matching CTS may infer that it is an exposed terminal — it is not near the receiver — and is in principle free to transmit, whereas a station that hears the CTS (the hidden terminal of part (c)) must defer. This is what makes the mechanism asymmetric and useful. In practice, plain IEEE 802.11 does not exploit the inference fully: physical carrier sense still suppresses C for the duration of B's data frame, and C could not receive an ACK from D while B is transmitting anyway. So RTS-CTS-ACK solves the hidden terminal problem outright and only mitigates the exposed terminal problem; the remaining loss is addressed by directional antennas, power control, or scheduled access rather than by the control-frame exchange itself.

Part (e) — the shortest time to detect a collision. The question turns on which station is asked, and the honest answer distinguishes the two.

Given. A shared medium of end-to-end length $L$ with signal propagation speed $v$, and the worst-case classical Ethernet segment $L = 2500\ \text{m}$, $v = 2\times 10^{8}\ \text{m/s}$, $R = 10\ \text{Mbit/s}$.

Find. The shortest interval that can elapse before a collision is detected, and the corresponding worst case.

1. Part (e) — the shortest case is essentially instantaneous. Let A begin transmitting at $t = 0$ and let its signal reach B at $t = \tau$, where $$\tau = \frac{L}{v} = \frac{2500}{2\times 10^{8}} = 12.5\ \mu\text{s}.$$ If B starts its own transmission at $t = \tau - \epsilon$ for an arbitrarily small $\epsilon$, then B is transmitting when A's signal arrives an instant later, and B detects the collision after a time $\epsilon \rightarrow 0$. The shortest period is therefore arbitrarily close to zero: a station can begin transmitting at the very instant a competing signal is about to arrive, and know immediately.
2. The bound that actually matters is the round trip. Station A, the earlier transmitter, does not learn of the collision until B's signal has travelled back to it, at $$t_{\max} = 2\tau = 25\ \mu\text{s}.$$ So while some station may detect a collision in essentially no time, the guarantee the protocol needs is that every station still detects it, and that takes one round-trip propagation time.
3. Why the round trip fixes the minimum frame size. A must still be transmitting at $t = 2\tau$, or it would finish, conclude the frame succeeded, and never retransmit. The frame must therefore last at least $2\tau$, which at $10\ \text{Mbit/s}$ is $2\tau R = 250\ \text{bits}$. IEEE 802.3 rounds this up to a slot time of $$T_{\text{slot}} = 512\ \text{bits} = 51.2\ \mu\text{s} \quad\text{at }10\ \text{Mbit/s},$$ a $64$-byte minimum frame, the extra margin covering repeater and transceiver latency along the worst-case path. $$\boxed{t_{\min} \rightarrow 0,\qquad t_{\text{guaranteed}} = 2\tau = 25\ \mu\text{s}, \qquad T_{\text{slot}} = 51.2\ \mu\text{s}}$$

The same reasoning explains why Gigabit Ethernet had to add carrier extension: at 1 Gbit/s a 64-byte frame lasts only $0.512\ \mu\text{s}$, far less than the round trip across even a small collision domain, so the slot time had to be padded to 512 bytes to keep collision detection sound — and why switched full-duplex Ethernet, which has no collision domain at all, replaced the whole mechanism.

Final results.