Question 4 of 5: Medium Access Control Protocols

Question 4: 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) — the exposed terminal problem, and RTS/CTS. Carrier sensing asks the wrong question. A station listens at its own antenna and defers if it hears a transmission, but what determines whether a transmission succeeds is the interference at the receiver, and in a radio network the two are not the same place. The exposed terminal problem is the resulting false alarm: a station defers to a transmission that would not have interfered with its own, and capacity is wasted.

In the figure B is sending to A, and C wishes to send to D. C is within range of B, so its carrier sense returns busy and it defers. Yet A cannot hear C and D cannot hear B, so the two transmissions would have succeeded concurrently: C is exposed to a transmission that is irrelevant to it, and the channel is idle at both receivers while both senders wait. The mirror-image fault is the hidden terminal problem, in which a station cannot hear a transmission that does collide at the receiver.

How RTS/CTS helps. The IEEE 802.11 handshake replaces carrier sense with an explicit reservation. A sender transmits a short request to send (RTS) naming the intended receiver and the duration of the exchange; the receiver, if free, answers with a clear to send (CTS) carrying the same duration. Every station that hears either frame sets its network allocation vector — a virtual carrier sense — for that duration. The key asymmetry is that the reservation is made by the CTS, which originates at the receiver, and so covers exactly the stations that could interfere there. In the figure C hears B's RTS but never hears A's CTS, so it learns that the transmission in progress is directed away from it and may proceed to D. Conversely, a hidden station that hears only the CTS is silenced, which is the case RTS/CTS solves outright.

The honest qualification is that RTS/CTS mitigates rather than eliminates the exposed terminal problem: C still cannot receive an acknowledgement from D reliably while B transmits, and a conservative implementation that defers on any RTS heard gains nothing. Because the handshake also costs two extra frames and two interframe spaces per exchange, 802.11 applies it only above an RTS threshold, typically to frames of more than a few hundred bytes.

Part (b) — CSMA/CD in Ethernet. Classic shared-medium Ethernet (IEEE 802.3) is 1-persistent carrier sense multiple access with collision detection, and it runs as follows. A station with a frame to send first listens; if the cable is busy it waits and transmits as soon as the medium goes idle (this is the 1-persistent part), after an interframe gap of 96 bit times. While transmitting it continues to monitor the medium, comparing what it hears with what it sent.

Collisions. Two stations that find the medium idle within one propagation delay of each other will both begin, and their signals superpose somewhere on the cable. Collisions are therefore not a failure of the protocol but an unavoidable consequence of a finite signal speed on a shared medium — the vulnerable interval is one end-to-end propagation delay, $\tau$, long. Each transmitting station detects the anomaly electrically, either by the doubled voltage on coaxial cable or by simultaneous activity on both pairs of a twisted-pair link.

Recovery. On detecting a collision a station does three things. It aborts the frame at once, rather than wasting the medium for the remaining bytes, and sends a 32-bit jam sequence so that every other party recognises the event. It then backs off for a random number of slot times drawn by truncated binary exponential backoff: after the $n$th successive collision the delay is $r \times 51.2\ \mu s$ with $r$ uniform on $\{0, 1, \ldots, 2^{\min(n,10)} - 1\}$, so the contention window doubles with each failure and adapts to the offered load without any station knowing how many others there are. After 16 attempts the frame is discarded and the failure reported upward. Finally, the minimum frame length of 64 bytes (512 bits) exists so that a station is still transmitting when the worst-case collision reaches it — a frame that finished earlier could not be known to have collided, and the retransmission responsibility would fall to a slower layer.

Two limits are worth stating: CSMA/CD applies only to half-duplex shared media, so a modern full-duplex switched link never runs it, and it cannot be used on radio, where a transmitter's own signal swamps its receiver — hence the collision avoidance of 802.11.

Part (c) — ALOHA, and whether collisions are possible. ALOHA, devised at the University of Hawaii in 1970 to link island campuses by radio, is the simplest possible multiple-access rule: transmit whenever you have a frame. There is no carrier sense and no coordination. Terminals send on a common inbound channel to a central hub, which repeats every correctly received frame on a separate outbound channel; a sender that hears its own frame repeated (or receives an acknowledgement) knows it succeeded, and a sender that does not, waits a random time and tries again. Slotted ALOHA adds one refinement, a global clock that forces every transmission to begin at a slot boundary.

