OSPF Routing Protocol implemented using Dijkstra’s Algorithm

OSPF(Open Shortest Path First) Routing Protocol

Open Shortest Path First (OSPF) is a link-state routing protocol that was developed for IP networks and is based on the Shortest Path First (SPF) algorithm. OSPF is an Interior Gateway Protocol used to distribute routing information within a single Autonomous System.

Dijkstra’s Algorithm

Dijkstra’s algorithm aims to find the shortest path in a directed or undirected graph with non-negative edge weights.

The main logic of this algorithm is based on the following formula:-

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

• It states that distance vertex r, which is adjacent to vertex q, would be updated only if the value of dist[q]+cost[q][r]is less than dist[r].
• dist is a 1-D array that keeps track of the shortest distance at every step from the source vertex to all other vertices.
• cost is a 2-D array that represents the cost adjacency matrix for the graph

Complexity:

• Time complexity: Θ(E+V log V) (V for vertices & E for edges)
• Space complexity: Θ(V)
• Time complexity(If priority queue is not used): Θ(E+V²)

Implementation of OSPF using Dijkstra’s Algorithm

OSPF uses a shorted path first algorithm in order to build and calculate the shortest path to all known destinations. The shortest path is calculated with the use of the Dijkstra algorithm. The simplified way of looking at the various steps of the algorithm:

1. Upon initialization or due to any change in routing information, a router generates a link-state advertisement. This advertisement represents the collection of all link-states on that router.
2. All routers exchange link-states by means of flooding. Each router that receives a link-state update should store a copy in its link-state database and then propagate the update to other routers.
3. After the database of each router is completed, the router calculates a Shortest Path Tree to all destinations. The router uses the Dijkstra algorithm in order to calculate the shortest path tree. The destinations, the associated cost and the next hop to reach those destinations form the IP routing table.
4. In case no changes in the OSPF network occur, such as the cost of a link or a network being added or deleted, OSPF should be very quiet. Any changes that occur are communicated through link-state packets, and the Dijkstra algorithm is recalculated in order to find the shortest path.

The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest-path tree using the same link-state database.