How OSPF protocol implements Dijkstra Algorithm ..

In this article we will see the Dijkstra Algorithm & how OSPF routing protocol uses it behind the scene.

Introduction to Dijkstra’s Algorithm

Purpose and Use Cases

With Dijkstra’s Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the “source node”) to all other nodes in the graph, producing a shortest-path tree. This algorithm is used in GPS devices to find the shortest path between the current location and the destination. It has broad applications in industry, specially in domains that require modeling networks.

History

This algorithm was created and published by Dr. Edsger W. Dijkstra, a brilliant Dutch computer scientist and software engineer. In 1959, he published a 3-page article titled “A note on two problems in connexion with graphs” where he explained his new algorithm.

Dr. Edsger Dijkstra at ETH Zurich in 1994 (image by Andreas F. Borchert)

During an interview in 2001, Dr. Dijkstra revealed how and why he designed the algorithm:

What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. — As quoted in the article Edsger W. Dijkstra from An interview with Edsger W. Dijkstra.

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

Dijkstra’s Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path.

If there is a negative weight in the graph, then the algorithm will not work properly. Once a node has been marked as “visited”, the current path to that node is marked as the shortest path to reach that node. And negative weights can alter this if the total weight can be decremented after this step has occurred.

🔹 Example of Dijkstra’s Algorithm

Now that you know more about this algorithm, let’s see how it works behind the scenes with a a step-by-step example. We have this graph:

The algorithm will generate the shortest path from node 0 to all the other nodes in the graph.

💡 Tip: For this graph, we will assume that the weight of the edges represents the distance between two nodes.

We will have the shortest path from node 0 to node 1, from node 0 to node 2, from node 0 to node 3, and so on for every node in the graph.

Initially, we have this list of distances :

• The distance from the source node to itself is 0. For this example, the source node will be node 0 but it can be any node that you choose.
• The distance from the source node to all other nodes has not been determined yet, so we use the infinity symbol to represent this initially.

We also have this list (see below) to keep track of the nodes that have not been visited yet (nodes that have not been included in the path):

💡 Tip: Remember that the algorithm is completed once all nodes have been added to the path.

Since we are choosing to start at node 0, we can mark this node as visited. Equivalently, we cross it off from the list of unvisited nodes and add a red border to the corresponding node in diagram:

Now we need to start checking the distance from node 0 to its adjacent nodes. As you can see, these are nodes 1 and 2 (see the red edges):

💡 Tip: This doesn’t mean that we are immediately adding the two adjacent nodes to the shortest path. Before adding a node to this path, we need to check if we have found the shortest path to reach it. We are simply making an initial examination process to see the options available.

We need to update the distances from node 0 to node 1 and node 2 with the weights of the edges that connect them to node 0 (the source node). These weights are 2 and 6, respectively:

After updating the distances of the adjacent nodes, we need to:

• Select the node that is closest to the source node based on the current known distances.
• Mark it as visited.
• Add it to the path.

If we check the list of distances, we can see that node 1 has the shortest distance to the source node (a distance of 2), so we add it to the path.

In the diagram, we can represent this with a red edge:

We mark it with a red square in the list to represent that it has been “visited” and that we have found the shortest path to this node:

We cross it off from the list of unvisited nodes:

Now we need to analyze the new adjacent nodes to find the shortest path to reach them. We will only analyze the nodes that are adjacent to the nodes that are already part of the shortest path (the path marked with red edges).

Node 3 and node 2 are both adjacent to nodes that are already in the path because they are directly connected to node 0 and node 1, respectively, as you can see below. These are the nodes that we will analyze in the next step.

Since we already have the distance from the source node to node 2 written down in our list, we don't need to update the distance this time. We only need to update the distance from the source node to the new adjacent node (node 3):

This distance is 7. Let’s see why.

To find the distance from the source node to another node (in this case, node 3), we add the weights of all the edges that form the shortest path to reach that node:

• For node 3: the total distance is 7 because we add the weights of the edges that form the path 0 -> 1 -> 3 (2 for the edge 0 -> 1 and 5 for the edge 1 -> 3).

