OSPF SPF.

OSPF is all about finding the shortest path. To find this shortest path, OSPF routers run the Shortest-Path-First (SPF) algorithm. This SPF algorithm is based on the Dijkstra algorithm. The purpose of running the SPF algorithm is to find the shortest path to all the prefixes in the LSDB.

The SPF algorithm is run against the OSPF routing information on the router. During an SPF run, OSPF uses the following three databases;
    • LSDB: all per-area routing information that an OSPF router has is stored in a LSDB.
    • Candidate database: during an SPF run, this database is filled with links from the LSDB.
    • Tree database: the lowest-cost links from the candidate database are put in the tree database.

In short, at the end of the SPF algorithm, the tree database is a complete network map with the best routes. These routes are passed from the tree database to the routing engine. The routing engine can then determine which of these OSPF routes can be used.

The following picture is an attempt to provide an overview of this SPF process:



scenario


An OSPF router has an LSDB for every area it is connected to. Consequently, an OSPF router is running SPF for every individual area. In the picture, R1 has an LSDB that contains all OSPF routing information for area 1. This LSDB consists of tuples. The tuples are a combination of the router ID originating the LSA, the router ID to where the link goes to and an associated link-cost.

During an SPF run, these tuples are placed into the candidate database. This database will be used by the OSPF router to build a tree of the area's topology. The tree is build by taking only the best routes from the candidate database and placing them into the tree database.

When the OSPF router is finished constructing the entire tree, the result is handed over to the routing engine. These routes may or may not be used in the routing table. The routing engine can have different reasons for not installing the route that is the best OSPF route. For instance, the best OSPF route might not get installed because there is a static route with a lower preference present as well.

10-10-2014.