How OSPF(Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm behind the scene
What is OSPF(Open Shortest Path First)?
Open Shortest Path First(OSPF) is a standard routing protocol that’s been used in the world for many years. Supported by practically every routing vendor, as well as the open-source community, OSPF is one of the few protocols in the IT industry you can count on being available just about anywhere you might need it.
OSPF uses a shorted path first algorithm to build and calculate the shortest path to all known destinations. The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high-level, simplified way of looking at the various steps of the algorithm.
Working of OSPF:
- 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.
What is Dijkstra Algorithm? How does OSPF use Dijkstra behind the scene?
- 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.
Cost = Reference Bandwidth / Interface Bandwidth, where reference bandwidth is 100 Mb/s.
I Hope You Like It…
Thank You For Reading…
If you like it please clap it.😁🤗