Question 3 of 5: Medium access control protocols

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.

(a) The operation of CSMA/CD

CSMA/CD — Carrier Sense Multiple Access with Collision Detection, standardised as IEEE 802.3 — governs a set of stations sharing one broadcast medium on which any two overlapping transmissions destroy each other. It proceeds in three movements: sense, transmit while listening, and recover.

Carrier sense. A station with a frame ready first listens to the medium. If energy is present it defers; 802.3 is 1-persistent, so it keeps listening and transmits as soon as the medium goes idle, after an inter-frame gap of 96 bit times. If the medium is already idle it transmits immediately.

Collision detection. Sensing before transmitting is not enough, because the medium has a non-zero propagation delay: a second station at the far end may have started while the first station's signal was still in flight, and would have heard silence. So the transmitter keeps its receiver active throughout its own transmission and compares what is on the wire with what it is putting there. A discrepancy — on coaxial Ethernet, an abnormal DC level; on twisted pair, simultaneous activity on both pairs — means a collision is in progress.

Recovery. On detecting a collision the station does not finish its frame. It aborts at once and sends a 32-bit jam sequence, which guarantees the collision lasts long enough for every other station to notice it, then backs off. The back-off is truncated binary exponential: after the $n$th successive collision the station waits $k$ slot times, where $k$ is drawn uniformly from $\{0, 1, \ldots, 2^{m}-1\}$ with $m = \min(n, 10)$, and abandons the frame after 16 attempts. Doubling the interval on each failure lets the station estimate the number of contenders without ever counting them: the more collisions it sees, the wider the window it draws from.

The whole scheme rests on one constraint. A station can only detect a collision while it is still transmitting, so every frame must be longer than the worst-case round-trip time of the medium. That is the origin of the 512-bit (64-byte) minimum frame and the 51.2 µs slot time at 10 Mbit/s, and hence of the 2500 m limit on a collision domain — the subject of part (d). The payoff for all this is that a collision costs one slot time rather than a whole wasted frame.

(b) How Aloha differs, and whether collisions are possible

Aloha, designed for the packet radio network linking the Hawaiian islands, does away with the first two movements entirely. Pure Aloha transmits whenever a frame is ready: there is no carrier sense, no deferral, and no listening while transmitting. A frame is lost if any other transmission overlaps it even partially, so the vulnerable period is two frame times — one before and one after the frame starts. Success is inferred from the arrival of an acknowledgement; its absence, after a timeout, is the only collision indication available, and the station then retransmits after a random delay.

Yes, collisions are not merely possible in Aloha but routine, and far more costly than in CSMA/CD because the entire frame is transmitted and wasted rather than aborted after a slot time. With Poisson offered load $G$ frames per frame time, the throughput of pure Aloha is $S = G e^{-2G}$, which peaks at $1/(2e) = 18.4\%$ of the channel; slotted Aloha, which forces every transmission to start on a slot boundary and so halves the vulnerable period to one frame time, gives $S = G e^{-G}$ with a maximum of $1/e = 36.8\%$.

The reason Aloha does not simply adopt carrier sense is physical, not historical. Carrier sense is only useful when the propagation delay is small compared with the frame time, so that "the medium is idle" is still true a moment later; over long radio paths, and certainly over a satellite hop, the medium's state as heard by a station is stale by the time it acts on it. Collision detection additionally requires a station to hear the medium accurately while transmitting, which a half-duplex radio cannot do — its own transmission swamps its receiver. Both of those constraints reappear in Wi-Fi, which is why 802.11 uses collision avoidance and acknowledgements rather than 802.3's collision detection.

(c) Hidden terminals, exposed terminals, and the RTS-CTS-ACK exchange

Both problems arise from the same fact: in a wireless network, carrier sense is performed by the transmitter, but collisions occur at the receiver, and the two are in different places with different sets of audible neighbours. On a wire every station hears every other, so the transmitter's measurement is a valid proxy for the receiver's situation; on radio it is not.

The hidden terminal problem. A and C both wish to send to B, and each is within B's range, but they are out of range of one another. Each senses the medium, hears nothing, and transmits. The two signals collide at B, and B receives nothing usable. Neither transmitter can detect this: they cannot hear each other by construction, and a half-duplex radio cannot listen while it transmits in any case. The loss is therefore a whole frame, discovered only when the acknowledgement fails to arrive. As the number of hidden pairs grows the throughput of a wireless cell collapses, because the collisions are full-length and the retransmissions collide again.

The exposed terminal problem. The reverse error. B is transmitting to A; C hears B's carrier, concludes the medium is busy, and defers, even though a transmission from C to D would have succeeded — D is out of B's range and so would not have been interfered with, and A is out of C's range and so would not have been disturbed by C. Carrier sense at C measured the wrong thing: C's own neighbourhood rather than its intended receiver's. The cost is not a collision but wasted capacity, and it grows with node density.

