Open Short Path First Routing Protocol implemented using Dijkastra Algorithm

How Dijkstra’s Algorithm works

• It 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.

Routing Information Protocol (RIP)

It is one of the oldest distance-vector routing protocols that uses hop count as a routing metric to find the best path between the source and the destination network.

Hop count is the number of routers occurring in between the source and destination network. RIP prevents routing loops by limiting the number of hops allowed in a path from source and destination. In a vector routing protocol, the routers exchange network reachability information with their nearest neighbors.

A vector routing protocol floods reachability information throughout all routers participating in the protocol, so that every router has a routing table containing the complete set of destinations known to the participating routers.

Working of RIP protocol-----

• Each router initializes its routing table with a list of locally connected networks.
• Periodically, each router advertises the entire contents of its routing table over all of its RIP-enabled interfaces.
• Whenever a RIP router receives such an advertisement, it puts all of the appropriate routes into its routing table and begins using it to forward packets. This process ensures that every network connected to every router eventually becomes known to all routers.
• If a router does not continue to receive advertisements for a remote route, it eventually times out that route and stops forwarding packets over it. In other words, RIP is a “soft state” protocol.
• Every route has a property called a metric, which indicates the “distance” to the route’s destination.
• Every time a router receives a route advertisement, it increments the metric.
• Routers prefer shorter routes to longer routes when deciding which of two versions of a route to program in the routing table.

Open Shortest Path First (OSPF)

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. In this, the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the Autonomous System (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.

OSPF terms –

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

Dijkstra’s Algorithm: The Shortest Path Algorithm

What if you are provided with a graph of nodes where every node is linked to several other nodes with varying distance. Now, if you begin from one of the nodes in the graph, what is the shortest path to every other node in the graph? 

Well simply explained, an algorithm that is used for finding the shortest distance, or path, from starting node to target node in a weighted graph is known as Dijkstra’s Algorithm.

This algorithm makes a tree of the shortest path from the starting node, the source, to all other nodes (points) in the graph.

Dijkstra's algorithm makes use of weights of the edges for finding the path that minimizes the total distance (weight) among the source node and all other nodes. This algorithm is also known as the single-source shortest path algorithm.

Duri

Algorithm Execution

Here’s how the algorithm is implemented:

1. Mark all nodes as unvisited.
2. Mark the selected initial node with a current distance of 0 and the rest with infinity.
3. Set the initial node as current node.
4. For the current node, consider all of its unvisited neighbors and calculate their distances by adding the current distance of current node to the weight of the edge connecting neighbor node and current node.
5. Compare the newly calculated distance to the current distance assigned to the neighboring node and set is as the new current distance of neighboring node.
6. When done considering all of the unvisited neighbors of the current node, mark the current node as visited.
7. If the destination node has been marked visited then stop. The algorithm has finished.
8. Otherwise, select the unvisited node that is marked with the smallest distance, set it as the new current node, and go back to step 4.

Uses of Dijkstra’s Algorithm

Dijkstra’s Algorithm has several real-world use cases, including the following:

• Map applications.
• Finding locations of a map referring to vertices of a graph.
• IP routing to find Open Shortest Path First.
• Telephone networks.

Now Let’S look at the implementation of OSPF-

Dijkstra’s algorithm is a graph traversing algorithm. It is responsible for choosing the path on which the sender will send data bits or frames of a message to the receiver. It is the algorithm who is responsible to find the shortest path i.e, with the smallest weight total encountered in the path traversal from source to destination i.e, sender to receiver.

Consider a network structure given below, the figure contains the nodes between A to H. We need to examine the shortest path, between A to Z, where A being the sender and D being the Receiver.

Here A is the source, and Z is the destination; it is an undirected weighted graph. From the graph, we can observe there are multiple paths from A to Z like a -> b ->f ->z, a ->c ->e ->z, and many more.

1. During the first stage, we need to find the shortest node from the neighbor nodes of the source node.

2. During the second stage, it looks for the second shortest path node, which can be a neighbor node of the source node or to the node found in the first stage.

3. During the third stage, the algorithm looks for the third shortest path node from the source node. This node can be the neighbor of the source node or the nearest node found from the first stage or second stage.

4. The process is repeated until all nodes are visited at least once and if all nodes are visited once, then we can find the shortest path from the source node to the destination.

With the help of this procedure, we can find the smallest distance between two routers to send & receive packets.