# Behind the Scenes : Open Shortest Path First Protocol

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.