OSPF Routing Protocol using Dijkstra Algorithm

Objectives:-

In this article, We will learn about Dijkstra Algorithm and Open Short Path First(OSPF) Routing Protocol . And we will also learn how Open Short Path First Routing Protocol is implemented by the Dijkstra Algorithm.

Let's us first know about Dijkstra Algorithm.

Dijkstra Algorithm

Dijkstra algorithm is a greedy algorithm. It finds a shortest-path tree for a weighted undirected graph. This means it finds the shortest paths between nodes in a graph, which may represent, for example, road networks For a given source node in the graph, the algorithm finds the shortest path between the source node and every other node.

Also called the Shortest Path First (SPF). SPF is a routing algorithm in which a router computes the shortest path between each pair of nodes in the network. The Open Shortest Path First (OSPF) Protocol is based on the Shortest Path First (SPF) algorithm.

Open Shortest Path First (OSPF) protocol

• Open shortest path first is a protocol for the routing process. This protocol is used to find the shortest path between multiple routers. in this scenario, multiple routers are connected through each other with the help of links these routers are called nodes. Each node is connected with other nodes like a hierarchy. There is no limit to nodes connections.
• The work of each node is to send topology information to the other node this procedure continuous vice versa means if one sends the information completely then the other will send information. Each node is independent and they can find an appropriate and convenient path for the process themselves.
• OSPF is used to find the best path between the source and the destination router using it’s own Shortest Path First. Dijkstra’s algorithm is widely used in the routing protocol required by the routers to update their forwarding table.
• It provides the shortest cost path from the source router to other routers in the network.
• Also, the protocol recalculates routes when network topology changes by using Dijkstra’s algorithm and minimizes the routing protocol traffic that it generates.

Important Terms related with Open Shortest Path First (OSPF)

1. Router_Id:-Every Router in an OSPF network needs a unique OSPF Router ID. The OSPF Router ID is used to provide a unique identity to the OSPF Router. Priority is every person has a different identity to identify uniquely, the same condition is applied to a router. we can assign a router-id manually and it can be automatically configured by protocol.
2. Router Priority:-8 bit value that configures to a router to assign priority. A router that has a higher priority will start first and this condition is called DR .if the router priority is the same or tie then the router with a higher id will consider it first. There is also a condition when router-id is not defined, then the priority will be considered on the basis of the active IP address.
3. Down:- down is a condition in which the router doesn’t send any packages or messages that don’t mean the router is not working which means OSPF is not started working yet.
4. Master-Slave Relation:- A router that has a higher priority is to act as a master node and the rest are called slave nodes. to identify the priority, some elections are taking place who tells which node will send the message first.

Implementation of OSPF by Dijkstra Algorithm

When an OSPF router is initialized, it sends a Hello message to determine whether it has any neighbors (routers that have an interface on the same network). Neighbors respond to the initiating router by using the same Hello packets. In fact, these Hello packets also serve to tell other routers that the transmitting router is still alive (keep-alive function).

If more than two OSPF routers are on the internetwork, the Hello protocol causes one of the routers to be designated as the one to send out link state advertisements (LSAs) to all other routers on the network.

Neighbors then synchronize their topological databases with each other to become “adjacent” routers. Each router periodically floods the network with cost information for its adjacent nodes in the form of LSAs, allowing them to compile complete tables of network connections and calculate the path of least cost between any two nodes.

Finally, each router analyzes its own database of network topology information and uses it to determine a shortest-path tree using itself as the root; from this tree, it derives a routing table for itself.

Advantages and Disadvantages of OSPF

Advantages:- The main advantage of link state routing (OSPF) is that complete knowledge of topology allows routers to calculate routes that satisfy the incoming request. Which can be useful for traffic engineering purposes where routes can be manipulated to meet different service requirements.

Disadvantage:- The main disadvantage of a link state protocol is that it does not scale well as more routers are added to the routing domain. By adding more routers increases the size and frequency of the topology updates, and also the length of time it takes to calculate end-to-end routes. This creates a very large OSPF database, using a large amount of memory, which would adversely affect the network integrity. This lack of scalability means that a link state routing protocol is unsuitable for routing across the Internet at large, and is also reason why Imps only route traffic within a single AS.

I hope this will help you to understand that how OPSF is internally using Dijkstra Algorithm. Thanks for reading ... .