OSPF (Open Short Path First) Routing Protocol using Dijkstra Algorithm
Hey Guys,
In this blog I am going to tell you how OSPF protocol works on the top of Dijkstra’s Algorithm. It’s going to be a small blog in which I will just give you an high level idea about the linkage between OSPF and Dijkstra’s Algorithm.
OSPF Protocol
The OSPF (Open Shortest Path First) protocol is one of a family of IP Routing protocols, and is an Interior Gateway Protocol (IGP) for the Internet, used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.
The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the AS, so that every router within the AS has a complete picture of the topology of the AS. This picture is then used to calculate end-to-end paths through the AS, normally using a variant of the Dijkstra algorithm. Therefore, in a link-state routing protocol, the next hop address to which data is forwarded is determined by choosing the best end-to-end path to the eventual destination.
Dijkstra Algorithm
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants.
We step through Dijkstra’s algorithm on the graph used in the algorithm above:
- Initialize distances according to the algorithm.
- Pick first node and calculate distances to adjacent nodes.
- Pick next node with minimal distance; repeat adjacent node distance calculations.
- Final result of shortest-path tree.
OSPF Working
OSPF is a routing protocol. Two routers speaking OSPF to each other exchange information about the routes they know about and the cost for them to get there.
When many OSPF routers are part of the same network, information about all of the routes in a network are learned by all of the OSPF routers within that network — technically called an area.
Each OSPF router passes along information about the routes and costs they’ve heard about to all of their adjacent OSPF routers, called neighbors.
OSPF routers rely on cost to compute the shortest path through the network between themselves and a remote router or network destination. The shortest path computation is done using Djikstra’s algorithm.
Consider a simple example of five routers connected as shown in the diagram below. Assuming all links have the same cost, what’s the fastest way for R3 to connect to R5? Through R4 — R4 is the lowest cost path. (R3’s path to R5 via R1, for example, adds another link and therefore additional cost.)
There are a lots of other things matter in the OSPF protocol, but it’s algorithm for finding the shortest path to other routers is been determined by Dijkstra's Algorithm only.
You can read more about OSPF and Dijkstra ’s Algorithm in below Wikipedia articles.
For next blog topic suggestions or queries you can DM me on LinkedIn. If you like this blog make sure you clap it.
Thank You
Signing off 🙌
