The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
3.6k views

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

  1. $S1$, $S2$, and $S3$ are all true.
  2. $S1$, $S2$, and $S3$ are all false. 
  3. $S1$ and $S2$ are true, but $S3$ is false.
  4. $S1$ and $S3$ are true, but $S2$ is false.
asked in Computer Networks by Veteran (112k points)
edited by | 3.6k views
+7

Split Horizon

In this strategy, flooding the table through each interface doesn't happen. If, according to its table, node B thinks that the optimum route to reach X is via A, it does not need to advertise this piece of information to A; the information has come from A (A already knows). Taking information from node A, modifying it, and sending it back to node A creates the confusion.

$Remark:$ Split horizon solution doesn't work for 3-node instability.
 

+1

"3 node instability still after split horizon":



A----B---C(each distance to D)

2----6-----8(before link AD failes)

inf---6----8(after link fails)

16---6----8

16---20---8

16----20---22

30----20---22

30----34----22

30----34----36

.........infinity

here even after split horizon, packet is looping between these 3 NOdes and persistant looping is still there.

0
that's what i said split horizon doesn't help in 3-nodw stability.
+4

@Manu+Thakur 

This is from book Kurose and Ross 

Does poisoned reverse solve the general count-to-infinity problem? It does not.
You should convince yourself that loops involving three or more nodes (rather than
simply two immediately neighboring nodes) will not be detected by the poisoned
reverse technique.

So I think Reasoning for S2 to be false: Poisoned reverse does not always solve persistent looping problem.

It has nothing to do with LSR as given by answer.
 

0
@shivam i think so!, even the first half part of the statement ii itself is incorrect, right?
0
@Manu+Thakur

Correct First half of statement is wrong:

And for the Second part:  nowhere, I have read about poisoned reverse + LSR. Also, LSR has non-persistent loops which occur during convergence process.
0
LSR doesn't have count to infinity problem, so no point in applying the split horizon solution.
0
Correct @Manu+Thakur and Thanks

5 Answers

+30 votes
Best answer

The computational overhead in link state protocols is higher than in distance vector protocols. Bcz LSR is based upon global knowledge whereas DVR is based upon Local info .

Persistent looping can be avoid with the help of split horizon in DVR.But there is no concept of persisitent looping in LSR, in LSR only temporary loop exist and can automatically 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.

answered by Loyal (9.3k points)
edited by
0
@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 !
0
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
0
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..
0
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
+19 votes
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.
answered by Veteran (55.6k points)
+2
you mean the answer is?
0

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

+7 votes

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

 

 

answered by (295 points)
+3 votes

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

answered by Loyal (8.8k points)
0

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

What are its limitations ?

+3
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.
0 votes
Ans D
answered by Loyal (6.2k points)
0
Explanation please?
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,456 questions
49,913 answers
165,384 comments
65,897 users