In this article let’s deep dive into the distinguished routing protocol : OSPF
👉What actually OSPF is ?
Open Shortest Path First is a routing protocol for Internet Protocol(IP) networks,which uses a link state routing (LSR) algorithm ,falling into the groups of interior gateway protocols (IGPs) , operating within a single autonomous system(AS).
In addition to above details , OSPF supports the Classless Inter-Domain Routing (CIDR) addressing model.It is a widely used IGP in large enterprise networks,IS-IS ,another LSR-based protocol,is more common in large service provider networks.
👉How does OSPF operate?
- OSPF 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 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 the network topology changes by using Dijkstra’s algorithm and minimizes the routing protocol traffic that it generates.
- As a link-state routing protocol, OSPF maintains link-state databases, which are really network topology maps, on every router on which it is implemented. The state of a given route in the network is the cost, and OSPF algorithm allows every router to calculate the cost of the routes to any given reachable destination.
- The Link State Database (LSDB) contains the link state advertisements sent around the ‘Area’ and each router holds an identical copy of this LSDB. The router then creates a Shortest Path First (SPF) tree using Dijkstra’s algorithm on the LSDB and a routing table can be derived from the SPF tree which now contains the best route to each router.
👉Dijsktra’s Algorithm :
Dijkstra’s algorithm was published in 1959 ,named after 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.
This algorithm predominantly follows the Greedy approach for finding the locally optimal solutions, whereas for building globally optimal solutions, it uses the Dynamic Programming approach.
Dijkstra’s algorithm uses a data structure for storing and querying partial solutions sorted by distance from the start. While the original algorithm uses a min-priority queue and runs in time ⊖((|V|+|E|)\log |V|)
(where {|V|}, is the number of nodes and {|E|} is the number of edges), it can also be implemented in { ⊖(|V|^{2})}using an array.
The idea of this algorithm is also given in Leyzorek et al. 1957. Fredman & Tarjan 1984 propose using a Fibonacci heap min-priority queue to optimize the running time complexity to {⊖(|E|+|V|\log |V|)}.
This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can indeed be improved further as detailed in Specialized variants. Additionally, if pre-processing is allowed algorithms such as contraction hierarchies can be up to seven orders of magnitude faster.
In some fields, artificial intelligence in particular, Dijkstra’s algorithm or a variant of it is known as uniform cost search and formulated as an instance of the more general idea of best-first search.