Question 3 of 5: Medium access control

Question 3: Medium access control (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 Ethernet medium access control method

Classical Ethernet uses one-persistent carrier sense multiple access with collision detection. A station with a frame to send first listens; if the medium is busy it keeps listening and transmits the instant the medium goes idle, which is what “one-persistent” means. While transmitting it continues to monitor the medium, comparing what it hears with what it sent. A mismatch means another station began transmitting before its signal had propagated the length of the cable, so the two transmissions are overlapping: this is a collision, and it is a normal, expected event on a shared medium, not a fault.

Recovery has two parts. First, the detecting station immediately aborts the frame and transmits a 32-bit jam sequence, which guarantees that every other station on the segment also registers the collision rather than some of them mistaking a short burst for a valid frame. Second, each colliding station backs off for a random time chosen by truncated binary exponential backoff: after the $k$-th consecutive collision it waits $r$ slot times where $r$ is drawn uniformly from $0 \le r \lt 2^{\min(k,10)}$, retrying up to sixteen times before reporting failure to the higher layer. Doubling the window on each collision makes the stations progressively less likely to choose the same instant again, so the algorithm adapts its aggressiveness to the observed load without any station ever knowing how many others exist. The randomisation is essential: two stations that backed off by the same fixed amount would collide again forever.

(b) The longest time before a collision is detected

Given. A classical shared-medium Ethernet segment whose end-to-end one-way propagation delay, including repeater and transceiver latency, is $\tau$. For the IEEE 802.3 10 Mbit/s configuration this is the worst-case 2500 m path through four repeaters, and signals travel on coaxial cable at about $2.31\times10^{8}$ m/s.

Find. The worst-case interval between the start of a transmission and the moment the transmitting station learns that a collision has occurred, and the minimum frame length that interval implies.

Approach. Construct the worst case by placing the two stations at opposite ends of the segment and letting the second one start an instant before the first one’s signal arrives; the answer is then the round trip, $2\tau$.

1. Set up the worst-case timing. Station A at one end begins at $t=0$. Its signal reaches station B at the far end at $t=\tau$. If B has sensed an idle medium and begins its own transmission at $t=\tau-\varepsilon$, the collision occurs at B almost immediately, but A knows nothing of it until B’s signal has travelled all the way back: $$t_{\text{detect}} = \tau + (\tau - \varepsilon) \to 2\tau$$ so the longest possible time before a collision is detected is one round-trip propagation delay, twice the end-to-end delay of the segment.
2. Put numbers on the standard configuration. The 2500 m of cable alone contributes $$t_{\text{cable}} = \frac{2500\ \text{m}}{2.31\times10^{8}\ \text{m}\,\text{s}^{-1}} = 10.8\ \mu\text{s}$$ and the four repeaters, their transceivers and the collision-detect logic account for the remainder of the allowance, which IEEE 802.3 fixes at $\tau_{\max}=25.6\ \mu$s one way. Hence $$t_{\text{detect,max}} = 2\tau_{\max} = \boxed{51.2\ \mu\text{s}}$$ This interval is the standard’s slot time.
3. Convert the slot time into the minimum frame length. A station must still be transmitting when the news arrives, or it will never hear the collision at all, so the frame must occupy at least one slot time: $$L_{\min} = R\,t_{\text{detect,max}} = 10\times10^{6} \times 51.2\times10^{-6} = 512\ \text{bits} = \boxed{64\ \text{bytes}}$$ which is exactly the 64-byte minimum Ethernet frame, and the reason short frames are padded.

The same reasoning explains why 100 Mbit/s Ethernet keeps a 512-bit slot time but shrinks the maximum span by a factor of ten, and why gigabit Ethernet needed carrier extension before switching made the whole question moot: on a full-duplex switched link there is no shared medium, so there are no collisions and no slot time at all.

(c) Hidden and exposed terminals, and a protocol that solves them

Carrier sensing answers the question “is the medium busy here?” On a cable that is the same as asking whether it is busy at the receiver, because the cable is one electrical object. On a radio it is not, because attenuation makes the medium busy in one place and idle in another, and both possible mismatches cause trouble.

The hidden terminal problem is a false idle. In the figure, A is transmitting to B, and C also wishes to send to B. C is out of A’s range, so C senses an idle medium, concludes it may transmit, and its frame collides with A’s at B. Neither sender can detect the collision, because neither is in range of the other; only B knows, and its evidence is a corrupted frame. The collision destroys both transmissions, and the cost rises with frame length, so hidden terminals cripple throughput exactly where it matters most.

The exposed terminal problem is the mirror image, a false busy. Suppose B is transmitting to A while C wishes to send to D. C hears B’s transmission and defers, yet the transmission it feared would collide would have arrived at D, far from A, and A hears nothing of C. A perfectly safe simultaneous exchange is suppressed, so the network wastes capacity it could have used. Hidden terminals cause collisions; exposed terminals cause needless idleness.

The protocol that addresses both is the RTS/CTS handshake, introduced as MACA and adopted, with acknowledgements, as the optional four-way exchange of the IEEE 802.11 distributed coordination function. Before sending a long frame the sender transmits a short request to send carrying the duration of the intended exchange. The intended receiver answers, after a SIFS, with a clear to send carrying the same duration. Every station that hears either control frame loads that duration into its network allocation vector and treats the medium as busy until the vector expires, whether or not it can hear anything on the air. This is virtual carrier sensing, and it works because the reservation is announced by the receiver as well as the sender.

The hidden terminal is solved because C, though deaf to A, is in range of B and so hears B’s clear-to-send; it therefore stays silent for the whole exchange, and the only frames at risk are the very short control frames rather than the data. The exposed terminal is solved because C hears B’s request to send but never receives a clear-to-send from A — and it is the clear-to-send, not the request-to-send, that obliges a station to defer — so C is free to start its own exchange with D. Two costs should be stated honestly: the handshake adds overhead that is only worth paying above a frame-length threshold, and it cannot help when the interferer is out of range of both the sender and the receiver.

(d) A channelized method such as FDMA compared with Ethernet

Advantage. A channelized method gives each user a private, permanently reserved channel, so access is deterministic: there are no collisions, no backoff and no retransmissions, and therefore a bounded and predictable delay and a throughput that does not collapse as the offered load rises. That guarantee is exactly what constant-bit-rate traffic such as voice needs, and it is why the cellular and satellite links of this paper are channelized while the office LAN is not. It also removes the round-trip-delay constraint that ties Ethernet’s minimum frame size to its maximum span.

Disadvantage. The channel is reserved whether or not it is used, so a silent user wastes its entire allocation while a busy user cannot borrow the idle capacity next to it. For the bursty traffic that dominates data networks — long silences punctuated by short bursts — this is very inefficient, whereas Ethernet lets a single active station take essentially the whole medium. A channelized system also caps the user population rigidly at the number of channels, needs explicit signalling to set up and tear down assignments, and pays for guard bands (or guard times) between channels, whereas Ethernet admits a new station with no coordination at all.