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

WHAT IS A ROUTING PROTOCOL?

A routing protocol is used to deliver application traffic. It provides appropriate addressing information in its internet layer or network layer to allow a packet to be forwarded from one network to another. Examples of routed protocols are the Internet Protocol (IP) and Internetwork Packet Exchange (IPX). The IP network is further classified into two categories:

1. Interior Gateway Protocol
2. 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)

What is Dijkstra Algorithm?

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.

How Dijkstra's Algorithm works?

• 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 Protocol (OSPF)

OSPF is a classless routing protocol, which means that in its updates, it includes the subnet of each route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility. These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).

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.

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,

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.

• During the first stage, we need to find the shortest node from the neighbor nodes of source node.
• 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.
• 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.
• 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.

So that's all . It was the basic idea how OSPF uses Dijkstra algorithm. Hope you like it.

Thank you for reading............