OSPF Routing Protocol

Implementation using Dijkstra’s Algorithm.

What is a routing protocol?

Before moving towards OSPF which is a routing protocol let us get an overview of what is a routing protocol. The network devised between the systems is mainly to send information from source to destination. These network packets, therefore, must have a destination to be reached.

Among the many routers and networks, the routing tables decide the path that can be followed by these packets. Routing protocols thus come up to help to set up these routing tables. There are many routing protocols depending upon the use cases. One such routing protocol is OSPF.

What is OSPF?

The acronym OSPF stands for Open Shortest Path First. OSPF is a widely used and supported standard routing protocol. Having the advantage of being called standard, OSPF can be supported by any route. A routing protocol is used for dynamically updating the routing tables in the network.

It is Interior Gateway Protocol (IGP) meaning it has been designed to be used in a single autonomous system. In addition, it is also a Link-state protocol. Link is the connection of one router with the other and state suggests whether the link is up or not.

Since the goal of every routing protocol is to learn about the routes in an IP network. OSPF on similar groundworks by analyzing every route and subnet within the entire network. The result is every router has the same information about the network as each other. The wave routers learn this information by sending LSA’s. ( Link- State Advertisements).

These LSA are signals which contain information about the routers, subnet, and network. All the information of LSA is stored by OSPF in a database called LSDB with aim of having the same information in all routers as in LSDB.

Working of OSPF

The working of OSPF is based on three basics rules which are as follows:

1. Becoming Neighbors: Two routers running on OSPF on the same link agree to form a neighbor. The link data for the neighbors is created for every router in the network.
2. Exchanging Database information: The neighbor routers swap their LSDB information with each other such that every router must have all and same information.
3. Choosing the best routes: The final step is to choose the best possible route to add to the routing table based on the learned information from LSDB. The open shortest path first uses Dijkstra’s algorithm to obtain the shortest path once the above two steps have been completed.

What is Dijkstra’s Algorithm?

Let us say you plan to visit a city ‘A’ in the shortest time possible. But for obvious to follow the desire you must go for the shortest path from your place to the desired destination ‘A’.

If we have multiple paths connecting multiple other cities between source and destination, we use the algorithm that will use to accomplish the shortest path. This algorithm is Dijkstra’s Algorithm.

It was proposed by a Dutch computer scientist, Edsger Dijkstra, in 1959, to find the shortest path in a weighted graph. The graph can either be directed or undirected with the stipulation that the graph needs to encompass a non-negative value on its every edge. He named this algorithm “Dijkstra’s Algorithm” at his name.

Dijkstra’s algorithm keeps track of the source node's current distance to the rest of the nodes and dynamically updates these values if a shorter path is found. A node is then marked as visited and added to the path if the distance between it and the source node is the shortest.

Implementation of Dijkstra’s Algorthim

The algorithm can be implemented from a source ‘S’ To a destination ‘D’ in the graph by following the below-mentioned points:

1. the Dijkstra algorithm starts from the node to be decided, the source node, and it scans the entire graph to determine the shortest path among that node and all the other nodes in the graph.
2. The algorithm keeps the track of the currently accepted shortest distance from each node to the source code and updates these values if it identifies another shortest path.
3. the algorithm has determined the shortest path amid the source code to another node, the node is marked as “visited” and can be added to the path.
4. This process is being continued till all the nodes in the graph have been added to the path

The distance of vertex connected to each other is taken as the weights and infinity if not connected. With every visit, it calculates the least possible weights following the formula :

dist[r]=min(dist[r], dist[q]+cost[q][r])

Applications of Open Shortest Path First

OSPF is the first broadly used routing protocol. It can unite with a network in very little time, and it is one of the protocols that can render loop-free paths. Aside from these features, Open Short Path First allows the imposition of policies for the propagation of routes in the network.

Open Short Path First is better at load sharing on external links compared to other IGPs. Considering these benefits, it can found widespread use.

Microsoft’s Windows NT 4.0 Server, Windows 2000 Server, and Windows Server 2003 all have OSPF v2 in the Routing and Remote Access Services.

OpenBSD Operating system has an implementation of OpenBGPD protocol which has OpenOSPFD implementation.

GNU Zebra is a GPL routing suite that supports OSPF for Unix-Like systems.