OSPF Incremental SPF (iSPF) Algorithm: Rebuilding The SPT Tree Fast

OSPF Incremental SPF is a more efficient algorithm than full SPF for calculating the SPF tree whenever there is a change in the network. The algorithm simply uses the saved SPT structure to calculate the shortest paths to the destinations affected by the network topology change, not including OSPF cost modification. This is instead of building an SPF tree for the whole OSPF routing domain from scratch.

Upon the completion of this tutorial, you will be able to answer the following questions:

What is OSPF SPF?
What is full SPF?
What is OSPF incremental SPF?
How does OSPF incremental SPF work?
How to configure the incremental SPF algorithm for OSPF on Cisco IOS?
How to verify OSPF incremental SPF on Cisco IOS?

In this guide, I will be using the following network topology. The routing domain consists of five routers, and it is divided into two areas: 0 and 5. Area 5 includes subnets 10.0.150.0/24 and 10.0.45.0/24, while all other subnets are connected to the backbone area. Finally, we configure OSPF to delay SPF runs by 1 millisecond in order to quickly verify whether or not OSPF executes the SPF algorithm after a particular network topology change.

Here are the initial configurations of the routers.

Router R1	Router R2	Router R3
Router R4	Router R5

Note that OSPF supports other features that enhance network convergence such as OSPF LSA retransmission pacing, OSPF LSA flood pacing, OSPF LSA group pacing, OSPF LSA throttling, and OSPF SPF throttling.

Table of Contents

Toggle

Before digging into OSPF incremental SPF, let’s define network convergence.

Network convergence refers to the process of updating the routing information in a network after a change occurs, such as the addition, modification, or removal of a link or OSPF node. The goal of convergence is to ensure that all OSPF nodes in the network have consistent and up-to-date RIBs so that IP packets can be forwarded to their intended destinations.

Network convergence can take some time, as OSPF nodes in the network need to exchange link state information and update their routing tables to reflect the changes in the network. The time it takes for a network to converge depends on a variety of factors, including the size of the network, the complexity of the routing protocol, and the speed of the links between the routers.

There are several strategies OSPF can use to optimize network convergence, including incremental SPF, OSPF SPF throttling, OSPF LSA throttling, and OSPF LSA group pacing.

What is OSPF SPF in Networking?

OSPF SPF is the algorithm OSPF uses to generate its Routing Information Base (RIB) or routing table of OSPF, a local table where OSPF stores the best routes before Cisco IOS chooses the ones to install in the global routing table.

Not all routes in OSPF’s RIB get installed in the OSPF node’s routing table. OSPF SPF runs per area and uses basically router and network LSAs of the area in order to generate the OSPF area’s shortest path tree that is loop-free and allows OSPF to find the shortest path to each network in the OSPF routing domain.

In addition, OSPF SPF does not use LSAs with an LS age equal to MaxAge. They are simply considered invalid. Here are the major steps of the SPF algorithm:

Step 1. OSPF stores a copy of the old RIB table in order to recognize modifications to the new RIB table entries. OSPF discards all routes currently in the OSPF RIB table, and then it starts building its RIB table from the beginning.

Step 2. OSPF calculates the shortest path to each intra-area destination by constructing a shortest path tree, using router and network LSAs, for each area the router is connected to.

Step 3. OSPF calculates the shortest paths to inter-area networks using all summary-LSAs in the OSPF database. If the router is an area border router, OSPF analyses area 0’s summary-LSAs only.

Step 4. Area border routers, attached to one or more non-backbone OSPF areas whose transit capability field is set to true, use those areas’ summary-LSAs to find optimal paths to the examined destinations in steps 2 and 3.

Step 5. OSPF generates the shortest paths to external destinations based on AS-external-LSAs.

What is OSPF Full SPF?

OSPF full SPF is the default SPF mode OSPF uses to generate the shortest path tree whenever there is a change in a router or network LSA whether it’s effect is minor or big. In this mode, the current OSPF instance calculates the SPT tree from scratch even though it may not be necessary.

By default, OSPF incremental SPF is disabled, as stated in the following show ip ospf command output, meaning full SPF is active.

