GATE CS 2010 Q54 — Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State

In a distance vector routing network, once the routing tables stabilize, data is always routed along the shortest paths between nodes. A link is never used if there exists an alternative path between its endpoints that has a strictly lower cost than the direct link itself.

The network consists of the following links and weights:

• $(R1, R2) = 6$
• $(R1, R3) = 3$
• $(R2, R3) = 2$
• $(R2, R4) = 1$
• $(R3, R4) = 2$
• $(R3, R5) = 5$
• $(R4, R5) = 1$
• $(R4, R6) = 2$
• $(R5, R6) = 2$

Let's analyze the direct links to see if they are bypassed by shorter paths:

1. Link $(R1, R2)$ (weight 6): The path $R1 \to R3 \to R2$ has a cost of $3 + 2 = 5$. Since $5 < 6$, the direct link $(R1, R2)$ is never used.
2. Link $(R3, R5)$ (weight 5): The path $R3 \to R4 \to R5$ has a cost of $2 + 1 = 3$. Since $3 < 5$, the direct link $(R3, R5)$ is never used.

For all other links, the direct link is the shortest path between its endpoints, so they will be used. Thus, exactly 2 links will never be used for carrying any data.