Yes — collisions are not merely possible, they are intrinsic. Because stations transmit without listening, any overlap in time between two frames destroys both. In pure ALOHA a frame of duration $T$ is destroyed by any other frame beginning in the interval from $T$ before it to $T$ after it, so the vulnerable period is $2T$; with Poisson traffic of $G$ frame-attempts per frame time the throughput is $S = G e^{-2G}$, maximised at $G = 0.5$ to give $S_{max} = 1/(2e) = 0.184$, that is 18.4 percent of the channel. Slotting halves the vulnerable period to $T$, giving $S = G e^{-G}$ and $S_{max} = 1/e = 0.368$. Those two numbers are the whole argument for carrier sensing: CSMA reduces the vulnerable period from a frame time to a propagation delay, and CSMA/CD reduces the cost of a collision from a whole frame to a fraction of one. ALOHA's descendants survive where sensing is impractical — the random-access channel used by a mobile to make its first contact with a base station, and RFID tag inventories, both use it.

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

Given. A shared medium in which a signal travels at $v \approx 2 \times 10^{8}$ m/s (about two thirds of the free-space speed of light in copper or fibre); two stations separated by a distance $d$ on that medium; for the numerical illustration, a classic 10 Mbit/s Ethernet segment of maximum span $L = 2500$ m operating at $R = 10$ Mbit/s.

Find. The shortest interval that can elapse between the start of a colliding transmission and the detection of the collision, and the worst case that the protocol must therefore be designed around.

Approach. A collision is a physical event that must propagate: no station can know of it before the other station's signal has physically reached it. Bound the detection time by the propagation delay between the two stations, then take the limits.

1. Write the propagation delay between the two stations. The interfering signal cannot arrive sooner than $$t_{prop} = \frac{d}{v},$$ so a station transmitting at time zero cannot detect a collision with a station a distance $d$ away any earlier than $t_{prop}$ after that station started.
2. Take the shortest case. As $d \to 0$ the delay vanishes, so the shortest possible detection time is essentially immediate — two stations at the same point on the medium, starting together, corrupt each other's first bit. The practical floor is set by the receiver, which needs about one bit time to register the anomaly: $$t_{min} \approx \frac{1}{R} = \frac{1}{10 \times 10^{6}} = \boxed{0.1\ \mu\text{s (one bit time)}}$$ Two stations 10 m apart, for instance, are only 50 ns of propagation apart, which is less than one bit time at 10 Mbit/s.
3. Take the worst case, which is what the protocol must survive. The unlucky pattern is a station at one end of the segment starting just before the other end's signal arrives; its own signal must then travel back before it learns of the collision, so $$t_{max} = 2\tau = \frac{2L}{v} = \frac{2 \times 2500}{2 \times 10^{8}} = 25\ \mu\text{s},$$ where $\tau = L/v = 12.5\ \mu$s is the one-way end-to-end delay.
4. Check the consequence for frame length. A station must still be transmitting when the worst-case collision reaches it, so its frame must last at least $2\tau$. At 10 Mbit/s the 512-bit minimum frame occupies $$T_{slot} = \frac{512}{10 \times 10^{6}} = 51.2\ \mu\text{s} > 25\ \mu\text{s},$$ which is why 64 bytes is the Ethernet minimum and why the slot time, not the shortest case, is the number that appears in the standard.

In one sentence: the shortest period is essentially zero — one bit time, 0.1 microseconds here — because two adjacent stations corrupt each other immediately; the number that matters to the designer is the worst case of one round-trip propagation, $2\tau = 25\ \mu$s across a maximum-length segment, since a station must remain transmitting for that long to be certain no collision occurred.

Part (e) — is token ring appropriate for a wireless network? No. Token ring works by circulating a small permit frame around a closed logical loop; a station may transmit only while holding the token, which makes access deterministic, collision-free and bounded in delay — genuinely attractive properties for the real-time traffic a wireless network increasingly carries. Every one of its structural assumptions, however, fails on radio.

The protocol assumes a fixed, known ring order, but a wireless network's membership changes as stations move, sleep, join and leave, so the ring must be continually rebuilt. It assumes full connectivity, since each station must reliably hear its predecessor; radio range is limited and asymmetric, and hidden terminals mean the graph is not even guaranteed to be connected, let alone a ring. It assumes a reliable medium: a token lost to a fading dropout stops the entire network until a monitor station times out and regenerates it, and a duplicated token corrupts it, so the maintenance overhead that is rare on cable becomes routine on radio. And a token must be passed even to stations with nothing to send, which on a battery-powered network conflicts directly with power-save operation.

The verdict is therefore that the pure protocol is inappropriate, while its idea is not: 802.11's optional point coordination function, and the HCCA of 802.11e, obtain the same collision-free determinism by having the access point poll stations in turn. Polling keeps the deterministic schedule but centralises it, so a lost poll costs one station one turn rather than halting the network, and the coordinator can maintain the membership list that a physical ring cannot. Where a genuinely distributed token has been tried on radio — for example in some mesh and industrial WirelessHART-style designs — it is always accompanied by substantial token-recovery machinery.