OSPF (Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm

OSPF (Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm

Let’s understand this by understanding the core first.

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.

In brief, the RIP protocol works as follows.

  • 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.
  • The maximum metric permitted by RIP is 16, which means that a route is unreachable. This means that the protocol cannot scale to networks where there may be more than 15 hops to a given destination

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.

The main advantage of a link-state routing protocol like OSPF is that the complete knowledge of topology allows routers to calculate routes that satisfy particular criteria. This can be useful for traffic engineering purposes, where routes can be constrained to meet the particular quality of service requirements.

OSPF Packet Format

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 Algorithm

Dijkstra’s algorithm is one of the types of Greedy Algorithms that enables us to find the shortest path between any two nodes in a graph (i.e, shortest path from the source node to destination node passing from the points in between in the aim to produce a shortest-path tree.

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 as it can alter the total weight. It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.

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.

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, especially in domains that require modeling 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.

Thank you for the read.