Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links. [S1] The computational overhead in link state protocols is higher than in distance vector protocols. [S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol. [S3] After a topology change, a link state protocol will converge faster than a distance vector protocol. Which one of the following is correct about S1, S2, and S3 ?

• [S1] is true: In link-state protocols (like OSPF), each node runs Dijkstra's shortest-path algorithm over the entire topology of the network ($O(V^2)$ or $O(E + V \log V)$), which requires higher computational and memory overhead than distance-vector protocols (like RIP) where nodes only execute simple vector additions from immediate neighbors.

• [S2] is false: Link-state protocols naturally prevent persistent routing loops because every node builds a complete, consistent topological map of the whole network before computing shortest paths. In contrast, distance-vector protocols suffer from the count-to-infinity problem and routing loops; split horizon and poison reverse mitigate two-node loops but cannot completely eliminate persistent loops in topologies with loops involving three or more nodes.

• [S3] is true: Link-state protocols propagate topology changes immediately via link-state advertisements (LSAs/flooding) and converge much faster than distance-vector protocols, which slowly propagate updates hop-by-hop and may suffer from slow convergence due to count-to-infinity.

Therefore, S1 and S3 are true, but S2 is false, which corresponds to option (D).