Aug 30, 2021

How is OSPF (Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm behind the scene?

Hello, Guys

Here I came up with a new article In this article we will be going to talk about how OSPF(Open Shortest Path First) Routing protocol is implemented using Dijkstra Algorithm Behind the Scene.

So let’s Begin,

Let me tell you first what is Dijkstra Algorithm is and how it works.

What is Graph?

Graphs are data structures used to represent “connections” between pairs of elements.

1. These elements are called nodes. They represent real-life objects, persons, or entities.
2. The connections between nodes are called edges.

Nodes are represented with colored circles and edges are represented with lines that connect these circles.

Types of Graphs

Graphs can be:

• Undirected if for every pair of connected nodes, you can go from one node to the other in both directions.
• Directed: if for every pair of connected nodes, you can only go from one node to another in a specific direction. We use arrows instead of simple lines to represent directed edges.

What is Dijkstra Algorithm?

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.

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

What is OSPF(Open Shortest Path First)?

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. This is a very high-level, simplified way of looking at the various steps of the algorithm.

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 were as RIP protocol is there?

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

Here I used cisco packet tracer to show you that how OSPF chooses the shortest path:-