The Link-State Algorithm
After starting, a router generates its link-state advertisements representing all the states on that router. Routers then exchange these link-states by flooding. When a router receives a link-state update, it stores it in its link-state database and then propagates the update to other routers. When the database is complete, the router uses Dijkstra’s Algorithm to calculate the shortest path tree through the network.
After this, OSPF will propagate topology changes but otherwise is a very quiet protocol.
Dijkstra published his algorithm in 1959 as a solution for finding optimal routes between 64 cities in the Netherlands.
We start from a node and call it the current node.
All the other nodes which have not been evaluated are called unvisited and are part of the unvisited set.
We list all the unvisited nodes as having an infinite cost to reach
From the current node, we calculate a tentative distance to all other neighbouring nodes.
When a newly calculated distance is less than the previously assigned distance, this is stored in the link-state database.
When all the neighbours of a node have been considered, the node has been visited, is removed from the unvisited set and is not further processed.
If no nodes remain to be processed, the algorithm is finished. If not, pick the unvisited node with the smallest tentative distance, make it the current node and loop to step 4.
Last updated