R1# show ip ospf
 Routing Process "ospf 1" with ID 1.1.1.1
 Start time: 00:04:33.453, Time elapsed: 01:25:55.640
 Supports only single TOS(TOS0) routes
 Supports opaque LSA
 Supports Link-local Signaling (LLS)
 Supports area transit capability
 Supports NSSA (compatible with RFC 3101)
 Supports Database Exchange Summary List Optimization (RFC 5243)
 Event-log enabled, Maximum number of events: 1000, Mode: cyclic
 Router is not originating router-LSAs with maximum metric
 Initial SPF schedule delay 5000 msecs
 Minimum hold time between two consecutive SPFs 10000 msecs
 Maximum wait time between two consecutive SPFs 10000 msecs
 Incremental-SPF disabled





omitted output

The SPF algorithm runs per area, and it is executed in reaction to changes in the router and network LSAs only. OSPF does not run the full SPF algorithm if a network topology event occurs in an area the current router does not belong to.

Moreover, changes in other LSA types do not trigger the SPF algorithm to be executed.

At this point, we set the cost of R5’s loopback0 interface to 100. Basically, router R1 would not execute the SPF algorithm because the change does not correspond to a router/network LSA in its OSPF database.

R1# show ip ospf statistics detail

            OSPF Router with ID (1.1.1.1) (Process ID 1)

  Area 0: SPF algorithm executed 5 times

SPF 1 executed 01:47:39 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  0      3      0      0      0      0      0      3
  LSIDs processed R:1 N:0 Stub:2 SN:0 SA:0 X7:0
  Change record 0x0
  LSIDs changed 2
  Changed LSAs. Recorded is LS ID and LS type:
  1.1.1.1(R) 1.1.1.1(R)


Omitted output
          
SPF 5 executed 01:46:14 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  1      2      0      2      1      0      0      5
  LSIDs processed R:5 N:6 Stub:0 SN:3 SA:0 X7:0
  Change record 0x0
  LSIDs changed 5
  Changed LSAs. Recorded is LS ID and LS type:
  4.4.4.4(R) 5.5.5.5(R) 10.0.25.5(N) 2.2.2.2(R)

The example above is the output of the show ip ospf statistics detail command, which indicates that SPF has been executed 5 times. We issue the following commands on router R5, and then check OSPF stats again.

R5(config)# interface loopback 0
R5(config-if)# ip ospf cost 100

Since the change affects a link that does not belong to one of R1’s areas, OSPF won’t run SPF. In fact, the example below shows that OSPF executed SPF five times, which means it did not run SPF after the last modification we made, as you can notice here.

R1# show ip ospf statistics detail

            OSPF Router with ID (1.1.1.1) (Process ID 1)

  Area 0: SPF algorithm executed 5 times

SPF 1 executed 01:47:39 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  0      3      0      0      0      0      0      3
  LSIDs processed R:1 N:0 Stub:2 SN:0 SA:0 X7:0
  Change record 0x0
  LSIDs changed 2
  Changed LSAs. Recorded is LS ID and LS type:
  1.1.1.1(R) 1.1.1.1(R)


Omitted output
          
SPF 5 executed 01:46:14 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  1      2      0      2      1      0      0      5
  LSIDs processed R:5 N:6 Stub:0 SN:3 SA:0 X7:0
  Change record 0x0
  LSIDs changed 5
  Changed LSAs. Recorded is LS ID and LS type:
  4.4.4.4(R) 5.5.5.5(R) 10.0.25.5(N) 2.2.2.2(R)

When adding or removing links to the network, OSPF runs full SPF, and thus it may consume an unnecessary amount of CPU cycles. To circumvent this issue, you can enable OSPF incremental SPF on all routers in the OSPF routing domain.

What is OSPF Incremental SPF?

Incremental SPF consumes fewer CPU cycles than the full SPF algorithm especially if the change is far away from the root of the SPT, but it does need more memory. When a network event happens in the routing topology, incremental SPF makes OSPF converge faster.

How Does OSPF Incremental SPF Work?

Incremental SPF is a feature of OSPF that can help optimize the CPU utilization of routers by cutting down the amount of SPF (shortest path first) computations. When a change occurs in the network, such as the addition or removal of a link, only the portion of RIB (routing information base) that is affected by the change needs to be recalculated, rather than the entire routing table. This can help reduce the load on the router’s CPU and improve performance.

