How OSPF (Open Short Path First) Routing Protocol implemented using Dijkastra Algorithm behind the scene?

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.

The IP network is classified into two categories: 

1) Interior Gateway Protocol

2)Exterior Gateway Protocol

Interior and Exterior Gateway Protocols:

Interior gateway protocols are used inside an organization’s network and are limited to the border router. Exterior gateway protocols are used to connect the different Autonomous Systems (ASs). A simple definition that fits most of the time defines the border router as a router that has a foot in two worlds: one going to the Internet and another that is placed inside the organization and that’s why it’s name as, border router.

OSPF Routing Protocol

Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a Link State Routing (LSR) algorithm and falls into the group of Interior Gateway Protocols (IGPs), operating within a single autonomous system (AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for IPv4.The updates for IPv6 are specified as OSPF Version 3 in RFC 5340 (2008). OSPF supports the Classless Inter-Domain Routing (CIDR) addressing model.

OSPF is a widely used IGP in large enterprise networks. IS-IS, another LSR-based protocol, is more common in large service provider networks.

OSPF is an interior gateway protocol that has been designed within a single autonomous system. It is based on a link-state routing algorithm in which each router contains the information of every domain, and based on this information, it determines the shortest path. The goal of routing is to learn routes. The OSPF achieves by learning about every router and subnet within the entire network. Every router contains the same information about the network. The way the router learns this information by sending LSA (Link State Advertisements). These LSAs contain information about every router, subnet, and other networking information. Once the LSAs have been flooded, the OSPF stores the information in a link-state database known as LSDB. The main goal is to have the same information about every router in an LSDBs.

Dijkstra’s Algorithm

Dijkstra’s algorithm allows us to find the shortest path between any two vertices of a graph.

It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.

History :- This algorithm was created and published by Dr. Edsger W. Dijkstra, a brilliant Dutch computer scientist and software engineer.

In 1959, he published a 3-page article titled “A note on two problems in connexion with graphs” where he explained his new algorithm.

During an interview in 2001, Dr. Dijkstra revealed how and why he designed the algorithm:

What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. — As quoted in the article Edsger W. Dijkstra from An interview with Edsger W. Dijkstra.

Requirements:- Dijkstra’s Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path.

If there is a negative weight in the graph, then the algorithm will not work properly. Once a node has been marked as “visited”, the current path to that node is marked as the shortest path to reach that node. And negative weights can alter this if the total weight can be decremented after this step has occurred.

Complexity:-

• Worst case time complexity: Θ(E+V log V)
• Average case time complexity: Θ(E+V log V)
• Best case time complexity: Θ(E+V log V)
• Space complexity: Θ(V)
• Time complexity is Θ(E+V^2) if priority queue is not used.

How to find the shortest path in 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

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.

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

And the weight of the shortest path is 2+2+2+2+2 = 10 unit.

Applications

• Telephone network:- In a telephone network the lines have bandwidth, BW. We want to route the phone call via the highest BW.
• Flight:- A travel agent requests software for making an agenda of flights for clients. The agent has access to a data base with all airports and flights. Besides the flight number, origin airport and destination, the flights have departure and arrival time. Specifically the agent wants to determine the earliest arrival time for the destination given an origin airport and start time.

Thanks for reading :)