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

The computational overhead in link state protocols is higher than in distance vector protocols because LSR is based upon global knowledge whereas DVR is based upon local knowledge.
Persistent looping can be avoided with the help of split horizon in DVR. There is no concept of persistent looping in LSR, in LSR only temporary loop exists and can automatically be solved by system or router. S2 is false.

And, after a topology change, a link state protocol will converge faster than a distance vector protocol. S3 is true.

Answer is option D.

Comments

Correct reason for statement S2 - false

Source: Forouzan

---

@hrupam So split horizon only solves 2 node looping, so it does not completely solve the problem of persistent looping in DVR? can you explain what is poison reverse?

---

@S_Sandeep refer to the slides below

 

Answer 2

S1 : because of flooding at each router computational overhead in link state routing  is more.
S2 : Persistent loop i.e. count to infinity problem takes place in Distance vector routing not in link state routing.
S3 : Link state routing protocol converges faster when topology changes.

Comments

you mean the answer is?

---

@digvijay. I completely disagree with your explanation for S3. COnsider the following example:

COnsider the situation where the link cost for BC changes from 20 to 19.

---------------------------------------------------

For link state routing, the link cost will first propagate to all nodes and then each node will do calculation of its own.

--------------------------------------------------

For distnace vector, the link cost change will be first informed to B and C . But after B and C do some computations, the vectors at B and C remain the same. So, the algorithm has converged in just 1 step.

---------------------------------------------------

So, I think its not possible to decide until exact toplogy is known. Even verifying for a given toplogy  may be difficult ( which may be NP-hard ).

Plz correct me if wrong.

---

If you observe in LSP also it will be changed in just one step because no need to converge. Because of flooding every hello packet will reach faster to every router and no router will change its vector. But if DVR change its value then surely LSR will take less time.

Answer 3

Link-state: Every node collects complete graph structure Each computes shortest paths from it Each generates own routing table Distance-vector No one has copy of graph Nodes construct their own tables iteratively Each sends information about its table to neighbors

[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.

S1 is clearly true as in Link State all nodes compute shortest path for whole network graph.

S3 is also true as Distance Vector protocol has count to infinity problem and converges slower.

S2 is false. In distance vector protocol, split horizon with poison reverse reduces the chance of forming loops and uses a maximum number of hops to counter the ‘count-to-infinity’ problem. These measures avoid the formation of routing loops in some, but not all, cases

 

http://tinyurl.com/hrolv6l

 

 

Answer 4

Link-state:
Every node collects complete graph structure
Each computes shortest paths from it
Each generates own routing table

Distance-vector
No one has copy of graph
Nodes construct their own tables iteratively
Each sends information about its table to neighbors 

Source: http://www.cs.cmu.edu/~srini/15-441/S05/lectures/10-Routing.ppt

[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.

S1 is clearly true as in Link State all nodes compute shortest path for whole network graph.S3 is also true as Distance Vector protocol has count to infinity problem and converges slower. S2 is false. In distance vector protocol, split horizon with poison reverse reduces the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases

Comments

Respected Mam Please tell How Count to Infinity problem can be solved using Split Horizon ?

What are its limitations ?

---

1. Split Horizon is a method of preventing routing loops in distance vector routing protocol.

2. It prohibits a router from advertising a route back into the interface from which it was learned. for example if router A learned an address 10.10.0.0 from router B(this means that address 10.10.0.0 is in both tables of router A and router B)then it can never send back that info to router B,thus preventing loops.Now let us assume that some error occurred in router A and address 10.10.0.0 will not function(means its hop count will become 16 that means unreachable). So split horizon will make sure that hop count is made 16 in router B and that info is never send back to router A.

Answer 5

Ans D

Comments

Explanation please?

Answer 6

 

COMMENT BELOW IF YOU HAVE ANY DOUBT

Comments

source??