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

Question 2 — 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. A shared medium carrying signals at a propagation velocity $v\approx2\times10^{8}\ \text{m/s}$; IEEE 802.3 10 Mbit/s Ethernet, whose slot time is 512 bit times; and a wireless network in which stations can hear some but not all of their peers. Find. How CSMA/CD detects and recovers from a collision, how ALOHA and token ring differ from it, how RTS/CTS/ACK repairs the hidden- and exposed-terminal problems, and the shortest time that can elapse before any scheme detects a collision.

Part (a) — Operation of CSMA/CD

Carrier Sense Multiple Access with Collision Detection is the access method of classical IEEE 802.3 Ethernet on a shared segment. It has three distinct phases — listen before, listen during, and recover after — and the marks are distributed across all three.

Listen before (carrier sense). A station with a frame ready senses the medium. If the medium is busy it waits; Ethernet is 1-persistent, so as soon as the medium goes idle the station transmits immediately, having waited only the 96-bit inter-frame gap. 1-persistence maximises utilisation at low load, at the price of making a collision near-certain if two stations were both waiting on the same busy medium.

Listen during (collision detection). Carrier sense cannot prevent collisions, because a station a propagation delay away may have started transmitting without its signal having reached us yet. The station therefore continues to monitor the medium while transmitting and compares what it hears with what it is sending — on coaxial cable by watching the average DC level, on twisted pair by detecting simultaneous activity on the transmit and receive pairs. A mismatch is a collision.

Recovery. On detecting a collision the station does three things in order. It aborts the data immediately, so no further bandwidth is wasted on a frame that is already lost. It then transmits a 32-bit jam sequence, which guarantees that the collision lasts long enough for every other station on the segment to notice it — without the jam, a station far away might see only a short glitch. Finally it backs off: after the $k$-th consecutive collision on the same frame it waits

which is truncated binary exponential backoff. Doubling the range at each attempt makes the retry set sparser exactly when the segment is congested, so the protocol adapts to load without measuring it; the truncation at $k=10$ caps the range at $2^{10}-1=1023$ slots, and after 16 attempts the frame is discarded and the failure reported upward.

The slot time is the quantity that ties the whole scheme together. It is the worst-case round-trip propagation time across a maximum-size collision domain, standardised as 512 bit times:

Hence the 64-byte minimum frame: a station must still be transmitting when the worst-case collision echo returns, otherwise it would finish, declare success and never learn that its frame was destroyed. The longest backoff the standard can impose follows from the same number, $1023\times51.2\ \mu\text{s}=52\,377.6\ \mu\text{s}\approx52.4\ \text{ms}$. Efficiency degrades with the ratio $a=\tau/T_{\text{frame}}$, which is why CSMA/CD could not simply be scaled to gigabit rates and was displaced by full-duplex switched links.

Part (b) — ALOHA compared with CSMA/CD, and collisions in token ring

An ALOHA network omits both the CS and the CD. In pure ALOHA a station transmits the instant a frame is ready, without listening first and without monitoring the medium afterwards; the only feedback is whether an acknowledgement arrives before a timeout, whereupon the frame is retransmitted after a random delay. Because a frame of duration $T$ is destroyed by any transmission starting in the window $2T$ around it, the maximum throughput is

slotting halving the vulnerable period by forcing all transmissions to begin on a slot boundary. The differences from CSMA/CD are therefore: no carrier sense, so collisions are provoked rather than largely avoided; no collision detection, so an entire doomed frame is transmitted instead of being aborted within a slot time; and no jam signal, recovery relying purely on timeout and random retransmission. The compensating virtue is that ALOHA needs no feedback path and no propagation-delay assumptions, which is why it survives in satellite and random-access cellular signalling channels.

Collisions in a token ring: no, by construction. Access is by explicit permission rather than by contention. A single token circulates around the ring and a station may transmit only while it holds that token; having transmitted, it releases the token to its downstream neighbour. Since exactly one token exists, exactly one station can be transmitting, so two transmissions can never overlap. The corresponding failure modes are different in kind — a lost token, a duplicated token, or a persistently circulating orphan frame — and are repaired by the active monitor, which times the ring, regenerates a lost token and drains orphaned frames. The trade is deterministic bounded access delay in exchange for token-management complexity and a rotation-time penalty at light load.

Part (c) — Hidden and exposed terminals, and RTS/CTS/ACK

