Question 5 of 6: Medium access control protocols

Question 5: 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 local area network. For the timing argument of part (d) the worked example is 10BASE5 Ethernet: a maximum collision domain of $d = 2500\text{ m}$, a signal propagation velocity of $v = 2\times10^{8}\text{ m/s}$ (about two thirds of the speed of light in coaxial cable), a bit rate of 10 Mbit/s and the standard slot time of 512 bit times.

Find. The operation of and recovery from collisions in CSMA/CD, how token ring differs and whether it can collide, the hidden and exposed terminal problems and the role of RTS/CTS/ACK, and the shortest time that can elapse before a collision is detected.

Part (a) — CSMA/CD. Carrier sense multiple access with collision detection is the access method of classical half-duplex Ethernet. A station with a frame to send first listens to the medium; if a carrier is present it defers, and in the 1-persistent form used by Ethernet it transmits as soon as the medium goes idle, after an interframe gap. Carrier sense does not eliminate collisions, because a station a propagation delay away may already have started transmitting without the signal having arrived yet; two stations that begin within one propagation delay of each other will overlap. While transmitting, a station therefore continues to monitor the medium and compares what it hears with what it is sending. A mismatch — on coaxial cable, an abnormal signal level — is a collision. Recovery has three parts. The station aborts the frame immediately, so no time is wasted finishing a frame that is already corrupt; it transmits a 32-bit jam sequence to guarantee that every other party to the collision also detects it; and it then backs off for a random interval before retrying. The randomisation is binary exponential backoff: after the $n$-th consecutive collision the station waits $k$ slot times where $k$ is drawn uniformly from $0$ to $2^{\min(n,10)}-1$, so the mean backoff doubles with each successive collision until it is capped at the tenth attempt, and the frame is abandoned with an excessive-collision error after sixteen attempts. Doubling the window is what makes the scheme stable: it adapts the retransmission rate to the offered load without any station knowing how many others are contending.

Part (b) — token ring, and whether it can collide. Token ring (IEEE 802.5) replaces contention with permission. The stations are connected in a physical or logical ring and a distinguished three-byte frame, the token, circulates continuously. A station may transmit only when it has captured the token; it changes the token into the start of its own frame, sends the frame around the ring, strips it off when it returns, and then issues a new token. The differences from CSMA/CD are fundamental rather than cosmetic. Access is deterministic: the worst-case time a station waits for the token is bounded by the ring latency plus the sum of the other stations’ token-holding times, so a delay guarantee can be given, which is why the method was preferred for factory-floor and process-control networks. Only one station may transmit at a time by construction, so the channel does not degrade under load — throughput approaches the full line rate as offered load rises, whereas CSMA/CD throughput falls away once collisions dominate. In exchange, the ring carries permanent token-management overhead even when idle, and it needs an active monitor station to recover from the failure modes that replace collisions: a lost token, a duplicated token, an orphaned frame that circulates forever because its sender has failed, and a break in the ring itself. So the direct answer to the question is that collisions in the CSMA/CD sense are not possible in a correctly operating token ring, because the token is a mutual-exclusion lock on the medium; the closest analogue is the contention that occurs during the claim-token process at ring initialisation, which is resolved deterministically by highest address rather than by random backoff.

Part (c) — hidden and exposed terminals, and RTS/CTS/ACK. The two problems, drawn in Figure 5.1, both arise because in a radio network carrier sense happens at the transmitter while collisions happen at the receiver, and the two are in different places. In the hidden terminal case, stations A and C are both within range of B but out of range of each other. Each senses the medium idle, each transmits to B, and the two signals collide at B; neither sender can detect the collision, because neither can hear the other, so the frames are lost and both senders time out. In the exposed terminal case, B is transmitting to A and C wishes to transmit to D. C hears B’s carrier and defers, yet C’s transmission would have reached only D, well away from A, so the two transfers could safely have proceeded at once; the deferral is pure lost capacity. The RTS/CTS/ACK handshake of IEEE 802.11 addresses both by replacing physical carrier sense with a virtual carrier sense centred on the receiver. The sender first transmits a short request-to-send frame carrying the duration of the exchange it proposes; the intended receiver answers with a clear-to-send frame 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, without listening. This solves the hidden terminal problem because C hears B’s CTS even though it cannot hear A, and so defers for exactly the length of A’s transfer; and because only the short RTS frames can now collide, the cost of a collision falls from a whole data frame to a few tens of microseconds. It relieves the exposed terminal problem because C, hearing B’s RTS but not A’s CTS, can infer that it is outside the receiver’s neighbourhood and that transmitting will not disturb the exchange. Finally, since a radio transmitter cannot listen while it transmits and therefore cannot detect collisions at all, the positive acknowledgement is what closes the loop: the receiver returns an ACK after a short interframe space, and its absence — not a detected collision — is what triggers retransmission and backoff. The three frames together turn an undetectable collision problem into an avoidance-and-acknowledgement problem, which is why the method is called CSMA/CA.

Part (d) — the shortest time before a collision is detected. The timing argument is worked below.

1. Identify the physical limit. A station cannot know about a transmission whose signal has not yet reached it, so the earliest a station can detect a collision is one one-way propagation delay after the other station starts: $$t_{min} = \tau = \frac{d}{v}$$ where $d$ is the separation and $v$ the propagation velocity. For two stations 100 m apart on coaxial cable this is $100 / (2\times10^{8}) = \boxed{0.5\ \mu\text{s}}$, and as the separation tends to zero the detection time tends to zero with it. That is the literal answer to “the shortest period of time that could pass”: it is bounded below only by the propagation delay between the two colliding stations, and for adjacent stations it is effectively instantaneous.
2. Contrast it with the worst case, which is what the standard must cover. The unlucky case is a station at the far end of the network beginning to transmit just before the first station’s signal arrives. The first station then learns of the collision only when the second station’s signal has travelled the whole way back, that is after a round trip: $$t_{max} = 2\tau = \frac{2d}{v} = \frac{2 \times 2500}{2\times10^{8}} = 25\ \mu\text{s}$$ so $\boxed{2\tau = 25\ \mu\text{s}}$ across a maximal 10BASE5 collision domain.
3. Relate this to the Ethernet slot time and minimum frame. A sender must still be transmitting when the collision reaches it, otherwise it will never know the frame was destroyed. The standard therefore fixes a slot time of 512 bit times, which at 10 Mbit/s is $$T_{slot} = \frac{512\text{ bits}}{10\times10^{6}\text{ bit/s}} = 51.2\ \mu\text{s}$$ comfortably larger than the 25 microsecond worst-case round trip, the margin covering repeater and transceiver delays. The same 512 bits fix the minimum frame at $\boxed{64\text{ bytes}}$, and it is also the quantum of the exponential backoff. This is why the maximum cable length and the minimum frame size of an Ethernet are not independent choices: raising the bit rate to 100 Mbit/s while keeping 512 bit times shrinks the slot to 5.12 microseconds and forces the collision domain down to about 205 m.