4.2 Steps to OSPF Operation
4.2.5 Step 4: Choosing routes
After a router has a complete link-state database, it is ready to create its routing table so it can send traffic. Recall that distance vector protocols, such as RIP, select the best route to a destination based on hop count. Distance vector routing protocols use the Bellman-Ford algorithm to determine the routes with the lowest hop count. The Bellman-Ford algorithm defines the process by which routers keep routing information to ensure the least-cost path, based on hop count.

Link-state protocols, on the other hand, use a cost metric to determine the best path to a destination. The default cost metric is based on media bandwidth. In general, cost decreases as the speed of the link increases. 10-Mbps Ethernet, for example, has a lower cost than a 56-kbps line because 10 Mbps is faster than 56 kbps.

To calculate the lowest cost to a destination, link-state protocols such as OSPF use the Dijkstra algorithm. In simple terms, the algorithm adds up the total costs between the local router (called the root) and each destination network. If there are multiple paths to a destination, the lowest-cost path is preferred. But note that OSPF keeps up to six equal-cost route entries in the routing table for load balancing.

The Dijkstra algorithm (named after its creator, Edsgar Dijkstra) requires the entire network picture to be placed in a "tree" design, with the local router appearing as the root. Touring loops are broken during this process (also known as the spanning tree protocol). The Dijkstra algorithm simply "walks" the tree from the root (local router) to the distant branches (remote networks), adding the costs associated with traversing each link. Paths are compared to ensure that least-cost paths are considered more favorable. Refer to the OSPF version 2 RFC for a detailed description of the Dijkstra algorithm. In the figure for example, router A uses this algorithm to select the lowest-cost route to network 3.3.3.0.

Sometimes a link, such as a serial line, will go up and down rapidly (called flapping), or a link-state change may affect another series of links. In these situations, a series of LSUs could be generated, which would cause routers to recompute a new routing table repeatedly. This flapping could be so severe that the routers link-state databases would never converge. To minimize this problem, each time an LSU is received, the router waits for a period of time (a holdtime) before recalculating its routing table. The spf holdtime command was added to the Cisco IOS software to prevent routers from computing a new routing table until 10 seconds (default) after a route change.