How OSPF Routing Protocol can be implemented using Dijkastra Algorithm

8 min readSep 7, 2022

Suppose you want to go to your shop from home. You book a cab or take an auto to your shop. In the path of your journey, your auto driver encounters several signboards which help him/her to take the proper turn or best path, or in the case of a cab, Google Maps will help you in choosing the best route. In this likeness consider yourself as the Data the auto or cab as the Routed Protocol, and the signboards or the GPS installed in your driver’s phone as the Routing Protocol.

Similarly, It provides appropriate addressing information in its internet layer or network layer to allow a packet to be forwarded from one network to another.

The IP network is classified into two categories: Interior Gateway and Exterior Gateway Protocol

Interior gateway protocols are used inside an organization’s network and are limited to the border router. Exterior gateway protocols are used to connect the different Autonomous Systems (ASs). A simple definition that fits most of the time defines the border router as a router that has a foot in two worlds: one going to the Internet and another that is placed inside the organization and that’s why its name is, border router.

Purpose and Use Cases

With 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.

This algorithm is used in GPS devices to find the shortest path between the current location and the destination. It has broad applications in industry, especially in domains that require modeling networks.

What is OSPF(Open Shortest Path First)?

OSPF is a link-state protocol that 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.OSPF is not a CISCO proprietary protocol like EIGRP.OSPF always determines the loop-free routes. If any changes occur in the network it updates fast.

These are some of the important points related to OSPF.

The OSPF is an open standard protocol that is most popularly used in modern networks.
It is used to find the best path between the source and the destination router using its own Shortest Path First.
Various protocols are used for the shortest path. But in real life mostly problems are undirected graph-like nature. OSPF using Dijkstra’s algorithm solved the shortest path problem in both types of problems i.e. directed and undirected graphs.

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.

Why there is a need for OSPF when there is RIP protocol?

The first routing protocol that was widely implemented, the Routing Information Protocol (RIP), calculated the shortest route based on hops, that is the number of routers that an IP Packet had to traverse to reach the destination host. RIP successfully implemented dynamic routing, where routing tables change if the network topology changes. But RIP did not adapt its routing according to changing network conditions, such as data transfer rate. Demand grew for a dynamic routing protocol that could calculate the fastest route to a destination. OSPF was developed so that the shortest path through a network was calculated based on the cost of the route,

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 is 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 the 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 Dijkstra’s Algorithm This algorithm isn’t unique to OSPF. Rather, it’s a mathematical algorithm that happens to have an obvious application to networking.

The routers work on the third layer of our OSI model. OSPF is a routing protocol. When data move across multiple networks, IP routing helps to determine the path of data by setting some protocols to reach the source destination. RIP (Routing Information Protocol) and OSPF (Open Shortest Path First) Protocol are types of dynamic routing.

Comparing the difference between Static and Dynamic Routing :

- Static routing is for small networks like small scale organization that has predicted number of users and static or minimum bandwidth usage

- Dynamic Routing is used in the case of large networks because of its capabilities like it keeps changing and updating along with network topologies. Dynamic Routing Protocols dynamically discover network destinations.

OSPF maintains information in three tables:-

Topology Table contains the entire road map of the network with all available OSPF routers and calculated best and alternative paths.

Neighbor Table that contains information about neighboring routers so that information can be interchanged.

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?

Dijkstra’s algorithm is one of the types of Greedy Algorithms that enables us to find the shortest path between any two nodes in a graph. 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.

Working of Dijkstra’s Algorithm:-

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.

Requirements:

Dijkstra’s Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path.If there is a negative weight in the graph, then the algorithm will not work properly. Once a node has been marked as “visited”, the current path to that node is marked as the shortest path to reach that node. And negative weights can alter this if the total weight can be decremented after this step has occurred.

How to find the shortest path in OSPF using Dijkstra’s Algorithm?

Dijkstra’s algorithm is a graph traversing algorithm. In a computer network we have sender and receiver, the sender will send some frame or message to the receiver, but by the time receiver could receive the message, there are many parts which the message can take, that is the job of this algorithm. It will find the shortest path traversed to carry the message from sender to receiver.

Consider a network structure given below, the figure contains the nodes between A to H. We need to examine the shortest path, between A to D, where A being the sender and D being the Receiver.

During the first stage, we need to find the shortest node from the neighbor nodes of the source node.
During the second stage, we need to look for the second shortest path node, which can be a neighbor node of the source node or to the node found in the first stage.
During the third stage, the algorithm looks for the third shortest path node from the source node. This node can be the neighbor of the source node or the nearest node found from the first stage or second stage.
The process is repeated until all nodes are visited at least once and if all nodes are visited once, then we can find the shortest path from the source node to the destination.

Complexity:

E — EDGES AND

V- VERTICES

Space complexity: Θ(V)
Time complexity is Θ(E+V²) if the priority queue is not used.
Worst-case time complexity: Θ(E+V log V)
Average case time complexity: Θ(E+V log V)
Best case time complexity: Θ(E+V log V)

The Formula used to compare between two nodes to find minimum value:

Minimum(Destination value, Marked value + node value) where

Destination values are the destination node value,

Marked value is the source node value,

Node value is the weightage of the edge that connects source and destination.

Example:

Let,Destination value = 18 Marked value = 10 Edge weight = 4 Substituting in the formula, we get= Min(18, 10+4)= Min(18, 14)= 14 (since, 14 is smaller than 18)

Similarly here is the example 1: