How Open Shortest Path First (OSPF) uses Dijkstra's Algorithm for finding Shortest?Routing?

In this article, we will be understanding Routing Protocols and their background Working. There are many protocols for routing but my special focus will be on OSPF (Open Shortest Path First) routing protocol.

What is Dynamic Routing?

• Dynamic Routing is a network routing procedure that facilitates the routers to pick and choose the routing paths depending on the network structure’s logical changes in real-time. This is opposite to the typical traditional static network routing. This is an automated routing technique that requires very little administration and supervision. Various protocols used in this routing method are Open Shortest Path First (OSPF), Routing Information Protocol (RIP), Border Gateway Protocol (BGP), and Enhanced Interior Gateway Routing Protocol (EIGRP).

Background Information of OSPF

OSPF protocol was developed due to a need in the internet community to introduce a high functionality non-proprietary Internal Gateway Protocol (IGP) for the TCP/IP protocol family. The discussion of the creation of a common interoperable IGP for the Internet started in 1988 and did not get formalized until 1991. At that time the OSPF Working Group requested that OSPF be considered for advancement to Draft Internet Standard.

The OSPF protocol is based on link-state technology, which is a departure from the Bellman-Ford vector-based algorithms used in traditional Internet routing protocols such as RIP. OSPF has introduced new concepts such as authentication of routing updates, Variable Length Subnet Masks (VLSM), route summarization, and so forth.

Open Shortest Path First Algorithm

OSPF uses a shorted path first algorithm to build and calculate the shortest path to all known destinations. The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high level, simplified way of looking at the various steps of the algorithm:

1. Upon initialization or due to any change in routing information, a router generates a link-state advertisement. This advertisement represents the collection of all link-states on that router.
2. All routers exchange link-states using flooding. Each router that receives a link-state update should store a copy in its link-state database and then propagate the update to other routers.
3. After each router's database is completed, the router calculates a Shortest Path Tree to all destinations. The router uses the Dijkstra algorithm to calculate the shortest path tree. The destinations, the associated cost, and the next hop to reach those destinations form the IP routing table.
4. In case no changes in the OSPF network occur, such as the cost of a link or a network being added or deleted, OSPF should be very quiet. Any changes that occur are communicated through link-state packets, and the Dijkstra algorithm is recalculated to find the shortest path.

The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest-path tree using the same link-state database. The following sections indicate what is involved in building a shortest-path tree.

OSPF Cost

The cost (also called metric) of an interface in OSPF is an indication of the overhead required to send packets across a certain interface. The cost of an interface is inversely proportional to the bandwidth of that interface. A higher bandwidth indicates a lower cost. More overhead (higher cost) and time delays involved crossing a 56k serial line than crossing a 10M ethernet line. The formula used to calculate the cost is:

• cost= 10000 0000/bandwidth in bps

For example, it will cost 10 EXP8/10 EXP7 = 10 to cross a 10M Ethernet line and will cost 10 EXP8/1544000 = 64 to cross a T1 line.

By default, the cost of an interface is calculated based on the bandwidth; you can force the cost of an interface with the IP OSPF cost <value> interface sub configuration mode command.

Shortest Path Tree

Assume we have the following network diagram with the indicated interface costs. In order to build the shortest path tree for RTA, we would have to make RTA the root of the tree and calculate the smallest cost for each destination.

The above is the view of the network as seen from RTA. Note the direction of the arrows in calculating the cost. For example, the cost of RTB’s interface to network 128.213.0.0 is not relevant when calculating the cost to 192.213.11.0. RTA can reach 192.213.11.0 via RTB with a cost of 15 (10+5). RTA can also reach 222.211.10.0 via RTC with a cost of 20 (10+10) or via RTB with a cost of 20 (10+5+5). In case equal-cost paths exist to the same destination, Cisco’s implementation of OSPF will keep track of up to six next hops to the same destination.

After the router builds the shortest path tree, it will start building the routing table accordingly. Directly connected networks will be reached via a metric (cost) of 0 and other networks will be reached according to the cost calculated in the tree.

Working of OSPF

• OSPF is based on a link-state routing algorithm in which each router contains the information of every domain and based on this information it defines the shortest path also known as the Dijkstra algorithm. The OSPF learns about every router and subnet within the entire network. A link-state routing protocol is a protocol that 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
• The way through which OSPF learns about other routers is by sending Link State Advertisement or LSA. This LSA contains information about subnets, routers, and some of the network information. Once all the LSA’s are transferred within the network, OSPF put’s these in a database called LSDB i.e Link State Database. The main goal here is to have each router with the same information in their LSDB’s.
• OSPF maintains information in three tables named “Neighbor Table” that contain all discovered OSPF neighbors 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. The “Routing Table” where the current working best paths will store and are used to forward the data traffic between neighbors.

What is Dijkstra Algorithm? How OSPF uses Dijkstra behind the?scene?

• Dijkstra Algorithm is a very famous greedy algorithm. It is used for solving the single-source shortest path problem. It computes the shortest path from one particular source node to all other remaining nodes of the graph.
• 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.
• The way through which OSPF chooses the best route is by a metric called cost. OSPF cost is the value given to a link based on the bandwidth of that interface.
• Cost = Reference Bandwidth / Interface Bandwidth, where reference bandwidth is 100 Mb/s.

Thanks for reading ?? . Hope you have learned something from this?article!!