22-Elec-B4 Information Technology Networks · December 2018

Question 4 of 5: Medium Access Control Protocols

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

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) — Tasks of the MAC sublayer (5 marks)

The MAC sublayer is the lower half of OSI layer 2, sitting between the physical layer beneath it and the logical link control (LLC) sublayer above. Its defining responsibility is to decide which station may transmit, and when, on a medium that several stations share. Concretely it performs: channel allocation — contention (CSMA, Aloha, backoff algorithms), reservation (RTS/CTS, polling) or scheduling (TDMA, token passing) — and the collision handling that goes with it; framing, delimiting the bit stream into frames and adding the MAC header and trailer; physical addressing, filling in and filtering on the source and destination hardware addresses so that a station accepts only frames meant for it or for a group it has joined; error detection over the frame using a cyclic redundancy check, and discarding of frames that fail it; and, in the protocols that support it, acknowledgement and retransmission of individual frames, as 802.11 does but Ethernet does not.

Two boundaries are worth drawing explicitly, because marks are lost on them. The MAC sublayer does not route: forwarding between networks on logical addresses is layer 3. And it does not present a uniform service to the network layer by itself — that is precisely the job of LLC, which hides the differences between Ethernet, 802.11 and token ring so that IP need not know which medium is underneath.

Part (b) — The hidden terminal problem and RTS/CTS (5 marks)

Carrier sensing works only when every station that can interfere at the receiver can also be heard by the transmitter, and in a radio network that is routinely false. In the figure, station A and station C both lie within range of the access point B, but the distance between A and C exceeds either one's range. When A is transmitting to B, station C senses the medium, hears nothing, and concludes it is idle — the transmission it would interfere with is hidden from it. C therefore transmits, its signal arrives at B on top of A's, and both frames are destroyed. Neither sender learns of the failure by listening, since a radio transceiver cannot hear a weak remote signal while its own transmitter is on; the loss is discovered only when the acknowledgement fails to arrive.

The RTS/CTS handshake fixes this by moving the reservation to the receiver, which is the only station that knows what will interfere with it. Before sending a data frame, A transmits a short request to send naming the destination and the duration of the exchange to follow. B replies with a clear to send carrying the same duration, and because C is within range of B, C hears that CTS even though it never heard the RTS. Every station that hears either frame sets a network allocation vector — a countdown timer holding the announced duration — and treats the medium as busy for that period whether or not it can sense any carrier. This is virtual carrier sensing, and it silences C for exactly as long as B needs. The residual risk shrinks to a collision between two short RTS frames, which costs microseconds rather than a whole data frame; the price is the handshake overhead, which is why 802.11 applies RTS/CTS only to frames longer than a configurable threshold.

Part (c) — The exposed terminal problem and RTS/CTS (5 marks)

The exposed-terminal problem is the mirror image: carrier sensing is too conservative. In the figure B is transmitting to A while C wishes to transmit to D. Station C senses B's carrier, finds the medium busy and defers — yet C's transmission would have reached only D, which is out of B's range, and B's reception at A is unaffected by C because A is out of C's range. The two exchanges could have proceeded simultaneously; instead one is needlessly suppressed and the capacity of the network falls. The error arises because a station senses the medium at the transmitter, whereas what actually matters is the state of the medium at the intended receiver.

RTS/CTS mitigates this by letting a station distinguish the two frames it might overhear. C hears B's RTS but, being out of A's range, hears no answering CTS. The rule — defer only when a CTS is heard, or when an RTS is heard and a CTS is expected to follow — tells C that it is exposed rather than hidden, and it may proceed to transmit to D provided it does not need to receive anything itself during that window. It must not expect to hear D's acknowledgement cleanly while B is still transmitting, so a fully correct solution requires the acknowledgement timing to be handled as well. This is why the mitigation is only partial: 802.11's defer-on-RTS behaviour and its use of physical carrier sense alongside the NAV mean real hardware still loses some exposed-terminal opportunities, and protocols such as MACA, MACAW and dual busy-tone multiple access were designed specifically to recover them.

Part (d) — Aloha and where it is used (5 marks)

