GATE IT 2008 | Question: 67

Question

Two popular routing algorithms are Distance Vector(DV) and Link State (LS) routing. Which of the following are true?

(S1):  Count to infinity is a problem only with DV and not LS routing
(S2):  In LS, the shortest path algorithm is run only at one node
(S3):  In DV, the shortest path algorithm is run only at one node
(S4):  DV requires lesser number of network messages than LS

• A. S1, S2 and S4 only
• B. S1, S3 and S4 only
• C. S2 and S3 only
• D. S1 and S4 only

Answer 1

S1 is true, S2 and S3 are false and S4 is true. 

Link State: https://cseweb.ucsd.edu/classes/fa10/cse123/lectures/123-fa10-l12.pdf

Distance Vector: http://cseweb.ucsd.edu/classes/fa10/cse123/lectures/123-fa10-l13.pdf

Correct Answer: $D$

Comments

question :- why only for DVRP? why can't with LSRP? does LSRP guarantee that routing loops won't occur?

Possible answer :-Routing loops and hence count to infinity is a general problem with DVRP(specially RIPv1 and RIPv2) but with LSRP even if some looping happens , it won't go on infinitely.

---

Looping problem is transient in case of LSR, it will correct itself whereas In DVR it will remain forever(persistent problem), we have to use split horizon...

---

Since DVR is based upon local knowledge whereas LSR is based upon global knowledge. So, count to infinity problem donot arise with LSR.

Answer 2

Count to infinity problem only exist into the DVR.

In LSR shortest path is calculated at each and every router so option B is wrong.

Similar case also arise for the DVR so option C is also wrong.

Since DVR is based upon local knowledge whereas LSR is based upon global knowledge.

Comments

@AnilGoudar

DVR works on Bellman ford algorithm while LSR works on Dijikstra algorithm

---

Thanks

---

Hello anil

yes! DVRP uses bellman ford , that is single source shortest path algo..

DVRP just doesn't have entire topology for the network , entire topology is something like complete map of network , in which every node can tell you what path to follow to reach some particular destination ...it's something like you are driving and after every KM , you get a route map on the side of road that tells you that to reach G first go to B then D then J then you will have G .....DVRP only tells you about the direction , it says hey i don't know what path to follow for this destination but i can tell you in which direction you have to go from here , something like ARROW MARKS on highways...

Answer 3

Answer (D)

Comments

why option S4 is correct?

---

DV requires the lesser number of network messages than LS because each node share information to only its neighbor, while in LSR all share nodes share information to each other.

Answer 4

Count to Infinity problem has only direct connection with DV algorithm. As Good information spreads slow and bad information spreads faster. This count to infinity problem has no link with LS Algorithm.

DV requires lesser number of network messages then LS as DV is a static algorithm.

So rest information in question is not valid so only A and D are true