Dijkshtra's Algorithm in Routing Protocol

Dijkshtra's algorithm

  • The Dijkshtra algorithm creates a shortest path tree from a given graph.
  • The algorithm divides the nodes into two sets.
    • i. Provisional
    ii. Permanent
  • Algorithm finds the neighbors of a current node, enlists them as provisional and if neighbors fulfill the criteria, it is stored permanently.
Dijkastra

Example: The dijkshtra's algorithm can be explained in the following diagrams.

Different steps are:

Step 1: Select root node as 'A'
Step 2: Move 'A' to permanent list and add 'B', 'C' and 'D' to provisional list.
Step 3: Move 'C' and add 'E' to provisional list.
Step 4: Move 'D' to permanent list.
Step 5: Move 'B' to permanent list.
Step 6: Move 'E' to permanent list.

given network topology

dijkastra solution

An OSPF (Open Shortest Path First) protocol is used in the link state algorithm.

The LSP consists of following information:
1. The ID of node, which is created by  LSP.
2. A list of directly connected neighbors of that node, with the cost of the link to each other.
3. Sequence number.
4. Time to live for this packet(TTL).

Some of the well known link state  routing protocols are mentioned below:
  • Open Shortest Path Frist
  • Netware Link Services Protocol (NSLP)
  • Apple's AURP
  • ISO's Intermediate System-Intermediate System (IS-IS)
▲