Home / Networking Basics / Link State Protocols: The Dijkstra Algorithm

Link State Protocols: The Dijkstra Algorithm

Each router calculates the lowest cost path to each other router.

Routers exchange link states. They send information about their connected links to all the other routers by flooding their links.

Flooding means that whenever a router receives information on one interface, it sends it out of all the other interfaces. Flooding has the associated risk of creating loops.

When there is a link failure or a topology change, the information is flooded to all other routers. All routers re-run the Dijkstra algorithm.

How the Dijkstra algorithm works

To determine the shortest path from router R1 to all other routers, we do the following:

  • draw a table for R1, with the following rows: Shortest Path set, Candidate, Selected
    • Shortest Path Set: the shortest path we find after each iteration of the algorithm
    • Candidate: the potential new members of the shortest path set
    • Selected: the selected member of the shortest path set
  • iteration 1: beginning from R1, what are the paths that have a cost of 1? We add routers in the Candidate row. Then we choose one among them. Don’t worry if you have more than one router with the same link cost; that router will be added to the tree in a later iteration. Now the Shortest Path Set grew one router.
  • iteration 2: beginning from R1, are there still paths with cost of 1? if yes, add the router in the Candidate row then select one. The Shortest Path Set grows one more router
  • iteration 3: beginning from R1, are there still paths with cumulative cost of 2? repeat the steps
  • iteration 4: beginning from R1, are there still paths with cumulative cost of 3? repeat the steps
  • etc.
  • when the Candidate row becomes empty, then the algorithm is done.

The number of iterations of the link state algorithm is equal to the number of the routers participating in the algorithm.

Nb_iter = nb_routers

So if we have 5 routers, then to build a shortest path from any router to any other one we will iterate the algorithm 5 times.

A good example of how Dijkstra works is given by Professor Nick McKeown here.

Here is a sample trace I’ve done of the Dijkstra algorithm. Notice that with practice, you won’t need to constantly fill the Candidate row.

link-state-algorithms-my-example

Figure: a sample trace of the Dijkstra algorithm

When the algorithm converges, each router in the shortest path to a destination X is the next hop of its precedent router for that same destination X. Using the trace above, starting from router R4, his next hop R5 is the router on the shortest path to reach R6.

 

Related posts

Advanced OSPF notes

OSPF Troubleshooting case 1

OSPFv3

Top Courses in IT & Software 300x250

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Adsense black background: