Question 3 of 5: Medium access control protocols (25 marks)

Question 3 — 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.

Given. Three families of medium access control: contention with carrier sensing (CSMA/CA in 802.11, CSMA/CD in 802.3), controlled access by token passing (IEEE 802.5), and random access without sensing (Aloha). The illustrative constants used below are the standard ones: signal speed on copper $v \approx 2.0 \times 10^{8}$ m/s, the 10BASE5 maximum span of 2500 m, the 802.3 slot time of 512 bit times, the geostationary altitude of 35,786 km and $c = 2.998 \times 10^{8}$ m/s. Find. Explanations of the hidden and exposed terminal problems and of what RTS-CTS does about each; the operation of a token ring and whether it can suffer collisions; the shortest possible collision-detection time with the reasoning that bounds it; and why Aloha beats CSMA/CD when propagation delay is large.

Approach. Parts (a) and (b) are geometric: draw the range circles and read off who can hear whom. Parts (d) and (e) both turn on the single ratio $a = \tau / T_{\text{frame}}$ of propagation delay to frame transmission time, so both are computed from that.

Part (a) — The hidden terminal problem

Part (a) — the problem. Carrier sensing asks the wrong question. A transmitter senses the medium at itself, but a collision is an event at the receiver. In the left panel of Figure 3.1, stations A and C are each within range of B but the distance between them exceeds either one's range, so A is hidden from C and vice versa. Both sense an idle medium, both transmit to B, and the two signals overlap at B. B receives a corrupted frame and sends no acknowledgement; neither sender has any way to know that the other exists. Because both then retry, the failure repeats, and throughput on a network with many hidden pairs collapses well below the single-transmitter rate.

How RTS-CTS mitigates it. RTS-CTS replaces physical carrier sensing with virtual carrier sensing centred on the receiver. Before sending data, A transmits a short Request To Send naming B and stating the duration of the exchange it wants. B answers with a Clear To Send carrying the same duration field. The essential point is that the CTS comes from B, so it is heard by everyone within range of the receiver — including C, precisely the station that could ruin the reception. C loads the duration into its Network Allocation Vector, a countdown timer, and treats the medium as busy until the NAV expires, whether or not it can hear anything. The collision window is reduced from the whole data frame to the short RTS itself, which is the quantitative benefit: two hidden stations can still collide, but only on a 20-byte RTS rather than on a 1500-byte data frame.

Part (b) — The exposed terminal problem

Part (b) — the problem. This is the dual fault, and it costs capacity rather than correctness. In the right panel of Figure 3.1, B is transmitting to A. Station C is within range of B and therefore senses a busy medium, so C defers — but C wanted to send to D, and D is out of B's range while A is out of C's range. The two transmissions could have proceeded simultaneously with no interference at either receiver. C is exposed: it has been silenced by a transmission that was never a threat to it, and the spatial reuse the geometry allows is thrown away.

How RTS-CTS mitigates it. The RTS-CTS handshake gives a station enough information to distinguish the two cases, because the two control frames travel in opposite directions. A station that hears an RTS but no matching CTS is, by construction, in range of the sender but not of the receiver — that is the definition of being exposed — and the MACA rule is that such a station may transmit. A station that hears the CTS is in range of the receiver, is therefore hidden or a genuine interferer, and must defer.

Part (c) — Token ring operation, and whether it can collide

Part (c) — operation. In IEEE 802.5 the stations are wired into a closed loop and each station acts as an active repeater, so bits circulate in one direction around the ring. Access is granted by a three-octet token that circulates when the ring is idle. A station with data waits for the token, seizes it by flipping the token bit in the access-control field, and appends its frame — so the token is converted into the header of the frame rather than being destroyed. The frame travels around the ring; the addressed station copies it and sets the address-recognised and frame-copied bits in the trailing frame-status field, which serves as a hardware acknowledgement. The frame continues round to the original sender, which drains it from the ring and, having either exhausted its token-holding time or run out of data, issues a fresh token to its downstream neighbour.

Are collisions possible? In normal operation, no. This is controlled rather than contention access: exactly one token exists and only the station holding it may transmit, so two transmissions can never overlap. That gives token ring its defining property — deterministic, bounded access delay. With $N$ stations and a token-holding time $\text{THT}$, no station waits longer than

$$T_{\text{access,max}} = N \times \text{THT} + \text{ring latency}$$

and for $N = 250$ stations with $\text{THT} = 10$ ms this is 2.5 s: large, but bounded, which is what a real-time control application needs and what CSMA/CD cannot offer at any load. Passing the token itself is cheap — 24 bits, or 1.5 µs at 16 Mbit/s.

