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

ROUTING PROTOCOL :

  • IP routing sending data packets from one network to another through routers. It is routers that examine destination IP address, determine next hop address to address a packet.
  • Remote router IP address of router used to reach that network outgoing interface. Populating routing table directly connected to subnets, static routing, default, dynamic routing.
  • Directly Connected Interface routes local to router (One or More) network subnets easily recognizable traffic directed to these network can be forwarded without any help from routing protocols.
  • Static Routing : Routes to destination manually entered by network administrators in router’s route table, don’t adjust to changes in the network.
  • Default Gateway : The router that hosts use to communicate with other hosts — remote networks.
  • Default Routing : Network having only one output interface, all the data going through a single exit. Instead of having many static routers connecting to remote networks, single output interface is configured to match all routes.
  • Dynamic Routing : Optimal data routing, enables routes to select paths according to real-time logical network changes. Routing protocol responsible for the creation, maintenance, update of a dynamic routing table. While in static routing all routing job have done manually by network administrator.

OSPF ROUTING PROTOCOL :

Note :

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

DIJKSTRA’S ALGORITHM :

dist[r]=min(dist[r], dist[q]+cost[q][r])
  • 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[r].
  • 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

Basics of Dijkstra’s Algorithm :

  • Dijkstra’s Algorithm basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
  • The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
  • Once the algorithm has found the shortest path between the source node and another node, that node is marked as “visited” and added to the path.
  • The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.

Requirements :

Complexity :

  • 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²)

DIJKSTRA’S BEHIND THE OSPF :

OSPF Interfaces :

  1. An OSPF broadcast interface is connected to a shared network, like Ethernet.
  2. An OSPF point-to-point interface is connected to a link where there can only be a single OSPF router on either end, such as a WAN link or a purpose-built Ethernet link.

OSPF Areas :

  • Route summarization & aggregation (replacing several small routes with one larger route that covers them) can only happen at OSPF area boundaries.
  • Not all routers need to know about every other route available in a network. Using OSPF areas, it’s possible to inject a default route representing all routes outside of the local area.

A simple two-router OSPF network :

--

--

--

ARTH - Learner

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

Recommended from Medium

`Probably` the fastest Black Scholes Pricer in world

DevOps Activity: create a CI/CD pipeline to build, deploy, and monitor the web application using…

CS371g Summer 2021 Week 2: Andrew Li

Chapter 1. “Terraform” A Powerful Tool for Infrastructure as Code

France has just won the World Cup, but I hate both my TV and Internet providers now.

SOLD Principles in C#

K8s — Secret

You should probably be paying closer attention to your CI build times

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
Yash Panchwatkar

Yash Panchwatkar

ARTH - Learner

More from Medium

Introduction to Algorithms — Selection Sort, Bubble Sort

CS371p Spring 2022: Relena Lai

Detect the face from live video Streaming and blur the face Using OpenCV

Deep learning for BARCODE Deblurring Part 1: Create training datasets