How is Open Short Path First Routing Protocol implemented?

The OSPF (Open Shortest Path First) protocol is one of a family of IP Routing protocols, and is an Interior Gateway Protocol (IGP) for the Internet, used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.

The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the 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 particular quality of service requirements. The main disadvantage of a link state routing protocol is that it does not scale well as more routers are added to the routing domain. Increasing the number of routers increases the size and frequency of the topology updates, and also the length of time it takes to calculate end-to-end routes. This lack of scalability means that a link state routing protocol is unsuitable for routing across the Internet at large, which is the reason why IGPs only route traffic within a single AS.

Each OSPF router distributes information about its local state (usable interfaces and reachable neighbors, and the cost of using each interface) to other routers using a Link State Advertisement (LSA) message. Each router uses the received messages to build up an identical database that describes the topology of the AS.

From this database, each router calculates its own routing table using a Shortest Path First (SPF) or Dijkstra algorithm. This routing table contains all the destinations the routing protocol knows about, associated with a next hop IP address and outgoing interface.

• The protocol recalculates routes when network topology changes, using the Dijkstra algorithm, and minimises the routing protocol traffic that it generates.
• It provides support for multiple paths of equal cost.
• It provides a multi-level hierarchy (two-level for OSPF) called “area routing,” so that information about the topology within a defined area of the AS is hidden from routers outside this area. This enables an additional level of routing protection and a reduction in routing protocol traffic.
• All protocol exchanges can be authenticated so that only trusted routers can join in the routing exchanges for the AS

=> Before we proceed further, let’s familiarize ourselves with some important terms −

• Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
• Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represent edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2, and so on, keeping other combinations as 0.
• Adjacency − Two nodes or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
• Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.

Dijkstra’s algorithm

The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. A widely used application of shortest path algorithm is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and Open Shortest Path First (OSPF). It is also employed as a subroutine in other algorithms such as Johnson’s.

The Dijkstra algorithm uses labels that are positive integers or real numbers, which are totally ordered. It can be generalized to use any labels that are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. This generalization is called the generic Dijkstra shortest-path algorithm.

Algorithm

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

1. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
2. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.[15]
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
4. When we are done considering all of the unvisited neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new “current node”, and go back to step 3.

When planning a route, it is actually not necessary to wait until the destination node is “visited” as above: the algorithm can stop once the destination node has the smallest tentative distance among all “unvisited” nodes (and thus could be selected as the next “current”).

Using Dijkstra’s Algorithm, find the shortest distance from source vertex ‘S’ to remaining vertices in the following graph-

Also, write the order in which the vertices are visited.

Solution-

Step-01:

The following two sets are created-

• Unvisited set : {S , a , b , c , d , e}
• Visited set : { }

Step-02:

The two variables Π and d are created for each vertex and initialized as-

• Π[S] = Π[a] = Π[b] = Π[c] = Π[d] = Π[e] = NIL
• d[S] = 0
• d[a] = d[b] = d[c] = d[d] = d[e] = ∞

Step-03:

• Vertex ‘S’ is chosen.
• This is because shortest path estimate for vertex ‘S’ is least.
• The outgoing edges of vertex ‘S’ are relaxed.

Before Edge Relaxation-

Now,

• d[S] + 1 = 0 + 1 = 1 < ∞

∴ d[a] = 1 and Π[a] = S

• d[S] + 5 = 0 + 5 = 5 < ∞

∴ d[b] = 5 and Π[b] = S

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

• Unvisited set : {a , b , c , d , e}
• Visited set : {S}

Step-04:

• Vertex ‘a’ is chosen.
• This is because shortest path estimate for vertex ‘a’ is least.
• The outgoing edges of vertex ‘a’ are relaxed.

Before Edge Relaxation-

Now,

• d[a] + 2 = 1 + 2 = 3 < ∞

∴ d[c] = 3 and Π[c] = a

• d[a] + 1 = 1 + 1 = 2 < ∞

∴ d[d] = 2 and Π[d] = a

• d[b] + 2 = 1 + 2 = 3 < 5

∴ d[b] = 3 and Π[b] = a

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

• Unvisited set : {b , c , d , e}
• Visited set : {S , a}

Step-05:

• Vertex ‘d’ is chosen.
• This is because shortest path estimate for vertex ‘d’ is least.
• The outgoing edges of vertex ‘d’ are relaxed.

Before Edge Relaxation-

Now,

• d[d] + 2 = 2 + 2 = 4 < ∞

∴ d[e] = 4 and Π[e] = d

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

• Unvisited set : {b , c , e}
• Visited set : {S , a , d}

Step-06:

• Vertex ‘b’ is chosen.
• This is because shortest path estimate for vertex ‘b’ is least.
• Vertex ‘c’ may also be chosen since for both the vertices, shortest path estimate is least.
• The outgoing edges of vertex ‘b’ are relaxed.

Before Edge Relaxation-

Now,

• d[b] + 2 = 3 + 2 = 5 > 2

∴ No change

After edge relaxation, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

• Unvisited set : {c , e}
• Visited set : {S , a , d , b}

Step-07:

• Vertex ‘c’ is chosen.
• This is because shortest path estimate for vertex ‘c’ is least.
• The outgoing edges of vertex ‘c’ are relaxed.

Before Edge Relaxation-

Now,

• d[c] + 1 = 3 + 1 = 4 = 4

∴ No change

After edge relaxation, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

• Unvisited set : {e}
• Visited set : {S , a , d , b , c}

Step-08:

• Vertex ‘e’ is chosen.
• This is because shortest path estimate for vertex ‘e’ is least.
• The outgoing edges of vertex ‘e’ are relaxed.
• There are no outgoing edges for vertex ‘e’.
• So, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

• Unvisited set : { }
• Visited set : {S , a , d , b , c , e}

Now,

• All vertices of the graph are processed.
• Our final shortest path tree is as shown below.
• It represents the shortest path from source vertex ‘S’ to all other remaining vertices.

The order in which all the vertices are processed is :

S , a , d , b , c , e.

=>Drawback of this algorithm is that it can only work on positive weighted data.

Thankyou : )