GATE CS 2014 Set 1 Q23 — Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State

To determine the correct option, let us analyze each statement for a large network with $V = 500$ nodes and $E = 4000$ links:

• Statement [S1]: The computational overhead in link state protocols is higher than in distance vector protocols. (TRUE)
  In Link State (LS) protocols, each node maintains a complete map of the network topology and independently runs Dijkstra's shortest path algorithm. For a network with $V$ vertices and $E$ edges, the computational complexity is $O(E + V \log V)$ per node. In contrast, Distance Vector (DV) protocols only perform simple local additions and comparisons (Bellman-Ford update step), which require minimal computational overhead. Thus, LS has a higher computational overhead.


• Statement [S2]: A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol. (FALSE)
  Link State protocols naturally avoid persistent routing loops because every node has a complete and consistent view of the entire network topology, allowing them to calculate loop-free paths. Distance Vector protocols are highly prone to routing loops (e.g., the count-to-infinity problem). While techniques like split horizon prevent two-node routing loops, they cannot completely prevent persistent loops in complex topologies involving three or more nodes.


• Statement [S3]: After a topology change, a link state protocol will converge faster than a distance vector protocol. (TRUE)
  In LS protocols, any change in link status is immediately flooded to all nodes in the network, allowing rapid recalculation of paths and fast convergence. In DV protocols, updates propagate slowly step-by-step (hop-by-hop) through neighboring nodes, leading to much slower convergence.

Since $S1$ and $S3$ are true, and $S2$ is false, the correct option is D.