Shortest Path First
The SPF algorithm creates a shortest-path tree for all hosts in an area or in the network backbone, with the router that is performing the calculation at the root of that tree. In order for the SPF algorithm to work correctly, all routers in the area should have the same database information. We cover OSPF in great detail in our Cisco CCNP courses, such as the ENARSI course. In OSPF, this is performed via the database exchange process, which will be described in other blog posts. The SPF calculation is performed in iterations using three sets, as follows:
- Tentative (TENT)
When the SPF algorithm initializes, all nodes, except for the root, which is also referred to as ‘self,’ is placed in the Unknown set or list. The root is the router performing the SPF calculation. As SPF continues to run, nodes in the Unknown set are moved to the Tentative set, beginning with the nodes directly connected to the root. The Tentative set is also commonly referred to simply as the TENT set or list.
As the router goes through the SPF calculation, the node in the TENT set or list that is closest to the root is moved to the PATH or PATHS list or set. This process is repeated until all nodes are in the PATH set and the shortest-path tree is built. Once the tree has been completely built, routes are then derived from the tree. This concept is illustrated by referencing the basic network topology in Figure 1 below:
Fig. 1. Shortest Path First Algorithm
Referencing Figure 1, it is assumed that R1 is the router performing the SPF calculation. The following are the sequence of steps taken by this router:
- R1 places itself in the PATH list with a next-hop of itself and a cost of 0. When R1 places itself in the PATH list, R1 is also referred to as the PATH node, in addition to being the SPF root. All other nodes or routers are temporarily placed in the Unknown set and have their cost presently set to infinity.
- R1 examines the neighbors of the PATH node (itself), and because its only neighbor is R2, R1 adds R2 to the TENT list. Open Shortest Path First is able to do so by looking at the Link State Advertisement (LSA) packets that are exchanged during the database exchange and the synchronization process.
- R1 calculates the cost to R2 from the PATH node. This is performed by adding the cost to the PATH node and the cost from the PATH node to the TENT node. In this example, the cost from R1 to the PATH node (itself) is 0, and the cost from the PATH node (R1) to the TENT node (R2) is 10. The total path cost to reach R2 from R1 is 0 + 10 = 10.
- Because the cost of 10 is less than the cost of infinity that was initially assigned, the infinity value is overwritten with the cost value of 10. R2 is then moved to the PATH list.
- Once R2 is placed in the PATH list, it becomes the newest PATH node and the second SPF iteration begins on R1. Remember, SPF stops when all nodes are in the PATH set.
- R1 examines the neighbors of the new PATH node (R2), which are R3 and itself. Because R1 is already added to the PATH list (in step 1) it is ignored. R3, however, is moved from the Unknown set to the TENT set.
- R1 calculates the cost to R3 by adding the cost to the PATH node (R2) and the cost from the PATH node (R2) to the TENT node (R3). The cost from R1 to the PATH node (R2) is 10, and the cost from the PATH node to the TENT node (R2) is 10. The total path cost to reach R3 from R1 is 10 + 10 = 20.
- Because the cost of 20 is less than the cost of infinity that was initially assigned, the infinity value is overwritten with the cost value of 20. R3 is then moved to the PATH list.
This process is repeated until there are no more routers in the TENT list on any of the routers participating in OSPF. Figure 2 below shows the SPF tree as it would appear on routers R1 and R2:
Fig. 2. SPF Tree on R1 and R2
Referencing the diagram in Figure 2, notice that the tree is built on the perspective of the root, which is the local router itself. Figure 3 below shows the SPF tree as it would appear on R3 and R4:
Fig. 3. SPF Tree on R3 and R4