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

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

Let’s understand this by understanding the core first.

Routing Information Protocol (RIP)

It is one of the oldest distance-vector routing protocols that uses hop count as a routing metric to find the best path between the source and the destination network. Hop count is the number of routers occurring in between the source and destination network. RIP prevents routing loops by limiting the number of hops allowed in a path from source and destination. In a vector routing protocol, the routers exchange network reachability information with their nearest neighbors. A vector routing protocol floods reachability information throughout all routers participating in the protocol, so that every router has a routing table containing the complete set of destinations known to the participating routers.

In brief, the RIP protocol works as follows.

  • Each router initializes its routing table with a list of locally connected networks.

Open Shortest Path First (OSPF)

Open Shortest Path First (OSPF) is a link-state routing protocol that is used to find the best path between the source and the destination router using its own Shortest Path First. In this, the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the Autonomous System (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.

The main advantage of a link-state routing protocol like OSPF is that the complete knowledge of topology allows routers to calculate routes that satisfy particular criteria. This can be useful for traffic engineering purposes, where routes can be constrained to meet the particular quality of service requirements.

OSPF Packet Format

OSPF terms –

  1. Router I’d — It is the highest active IP address present on the router. First, the highest loopback address is considered. If no loopback is configured then the highest active IP address on the interface of the router is considered.

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 (i.e, shortest path from the source node to destination node passing from the points in between in the aim to produce a shortest-path tree.

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 as it can alter the total weight. It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.

How Dijkstra’s Algorithm works

  • It 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.

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.

NOW LET’S LOOK AT THE IMPLEMENTATION OF OSPF

Dijkstra’s algorithm is a graph traversing algorithm. It is responsible for choosing the path on which the sender will send data bits or frames of a message to the receiver. It is the algorithm who is responsible to find the shortest path i.e, with the smallest weight total encountered in the path traversal from source to destination i.e, 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 Z, where A being the sender and D being the Receiver.

Here A is the source, and Z is the destination; it is an undirected weighted graph. From the graph, we can observe there are multiple paths from A to Z like a -> b ->f ->z, a ->c ->e ->z, and many more

1. During the first stage, we need to find the shortest node from the neighbor nodes of the source node.

2. During the second stage, it looks 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.

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

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.

With the help of this procedure, we can find the smallest distance between two routers to send & receive packets.

Thank you for the read.