Open Shortest Path First Protocol

Open Shortest Path First(OSPF)

  1. The OSPF is an open standard protocol that is most popularly used in modern networks.
  2. It is a link state protocol.
  3. It is used to find the best path between the source and the destination router using its own Shortest Path First.
  4. Various protocols are used for shortest path. But in real life mostly problems are undirected graph like nature. OSPF using Dijkstra’s algorithm solved shortest path problem in both type of problems i.e. directed and undirected graph.
  5. OSPF is not a CISCO proprietary protocol like EIGRP.
  6. OSPF always determines the loop free routes. If any changes occur in the network it updates fast.
  7. 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.

OSPF terms

  1. Router I’d: It is the highest active IP address present on the router.
  2. Router priority: It is an 8-bit value assigned to a router operating OSPF, used to elect DR and BDR in a broadcast network.
  3. Designated Router (DR): It is to act as a central point for exchanging of OSPF information between multiple routers on the same, multiaccess broadcast network segment
  4. Backup Designated Router (BDR): BDR is a backup to DR in a broadcast network. When DR goes down, BDR becomes DR and performs its functions.

Working of OSPF:

  • 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.

Dijkstra’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.

Thanks for reading.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store