GATE CS 2022 Q47 — Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State

Initially, the network is connected as $P - Q - R$ with unit link costs. The routing paths to destination $R$ before the link failure are:

• $Q$ reaches $R$ directly with a cost of $1$ (next hop: $R$).
• $P$ reaches $R$ via $Q$ with a cost of $2$ (next hop: $Q$).

When the link $Q-R$ fails, $Q$ immediately detects the failure and updates its distance to $R$ to $\infty$.

Since $P$ and $Q$ send routing updates independently at random times with the same average rate, the next update event is equally likely to be initiated by either router (each with probability $0.5$):

• Case 1: $P$ sends its update to $Q$ first (Probability = $0.5$)
  Before $Q$ can inform $P$ about the failure, $P$ sends its periodic update advertising a path to $R$ with cost $2$. $Q$ receives this and, having no other path, updates its route to $R$ via $P$ with cost $2 + 1 = 3$. This creates a routing loop ($P \to Q \to P$), leading to the count-to-infinity problem.
• Case 2: $Q$ sends its update to $P$ first (Probability = $0.5$)
  $Q$ informs $P$ that $R$ is unreachable (cost $\infty$). $P$ updates its routing table accordingly, and no loop is formed.

Thus, the probability of a routing loop formation is $\mathbf{0.5}$.