OSPF (Open Short Path First)

Routing Protocol implemented using Dijkastra Algorithm

Open Shortest Path First (OSPF) protocol States

Open Shortest Path First (OSPF) is a link-state routing protocol that is used to find the best path between the source and the destination router using its own Shortest Path First). OSPF is developed by Internet Engineering Task Force (IETF) as one of the Interior Gateway Protocol (IGP), i.e, the protocol which aims at moving the packet within a large autonomous system or routing domain. It is a network layer protocol which works on the protocol number 89 and uses AD value 110. OSPF uses multicast address 224.0.0.5 for normal communication and 224.0.0.6 for update to designated router(DR)/Backup Designated Router (BDR).

OSPF terms –

  1. Router I’d — It is the highest active IP address present on the router. First, highest loopback address is considered. If no loopback is configured then the highest active IP address on the interface of the router is considered.
  2. Router priority — It is a 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 elected to minimize the number of adjacency formed. DR distributes the LSAs to all the other routers. DR is elected in a broadcast network to which all the other routers shares their DBD. In a broadcast network, router requests for an update to DR and DR will respond to that request with an update.
  4. Backup Designated Router (BDR) — BDR is backup to DR in a broadcast network. When DR goes down, BDR becomes DR and performs its functions.

DR and BDR election — DR and BDR election takes place in broadcast network or multi-access network. Here are the criteria for the election:

  1. Router having the highest router priority will be declared as DR.
  2. If there is a tie in router priority then highest router I’d will be considered. First, the highest loopback address is considered. If no loopback is configured then the highest active IP address on the interface of the router is considered.

OSPF is link state. That really means to me one thing. That means it runs Dijkstra’s Shortest Path First (SPF) Algorithm; that is something that is common to all link state routing protocols. They do tend to be more scalable, although EIGRP is tremendously scalable. One thing that does separate them from all the other dynamic routing protocols is, they have a full picture of the topology inside of their own area and they have a pretty good set of details regarding networks outside of their area, but not the same level, okay. Dijkstra’s algorithm really helps us get around our own area.

OSPF Data Overview

This is going to be a review for you, but I want you to understand where Open Shortest Path First, or OSPF, lives in the world of dynamic routing protocols. There’s Routing Information Protocol, or RIP, which is distance vector, there’s Enhanced Interior Gateway Routing Protocol, or EIGRP, which is balanced hybrid or advanced distance vector, whatever you want to say there. OSPF is link state. That really means to me one thing. That means it runs Dijkstra’s Shortest Path First (SPF) Algorithm; that is something that is common to all link state routing protocols. They do tend to be more scalable, although EIGRP is tremendously scalable. One thing that does separate them from all the other dynamic routing protocols is, they have a full picture of the topology inside of their own area and they have a pretty good set of details regarding networks outside of their area, but not the same level, okay. Dijkstra’s algorithm really helps us get around our own area. When we do have changes we just compartmentalized a small, little change, that is a link-state advertisement.

Link-State Routing Protocol

A link-state advertisement is a piece of information, which can be contained within what is called a link-state update and we send these around the topology. We listen to these as well when we get them, we update our own routing table based on first-hand information. And we get a lot of details, things like router ID, who generated this update, the sequence number to make sure that this is new information and not stale information. But still let’s not lose sight of the fact that we’re still just trying to understand all of the different subnets in our autonomous system and figure out the best way to get there.

Dijkstra’s Algorithm

So, so far we’ve seen things that are really common to EIGRP as well neighbor table in EIGRP; a topology table in EIGRP. But do you remember EIGRP’s algorithm? It was DUAL. Here we’re talking about OSPF; OSPF has a different set of gears that are going to churn on that data called the Shortest Path First Algorithm, named by the gentleman who invented it, Dijkstra. And this SPF Algorithm is going to go destination by destination; here is the way to visualize it, not like you need to program this. You place yourself at the root of the tree. You find yourself basically in the topology database. Router does that and then it has a list of all the destination networks that it knows about. How do we know that? The topology table can easily be read to list off all of the networks and then one-by-one Dijkstra’s algorithm calculates the best path to each of those destinations. So it’s not like we run Dijkstra’s algorithm and it answers all of the best paths. We run it each time we have to get to a unique destination network. And the way that it works is it assigns a cost to the links. And when it gets to a certain point when it says oh, I got something better, I’m going to stop running that calculation because I’ve already established a better pathway to that destination. And so Dijkstra’s algorithm, a complex algorithm, but ultimately it just tells us here’s the best way to go, and then where does that information go inside of our router? Well that path with the shortest metric to get to that destination network ends up in our routing table.

So you can see the relationship we have here. Routing table gets populated based on the answers that Dijkstra’s Shortest Path First Algorithm comes up with based on its calculations.

OSPF Metric

Pop quiz everyone! Can anybody tell us the name of the metric for EIGRP? I’m going to remind you folks of the other types of metrics that are out there. Let’s use that as an opportunity to review. RIPs metric, not like we care about that this much these days, but RIP is hop count. It’s just a number of routers to get there. EIGRP, if you remember EIGRP, bonus points for you. What would you call EIGRP’s metric? Well we could say feasible distance, that’s the composite metric. OSPF’s metric is a ‘cost’. That is the metric and it is derived from this equation: Cost = Reference Bandwidth / Interface Bandwidth, where reference bandwidth is 100 Mb/s. The equation sets up a sort of a fraction. On the top of the fraction, the numerator, if you will, we have the reference bandwidth. And the denominator beneath the slash of that fraction is the interface bandwidth, so this is accumulated. Now it’s interface bandwidth.

So if you wanted to change it to 40,000, that would say 40 Gbps, for reference bandwidth. And some operating systems, in fact give you the way to say, “Instead of measuring in megabits, I want to measure in gigabits because I’m putting in a really big number for you.” Folks, always remember when it comes to OSPF’s metric, when it comes to cost, lower is better and that would be the path that would end up in our routing table.

Thanks for Reading 😃

🔰Keep Learning❗❗🔰Keep Sharing❗❗

--

--

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