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

Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks by the interior gateway protocol (IGP) working group of the Internet Engineering Task Force (IETF). The working group was formed in 1988 to design an IGP based on the shortest path first (SPF) algorithm for use in the Internet. Similar to the Interior Gateway Routing Protocol (IGRP), OSPF was created because in the mid-1980s, the Routing Information Protocol (RIP) was increasingly unable to serve large, heterogeneous internetworks.

OSPF is a classless routing protocol, which means that in its updates, it includes the subnet of each route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility.These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).

The diagram below shows us the information that each field of an OSPF packet contains:

All OSPF packets begin with a 24-byte header, which is shown right above. There is however one field I would like to give a bit more attention to, and this is the “Type” field which is 1 byte long.

As illustrated in the diagram, the “Type” field identifies the OSPF packet type as one of the following:

Hello: Establishes and maintains neighbor relationships.
Database Description: Describes the contents of the topological database. These messages are exchanged when an adjacency is initialized.
Link-state Request: Requests pieces of the topological database from neighbor routers. These messages are exchanged after a router discovers (by examining database-description packets) that parts of its topological database are out of date.
Link-state Update: Responds to a link-state request packet. These messages also are used for the regular dispersal of Link-State Acknowledgments (LSA). Several LSAs can be included within a single link-state update packet.
Link-state Acknowledgment: Acknowledges link-state update packets.

OSPF has two primary characteristics:

1) The protocol is open (non proprietary), which means that its specification is in the public domain. The OSPF specification is published as Request For Comments (RFC) 1247.

2) The second principal characteristic is that OSPF is based on the SPF algorithm, which sometimes is referred to as the Dijkstra algorithm, named for the person credited with its creation.

OSPF is a Link State routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use the SPF algorithm to calculate the shortest path to each node.

As a Link State routing protocol, OSPF contrasts with RIP and IGRP, which are Distance Vector routing protocols. Routers running the Distance Vector algorithm send all or a portion of their routing tables in routing-update messages to their neighbors.

Additional OSPF features include equal-cost, multipath routing, and routing based on upper-layer type-of-service (TOS) requests. TOS-based routing supports those upper-layer protocols that can specify particular types of service. An application, for example, might specify that certain data is urgent. If OSPF has high-priority links at its disposal, these can be used to transport the urgent datagram.

OSPF supports one or more metrics. If only one metric is used, it is considered to be arbitrary, and TOS is not supported. If more than one metric is used, TOS is optionally supported through the use of a separate metric (and, therefore, a separate routing table) for each of the eight combinations created by the three IP TOS bits (the delay, throughput, and reliability bits). If, for example, the IP TOS bits specify low delay, low throughput, and high reliability, OSPF calculates routes to all destinations based on this TOS designation.

Dijkstra’s 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.

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.

Working 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.

How to find the shortest path in OSPF using Dijkstra’s Algorithm?

Dijkstra’s algorithm is graph traversing algorithm. In computer network we have sender and receiver, sender will send some frame or message to receiver, but by the time receiver could receive the message, there are many parts which the message can take, that is the job of this algorithm. It will find the shortest path traversed to carry the message from 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 D, where A being the sender and D being the Receiver.

1. During the first stage, we need to find the shortest node from the neighbor nodes of source node.
2. During the second stage, we need to look for second shortest path node, which can be a neighbor node of source node or to the node found in the first stage.
3. During the third stage, the algorithm looks for third shortest path node form the source node. This node can be neighbor of source node or the nearest node found from first stage or second stage.
4. The process repeated, until all nodes are visited at least once and if all nodes are visited once, then we can find the shortest path form the source node to destination.