# How is Open Short Path First Routing Protocol implemented?

## What are Graphs?

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as,

*A Graph consists of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.*

## Real-World Uses of Graph

**Graphs are used in diverse industries and fields:**

**GPS systems and Google Maps**use graphs to find the shortest path from one destination to another.**Social Networks**use graphs to represent connections between users.**The Google Search**algorithm uses graphs to determine the relevance of search results.**Operations Research**is a field that uses graphs to find the optimal path to reduce the cost of transportation and delivery of goods and services.**Even Chemistry**uses graphs

## Graph Data Structure

Mathematical graphs can be represented in the data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let’s familiarize ourselves with some important terms −

**Vertex**− Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.**Edge**− Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represent edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2, and so on, keeping other combinations as 0.**Adjacency**− Two nodes or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.**Path**− Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.

# Traversal in Graph

## Depth-first search

A depth-first search (DFS) is an algorithm for traversing a finite graph. DFS visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. A stack (often the program’s call stack via recursion) is generally used when implementing the algorithm.

DFS is the basis for many graph-related algorithms, including topological sorts and planarity testing.

**procedure** DFS(*G*, *v*) **is**

label *v* as explored

**for all** edges *e* in *G*.incidentEdges(*v*) **do**

**if** edge *e* is unexplored **then**

*w* ← *G*.adjacentVertex(*v*, *e*)

**if** vertex *w* is unexplored **then**

label *e* as a discovered edge

recursively call DFS(*G*, *w*)

**else**

label *e* as a back edge

# Breadth-first search

A breadth-first search (BFS) is another technique for traversing a finite graph. BFS visits the sibling vertices before visiting the child vertices, and a queue is used in the search process. This algorithm is often used to find the shortest path from one vertex to another.

**procedure** BFS(*G*, *v*) **is**

create a queue *Q*

enqueue *v* onto *Q*

mark *v*

**while** *Q* is not empty **do**

*w* ← *Q*.dequeue()

**if** *w* is what we are looking for **then**

return *w*

**for all** edges *e* in *G*.adjacentEdges(*w*) **do**

*x* ← *G*.adjacentVertex(*w*, *e*)

**if** *x* is not marked **then**

mark *x*

enqueue *x* onto *Q*

**return** null

# Shortest Path Problems

The Single-Source Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex *v* and all other vertices in the graph. Algorithms such as Breadth-First-Search (BFS) for unweighted graphs or Dijkstra solve this problem. The All-Pairs Shortest Path (APSP) problem consists of finding the shortest path between all pairs of vertices in the graph. To solve this second problem, one can use the Floyd-Warshall algorithm or apply the Dijkstra algorithm to each vertex in the graph.

## What is Djiskstra Algorithm?

Dijkstra’s algorithm is one of the most popular algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by computer scientist **Edsger W. Dijkstra** in 1956 and published three years later.

Dijkstra’s Algorithm has several real-world use cases, some of which are as follows:

**Digital Mapping Services in Google Maps:**Many times we have tried to find the distance in G-Maps, from one city to another, or from your location to the nearest desired location. There encounters the Shortest Path Algorithm, as there are various routes/paths connecting them but it has to show the minimum distance, so Dijkstra’s Algorithm is used to find the minimum distance between two locations along the path. Consider India as a graph and represent a city/place with a vertex and the route between two cities/places as an edge, then by using this algorithm, the shortest routes between any two cities/places or from one city/place to another city/place can be calculated.**Social Networking Applications:**In many applications, you might have seen the app suggests the list of friends that a particular user may know. How do you think many social media companies implement this feature efficiently, especially when the system has over a billion users. The standard Dijkstra algorithm can be applied using the shortest path between users measured through handshakes or connections among them. When the social networking graph is very small, it uses standard Dijkstra’s algorithm along with some other features to find the shortest paths, and however, when the graph is becoming bigger and bigger, the standard algorithm takes a few several seconds to count and alternate advanced algorithms are used.**Telephone Network:**As we know, in a telephone network, each line has a bandwidth, ‘b’. The bandwidth of the transmission line is the highest frequency that that line can support. Generally, if the frequency of the signal is higher in a certain line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. If we imagine a city to be a graph, the vertices represent the switching stations, and the edges represent the transmission lines and the weight of the edges represents ‘b’. So as you can see it can fall into the category of shortest distance problem, for which the Dijkstra is can be used.**IP routing to find Open shortest Path First:**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. Dijkstra’s algorithm is widely used in the routing protocols required by the routers to update their forwarding table. The algorithm provides the shortest cost path from the source router to other routers in the network.**Flighting Agenda:**For example, If a person needs software for making an agenda of flights for customers. The agent has access to a database with all airports and flights. Besides the flight number, origin airport, and destination, the flights have departure and arrival times. Specifically, the agent wants to determine the earliest arrival time for the destination given an origin airport and start time. There this algorithm comes into use.**Designate file server:**To designate a file server in a LAN(local area network), Dijkstra’s algorithm can be used. Consider that an infinite amount of time is required for transmitting files from one computer to another computer. Therefore to minimize the number of “hops” from the file server to every other computer on the network the idea is to use Dijkstra’s algorithm to minimize the shortest path between the networks resulting in the minimum number of hops.**Robotic Path:**Nowadays, drones and robots have come into existence, some of which are manual, some automated. The drones/robots which are automated and are used to deliver the packages to a specific location or used for a task are loaded with this algorithm module so that when the source and destination are known, the robot/drone moves in the ordered direction by following the shortest path to keep delivering the package in a minimum amount of time.

# Routing Protocol

The work of nodes is to communicate information between nodes assigned by the 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 protocols used in IP networks. 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)

**OPEN SHORTEST PATH FIRST (OSPF) :**

The most widely used routing protocol is OSPF and is suitable for large networks. 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 node holds the entire network structure information, each node can independently calculate the path to reach the destination by adopting the shortest path algorithm namely Dijkstra’s algorithm.

**GRAPH THEORY ALGORITHM: DIJKSTRA'S ALGORITHM**

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

**Dijkstra's Algorithm:**

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

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

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

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

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

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

**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, the sender will

send some frame or message to the 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

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 the source node.

2. During the second stage, we need to look 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 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

node.

**The formula used for comparing two nodes to findthe minimum value**

Minimum(Destination value, Marked value + node value)

where Destination values are the destination node value,

Marked value is the source node value, Node value is the

weightage of edge that connects 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.**

**PERFORMANCE OF OSPF:**

We can measure the performance of OSPF under a variety of strategies. The performance measure of OSPF is specified in the table.

## Conclusion

OSPF is a Link State Routing Protocol that is used for the construction of larger network sizes. In this paper, we have concentrated

on the 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.