Welcome back to my new article, In this article, I Am going to describe you how OSPF (Open Short Path First) Routing Protocol is implemented using Dijkstra Algorithm. So let's begin with Dijkstra Algorithm.
Dijkstra Algorithm:-
It 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.
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.
What is OSPF(Open Shortest Path First)?
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.
How OSPF Works?
When it is configured, it listens to its neighbours in the networks, and it gathers all the link state data available. This data is then used to make a topology map that contains all available paths in the network. This database is saved for use, and we call it Link State Database.
Once the Link State Database is made, it is used to calculate the shortest path to subnets/networks using an algorithm known as Shortest Path First, developed by Edsger W Dijkstra. OSPF creates 3 tables:
Routing Table: It contains currently working best paths that will be used to forward traffic between two neighbours.
Neighbour Table: This contains all discovered Open Short Path First neighbours.
Topology Table: This one contains the entire road map of the network. This road map includes all the available Open Short Path First routers and keeps calculated data about best and alternative paths.
Shortest Path First Algorithm
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. Routing protocols like OSPF calculate the shortest route to a destination through the network based on an algorithm.
The way through which OSPF chooses best route is by a metrics called cost. OSPF cost is the value to given to a link based on the bandwidth of that interface.
Cost = Reference Bandwidth / Interface Bandwidth, where reference bandwidth is 100 Mb/s.
Comments