The qualification that earns the last mark is that the guarantee holds only while the ring is healthy. If the token is lost, corrupted or duplicated — by a station failing while holding it, or by a transient on the medium — the ring would either deadlock or carry two simultaneous transmissions. IEEE 802.5 therefore elects one station as active monitor: it runs a valid-transmission timer, purges the ring and regenerates a single token if the timer expires, and removes circulating orphan frames using the monitor bit. So overlapping transmissions are possible only as a transient fault condition, are detected and cleared by the monitor, and are not collisions in the CSMA/CD sense of a normal, expected part of the access mechanism.

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

1. Part (d) — identify what fixes the detection time. In a collision-detecting scheme a transmitter recognises a collision when the energy it senses on the medium differs from what it is sending. The delay is therefore the time for the other station's signal to propagate to it, $\tau = d / v$, where $d$ is the separation of the two colliding stations and $v$ is the signal velocity on the medium.
2. Take the best case. Nothing in the question bounds $d$ from below. Two stations attached at essentially the same point on the cable, transmitting at essentially the same instant, have $d \to 0$ and hence $\tau \to 0$: each hears the other's signal almost immediately and aborts within a few bit times. For $d = 1$ m on copper, $\tau = 1 / (2 \times 10^{8}) = 5$ ns.
3. Take the worst case, which is the one that sizes the standard. The longest wait occurs when station X begins transmitting an instant before Y's signal — launched $\tau$ earlier from the far end — would have reached it. Y hears X and aborts, but X only learns of the collision when Y's signal completes the round trip:
   $$T_{\text{detect,max}} = 2\tau_{\max} = \frac{2L}{v} = \frac{2 \times 2500\ \text{m}}{2.0 \times 10^{8}\ \text{m/s}} = 25\ \mu\text{s}$$
4. Check the standard against that bound. A station must still be transmitting when the news arrives, or it would never detect the collision. IEEE 802.3 therefore 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} = 2.05 \times 2\tau_{\max}$$and mandates a minimum frame of $512/8 = 64$ bytes, padding shorter frames to reach it.

Collecting the two bounds:

$$\boxed{0 \;\le\; T_{\text{detect}} \;\le\; 2\tau_{\max}, \qquad T_{\text{detect,min}} \to 0 \text{ for adjacent stations}, \qquad 2\tau_{\max} = 25\ \mu\text{s on a 2500 m 10BASE5 segment}}$$

The answer the examiner is looking for is the reasoning rather than a single number: the shortest possible detection time is essentially immediate — one propagation delay between the two colliding stations, which can be made arbitrarily small — while the design constraint comes from the worst case of one full round trip.

Part (e) — Why Aloha, not CSMA/CD, over a satellite link

1. Part (e) — compute the propagation delay. A geostationary satellite sits 35,786 km above the equator, and a frame travels up and down:
   $$\tau = \frac{2h}{c} = \frac{2 \times 35\,786\ \text{km}}{2.998 \times 10^{8}\ \text{m/s}} = 238.7\ \text{ms}$$
2. Compare it with the frame time. For a 1000-bit frame on a 64 kbit/s channel, $T_{\text{frame}} = 1000 / 64\,000 = 15.6$ ms, so the normalised propagation delay is
   $$a = \frac{\tau}{T_{\text{frame}}} = \frac{238.7\ \text{ms}}{15.6\ \text{ms}} = 15.3$$against $a \approx 0.02$ for a frame of the same length on a LAN.
3. Read off what that does to carrier sensing. The channel state a station senses is the state as it was $\tau = 238.7$ ms ago. Fifteen frame times can have started in that interval without the sensing station seeing any of them, so an idle reading carries almost no information and CSMA degenerates to pure Aloha while still paying the sensing delay.
4. And to collision detection. To learn of a collision the sender must wait a full round trip,
   $$2\tau = 477.5\ \text{ms} \;\gg\; T_{\text{frame}} = 15.6\ \text{ms}$$so the frame finished transmitting roughly thirty frame-times before the news could arrive. There is nothing left to abort, and the aborting — which is the entire benefit of the “CD” in CSMA/CD — saves nothing.

Therefore

$$\boxed{a = \tau / T_{\text{frame}} \approx 15 \gg 1 \;\Longrightarrow\; \text{sense-before-send and abort-on-collision are both useless; use Aloha}}$$

Aloha makes the opposite bet and it is the right one here: transmit whenever you have data, wait for an acknowledgement, and if none arrives retransmit after a random backoff. It needs no knowledge of the channel state, which is exactly the knowledge that is unobtainable. The price is throughput — pure Aloha peaks at $1/2e = 0.184$ and slotted Aloha, which aligns transmissions to slot boundaries and so halves the vulnerable period, at $1/e = 0.368$, against 0.9 or better for CSMA/CD on a LAN. On a satellite channel that ceiling is not a defect of Aloha but the best any protocol can do without usable channel state, and it is why satellite systems that need more than 37 per cent use reservation or demand-assignment schemes rather than trying to sense the carrier.