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

Hello Sir

I think option A ia false too. Due to fast convergence and other techniques like allocating sequence number to LSPs.. yes there is negligible possibility of Routing loops in LSRP but yet routing loops can occur if somehow routing tables are corrupted ...and when routing loops are possible , count to infinity might be outcome.

---

why option a) false?
count to infinity is only for DVR

---

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.

---

somewhere i studied, In LSR only temporary loop exists and can automatically be solved by system or router. then how option 1 is wrong ?? this statement concludes in LSR loop exist.   plaese clear my doubt.

---

@Rana01

Loop doesn't exist in LSR because there is this field called 'age' in every link state packet where after certain time / hops, the packet becomes invalid and hence routers will jettison(discard) them.

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

(S1): Count to infinity is a problem only with DV and not LS routing

• The count-to-infinity problem occurs in DV routing when routers exchange distance vectors, and bad news (e.g., a link failure) propagates slowly through the network. LS routing does not suffer from this problem because each router has a global view of the network topology.

 

• True for DV; False for LS.

      True

---

(S2): In LS, the shortest path algorithm is run only at one node

• In LS routing, every node gathers a complete view of the network topology (via link-state advertisements) and independently runs the Dijkstra’s shortest path algorithm to compute the shortest paths to all other nodes.

 

• False, because the shortest path algorithm is run at all nodes, not just one.

        False

---

(S3): In DV, the shortest path algorithm is run only at one node

• In DV routing, no single node runs the shortest path algorithm. Instead, all nodes exchange distance vectors with their neighbors and update their routing tables iteratively using the Bellman-Ford algorithm.

 

• False, because the shortest path algorithm is not run at only one node.

     False

---

(S4): DV requires lesser number of network messages than LS

• In DV routing, nodes exchange only distance vectors with neighbors, which typically involves fewer messages compared to LS routing.\

 

• In LS routing, each router floods link-state advertisements (LSAs) throughout the network, which generates a higher number of messages, especially in large networks.

 

• True, as DV typically requires fewer network messages.

       True

Answer 4

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.

---

but in DVR after every some period of time the information is shared b/w neighbours !!

but in LSR, after sometime the information sharing will stop right , unless there is any topological    change !!

now how will you justify this statement ??

 

Answer 5

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

Answer 6

COMMENT BELOW IF YOU HAVE ANY DOUBT