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

OSPF is:

Open shortest path first (OSPF) is a link-state routing protocol which is used to find the best path between the source and the destination router using its own shortest path first (SPF) algorithm. A link-state routing protocol is a protocol which uses the concept of triggered updates, i.e., if there is a change observed in the learned routing table then the updates are triggered only, not like the distance-vector routing protocol where the routing table are exchanged at a period of time.

It is:

1>Widely used and supported Protocol

2>Interior Gateway Protocol

3>Link state routing Protocol

The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the AS, so that every router within the AS has a complete picture of the topology of the AS. This picture is then used to calculate end-to-end paths through the AS, normally using a variant of the Dijkstra algorithm. Therefore, in a link-state routing protocol, the next hop address to which data is forwarded is determined by choosing the best end-to-end path to the eventual destination.

Dijkstra Algorithm

The Dijkstra Algorithm converts routers, subnets, and links into a tree

In the above example, the layer 3 network consists of LANs, connecting hosts connected via routers.

The building represents LANs, We can imagine the equipment in the building that makes up the LAN

Each LAN is a separate IP subnet

The individual subnets can be regarded as jigsaw that can be clipped together to form a network.

The point where the pieces clip together is called the router

The aim of the algorithm is to find the shortest path to each subnet, so we need to assign a length value to every link

In OSPF, the length of a link is referred to as the cost, the application of the Djikstra Algorithm to OSPF actually finds the least-cost paths.

Link costs are related to link bandwidth, We have actually assigned some arbitrary costs to the link from the routers to the subnets

Turning the network into a tree

Every router can treat the network as a tree, with the router itself as the root.

So, let us build up the tree with R2 as the root

This means we are re-arranging the subnets according to Djikstra's rules.

From the root, branches have added a subnet at a time, starting with the subnets directly connected to R2.

The subnet with the least cost pth is chosen at every step, Sticking to this rule results in a tree of least cost paths.

If a subnet is already connected to the tree,but a less-cost connection point becomes available (R1),move it to the less cost point

The Route R2 to S5 has cost of :1+10+1=12

The ROute R2 to S1 has a cost of :1+10+10+10=31

SO that’s how this Protocol is used!!

--

--

--

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

Recommended from Medium

Handlebars for Beginners

What People Get Wrong About DevOps

The Failed AoG Story ….

Adventures of building a Sitecore automated CI/CD pipeline with Kubernetes and Azure DevOps — Part…

Enforce your policies as code on Kubernetes using GateKeeper(OPA)

How To Set Up DynamoDB Locally

Baremetal Rust for Beaglebone Black: Interrupts

In-House Development vs. Outsourcing. Making the right choice

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
Jaindivya

Jaindivya

More from Medium

Upgrade SSD for Windows 10 machine

CS373 Spring 2022: Ramón Márquez, Week 2

CS373 Spring 2022: Joann Feng

Dockerfile Implementations.