Aloha is the simplest possible multiple-access rule: a station with a frame to send transmits it immediately, without listening first. If an acknowledgement comes back, the frame succeeded. If it does not, the frame collided with somebody else's, and the station waits a random backoff interval and tries again; randomising the wait is essential, since two stations that retried after a fixed delay would collide again forever. A frame is vulnerable to any transmission that begins within one frame time before or after its own start, so the vulnerable window is two frame times and the throughput of pure Aloha peaks at $S = G e^{-2G} $, that is $1/(2e) \approx 18\%$ of the channel capacity at an offered load $G = 0.5$. Slotted Aloha requires transmissions to begin only at slot boundaries, which halves the vulnerable window to one frame time and doubles the peak throughput to $1/e \approx 37\%$ at $G = 1$.

Aloha's low efficiency is deliberate: it buys extreme simplicity, needs no carrier sensing hardware, no coordination and no clock synchronisation (in the unslotted form), and it works when propagation delays are large enough to make carrier sensing useless. Those properties make it the right answer wherever many stations each send a rare, short message. It was designed for exactly that on the University of Hawaii's packet radio network. Its descendants run today in the random-access channels used by cellular systems for initial access — GSM's RACH, and the LTE and 5G PRACH preamble — where a handset must announce itself before it has any scheduled resource; in satellite return links, where the round-trip delay of a geostationary hop makes listening before transmitting meaningless; in RFID tag inventory protocols; and in low-power wide-area IoT networks such as LoRaWAN and Sigfox, whose end devices transmit a few bytes an hour and cannot afford the energy of a listening receiver.

Part (e) — The shortest time before a collision is detected (5 marks)

Given. Two stations separated by a distance $d$ on a shared medium in which signals propagate at speed $v$, using a collision-detection scheme (CSMA/CD). The illustration below uses the classic 10 Mbit/s Ethernet limits: a maximum span $d = 2500$ m and $v = 2\times10^{8}$ m/s.

Find. The shortest interval that can elapse between the start of a collision and its detection, and the interval that a protocol must allow for detection to be guaranteed.

Approach. A station detects a collision only when the other station's signal physically reaches it, so the detection time is a propagation delay; the shortest case is the one-way delay between the two colliding stations, and the guaranteed case is the round trip across the network's maximum span.

1. Identify what limits detection. Nothing can be detected before the interfering energy arrives, so the floor is set by the one-way propagation delay between the two transmitters: $$\tau = \frac{d}{v}$$ If the two stations begin transmitting at the same instant, each detects the other's signal after exactly $\tau$; if one starts slightly later it detects the collision the moment it begins to transmit into an already-busy medium, so the theoretical minimum shrinks toward zero for two stations that are adjacent. The shortest meaningful interval is therefore one propagation delay between the colliding pair.
2. Evaluate the one-way delay for the illustration. Substituting the maximum Ethernet span, $$\tau = \frac{2500\ \text{m}}{2\times10^{8}\ \text{m/s}} = 12.5\ \mu\text{s}$$ A station only 100 m from its collision partner detects in $0.5\ \mu\text{s}$, which shows how strongly the answer depends on separation rather than on the protocol.
3. Find the interval that guarantees detection. The worst case is a station at one end that begins transmitting an instant before the far end's signal reaches it: its own signal must still travel the whole span back, so the last station to learn of the collision learns after $$\boxed{2\tau = 25\ \mu\text{s}\quad\text{(round-trip, worst case); minimum} = \tau = 12.5\ \mu\text{s}}$$
4. Check against the protocol constant this sets. A sender must still be transmitting when the collision news arrives, or it will never know, so the minimum frame time must exceed $2\tau$. Ethernet's slot time is 512 bit periods, which at 10 Mbit/s is $$T_{slot} = \frac{512\ \text{bits}}{10\times10^{6}\ \text{bit/s}} = 51.2\ \mu\text{s} \gt 2\tau = 25\ \mu\text{s}$$ comfortably satisfying the requirement — and this is exactly why the minimum Ethernet frame is 64 bytes.

The general statement the question is looking for is therefore: a collision cannot be detected any sooner than the propagation delay between the two colliding stations, and a protocol must allow twice that delay across its maximum span before it may assume a transmission is safe. The same reasoning explains why CSMA/CD is abandoned at high bit rates — keeping $2\tau$ below the frame time at 1 Gbit/s would force either an implausibly long minimum frame or a network span of a few tens of metres — and why wireless networks avoid collision detection entirely in favour of collision avoidance, since a radio cannot hear a distant collision while its own transmitter is running.