Question 5 of 5: Medium access control protocols

Question 5: Medium access control protocols (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) — hidden and exposed terminals. Both problems arise because in a radio network, unlike on a cable, "the medium is busy" is a statement about a place, and the place that matters is the receiver while the place a station can observe is itself.

The hidden terminal problem is a false idle. Stations A and C are both within range of B but out of range of each other; A begins transmitting to B, C senses the medium, hears nothing because A is hidden from it, and transmits to B as well. The two frames collide at B and both are lost, and neither sender ever learns why. Carrier sense has failed because it was performed at the wrong location.

The exposed terminal problem is the opposite error, a false busy. B is transmitting to A; C is in range of B but not of A, and wishes to send to D, which is not in range of B. C senses the medium, hears B, and defers — even though its transmission to D would have interfered with nothing, because D cannot hear B and A cannot hear C. Capacity is wasted rather than lost to collision.

The RTS/CTS handshake attacks both by moving the "busy" declaration to the receiver. Before sending, A 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; only then does A send the data frame, and B finally acknowledges. For the hidden terminal, C is by definition in range of B, so it hears the CTS and sets its network allocation vector — a virtual carrier-sense timer — for the stated duration, and stays silent for exactly as long as A needs. The collision is prevented, and any collision that does still occur involves only the very short RTS rather than a full data frame, so the cost of contention falls dramatically. For the exposed terminal, C hears B's RTS but never hears a CTS from A, and the rule is to defer on a CTS rather than on an RTS alone; a station that hears only an RTS therefore knows it is outside the receiver's neighbourhood and may transmit concurrently. In practice 802.11's relief of the exposed-terminal problem is only partial, because physical carrier sense still detects B's data transmission and because C's own reply timing may clash, which is why RTS/CTS is normally enabled only above an RTS threshold where the data frames are long enough to justify the overhead.

Part (b) — CSMA/CD in Ethernet. Classic shared-medium Ethernet uses 1-persistent carrier-sense multiple access with collision detection. A station with a frame to send listens to the cable: if it is idle for one interframe gap (96 bit times) the station transmits immediately, and if it is busy the station waits until the end of the current transmission and then transmits, which is the "1-persistent" behaviour and is also the reason collisions cluster just after a busy period.

Collisions are detected while transmitting. The station monitors the medium as it sends and compares what it hears with what it sent; a discrepancy, or on twisted pair simultaneous activity on the transmit and receive pairs, means another station also began transmitting inside the propagation window. Recovery has three parts. First the station aborts the frame at once, so the wasted time is a fraction of a frame rather than a whole one. Second it transmits a 32-bit jam sequence, which guarantees that every other station on the segment sees the collision long enough to recognise it. Third it backs off for a random interval using truncated binary exponential backoff: after the $n$-th successive collision it waits $k$ slot times where $k$ is drawn uniformly from $\{0, 1, \ldots, 2^{\min(n,10)}-1\}$ and a slot time is 512 bit times, doubling the contention window each time so the scheme adapts automatically to the number of contending stations; after 16 attempts the frame is discarded and the failure is reported upward. Two design rules make this work: the 96-bit interframe gap lets receivers recover between frames, and the 64-byte minimum frame length guarantees a station is still transmitting when the worst-case round-trip echo returns, so no collision can go undetected. In modern switched full-duplex Ethernet each link has exactly two stations and separate transmit and receive paths, so collisions cannot occur and CSMA/CD is disabled entirely.

Part (c) — token ring, and whether collisions are possible. In a token ring (IEEE 802.5, and FDDI on the same principle) the stations are connected in a closed loop and each acts as an active repeater, receiving each bit and re-transmitting it to the next station. Permission to transmit is carried by a single short frame called the token, which circulates continuously while the ring is idle. A station with data waits for the token to arrive, seizes it by changing its token bit into a start-of-frame delimiter (or, on FDDI, absorbs it), and transmits its data frame onto the ring. Every station repeats the frame; the addressed destination copies it as it passes and sets the address-recognised and frame-copied bits in the trailer, which gives the sender a hardware acknowledgment. The frame travels the whole loop back to the sender, who drains it from the ring — ensuring it circulates only once — and then issues a fresh token so the next station downstream may transmit. A token-holding timer bounds how long any station may keep the token, which makes the worst-case access delay deterministic and calculable, and priority and reservation bits let urgent traffic pre-empt the queue.

Collisions are not possible in normal operation, and the reason is structural: transmission requires possession of the token, exactly one token exists on the ring, and the ring is a set of point-to-point links rather than a shared broadcast medium, so two stations can never be transmitting new data at the same time. Access is therefore contention-free and the throughput does not collapse under heavy load the way a contention protocol's does. What replaces collisions is a set of token-maintenance failures — a token lost when a station crashes mid-transmission, a duplicated token, or an orphan frame whose sender has gone — and these are handled by an elected active monitor which times the token rotation, purges the ring and regenerates a token when necessary. The complexity does not disappear; it moves from collision recovery to token recovery.

