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

In this article, we will explore the Open Short Path First.So let’s get started.

So firstly I would like to tell you about the GRAPH and DIJKASTRA ALGORITHM

Graphs

In simple words, graphs are data structures that are used to depict connections amidst a couple of elements where these elements are called nodes (or vertex) that generally real-time objects, persons or entities and connections amid nodes are termed as edges. Also, two nodes only get connected if there is an edge between them.

“A graph is essentially an interrelationship of nodes/vertices connected by edges.”

Generally, graphs are suited to real-world applications, such as graphs can be used to illustrate a transportation system/network, where nodes represent facilities that transfer or obtain products and edges show routes or subways that connect nodes.

Graphs can be divided into two parts

• Undirected Graphs: For every couple of associated nodes, if an individual could move from one node to another in both directions, then the graph is termed as an undirected graph.
• Directed Graphs: For every couple of associated graphs, if an individual could move from one node to another in a specific (single) direction, then the graph is known as the directed graph. In this case, arrows are implemented rather than simple lines in order to represent directed edges.

Weighted Graphs

The weight graphs are the graphs where edges of the graph have “a weight” or “cost” and also where weight could reflect distance, time, money or anything that displays the “association” amid a couple of nodes it links. These weights are an essential element under Dijkstra’s Algorithm.

Now we will move to Dijkstra’s Algorithm

What is Dijkstra’s Algorithm?

What if you are provided with a graph of nodes where every node is linked to several other nodes with varying distance. Now, if you begin from one of the nodes in the graph, what is the shortest path to every other node in the graph?

Well simply explained, an algorithm that is used for finding the shortest distance, or path, from starting node to target node in a weighted graph is known as Dijkstra’s Algorithm.

This algorithm makes a tree of the shortest path from the starting node, the source, to all other nodes (points) in the graph.

Dijkstra’s algorithm makes use of weights of the edges for finding the path that minimizes the total distance (weight) among the source node and all other nodes. This algorithm is also known as the single-source shortest path algorithm.

Dijkstra’s algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph.

It is important to note that Dijkstra’s algorithm is only applicable when all weights are positive because, during the execution, the weights of the edges are added to find the shortest path.

Now its the time to learn about OSPF

OSPF was designed as an interior gateway protocol (IGP), for use in an autonomous system such as a local area network (LAN). It implements Dijkstra’s algorithm(Here it came😅!!), also known as the shortest path first (SPF) algorithm

How does OSPF work?

There are three steps that can explain the working of OSPF:

Step 1: The first step is to become OSPF neighbors. The two connecting routers running OSPF on the same link creates a neighbor relationship.

Now the question arises

How a router forms a neighbor relationship?

So, The first thing is happened before the relationship is formed is that each router chooses the router ID.

Router ID (RID): The router ID is a number that uniquely identifies each router on a network. The router ID is in the format of the IPv4 address. There are few ways to set the router ID, the first way is to set the router ID manually and the other way is to let the router decides itself.

Step 2: The second step is to exchange database information. After becoming the neighbors, the two routers exchange the LSDB information with each other.

Step 3: The third step is to choose the best route. Once the LSDB information has been exchanged with each other, the router chooses the best route to be added to a routing table based on the calculation of SPF.

💙💙Thanks for reading this article💙💙

I hope you got an idea on OSPF (Open Short Path First)

For more such articles

Stay Connected 😄

I’ll be grateful to have connections like you on Linkedln