How RTS-CTS-ACK addresses them. The 802.11 exchange replaces physical carrier sense with virtual carrier sense conducted at both ends of the intended link. The sender first transmits a short Request To Send frame carrying a Duration field — the time the whole exchange will occupy. The intended receiver answers with a Clear To Send frame carrying the same duration. Every station that hears either frame loads that duration into its Network Allocation Vector and treats the medium as busy until the NAV expires, whether or not it can hear any signal. Data and acknowledgement follow, each separated by a Short Interframe Space so short that no contending station can seize the medium between them.

The hidden terminal is solved by the CTS, and the reason is worth stating exactly: the CTS originates at the receiver, so it reaches every station that could interfere at the receiver, including the hidden station that cannot hear the sender. C therefore learns of the transfer it could not sense and stays quiet for its duration. The residual collisions are between short RTS frames rather than long data frames, so the cost of a collision falls by an order of magnitude. The ACK supplies the missing collision-detection function: since a wireless sender cannot detect a collision while transmitting, delivery is confirmed positively, and a missing ACK triggers back-off and retransmission at the link layer, fast enough that TCP never sees the loss.

The exposed terminal is not genuinely solved, and saying so earns the mark. A station that hears the RTS also sets its NAV, so C defers exactly as it did under physical carrier sense — arguably the exchange makes the problem slightly worse. The standard's partial remedy is that a station which hears an RTS but does not subsequently hear the corresponding CTS may reset its NAV and transmit, on the reasoning that it evidently lies outside the receiver's neighbourhood. Fully exploiting exposed terminals needs the transmitters to be synchronised so that their transmissions overlap in time, which 802.11's distributed coordination function does not attempt.

(d) The shortest time that could pass before a collision is detected

Given. Two stations share a medium along which signals travel at $v \approx 2\times10^{8}$ m/s (about two-thirds of $c$ in coaxial cable or twisted pair), separated by a distance $d$; for the worst case, the maximum 10 Mbit/s collision domain of $d_{\max} = 2500$ m is used.

Find. The shortest interval that can elapse between a collision occurring and some station detecting it, and the bound that actually constrains the protocol.

Approach. A collision is detected at the instant the interfering signal physically arrives, so the detection time is a propagation delay; find the smallest and largest values that delay can take.

1. Recognise that detection is limited by propagation, not by processing. A station learns of a collision when the other station's signal reaches it. The one-way propagation delay between two stations $d$ apart is $$ \tau = \frac{d}{v} $$ and nothing in the protocol can detect the collision sooner than that, because until $\tau$ has elapsed there is physically no evidence of it at the station.
2. Take the shortest case: two stations arbitrarily close together. Nothing in $\tau = d/v$ has a floor other than the separation itself, so as $d \to 0$ the detection time tends to zero. For two stations on the same patch panel, say 10 m apart: $$ \tau_{\min} = \frac{10\ \text{m}}{2\times10^{8}\ \text{m/s}} = \boxed{50\ \text{ns}} $$ which is under one bit time at 10 Mbit/s. The honest answer to the question as asked is therefore that the shortest possible period is one one-way propagation delay between the two colliding stations, which is essentially instantaneous and has no useful lower bound.
3. Take the case the protocol must actually survive: the round trip. A station at one end that begins transmitting at $t = 0$ may collide with a station at the far end that starts just before the first signal arrives, at $t = \tau^{-}$; the resulting interference gets back to the first station only at $t \to 2\tau$. On a maximum-length domain, $$ 2\tau_{\max} = \frac{2 \times 2500\ \text{m}}{2\times10^{8}\ \text{m/s}} = 25\ \mu\text{s} $$ so a station must still be transmitting 25 µs after it began, or it will never learn that its frame was destroyed.
4. Convert the worst case into the minimum frame size. IEEE 802.3 rounds $2\tau_{\max}$ up to a slot time of 51.2 µs to allow for repeater and transceiver latency as well as pure propagation, and requires every frame to be at least one slot time long: $$ L_{\min} = t_{\text{slot}} R = (51.2\ \mu\text{s})(10\ \text{Mbit/s}) = \boxed{512\ \text{bits} = 64\ \text{bytes}} $$ which is why an Ethernet frame carrying fewer than 46 bytes of payload must be padded.

One qualification completes the answer. All of the above assumes a scheme that has collision detection at all. In a scheme without it — pure or slotted Aloha, or 802.11, where a half-duplex radio cannot hear the medium while transmitting — the shortest detection time is not a propagation delay but an acknowledgement timeout: a full frame transmission, plus the turnaround interval, plus the acknowledgement. That is three or four orders of magnitude longer, and it is the reason wireless protocols work so hard to avoid collisions rather than detect them.