How OSPF(Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm behind the scene

  • OSPF is based on a link-state routing algorithm in which each router contains the information of every domain and based on this information it defines the shortest path also known as the Dijkstra algorithm. The OSPF learns about every router and subnet within the entire network. A link-state routing protocol is a protocol that uses the concept of triggered updates, i.e., if there is a change observed in the learned routing table then the updates are triggered only
  • The way through which OSPF learns about other routers is by sending Link State Advertisement or LSA. This LSA contains information about subnets, routers, and some of the network information. Once all the LSA’s are transferred within the network, OSPF put’s these in a database called as LSDB i.e Link State Database. The main goal here is to have each router with the same information in their LSDB’s.
  • OSPF maintains information in three tables named “Neighbor Table” that contain all discovered OSPF neighbors with whom routing information will be interchanged. “Topology Table” contains the entire road map of the network with all available OSPF routers and calculated best and alternative paths. The “Routing Table” where the current working best paths will store and it is used to forward the data traffic between neighbors.
  • In Dijkstra’s Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the “source node”) to all other nodes in the graph, producing a shortest-path tree.
  • Dijkstra’s Algorithm basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
  • The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
  • Once the algorithm has found the shortest path between the source node and another node, that node is marked as “visited” and added to the path.
  • The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.
  • Dijkstra Algorithm is a very famous greedy algorithm. It is used for solving the single-source shortest path problem. It computes the shortest path from one particular source node to all other remaining nodes of the graph.
  • So it’s not like we run Dijkstra’s algorithm and it answers all of the best paths. We run it each time we have to get to a unique destination network. And the way that it works is it assigns a cost to the links. And when it gets to a certain point when it says oh, I got something better, I’m going to stop running that calculation because I’ve already established a better pathway to that destination. And so Dijkstra’s algorithm, a complex algorithm, but ultimately it just tells us here’s the best way to go, and then where does that information go inside of our router? Well, that path with the shortest metric to get to that destination network ends up in our routing table.
  • The way through which OSPF chooses the best route is by a metric called cost. OSPF cost is the value to give to a link based on the bandwidth of that interface.

I Hope You Like It…

Thank You For Reading…

--

--

--

Lifelong learning technologies

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

ARK Core v2.6 Community Testing Results And Winners

Terraform: user-data

I automated all my dependency updates and you should to!

Micro-Frontends: What, Why (and why not) and How

Create and setup a EFS in AWS

Overlays are not the solution to your accessibility problem

How to Succeed at Your Tech Internship This Summer

Daily Dose of Programming Jokes

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
Arnab Saha

Arnab Saha

Lifelong learning technologies

More from Medium

219. Contains Duplicate II

The Line Between Real Human Interaction and Technology Usage Needs to Be Drawn.

868 Binary gap

ARTS Week 28