GATE 2022 CS Q.57: solution and answer

GATE 2022 · CSQ.57 · 2 marks · NAT

Consider a network with three routers P, Q, R shown in the figure below. All the links have cost of unity. The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q-R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to count-to-infinity problem, is ______.

GATE 2022 CS question 57: Three boxes in a row labelled P, Q, R. — Figure from the GATE 2022 CS paper. It is part of the question.

Answer and solution

ANSWER

The probability of a routing loop between P and Q is 0.5.

Official answer: 0.5Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

Before the failure the tables have converged. Q reaches R directly at cost 1. P reaches R through Q at cost 2.
The link Q-R fails. Q detects this and sets its distance to R to $\infty$ . P has not heard yet and still holds the old entry: R at cost 2 via Q.
Only the order of the next two routing updates matters: whether Q's update reaches P first, or P's update reaches Q first.
Case 1: Q sends its update first. Q advertises R at $\infty$ . P's route to R goes through Q, so P must follow Q and sets R to $\infty$ . The tables agree and no loop forms.
Case 2: P sends its update first, advertising R at cost 2. Q has no route to R, so it accepts, because $2 + 1 = 3 < \infty$ , and sets R to cost 3 via P. Q now sends R-bound packets to P, and P sends them back to Q. This is a routing loop. When Q next advertises cost 3, P changes its cost to 4, and so on, so the cost climbs without bound (count to infinity).
P and Q send updates at random times at the same average rate, so by symmetry each is equally likely to send first: $P (P first) = \frac{1}{2}$ .
A loop forms exactly in Case 2, so $P (loop) = \frac{1}{2} = 0.5$ .

KEY IDEA

After Q-R fails, a loop forms only if P advertises its stale route to R (cost 2 via Q) to Q before Q advertises that R is unreachable to P. With equal update rates each order is equally likely, so the probability is 1/2.

WATCH OUT FOR

Assuming a loop always forms (answer 1), or that it never forms because of split horizon. Here P's stale route goes through Q, so the order of the two updates decides the outcome.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 3 Routing questions, with notes

GATE 2022 CS Q.57: solution and answer

Answer and solution

More Routing questions