However, incremental SPF requires some memory space because it has to store the current structure of the SPT in the router’s memory in order to use it for future route optimizations.

Before continuing, here is R1’s SPT for area 0. Note that each router in an OSPF routing domain has its unique SPT. Routers’ SPTs do not have to match each other.

Incremental SPF gets executed in one of the following cases. Otherwise, OSPF runs full SPF instead.

Adding or Removing a Leaf Router or Stub Network

When a router is installed or removed from the network topology, the influence on the existing shortest path tree (SPT) depends on the location of the node within the tree.

If the router serves as a leaf node in the saved SPT, then OSPF performs relatively quick SPF calculations to update the corresponding routes in the RIB table.

For example, we connect router R6 to R3. R6 is connected to R3 via subnet 10.0.36.0/24, and it is linked to subnets 10.0.160.0/24 and 10.0.161.0/24, as you can see in this figure.

In this case, R1 can use distance-vector-like computations to calculate the metrics of the new routes. R1 would add the cost to reach R3 to R3’s cost to subnet 10.0.36.0/24 in order to calculate the path cost to reach R6. In this case, the cost is 2.

R1 would use similar logic to calculate the path cost to subnets 10.0.160.0/24 and 10.0.161.0/24. The metric is equal to the cost to reach R6 plus R6’s cost to reach subnet 10.0.16X.0/24, where X is 0 or 1. Therefore, the metric of the routes corresponding to those two subnets is 3.

If you remove a leaf router from the SPF tree, OSPF may eliminate the corresponding routes from the RIB and routing tables if the corresponding destinations don’t have alternate paths.

When you add or detach a stub network like subnet 10.0.160.0/24 from the SPT, incremental SPF behaves the same way as when you insert or remove a leaf OSPF node.

However, if the node is not a leaf node, more complex calculations may be required to update the routes. In either case, the goal is to update the SPT and routing table to reflect changes in the network topology.

Link That is Not Part of The SPT Gets Failed or Removed

There are certain situations where it is not necessary to perform any SPF (shortest path first) calculations after a link failure in an OSPF (Open Shortest Path First) network. For example, if the failed link is not part of the current SPT, then there is no need to recalculate the routes. This is because the link was not being used to reach any destinations.

For example, if we drop the link between routers R1 and R2, that would not affect how R1 redirects IP packets to the destinations in the network. Therefore, no SPF computations are required.

However, iSPF (incremental SPF) is not convenient when a transit link is added or the cost of a link is changed. In these cases, OSPF runs full SPF to build up an updated shortest path tree (SPT) in order to reflect updates in the network.

Link That is Part of The SPT Gets Failed or Removed

Imagine the link between R2 and R3 goes down. R1 would run incremental SPF to re-calculate the shortest paths to the destinations downstream of R2, the nearest point of failure to R1.

Similarly, if the link between R1 and R3 fails, R1 would need to recalculate the shortest paths to all OSPF nodes.

The major benefit of OSPF’s incremental SPF feature is that it can minimize the number of calculations needed after a link failure, depending on the location of the failure within the network. In general, the farther away the failed link is from the root node, the fewer calculations may be required.

Configuring OSPF Incremental SPF on Cisco IOS

Configuring OSPF Incremental SPF on Cisco IOS is an easy task. Use the ipspf command in router configuration mode to enable incremental SPF for a particular OSPF instance. Note that you don’t need to activate this feature for all routers in the OSPF routing domain for OSPF to work properly; however, it is recommended to do so mainly if the routing domain consists of a large number of OSPF nodes.

This example enables OSPF incremental SPF.

R1(config)# router ospf 1
R1(config-router)# ispf

To verify OSPF incremental SPF, use the show ip ospf command in enable mode. The command displays whether incremental SPF is enabled or not. The following example states that incremental SPF is active on router R1.

R1# show ip ospf
 Routing Process "ospf 1" with ID 1.1.1.1
 Start time: 01:03:39.802, Time elapsed: 00:13:50.199
 Supports only single TOS(TOS0) routes
 Supports opaque LSA
 Supports Link-local Signaling (LLS)
 Supports area transit capability
 Supports NSSA (compatible with RFC 3101)
 Supports Database Exchange Summary List Optimization (RFC 5243)
 Event-log enabled, Maximum number of events: 1000, Mode: cyclic
 Router is not originating router-LSAs with maximum metric
 Initial SPF schedule delay 5000 msecs
 Minimum hold time between two consecutive SPFs 10000 msecs
 Maximum wait time between two consecutive SPFs 10000 msecs
 Incremental-SPF enabled


