How is OSPF Routing Protocol implemented using Dijkstra’s Algorithm
Content of this Blog
- About OSPF(Open Shortest Path First) Routing Protocol
- About Dijkstra’s Algorithm
- Implementation of OSPF using Dijkstra’s Algorithm
About OSPF(Open Shortest Path First) Routing Protocol
OSPF routing protocol is a Link State protocol based on cost rather than hops or ticks i.e., it is not vector based routing protocol.
It is an Interior Gateway Protocol for the Internet which is used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.
- Autonomous System could be defined as the set of internet routable IP prefixes belonging to a network or a collection of networks managed by a single entity or organizations.
- Link State routing is the concept within which every node constructs a map of the connectivity to the network in the form of graph.
About Dijkstra’s Algorithm
Dijkstra’s algorithm was published in 1959 and named after it’s discoverer Edsger Dijkstra, who was a Dutch computer scientist. It aims to find the shortest-path in a directed or undirected graph with non-negative edge weights.
Main logic of this algorithm is based on the following formula:-
- 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 is a 1-D array which keeps track of the shortest distance at every step from source vertex to all other vertices.
- cost is a 2-D array that represents the cost adjacency matrix for the graph
- Set the distance to the source to 0 and the distance to the remaining vertices to infinity.
- Set the current vertex to the source.
- Flag the current vertex as visited.
- For all vertices adjacent to the current vertex, set the distance from the source to the adjacent vertex equal to the minimum of its present distance and the sum of the weight of the edge from the current vertex to the adjacent vertex and the distance from the source to the current vertex.
- From the set of unvisited vertices, arbitrarily set one as the new current vertex, provided that there exists an edge to it such that it is the minimum of all edges from a vertex in the set of visited vertices to a vertex in the set of unvisited vertices. To reiterate: The new current vertex must be unvisited and have a minimum weight edges from a visited vertex to it. This can be done trivially by looping through all visited vertices and all adjacent unvisited vertices to those visited vertices, keeping the vertex with the minimum weight edge connecting it.
- Repeat steps 3–5 until all vertices are flagged as visited.
- 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 is used to find the best path between the source and the destination router using it’s own Shortest Path First. Dijkstra’s algorithm is widely used in the routing protocol required by the routers to update their forwarding table.
- It provides the shortest cost path from the source router to other routers in the network.
- Also, the protocol recalculates routes when network topology changes by using Dijkstra’s algorithm and minimizes the routing protocol traffic that it generates.
Java Code for implementation of Dijkstra’s Algorithm in OSPF