GATE CS 2011 Q53 — Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State

To find the updated cost to $N1$ in the distance vector of $N3$, we trace the events step-by-step:

1. Initial State & Link Cost Change:
Initially, the cost of link $N2-N3$ is $6$. When it reduces to $2$, the incident nodes $N2$ and $N3$ immediately update their direct link cost to $2$ in their distance vectors:

• $D_2(3) = 2$
• $D_3(2) = 2$

2. Round 1 of Updates:
All nodes exchange their distance vectors and update.

• $N3$ updates its distance to $N1$ using the previous vectors of its neighbors $N2$ and $N4$: $$D_3(1) = \min \{ c(N3, N2) + D_2(1), \; c(N3, N4) + D_4(1) \} = \min \{ 2 + 1, \; 2 + 8 \} = 3$$
• $N4$ updates its distance to $N1$ using the previous vectors of $N3$ and $N5$: $$D_4(1) = \min \{ c(N4, N3) + D_3(1), \; c(N4, N5) + D_5(1) \} = \min \{ 2 + 7, \; 4 + 4 \} = 8$$

3. Link $N1-N2$ Goes Down:
Immediately after Round 1, the link $N1-N2$ fails. $N2$ reflects this change immediately in its distance vector: $$D_2(1) = \infty$$

4. Round 2 of Updates (Next Round):
$N3$ updates its distance to $N1$ using the updated vectors of its neighbors $N2$ and $N4$: $$D_3(1) = \min \{ c(N3, N2) + D_2(1), \; c(N3, N4) + D_4(1) \}$$ $$D_3(1) = \min \{ 2 + \infty, \; 2 + 8 \} = 10$$

Thus, the cost to $N1$ in the distance vector of $N3$ after the next round of updates is $10$.