Implementation of OSPF (Open Short Path First) Routing Protocol using Dijkastra Algorithm.
Hello Readers..,
In this article I am gonna talking about how OSPF (Open Short Path First) Routing Protocol taking the help of Dijkstra Algorithm behind the scene.
Before moving to core part of article let me first brief the Routing Protocol and OSPE.
📍ROUTING PROTOCOL:-
The work of node is to communicate information between nodes assigned by routing protocol. It also helps in passing information and data packets between the nodes. The nodes have information about the network directly attached and with the help of routing protocol, it is aware of the entire structure of the network. There are different types of protocol, but we discuss about protocols used in IP network.
The IP network is classified into two categories:
- Interior Gateway Protocol
- Exterior Gateway Protocol
Interior Gateway protocol communicates routing data within a single routing domain. It is divided into Link State Routing protocol and Distance Vector Routing protocol. The link state routing protocol maintains the full structure of the network on each router connected to its network. For example, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). In the Distance Vector Routing protocol, the route information is periodically shared in the entire network. For example, Interior Gateway Routing Protocol (IGRP). An exterior Gateway protocol communicates routing information with independent systems. For example,
Exterior Gateway Protocol (EGP)
Border Gateway Protocol (BGP)
✨Open Shortest Path First(OSPF):-
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing(LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system(AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for IPV4 The updates for IPV6 are specified as OSPF Version 3 in RFC 5340 (2008).OSPF supports the Classless Inter Domain Routing (CIDR) addressing model.
OSPF is a widely used IGP in large enterprise networks IS-IS another LSR-based protocol, is more common in large service provider networks.
OSPF was designed as an interior gateway protocol (IGP), for use in an autonomous system such as a LAN. It implements Dijkstra’s Algorithm also known as the shortest path first (SPF) algorithm. Routing protocols like OSPF calculate the shortest route to a destination through the network based on an algorithm. 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, taking into account bandwidth, delay and load. Therefore, OSPF undertakes route cost calculation on the basis of link-cost parameters, which can be weighted by the administrator. OSPF was quickly adopted because it became known for reliably calculating routes through large and complex local area networks.
OSPF Packet format:-
📌What does Open Shortest Path First do?
The OSPF (Open Shortest Path First) protocol is one of a family of IP Routing protocols, and is an Interior Gateway Protocol (IGP) for the Internet, used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.
❗ How does it work?
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. … OSPF routers rely on cost to compute the shortest path through the network between themselves and a remote router or network destination.
✨Dijkstra’s algorithm:-
Dijkstra’s Algorithm is used to find the shortest path between a node/vertex (source node) to any (or every) other nodes/vertices (destination nodes) in a graph. A graph is basically an interconnection of nodes connected by edges. This algorithm is sometimes referred to as Single source shortest Path Algorithm due to its nature of implementation.
With 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.
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, specially in domains that require modeling networks.
👉Basics of Dijkstra’s Algorithm:-
- 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.
✨How to find the shortest path in OSPF using Dijkstra’s Algorithm 👉👉
Dijkstra’s algorithm is graph traversing algorithm. In computer network we have sender and receiver, sender will send some frame or message to 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 neighbor nodes of source node.
2. During the second stage, we need to look for second shortest path node, which can be a neighbor node of source node or to the node found in the first stage.
3. During the third stage, the algorithm looks for third shortest path node form the source node. This node can be neighbor of source node or the nearest node found from first stage or second stage.
4. The process repeated, until all nodes are visited at-least once and if all nodes are visited once, then we can find the shortest path form the source node to destination
👉Formula used for comparing two nodes to find minimum value
Minimum(Destination value, Marked value + node value)where, Destination values is the destination node value, Marked value is the source node value, Node value is the weightage of edge that connect source and destination.For example:
If destination value =10, Marked value =5 and Edge weight=4.
Substituting in the formula, we get
Min(10,5+4)
=Min(10,9)
=9 (Since 9 is smaller than 10)
To find the shortest path, we have marked the visited and unvisited nodes list in a table.
shortest path between node A to node D. The final shortest path for the given node is
A ->B -> E ->F ->H ->D.
And the weight of the shortest path is 2+2+2+2+2 = 10 unit
✨ CONCLUSION :-
OSPF is a Link State Routing Protocol that is used for construction of larger network size. In this paper, we have concentrated about OSPF protocol. Dijkstra’s algorithm is one of the best suited algorithms to find the shortest path for the given vertices. In future work we would implement OSPF protocol using NS2 simulator.
