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

LSR doesn't have count to infinity problem, so no point in applying the split horizon solution.

---

Correct @Manu+Thakur and Thanks

---

After a topology change, a link state protocol will converge faster than a distance vector protocol.

What does this line mean? Can anyone explain with example.

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

@arjun sir : I am sure that persistent looping problem exits

but with Posion ratio we can avoid just loop instability not loop 3 instability . so option b is false . am i right behind  this reason . beacuse of this i am saying option b is wrong !

---

Sir I am not completely satisfied with reason for S2 statements my doubt is using DVR we can handle the routing problem and no persistent loops basically is there in LSR then why exactly S2 is false

---

See there are two types of problem here:
1) Persistent problem: The problem which will remain forever.
2) Transient problem: The problem that will correct by itself.
In DVR, we know that it suffers from count to infinity problem because of this there is a problem of persistent looping here, to avoid this looping we use something known as split Horizon.
In LSR , This algorithm uses link state packets, this packet will help the routers to know routing table, there is certain fields are available in link state packets like sequence number(to avoid duplicacy), TTL(to avoid loops) etc..and Since LSR uses flooding so there could be problem of looping but that is transient problem(for a very short span), because updates are sent periodically and TTL field will automatically correct themseleves..

---

In addition to  Flooding LSP applies dijkastra for shortest path between two nodes whereas Distance vector only add find the minimum of two.so computation overhead is way more in LSP than in Distance vector

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.