OSPF (Open Short Path First) Routing Protocol using Dijkstra Algorithm

What is Open Shortest Path First (OSPF)?

The OSPF (Open Shortest Path First) protocol is one of a family of IP Routing protocols, and is an Interior Gateway Protocol (IGP) for the Internet, used to distribute IP routing information throughout a
single Autonomous System (AS) in an IP network.

The main advantage of a link-state routing protocol like OSPF is that the complete knowledge of topology allows routers to calculate routes that satisfy particular criteria.
This can be useful for traffic engineering purposes, where routes can be constrained to meet the particular quality of service requirements.

The main disadvantage of a link-state routing protocol is that it does not scale well as more routers are added to the routing domain.
Increasing the number of routers increases the size and frequency of the topology updates, and also the length of time it takes to calculate end-to-end routes.
This lack of scalability means that a link-state routing protocol is unsuitable for routing across the Internet at large, which is the reason why IGPs only route traffic within a single AS.

From this database, each router calculates its own routing table using a Shortest Path First (SPF) or Dijkstra algorithm.
This routing table contains all the destinations the routing protocol knows about, associated with a next-hop IP address and outgoing interface.

  • The protocol recalculates routes when network topology changes, using the Dijkstra algorithm and minimizes the routing protocol traffic that it generates.
  • It provides support for multiple paths of equal cost.
  • It provides a multi-level hierarchy (two-level for OSPF) called “area routing,” so that information about the topology within a defined area of the AS is hidden from routers outside this area.
    This enables an additional level of routing protection and a reduction in routing protocol traffic.
  • All protocol exchanges can be authenticated so that only trusted routers can join the routing exchanges for the AS.

Dijkstra’s Algorithm

Dijkstra’s algorithm allows us to find the shortest path between any two vertices of a graph.
It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.

How Dijkstra’s Algorithm works

Dijkstra’s Algorithm works on the basis that any subpath B -> D of the shortest path A -> D between vertices A and D is also the shortest path between vertices B and D.

Djikstra used this property in the opposite direction i.e we overestimate the distance of each vertex from the starting vertex. Then we visit each node and its neighbors to find the shortest subpath to those neighbors.

The algorithm uses a greedy approach in the sense that we find the next best solution hoping that the end result is the best solution for the whole problem

OSPF Working

OSPF is a routing protocol. Two routers speaking OSPF to each other exchange information about the routes they know about and the cost for them to get there.

When many OSPF routers are part of the same network, information about all of the routes in a network are learned by all of the OSPF routers within that network — technically called an area.

Each OSPF router passes along information about the routes and costs they’ve heard about to all of their adjacent OSPF routers, called neighbors.

OSPF routers rely on cost to compute the shortest path through the network between themselves and a remote router or network destination.
The shortest path computation is done using Djikstra’s algorithm.

Consider a simple example of five routers connected as shown in the diagram below. Assuming all links have the same cost, what’s the fastest way for R3 to connect to R5? Through R4 — R4 is the lowest cost path.

(R3’s path to R5 via R1, for example, adds another link and therefore additional cost.)

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Rails for the first Time

Scalability in video-conferencing (Part 2)

Why we use Laravel & Wink

Be a volunteer and develop the story together!

How to Get all the Co-ordinates of Hand using Mediapipe Hand Solutions ?

Into Game Mechanics: Player Navigation

State of DevOps 2019 — my own TL;DR

Custom Annotation in the Spring Boot.

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
Akanksha Chhattri

Akanksha Chhattri

More from Medium

WONO, a rapidly growing worldwide community of independent contractor, issues a token so that…

The future of sports currency: What are fan tokens and how do they work?

Size Matters! Speed Matters! NuGenesis patented NFT Tech to filter the winners

Welshcorgicoin Partners with StacksArt to Provide NFT Access Point to Community