Consider a network with three routers P, Q, R shown in the figure below. All…
2022
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___________.
Attempted by 48 students.
Show answer & explanation
Correct answer: 0.5
Key insight: a loop (count-to-infinity) occurs only if P sends a routing update carrying the stale route to R before Q sends an update reflecting the broken link.
If P updates first: P advertises the old route to R (via Q). Q, having not yet told P that its link to R failed, accepts that route and increases its distance via P, producing a loop and starting the count-to-infinity process.
If Q updates first: Q advertises that R is unreachable (infinite distance). P receives this and removes the stale route, so no loop forms.
Because P and Q send updates at random times with the same average rate, the next update to occur is equally likely to come from P or Q. Therefore the probability that P's update precedes Q's (and so causes the loop) is 0.5.
Final answer (rounded to one decimal place): 0.5
A video solution is available for this question — log in and enroll to watch it.