How OSPF Protocol implements Dijkstra’s Algorithm

A Graph Theory Algorithm To Find Shortest Path In Routing Protocol

1) INTRODUCTION:

Routing protocol plays a vital role in establishing communication link between all its nodes. The nodes should have knowledge of the entire network structure. If an information has being passed from source node to destination node, then selecting the apt path to traversal is also assigned by routing protocols. To reach the destination node usage of shortest path will be benefited. Shortest path algorithm helps to find least expensive path on the network, based on the cost function.

This Article focuses on finding the shortest path between source and destination node in OSPF protocol using Dijkstra’s algorithm. Section II describes the role of Routing Protocol. Section III explains about OSPF protocol. Section IV discuss the pseudo code about Dijkstra’s algorithm. In Section V, we present about finding the shortest path in OSPF using Dijkstra’s algorithm. Section VI explains the performance of OSPF and we conclude with future work.”:

2) 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[1]. The IP network is classified into two categories: 

a) Interior Gateway Protocol

b)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[2].

For example,

 Exterior Gateway Protocol (EGP)

 Border Gateway Protocol (BGP)

3) OPEN SHORTEST PATH FIRST (OSPF) :

The most widely used routing protocols is OSPF and is suitable for large network. OSPF is a Link State protocol based on cost under a single routing solution that maintains information of all nodes on the network. Since each nodes holds the entire network structure information, each nodes can independently calculate the path to reach the destination by adopting shortest path algorithm namely Dijkstra’s algorithm.

4) GRAPH THEORY ALGORITHM: DIJIKSTRA’S ALGORITHM

Graph theory is the study of graphs that concern with the relationship with edges and vertices. Graph theory is used to determine the relationship among in with the computer network. One of the graph theory algorithm is Dijkstra’s algorithm, that is used to find the shortest path based on cost weightage. The advantage of using Dijkstra’s algorithm is to find shortest path from the staring vertex to all other vertices in the graphs.

4.1) Dijikstra’s Algorithm:

Step 1: Assign starting vertex to zero and assign all vertices distance to infinity.

Step 2: Starting vertex will be send to minimum priority queue based on distance & vertex.

Step 3: The vertex with minimum distance will be removed from the priority queue and update the queue.

Step 4: Check whether current vertex distance + edge weight is less than next vertex distance then send the next distance to the priority queue.

Step 5: Repeat step 2 to 4 until the priority queue is empty[3].

4.2) Pseudocode for Dijkstra’s Algorithm:

Consider source vertex is v and it should be a weighted graph g=(E,V). Source vertex S ∈ V to all vertex v ∈ V[10].

dist[s]←0
for all v ∈ V–{s}
do dist[v] ←∞
S ← ∅
Q←V
while Q≠∅
do u←mindistance(Q,dist)
S←S U {u}
for all v ∈ neighbors[u]
do if dist[v]>dist[u]+w(u,v)
then d[v] ←d[u]+w(u,v)
return dist
Some of the principles used in Dijkstra’s Algorithm are:
• It can be directed and undirected graphs
• All edges should have positive values.
• It should be a connected graph.

5) 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
node.

5.1) 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[6].

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.

With the help of Dijkstra’s algorithm, we were able to find the shortest path between node A to node D. The final shortest path
for the given node is A →B→E→F→H→D.

6). PERFORMANCE OF OSPF:
We can measure the performance of OSPF under variety of strategy[7]. The performance measure of OSPF is specified in the table.

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