Jul 4, 2021
OSPF Protocol implementing Dijkstra’s Algorithm
OSPF is link state. That means it runs Dijkstra’s Shortest Path First (SPF) Algorithm, that is something that is common to all link state routing protocols which makes topology detail regarding network outside their area…
In this blog we will be understanding about Routing Protocols and their Mechanism. Basically in networking world router works on third layer of our OSI model and we get the Static and Dynamic Routing among classless and Classful IP routes. There are many protocols for routing but my special focus will be on OSPF (Open Shortest Path First) routing protocol.
When data move across multiple network, IP routing helps to determine the path of data by setting some protocols to reach the source destination. Ultimately data travels at the physical level through routers IP routing protocols enable routers to setup a forwarding table that correlates final destination with next hop addresses. Let me take you through the internal Routing Mechanism and key terms,
- 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.
RIP (Routing Information Protocol) and OSPF (Open Shortest Path First) Protocol are types of dynamic routing which is a least expressive routing process. It delivers and receives routing messages on routing interface, information shared with other routers, swap routing information with others routes to find data about remote networks.
Comparing difference between Static and Dynamic Routing :
- Static routing is for small networks like small scale organization that has predicted number of users and static or minimum bandwidth usage, laborious tasks are set up. Here the roll of network admin is to troubleshoot manually at each failure hence it becomes a tedious task.
- Dynamic Routing used in case of large networks because of it’s capabilities like it keep changing and updating along with network topologies and are easier to maintain and supports network extension.
- Static Routing table are set by Network Administrator.
- Dynamic Routing Protocols dynamically discover network destinations. Continuously change network status updates between each other as broadcast or multicast-Routing Information Protocol (RIP). Enhanced Interior Gateway Routing Protocol (EIGRP), Open Shortest Path First (OSPF).
There are different types of Distance Protocols:
Vector Routing Protocol : This is simple algorithm to find out cumulative distance value between routers based on hop count. Example: RIP, IGRP.
Link-State Routing Protocol : This uses sophisticated algorithm which maintain a complex database of internetwork topology. Example : OSPF, IS-IS
Hybrid Routing Protocol : This uses combination of distance vector, link-state methods that try to incorporate the advantage of both. Example: EIGRP, RIP2.
OSPF (Open Shortest Path First) is a Link State Protocol and is a most famous protocol among the Interior Gateway Protocol (IGP) family, working group of IETF. When configured OSPF will listen to neighbors and gather all link state data available to build a topology map of all available paths in its network and then save the information in its topology database, also known as it’s LSDB (Link-State Database). OSPF has capability to calculate the best shortest path to each reachable subnet/network using an algorithm called SFP (Shortest Path First) also known as Dijkastra algorithm.
OSPF maintains information in three tables named “Neighbor Table” that contain all discovered OSPF neighbor with whom routing information will be interchanged. “Topology Table” contains the entire road map of the network with all available OSPF routers and calculated best and alternative paths. Lastly the “Routing Table” where the current working best paths will store and it is used to forward the data traffic between neighbors.
OSPF works with multiple areas and these layer area hierarchy is described below :
- Backbone Area : This interconnects all areas together and every area in OSPF must be connected via backbone area. Backbone areas are designed as a CORE area.
- Regular Area : These areas connects users and resource together. Regular areas are grouped based on geographical or functional purposes. One can reach other regular area using backbone area.
Various subtypes are embedded under this Regular area, they are :
- Stub area : Area that doesn’t allow external router to be propagated through. All router within the area must be configured as a stub to maintain neighbor relationship. Instead, external router are propagated by default route by ABR (Area Border Routers).
- Totally Stub area : Area that does not allow external and summary routers instead propagating them as one default route. All router in the area must be configured as stub routers. ABR connected to area must be configured as totally stub.
- Not-so-stubby area : Area that does not allow by default external routers to be propagated through, this rule can be bypass and some external routers can be propagated if necessary.
- Totally not-so-stubby area : This is also same as Not-so-stubby area, but in addition it does not allow summary routers to be propagated through.
🤔 Now the question comes, What is Dijkstra Algorithm? How OSPF uses Dijkstra behind the scene ?
Dijkstra algorithm is for finding the shortest paths between nodes in the graph. For the case of directed weighted graphs we conclude the minimum path by using this particular algorithm. As I have mentioned in above discussion about tables where OSPF stores information. Topology table can easily be read to list of all the network and then one-by-one Dijkstra algorithm calculates the best path to each of those destinations.
One concept of Metric for OSPF that calculates the reference bandwidth talks about the cost of data transfer. This calculation or prediction for the right path changes and updates the metrics and find better path from the initial one we have and after comparing with the topology table. Routing table gets populated based on the answers that Dijkstra’s Shortest Path First Algorithm comes up with based on it’s calculations. But it does not directly calculates the based on information it has in its topology table and we can’t have information in topology table unless we have Regular\Backbone area neighbors. The end result of path is stored inside Routing table so we can have troubleshooting for further path according to cost (bandwidth).
We can understand this via EIGRP and OSPF metrics comparison.
Here, cost = Reference Bandwidth \ Interface Bandwidth.
While researching for the explanation of faster connection in shortest path with Single Source Routing consideration in OSPF. Cisco routers also follows OSPF protocol which uses reference bandwidth metrics and keep on updating the same called as paranoid update.
Conclusion :
👉 Visit the following blog titled “OSPF Data Overview” from learncisco site where they have motioned the OSPF metrics and paranoid update clearly.
Link — Dijkstra’s Shortest Path First (SPF) Algorithm | ICND2 200–105 (learncisco.net)
You may connect me on LinkedIN for more such contents and blogs:
