How is Open Short Path First Routing Protocol implemented?

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

Algorithm

  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.

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

Solution-

Step-01:

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

Step-02:

  • Π[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-

  • d[S] + 1 = 0 + 1 = 1 < ∞
  • d[S] + 5 = 0 + 5 = 5 < ∞
  • 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-

  • d[a] + 2 = 1 + 2 = 3 < ∞
  • d[a] + 1 = 1 + 1 = 2 < ∞
  • d[b] + 2 = 1 + 2 = 3 < 5
  • 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-

  • d[d] + 2 = 2 + 2 = 4 < ∞
  • 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-

  • d[b] + 2 = 3 + 2 = 5 > 2
  • 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-

  • d[c] + 1 = 3 + 1 = 4 = 4
  • 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.
  • Unvisited set : { }
  • Visited set : {S , a , d , b , c , e}
  • 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jayesh Kumar

Jayesh Kumar

Btech ECE pursuing student ....Arth Learner