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

To find the new distance vector at node $N3$ after the link cost of $N2-N3$ reduces to $2$, we follow the Distance Vector Routing update rules.

Step 1: Identify neighbors and immediate updates
Node $N3$ is connected to neighbors $N2$, $N4$, and $N5$. Before the update round, the change in the link cost of $N2-N3$ to $2$ is updated only at the incident nodes $N2$ and $N3$:

• The direct link cost $c(N3, N2)$ becomes $2$.
• The distance vector of $N2$ immediately becomes: $D_2 = (1, 0, 2, 7, 3)$.
• The distance vectors of $N4$ and $N5$ remain unchanged:
  • $D_4 = (8, 7, 2, 0, 4)$
  • $D_5 = (4, 3, 6, 4, 0)$

Step 2: Calculate the new distance vector at $N3$
In the next round, $N3$ updates its distance vector $D_3$ using the Bellman-Ford equation:
$$D_3(X) = \min \{ c(N3, N2) + D_2(X), \; c(N3, N4) + D_4(X), \; c(N3, N5) + D_5(X) \}$$

We compute this for each destination $X$:

• For $N1$: $\min \{ 2 + 1, \; 2 + 8, \; 6 + 4 \} = \min \{ 3, 10, 10 \} = 3$
• For $N2$: $\min \{ 2 + 0, \; 2 + 7, \; 6 + 3 \} = \min \{ 2, 9, 9 \} = 2$
• For $N3$: Distance to itself is $0$.
• For $N4$: $\min \{ 2 + 7, \; 2 + 0, \; 6 + 4 \} = \min \{ 9, 2, 10 \} = 2$
• For $N5$: $\min \{ 2 + 3, \; 2 + 4, \; 6 + 0 \} = \min \{ 5, 6, 6 \} = 5$

Thus, the new distance vector at $N3$ is $(3, 2, 0, 2, 5)$.