OSPF (Open Short Path First) Routing Protocol Implemented using Dijkstra Algorithm
What is OSPF (Open Short Path First)?
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.
Routing Protocols are the set of defined rules used by the routers to communicate between source & destination. They do not move the information from the source to a destination, but only update the routing table that contains the information.
Network Rouer protocols help you to specify the way routers communicate with each other. It allows the network to select routes between any two nodes on a computer network.
What is Dijkstra Algorithm?
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks
The topology table can easily be read to list off all of the networks and then one-by-one Dijkstra’s algorithm calculates the best path to each of those destinations. So it’s not like we run Dijkstra’s algorithm and it answers all of the best paths. We run it each time we have to get to a unique destination network.
- 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.
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). OSPF is developed by Internet Engineering Task Force (IETF) as one of the Interior Gateway Protocol (IGP), i.e, the protocol which aims at moving the packet within a large autonomous system or routing domain. It is a network layer protocol that works on protocol number 89 and uses AD value 110. OSPF uses multicast address 224.0.0.5 for normal communication and 224.0.0.6 for update to designated router(DR)/Backup Designated Router (BDR).
- The protocol recalculates routes when network topology changes, using the Dijkstra algorithm, and minimises the routing protocol traffic that it generates.
- It provides support for multiple paths of equal cost.
- It provides a multi-level hierarchy (two-level for OSPF) called “area routing,” so that information about the topology within a defined area of the AS is hidden from routers outside this area. This enables an additional level of routing protection and a reduction in routing protocol traffic.
- All protocol exchanges can be authenticated so that only trusted routers can join in the routing exchanges for the AS.
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.
OSPF Packet format-
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.