Part (d) — the shortest time before a collision is detected.

Given. Two stations separated by a distance $d$ on a medium with signal propagation velocity $v$ (roughly $2 \times 10^{8}$ m/s on coaxial cable or fibre, about two-thirds of the free-space value).

Find. The shortest interval that can elapse between a station beginning to transmit and that station detecting a collision, with the reasoning that fixes it.

Approach. A station detects a collision only when the other station's signal physically reaches it, so the question is really about propagation delay; find the best case and contrast it with the worst case that protocol design must actually accommodate.

1. Part (d) — identify what detection requires. A transmitting station recognises a collision when energy from another transmitter arrives at its own receiver. If the two stations begin transmitting at the same instant and are separated by $d$, each hears the other after one one-way propagation delay $$\tau = \frac{d}{v}$$ so the shortest possible detection time is one propagation delay between the two colliding stations, and it tends to zero as the stations get closer: $$\boxed{t_{\min} = \tau = d/v \;\longrightarrow\; 0 \text{ as } d \to 0}$$ For two stations only 10 m apart, $\tau = 10/(2\times10^{8}) = 50$ ns — five bit times at 100 Mbit/s.
2. Contrast with the worst case, which is what the standard sizes. The unluckiest station starts transmitting an instant before the far station's signal arrives, so it has been sending for almost $\tau_{\max}$ when the other begins, and the resulting collision takes a further $\tau_{\max}$ to travel back: detection can take almost $2\tau_{\max}$, a full round trip. This is why IEEE 802.3 fixes a slot time of 512 bit times, which at 10 Mbit/s is $$T_{\text{slot}} = \frac{512\ \text{bits}}{10\ \text{Mbit/s}} = 51.2\ \mu\text{s}, \qquad \tau_{\max} \approx \frac{T_{\text{slot}}}{2} = 25.6\ \mu\text{s}$$ and why the minimum frame is 512 bits (64 bytes): a sender must still be transmitting when the worst-case echo returns, or it would finish the frame, believe it succeeded, and never retransmit.
3. State the answer with its condition. The shortest period is therefore one propagation delay, essentially zero for adjacent stations; the figure the protocol must be designed around is the round-trip $2\tau_{\max}$ across the largest permitted network span.

Part (e) — why Aloha is much less efficient, and when it is nonetheless the right choice.

Pure Aloha transmits a frame the moment the application has one, without listening first and without aborting when things go wrong. A frame is destroyed by any overlap with another frame, and since an interfering frame can begin at any time from one frame-time before to one frame-time after, the vulnerable period is two frame times. With Poisson offered traffic $G$ the throughput is

so at best 18.4 per cent of the channel carries useful data; slotting time so that transmissions may begin only on slot boundaries halves the vulnerable period and doubles this to $S_{\max} = 1/e = 0.368$, or 36.8 per cent. CSMA/CD does two things Aloha does not, and each attacks one of the two ways Aloha wastes the channel. Listening before transmitting means most potential collisions never start at all, since a station only transmits when the channel is genuinely idle; and detecting a collision while transmitting means the ones that do start are aborted after roughly a propagation delay instead of running for a whole frame time. The efficiency becomes approximately

and $a$ is small on a LAN: with $\tau_{\max} = 25.6\ \mu\text{s}$ and a 1500-byte frame at 10 Mbit/s, $T_{\text{frame}} = 1.2$ ms, so $a = 0.021$ and $\eta \approx 90.4$ per cent — roughly five times Aloha's best. In one sentence: Aloha wastes the channel because it neither avoids collisions nor truncates them, while CSMA/CD does both.

Aloha is more appropriate wherever carrier sense is impossible or worthless. The canonical case is a satellite channel: for a geostationary satellite the one-way path is 35 786 km, giving $\tau = 119\ \text{ms}$ and a 239 ms hop, so with a 1000-bit frame at 64 kbit/s ($T_{\text{frame}} = 15.6$ ms) the parameter is $a = 7.6$ — what a station senses is over seven frame times out of date, so listening tells it nothing about the present and collision detection cannot work at all. The same argument applies to any very large population of cheap, low-duty-cycle terminals, where coordination costs more than the collisions it would save: RFID tag inventories, sensor and telemetry uplinks, LoRaWAN class-A devices, and — the example every mobile phone uses several times a day — the random-access channel on which a handset requests a dedicated channel from a cellular base station, which is slotted Aloha precisely because the terminals cannot hear one another.