Dijkstra Algorithm and OSPF

Dijkstra Algorithm is the single source shortest path algorithm which is widely used when we have positive weights

According to Cisco, OSPF protocol was developed due to a need in the internet community to introduce a high functionality non-proprietary Internal Gateway Protocol (IGP) for the TCP/IP protocol family.

OSPF have some advantages over RIP or other protocols, it doesn’t have any hop count limit, better load balancing allows routing authentication by using different password authentication and many more.

Before moving to the algorithm, we need some vocabulary.

Link State Protocol: OSPF is a linked state protocol. Link state refers to the interface of the routers, any of the information which describes the own IP address, mask and relationship with the neighbouring routers.

OSPF Cost: The cost is inversely proportionally to the bandwidth, more the bandwidth less the cost.

How does this work?

  • OSPF uses the Dijkstra algorithm to calculate the shorted path between every node.
  • During initialization, the router generates a link-state advertisement which represents the collection of all the link states on that router.
  • Using flooding, the routers update the link states between all the routers keeping the copy of the original link state and sharing only the updated linked state.
  • When all the databases are updated, then the shortest between all the nodes is calculated using the Dijkstra algorithm, which helps create the routing table with cost and next-hops as the parameters.
  • OSPF remains quiet when there is no change in the topology like deletion or addition of node or changed cost.
  • When any of the changes occur, the cost will be recalculated using the Dijkstra algorithm and updated routing table.

This was a short introduction to the OSPF algorithm. Thanks for reading. Give a clap if you liked reading it.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store