omitted output

Finally, note that iSPF (incremental SPF) is not available on Cisco IOS XR.

Verifying OSPF Incremental SPF on Cisco IOS Using The show ip ospf statistics Command

The show ip ospf statistics command displays data about all SPF calculations OSPF executed. Additionally, this Cisco IOS command shows the LSA types that trigger each SPF calculation, as shown in the following example.

R1# show ip ospf statistics
            OSPF Router with ID (1.1.1.1) (Process ID 1)

  Area 0: SPF algorithm executed 5 times

  Summary OSPF SPF statistic

  SPF calculation time
Delta T   Intra D-Intra Summ    D-Summ  Ext     D-Ext   Total   Reason
05:07:11   3    0       0       0       0       0       4       R
05:06:18   3    3       0       0       0       0       7       R, N
05:06:07   3    2       0       0       0       0       6       R, N
05:05:56   1    1       0       0       0       0       4       R, N
05:05:46   2    0       2       1       1       0       7       R, N, SN, X
05:05:36   0    0       0       0       0       0       0       X

First, even though the table includes six rows, not including the first one, SPF got executed five times because the total time of the last entry is 0.

Here are the descriptions of the columns in the table.

Column	Description
Delta T	Time in milliseconds between the current time and the instant at which the SPF execution began.
Intra	Time in milliseconds consumed by SPF to process type 2 LSAs and install intra-area routes in OSPF’s RIB.
D-Intra	Time in milliseconds used by SPF to remove invalid intra-area routes from OSPF’s RIB.
Summ	Time in milliseconds consumed by SPF to process type 3 LSAs and install interarea routes in OSPF’s RIB.
D-Summ	Time in milliseconds used by SPF to remove invalid interarea routes from OSPF’s RIB.
Ext	Time in milliseconds consumed by SPF to process type 5 and 7 LSAs and install external and NSSA routes in OSPF’s RIB.
D-Ext	Time in milliseconds used by SPF to remove invalid external and NSSA routes from OSPF’s RIB.
Total	Total consumed duration time by SPF in milliseconds.
Reason	List of events that causes OSPF to run SPF. R means a change in a type 1 LSA. N means a change in a type 2 LSA. SN means a change in a type 3 LSA. SA means a change in a type 4 LSA. X means a change in a type 5 or 7 LSA.

When you use the show ip ospf statistics detail command, Cisco IOS displays extra OSPF statistics for each area like for example the type of the SPF implementation executed (full or incremental), the number of LSAs OSPF processed during the SPF calculation, the number of LSAs and the set of last ten intra-area LSAs updated between the current SPF calculation and the previous one, as you can see below.

R1# show ip ospf statistics detail

            OSPF Router with ID (1.1.1.1) (Process ID 1)

  Area 0: SPF algorithm executed 5 times

SPF 1 executed 05:07:05 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  0      3      0      0      0      0      0      3
  LSIDs processed R:1 N:0 Stub:2 SN:0 SA:0 X7:0
  Change record 0x0
  LSIDs changed 2
  Changed LSAs. Recorded is LS ID and LS type:
  1.1.1.1(R) 1.1.1.1(R)



Omitted output
          
SPF 5 executed 05:05:41 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  1      2      0      2      1      0      0      5
  LSIDs processed R:5 N:6 Stub:0 SN:3 SA:0 X7:0
  Change record 0x0
  LSIDs changed 5
  Changed LSAs. Recorded is LS ID and LS type:
  4.4.4.4(R) 5.5.5.5(R) 10.0.25.5(N) 2.2.2.2(R)
  5.5.5.5(R)

Related Lessons to OSPF Incremental SPF

Conclusion

I hope this blog post helps you learn something.
Now I’d like to turn it over to you:
What did you like about this tutorial?
Or maybe you have an excellent idea that you think I need to add.
Either way, let me know by leaving a comment below right now.

Cookie	Duration	Description
cookielawinfo-checkbox-analytics	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional	11 months	The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy	11 months	The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.