GATE CSE 2014 | Set 1 | Question: 23

Question

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$?

• A. $S1$, $S2$, and $S3$ are all true.
• B. $S1$, $S2$, and $S3$ are all false. 
• C. $S1$ and $S2$ are true, but $S3$ is false.
• D. $S1$ and $S3$ are true, but $S2$ is false.

Comments

 

---

can you also explain the s3

---

References : Kurose 

S1 : True 

An LS algorithm requires $O(N^2)$ operations in the worst implementation, or $O(N \log N + E)$ using efficient data structures, at each node. In contrast, the distance-vector algorithm is decentralized and distributed; computation at a node consists simply of updating its distance vector based on messages received from neighbors.

References : Tanenbaum & Forouzan

S2 : False 

==> Split Horizon (and Poison Reverse) only prevents two-node loops. It fails to prevent routing loops involving three or more nodes means distance vector protocols can still suffer from persistent count-to-infinity loops.

==>In link state routing, each router constructs a complete, explicit map of the network topology. Because every router computes its shortest-path tree independently from an identical graph, link state protocols do not suffer from the count-to-infinity problem or persistent routing loops.

References : Forouzan 

S3 : True 

When a topology change occurs, a link state protocol floods an LSP  to all nodes immediately, allowing every router to recompute its shortest-path tree in parallel. In distance vector protocols, news of a link failure trickles through the network hop-by-hop, leading to slow convergence that is count to infinity problem.

Answer 1

Answer: D

 

[S1]: The computational overhead in link state protocols is higher than in distance vector protocols. 

There are more calculations involved in link state protocols than distance vector protocols because link state routing uses Dijkstra's algorithm to calculate shortest path to all the routers in the network starting from a single source. TRUE ✅

 

[S2]: A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol. 

Both distance vector protocol (with split horizon) AND a link state protocol can avoid persistent routing loops. FALSE ❌

 

[S3]: After a topology change, a link state protocol will converge faster than a distance vector protocol. 

For "n" routers, a link state protocol will converge in a single step whereas a distance vector protocol will converge in (n-1) steps. TRUE ✅

Answer 2

https://www.youtube.com/watch?v=5ZQPOLgXZDY

Answer 3

https://www.youtube.com/watch?v=5ZQPOLgXZDY

 

https://www.youtube.com/watch?v=JPchzSIOnY8  second one