Now that we have the distance to the adjacent nodes, we have to choose which node will be added to the path. We must select the unvisited node with the shortest (currently known) distance to the source node.

From the list of distances, we can immediately detect that this is node 2 with distance 6:

We add it to the path graphically with a red border around the node and a red edge:

We also mark it as visited by adding a small red square in the list of distances and crossing it off from the list of unvisited nodes:

Now we need to repeat the process to find the shortest path from the source node to the new adjacent node, which is node 3.

You can see that we have two possible paths 0 -> 1 -> 3 or 0 -> 2 -> 3. Let's see how we can decide which one is the shortest path.

Node 3 already has a distance in the list that was recorded previously (7, see the list below). This distance was the result of a previous step, where we added the weights 5 and 2 of the two edges that we needed to cross to follow the path 0 -> 1 -> 3.

But now we have another alternative. If we choose to follow the path 0 -> 2 -> 3, we would need to follow two edges 0 -> 2 and 2 -> 3 with weights 6 and 8, respectively, which represents a total distance of 14.

Clearly, the first (existing) distance is shorter (7 vs. 14), so we will choose to keep the original path 0 -> 1 -> 3. We only update the distance if the new path is shorter.

Therefore, we add this node to the path using the first alternative: 0 -> 1 -> 3.

We mark this node as visited and cross it off from the list of unvisited nodes:

Now we repeat the process again.

We need to check the new adjacent nodes that we have not visited so far. This time, these nodes are node 4 and node 5 since they are adjacent to node 3.

We update the distances of these nodes to the source node, always trying to find a shorter path, if possible:

• For node 4: the distance is 17 from the path 0 -> 1 -> 3 -> 4.
• For node 5: the distance is 22 from the path 0 -> 1 -> 3 -> 5.

💡 Tip: Notice that we can only consider extending the shortest path (marked in red). We cannot consider paths that will take us through edges that have not been added to the shortest path (for example, we cannot form a path that goes through the edge 2 -> 3).

We also mark it as “visited” by adding a small red square in the list:

And we cross it off from the list of unvisited nodes:

And we repeat the process again. We check the adjacent nodes: node 5 and node 6. We need to analyze each possible path that we can follow to reach them from nodes that have already been marked as visited and added to the path.

For node 5:

• The first option is to follow the path 0 -> 1 -> 3 -> 5, which has a distance of 22 from the source node (2 + 5 + 15). This distance was already recorded in the list of distances in a previous step.
• The second option would be to follow the path 0 -> 1 -> 3 -> 4 -> 5, which has a distance of 23 from the source node (2 + 5 + 10 + 6).

Clearly, the first path is shorter, so we choose it for node 5.

For node 6:

• The path available is 0 -> 1 -> 3 -> 4 -> 6, which has a distance of 19 from the source node (2 + 5 + 10 + 2).

We mark the node with the shortest (currently known) distance as visited. In this case, node 6.

And we cross it off from the list of unvisited nodes:

Now we have this path (marked in red):

Only one node has not been visited yet, node 5. Let's see how we can include it in the path.

There are three different paths that we can take to reach node 5 from the nodes that have been added to the path:

• Option 1: 0 -> 1 -> 3 -> 5 with a distance of 22 (2 + 5 + 15).
• Option 2: 0 -> 1 -> 3 -> 4 -> 5 with a distance of 23 (2 + 5 + 10 + 6).
• Option 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 with a distance of 25 (2 + 5 + 10 + 2 + 6).

We select the shortest path: 0 -> 1 -> 3 -> 5 with a distance of 22.

We mark the node as visited and cross it off from the list of unvisited nodes:

And voilà! We have the final result with the shortest path from node 0 to each node in the graph.

In the diagram, the red lines mark the edges that belong to the shortest path. You need to follow these edges to follow the shortest path to reach a given node in the graph starting from node 0.

For example, if you want to reach node 6 starting from node 0, you just need to follow the red edges and you will be following the shortest path 0 -> 1 -> 3 -> 4 - > 6 automatically.

