Applying Dijkstra SPF Math to Find the Best Routes

The link-state flooding process results in every router having an identical copy of the LSDB in memory, but the flooding process alone does not cause a router to learn what routes to add to the IP routing table.  The information in the LSDB does not explicitly state each router’s best route to reach a destination.  Link-state protocols must use another major part of the link-state algorithm to find and add routes to the IP routing table – routes that list a subnet number and mask, an outgoing interface, and a next-hop router IP address.  This process uses something called the Dijkstra Shortest Path First (SPF) algorithm.

The LSDB holds all the information about all the possible routers and links.  The SPF algorithm defines how a router should process the LSDB, with each router considering itself to be the starting point for the route.  Each router uses itself as the starting point because each router needs to put routes in its own routing table.  The SPF algorithm calculates all the possible routes to reach a subnet, and the cumulative metric for each entire route, for each possible destination subnet.  Each router must view itself as the starting point, and each subnet as the destination, and use the SPF algorithm to look at the LSDB road map to find and pick the best route to each subnet.

Generally, each router runs the SPF process to find all routes to each subnet, and then the SPF algorithm can pick the best route.  To pick the best route, a router’s SPF algorithm adds the cost associated with each link between itself and the destination subnet, over each possible route.