GATE 2018 CS Q.55: solution and answer

GATE 2018 · CSQ.55 · 2 marks · NAT

Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium.

Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0 and begins to carrier-sense the medium.

The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P's ongoing transmission is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum distance is 50 meters.

Official answer: 50Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Q avoids a collision only if it hears P's signal during its 5-unit carrier-sense window. It then waits until P finishes instead of starting to transmit.
P starts at $t = 0$ . The signal travels at 10 meters per unit time, so it reaches Q after $t_{p} = \frac{d}{10}$ units.
Q senses the medium from $t = 0$ to $t = 5$ . P's transmission lasts 20 units, so it is still on air throughout this window. Q detects P if $\frac{d}{10} \leq 5$ .
This gives $d \leq 10 \times 5 = 50$ meters.
If $d > 50$ , P's signal reaches Q only after the sensing window has closed. Q finds the medium idle and starts transmitting, and the two transmissions collide because there is no collision detection.
So the maximum distance is $d = 50$ meters, taking a signal that arrives exactly at the end of the window as detected.

KEY IDEA

Q avoids a collision only if P's signal reaches it within Q's 5-unit sensing window. The propagation delay $d /10$ must not exceed 5, so $d \leq 50$ m.

WATCH OUT FOR

Using the 20-unit transmission time, or twice the propagation delay as in CSMA/CD. Here the nodes never detect collisions, and only the one-way delay against the 5-unit sensing window matters.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 3 Data link & MAC questions, with notes

GATE 2018 CS Q.55: solution and answer

Answer and solution

More Data link & MAC questions