4

In Link-state routing protocol Dijkstra's algorithm is used. In Distance-vector routing protocol Bellman-Ford algorithm is used. My question is why we use two different algorithm. Why not only one algorithm?

Dijkstra's Algorithm can't work on negative edge, but in routing there can't be any negative edge. OK but in matter of debate let's say there can be any negative edge in case of malfunctioning. Then why not use Bellman-Ford in both protocol?

  • What do you mean by a Negative Edge? – Eddie Dec 30 '14 at 22:39
  • @Eddie I meant this. For more info you can google "negative edge dijkstra's algo". – Anirban Nag 'tintinmj' Dec 31 '14 at 10:49
  • Did any answer help you? if so, you should accept the answer so that the question doesn't keep popping up forever, looking for an answer. Alternatively, you could provide and accept your own answer. – Ron Maupin Aug 10 '17 at 4:01
3

Distributed Bellman-Ford (BF) and Dijkstra work in opposite directions: BF builds path starting at the source of the routing information (the data sink), while Dijkstra starts at the data sender.

Since distance vector protocols work incrementally starting at the source, they cannot use Dijkstra, and hence use distributed BF. There is nothing in principle that would prevent a link-state protocol from using BF, but (non-distributed) BF has cubic complexity, while Dijkstra (if implemented correctly) is O(n² log n).

(Because of the different directions, BF and Dijkstra will build different paths with some very weird metrics — metrics that fail Sobrinho's isotonicity condition —, but the difference is unlikely to be relevant in practice.)

| improve this answer | |
5

Link-state and distance vector aren't actual routing protocols, but types of routing protocol. Since different environments have different requirements, there are different routing protocols. The protocol internet routing works on (BGP) is a distance vector protocol, because it is extremely scalable. Also, you don't want to be dependant on the link state information from other companies to route your traffic. You basically only want to know if they can get the traffic towards the destination and if they are closer to the destination than yourself and the other systems you are connected to.

| improve this answer | |
  • But why two different algorithm? When there can't be any negative edge why not use Dijkstra for both type of protocol? – Anirban Nag 'tintinmj' May 23 '14 at 16:54
5

The fact that Dijkstra's algorithm cannot handle negative edges is not an issue in routing. Because Dijkstra's is a greedy algorithm, it needs to know about all nodes to be able to calculate path costs. In link state routing protocols, every router has a full map of the network on which it can executes Dijkstra's algorithm to populate its routing table.

Unlike Dijkstra's, the distributed version of Bellman-Ford used in distance-vector routing protocols can handle the gradual increase of available information in the incoming advertisements.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.