The GATE Grind

GATE 2022 CS – Question 57

Computer Networks · Routing: Distance Vector and Link State Routing · 2 marks · Numerical answer

Consider a network with three routers P, Q, R connected in a line P—Q—R. 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 ___________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 0.5

Explanation

Routers P—Q—R, all links cost 1. Before the failure P knows R at cost 2 (via Q) and Q knows R at cost 1.

After Q–R fails, Q marks R unreachable. Two things can happen next:
1. **Q advertises first.** P learns R is unreachable and drops its route. No loop.
2. **P advertises first.** Q hears from P "R at cost 2" and adopts it as R at cost 3 via P. Now P sends traffic for R to Q and Q sends it back to P, and the costs count up to infinity.

P and Q send updates at random times at the same average rate, so each is equally likely to send first. The probability of a loop is $1/2=\mathbf{0.5}$.

More Routing: Distance Vector and Link State Routing questions

All Routing: Distance Vector and Link State Routing questions →