So That’s how Dijkstra Algorithm works .. now let’s see about OSPF & how it implements this algorithm behind the scene.

What’s OSPF ?

OSPF (Open Shortest Path First) is a link state routing protocol. Because it is an open standard, it is implemented by a variety of network vendors. OSPF will run on most routers that doesn’t necessarily have to be Cisco routers (unlike EIGRP which can be run only on Cisco routers).

Here are the most important features of OSPF:

• a classless routing protocol
• supports VLSM, CIDR, manual route summarization, equal cost load balancing
• incremental updates are supported
• uses only one parameter as the metric — the interface cost.
• the administrative distance of OSPF routes is, by default, 110.
• uses multicast addresses 224.0.0.5 and 224.0.0.6 for routing updates.

OSPF terms

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.

1. Router priority — It is a 8 bit value assigned to a router operating OSPF, used to elect DR and BDR in a broadcast network.
2. 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.
3. Backup Designated Router (BDR) — BDR is backup to DR in a broadcast network. When DR goes down, BDR becomes DR and performs its functions.

OSPF states — The device operating OSPF goes through certain states. These states are:

1. Down — In this state, no hello packet have been received on the interface.
   Note — The Down state doesn’t mean that the interface is physically down. Here, it means that OSPF adjacency process has not started yet.
2. INIT — In this state, hello packet have been received from the other router.
3. 2WAY — In the 2WAY state, both the routers have received the hello packets from other routers. Bidirectional connectivity has been established.
   Note — In between the 2WAY state and Exstart state, the DR and BDR election takes place.
4. Exstart — In this state, NULL DBD are exchanged.In this state, master and slave election take place. The router having the higher router I’d becomes the master while other becomes the slave. This election decides Which router will send it’s DBD first (routers who have formed neighbourship will take part in this election).
5. Exchange — In this state, the actual DBDs are exchanged.
6. Loading — In this sate, LSR, LSU and LSA (Link State Acknowledgement) are exchanged.
   Important — When a router receives DBD from other router, it compares it’s own DBD with the other router DBD. If the received DBD is more updated than its own DBD then the router will send LSR to the other router stating what links are needed. The other router replies with the LSU containing the updates that are needed. In return to this, the router replies with the Link State Acknowledgement.
7. Full — In this state, synchronization of all the information takes place. OSPF routing can begin only after the Full state.

Each OSPF router stores routing and topology information in three tables:

1. Neighbor table : stores information about OSPF neighbors
2. Topology table : stores the topology structure of a network
3. Routing table : stores the best routes

OSPF divides the autonomous systems into areas where the area is a collection of networks, hosts, and routers. Like internet service providers divide the internet into a different autonomous system for easy management and OSPF further divides the autonomous systems into Areas. Routers that exist inside the area flood the area with routing information

In Area, the special router also exists. The special routers are those that are present at the border of an area, and these special routers are known as Area Border Routers. This router summarizes the information about an area and shares the information with other areas.

All the areas inside an autonomous system are connected to the backbone routers, and these backbone routers are part of a primary area. The role of a primary area is to provide communication between different areas.

How does OSPF work?

There are three steps that can explain the working of OSPF:

Step 1: The first step is to become OSPF neighbors. The two connecting routers running OSPF on the same link creates a neighbor relationship.

Step 2: The second step is to exchange database information. After becoming the neighbors, the two routers exchange the LSDB information with each other.

Step 3: The third step is to choose the best route. Once the LSDB information has been exchanged with each other, the router chooses the best route to be added to a routing table based on the calculation of SPF.

Shortest Path First Algorithm

OSPF uses a shorted path first algorithm in order 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 by means of 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 the database of each router is completed, the router calculates a Shortest Path Tree to all destinations. The router uses the Dijkstra algorithm in order 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 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 in order to find the shortest path.
5. 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. There is more overhead (higher cost) and time delays involved in 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.

Read more about the architecture & design ..

That’s all guys, we have seen how Open Shortest Path First implementing the Dijkstra algorithm internally. Hope it will be helpful for you guys. Thank You.

Have a wonderful read ..