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 \(\underline{\hspace{1cm}}\).
Show Hint
In distance-vector routing, the count-to-infinity problem can cause prolonged instability due to incorrect routing information. Random update rates influence the likelihood of routing loops.
Assume we have three routers, $P$, $Q$, and $R$, where $P$ reaches $R$ through $Q$. When the link $Q-R$ fails, $Q$ must inform $P$ that $R$ is unreachable. A routing loop occurs if $P$ sends its own (now stale) routing table to $Q$ before $Q$ can send its failure update to $P$.
Step 1: Define the Independent Update Events
Let $T_Q$ be the time at which Router $Q$ sends its "failure" update to $P$. Let $T_P$ be the time at which Router $P$ sends its "periodic" update to $Q$.
Since the routers send updates at random, independent intervals, we can treat $T_Q$ and $T_P$ as independent random variables following the same distribution.
Step 2: Determine the Condition for a Loop
A loop forms if $P$ advertises a route to $R$ back to $Q$ before $Q$ has told $P$ that the link is down. This happens if:$$T_P < T_Q$$In this case, $Q$ incorrectly believes $P$ has an alternative path to $R$ and updates its table to point back to $P$, creating a loop.
Step 3: Calculate the Probability of the Timing Mismatch
For any two independent, continuous random variables $X$ and $Y$ with the same distribution, the probability that $X < Y$ is equal to the probability that $Y < X$ due to symmetry.
Since the total probability must sum to 1:$$P(T_P < T_Q) + P(T_Q < T_P) = 1$$$$2 \times P(T_P < T_Q) = 1$$$$P(T_P < T_Q) = \mathbf{0.5}$$
Final Answer:
The probability that a routing loop will form between $P$ and $Q$ is: 0.5
