Question 57

Before the link $Q-R$ fails, both $P$ and $Q$ have stable routing entries for destination $R$:

• $Q$ reaches $R$ directly with cost 1 (via interface to $R$).
• $P$ reaches $R$ through $Q$ with cost 2.

When link $Q-R$ fails, router $Q$ immediately detects the failure and sets its direct cost to $R$ to $\infty$.

Now, $P$ and $Q$ independently broadcast periodic distance vector updates according to Poisson processes with equal average rates $\lambda$:

• If router $P$ transmits its update first: $P$ advertises that it has a path to $R$ of cost 2. Router $Q$ receives this advertisement before sending its own update to $P$. $Q$ incorrectly believes $P$ has an independent alternative path to $R$ of cost 2, and updates its routing table: path to $R$ via $P$ with cost $2 + 1 = 3$. This creates a routing loop between $P$ and $Q$ that leads directly to the count-to-infinity problem.
• If router $Q$ transmits its update first: $Q$ informs $P$ that $R$ is unreachable (cost $\infty$). $P$ updates its distance to $\infty$, avoiding a loop.

Since $P$ and $Q$ send updates independently at the identical average rate, the probability that $P$ transmits before $Q$ is: