OSPF (Open Short Path First) Routing Protocol implementation using Dijkstra Algorithm

What is Routing Protocol?

Let us try to understand this with an example-

Suppose you want to go to your home from college. You book a cab or take a bus to your home. In the path of your journey, you encounter several signboards which help you take the proper or best path, or in the case of a cab, Google Maps will help you in choosing the best route.

In this analogy, consider yourself as the DATA, the bus 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.

Open Shortest Path First(OSPF)

1. The OSPF is an open standard protocol that is most popularly used in modern networks.
2. It is a link-state protocol.
3. It is used to find the best path between the source and the destination router using its own Shortest Path First.
4. 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.
5. OSPF is not a CISCO proprietary protocol like EIGRP.
6. OSPF always determines the loop-free routes. If any changes occur in the network it updates fast.

OSPF Packet format-

OSPF terms-

1. Router ID: It is the highest active IP address present on the router.
2. Router priority: It is an 8-bit value assigned to a router operating OSPF, used to elect DR and BDR in a broadcast network.
3. Designated Router (DR): It is to act as a central point for exchanging of OSPF information between multiple routers on the same, multiaccess broadcast network segment
4. Backup Designated Router (BDR): BDR is a backup to DR in a broadcast network. When DR goes down, BDR becomes DR and performs its functions.

Dijkstra’s 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.

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.

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.

1. During the first stage, we need to find the shortest node from the neighbour nodes of the source node.
2. During the second stage, we need to look for the second shortest path node, which can be a neighbour node of the source node or to the node found in the first stage.
3. During the third stage, the algorithm looks for the third shortest path node from the source node. This node can be a neighbour of the source node or the nearest node found from the first stage or second stage.
4. 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.

Thank you for reading!!!