Dijkstra Algorithm

Dijkstra Algorithm

1. Start with the local node (router) as the root of the tree.

2. Assign a cost of 0 to this node and make it the first permanent node.

3. Examine each neighbor of the node that was the last permanent node.

4. Assign a cumulative cost to each node and make it tentative.

5. Among the list of tentative nodes :

      a. Find the node with the smallest cost and make it permanent .

      b. If a node can be reached from more than one  route then select the route with the shortest cumulative cost.

6. Repeat steps 3 to 5 until every node becomes permanent.

Calculation of Routing Table from Shortest Path Tree

•       Each node uses the shortest path tree protocol to construct its routing  table.

•       The routing table shows the cost of reaching each node from the  root.

shortest path tree

Formation of shortest path tree

•       Dijkstra algorithm is used  to find out the shortest path tree from the graph of nodes and links.

•       Calculates the shortest path between two points on a network, using a graph made up of nodes and edges.

•        Algorithm divides the nodes into two sets: tentative and permanent.

•        It chooses nodes, makes them tentative, examines them, and if they pass the criteria, makes them permanent.

Flooding of LSP

Flooding of LSP

•       After a node has prepared LSP, it must be scattered to all other nodes, not only to its neighbors. This process is called flooding, and based on   the following:

1. The creating node sends a copy of the LSP out of each interface.

2. A node that receives a LSP compares it with the copy it may already  have.

3. If newly arrived LSP is older, than the one it had, then the new one is discarded.
4. If newly arrived LSP is newer , then:-

      a) Discards the old LSP, and keeps the new one.

      b) Sends a copy of it out of each interface except the one  from    which the packet has arrived. This guarantees that flooding stops somewhere in the domain.

Creation of Link State Packet (LSP)

Creation of Link State Packet  (LSP)

•       LSP needs to carry a lot of information such as node identity, the list of links, a sequence number, and the age.

•        Node identity and  list of links are needed to make the topology.

•       Sequence number facilitates flooding and distinguishes new LSP from  old one.

•       Age prevents old LSP’s from remaining in the domain for a long time.

•       LSP’s are generated on two occasions:-

ü  When there is a change in the topology of the domain: Triggering of  LSP scattering is the main way of quickly informing any node in the domain to update its topology.

On a periodic basis: Period is much longer than Distance Vector   Routing  protocol. It is done to remove old information from the table