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