The hidden terminal problem. 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 — A is hidden from it — concludes the medium is free and also transmits to B. The two frames collide at B and both are lost, although neither sender did anything wrong by its own carrier sense. The lesson is that carrier sense tests the wrong place: what matters is whether the medium is free at the receiver, and the transmitter cannot observe that.

The exposed terminal problem is the mirror image and costs throughput rather than frames. B transmits to A. C hears B, so its carrier sense reports the medium busy and C defers — even though a transmission from C to D would have been received perfectly, because D is out of range of B and A is out of range of C. A perfectly feasible parallel transmission is suppressed.

How RTS/CTS/ACK repairs them. Before a data frame the sender transmits a short Request To Send carrying the duration of the entire exchange that is to follow. The intended receiver answers, a SIFS later, with a Clear To Send carrying the remaining duration. Every station that hears either frame loads that duration into its network allocation vector and treats the medium as busy for that long — virtual carrier sense, which needs no signal energy to work.

• Hidden terminal solved. C cannot hear A, but C is within range of B and therefore hears B's CTS. C sets its NAV and stays silent for the whole exchange, so the collision at B cannot occur. Only the short RTS remains at risk, and losing a 20-byte RTS costs far less than losing a 1500-byte data frame.
• Exposed terminal alleviated. C hears B's RTS but never hears a CTS addressed from the far side, which tells C that it is a neighbour of the sender rather than of the receiver; in the idealised model it may then proceed with its own transmission to D. In practice 802.11 has C defer on the RTS as well, so the exposed-terminal gain is only partially realised — a point worth stating explicitly.
• The ACK, returned after SIFS, is the substitute for collision detection. Its absence, not any observed interference, is what tells the sender to back off and retry.

Because the handshake costs an RTS, a CTS and two SIFS gaps, 802.11 applies it only to frames longer than a configurable RTS threshold; below that the overhead would exceed the collision cost it avoids.

Part (d) — Shortest period before a collision is detected

This part is quantitative, so it is worth setting it out formally.

Given. Two stations separated by a distance $d$ on a medium with propagation velocity $v\approx2\times10^{8}\ \text{m/s}$; a collision is detected by observing the other station's signal. Find. The shortest interval that can elapse between the start of a transmission and the detection of the resulting collision.

Approach. No station can react to a signal before that signal physically arrives, so the answer is governed entirely by the one-way propagation delay and by how the two start instants are placed.

1. Write the one-way propagation delay. The delay between the two stations is $$\tau=\frac{d}{v}.$$ This is the irreducible quantity: nothing either station does can make information cross the medium faster.
2. Take the most favourable start alignment. Suppose both stations begin transmitting at exactly the same instant $t=0$. Each one's leading edge reaches the other after $\tau$ seconds, so both discover the collision simultaneously at $$t_{\text{detect}}=\tau=\frac{d}{v}.$$ No alignment can do better, because before $\tau$ has elapsed neither station has received any evidence that the other exists.
3. Contrast with the least favourable alignment. Suppose instead the second station starts at $t=\tau^{-}$, an instant before the first station's signal arrives. Its own signal then needs a further $\tau$ to travel back, so the first station learns of the collision only at $$t_{\text{detect}}=2\tau,$$ the familiar round-trip bound that sets the Ethernet slot time.
4. Put numbers to it. For two stations $d=100$ m apart, $$\tau=\frac{100\ \text{m}}{2\times10^{8}\ \text{m/s}}=0.5\ \mu\text{s},\qquad 2\tau=1.0\ \mu\text{s}.$$ Detection therefore takes between half a microsecond and one microsecond on that particular pair.
5. Answer the question as asked. The question asks for the shortest period using any access scheme, so $d$ is ours to choose, and $\tau\to0$ as $d\to0$: $$\boxed{t_{\min}=\tau=\frac{d}{v}\ \longrightarrow\ 0\ \text{as}\ d\to0}$$ There is no positive lower bound imposed by the protocol. For two adjacent stations starting simultaneously, a collision is detected essentially immediately, and the only real floor is the transceiver's own collision-detect response time (a few bit times of analogue and logic delay).
6. State the design consequence. The shortest time is of no engineering use; the longest is. Because the standard must work for the worst-placed pair, 10 Mbit/s Ethernet fixes $$2\tau_{\max}=T_{\text{slot}}=51.2\ \mu\text{s}=512\ \text{bit times},$$ and requires every frame to be at least that long so that a transmitter is guaranteed to still be sending when the worst-case echo arrives.