OSPF Incremental SPF

OSPF runs the SPF (Shortest Path First) algorithm to calculate the SPT (Shortest Path Tree), finding the shortest path to each destination. OSPF routers in the same area all have the same LSAs; their LSDB is the same, so they build the same SPT. Even when there is just a single change in the network topology, (change to an LSA type 1 and/or LSA type 2), each OSPF router will run a full SPF calculation again and builds a new SPT.

Running a full SPT calculation when a topology change occurs is a good thing since we’ll have an updated SPT with the shortest paths to all destinations. The downside, however, is that we are also calculating paths that haven’t changed since the last SPF.

OSPF supports a method only to recalculate the part of the SPT that has changed, called incremental SPF.

Since you don’t run a full SPF all the time, the CPU load of the router decreases and convergence times improve. On the other hand, your router stores the previous copy of the SPT which requires some extra memory.

There are three scenarios where incremental SPF has a positive impact:

  • Adding (or removing) a leaf node to a branch
  • Link failure in non-SPT
  • Link failure in branch of SPT

Incremental SPF can be enabled per router; it’s an interesting feature if you have a lot of routers in a single area and your average CPU load is high because of OSPF.

In this lesson, I’ll walk you through these scenarios, and we’ll look at a “before” and “after” comparison where you can see how much faster incremental SPF is.

Configuration

Here is the physical topology I will use:

ospf incremental spf physical topology

Above we have five routers with Gigabit and loopback interfaces with the default OSPF cost value, and all interfaces are advertised in OSPF area 0. R1 is the router that we will test incremental SPF on. We can use this topology to test all three scenarios.

Want to take a look for yourself? Here you will find the startup configuration of each device.

Let’s get started!

Adding a leaf node to a branch

The first scenario we will try is when a new leaf node is added to a current branch. To test this, I’m going to shut the interface of R5:

R5(config)#interface GigabitEthernet 0/1
R5(config-if)#shutdown

When R1 wants to reach the network on the loopback interface of R2, R3 or R4, then it will use the direct links to each of these routers. Basically, from R1’s perspective, the SPT to reach these networks looks like this:

ospf incremental spf three branches

In the picture above, I removed the links in between R2/R3 and R3/R4 since these are not used by R1 to reach any of the loopback interfaces. R1 is the “root” of our tree and R2, R3 and R4 are three different “branches”. When we add R5 behind R4, the only thing that changes is the branch with R4:

ospf incremental spf r4 branch changes

It doesn’t influence the R2 or R3 branches. With a full SPF calculation, however, R1 will re-calculate SPF for all destinations.

Full SPF

Let’s start with a full SPF calculation. Let’s un-shut the interface on R5:

R5(config)#interface GigabitEthernet 0/1
R5(config-if)#no shutdown

If you want to see the details of all previous SPF calculations, you can use the show ip ospf statistics command. This will show you all SPF calculations, here’s the output of the last SPF calculation:

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 5 executed 00:00:02 ago, SPF type Full
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  3      4      1      0      0      0      0      5
  LSIDs processed R:4 N:6 Stub:4 SN:0 SA:0 X7:0
  Change record 0x0
  LSIDs changed 3
  Changed LSAs. Recorded is LS ID and LS type:
  5.5.5.5(R) 192.168.45.5(N) 4.4.4.4(R)

Above, you can see that R1 did a full SPF calculation which took 5 milliseconds in total.

Let’s shut R5 again so that we can do another test with incremental SPF:

R5(config)#interface GigabitEthernet 0/1
R5(config-if)#shutdown

Incremental SPF

To enable incremental SPF, you only need one command:

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

The ispf command enables incremental SPF on your router. Let’s un-shut the interface of R5 again:

R5(config)#interface GigabitEthernet 0/1
R5(config-if)#no shutdown

And take another look at the latest SPF calculation:

R1#show ip ospf statistics detail 

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

  Area 0: SPF algorithm executed 9 times

SPF 9 executed 00:00:06 ago, SPF type Incremental
  SPF calculation time (in msec):
  SPT    Intra  D-Intr Summ   D-Summ Ext7   D-Ext7 Total
  1      1      1      0      0      0      0      2
  LSIDs processed R:1 N:2 Stub:1 SN:0 SA:0 X7:0
  Change record 0x0
  LSIDs changed 4
  Changed LSAs. Recorded is LS ID and LS type:
  5.5.5.5(R) 192.168.45.5(N) 4.4.4.4(R) 192.168.45.4(N)

The output above now shows that R1 did an incremental SPF and it only took two milliseconds. That’s 2.5 times faster than a full SPF calculation. This is a small topology, so 2 ms or 5 ms doesn’t matter much, but in a larger topology, this might be a significant difference.

Let’s disable incremental SPF so that we are ready for the next scenario:

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

And we won’t need R5 anymore:

R5(config)#interface GigabitEthernet 0/1
R5(config-if)#shutdown

Time for the next scenario…

Link failure in non-SPT

Another scenario where incremental SPF is faster is when a link fails that isn’t used in the SPT. Let’s take another look at the SPT from R1’s perspective to reach the loopbacks of R2, R3 or R4:

ospf incremental spf three branches

To reach these networks, R1 doesn’t use the links in between R2/R3 or R3/R4. What if one of these links fail?

ospf incremental spf non spt link failure

The failure of this link in between R2/R3 doesn’t influence the SPT to reach any of the loopback interfaces behind R2, R3 or R4. Let’s see how long it takes to calculate the SPT with full SPF or incremental SPF.

Full SPF

Let’s shut the link in between R2 and R3:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#shutdown

Here’s the last SPF calculation:

R1#show ip ospf statistics detail 

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

  Area 0: SPF algorithm executed 12 times

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

As you can see above, it took R1 4 milliseconds to run a full SPF calculation.

Let’s restore the link so that we can do another test with incremental SPF:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#no shutdown

Incremental SPF

Let’s enable incremental SPF again:

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

And shut the interface on R2:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#shutdown

Here’s the result of the last SPF calculation:

R1#show ip ospf statistics detail 

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

  Area 0: SPF algorithm executed 16 times

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

It only took two milliseconds to run incremental SPF; that’s twice as fast. OSPF still has to calculate a new path to 192.168.23.0/24 but doesn’t have to re-calculate the SPT for all destinations.

Let’s clean up:

R1(config)#router ospf 1
R1(config-router)#no ispf
R2(config)#interface GigabitEthernet 0/2
R2(config-if)#no shutdown

Link failure in branch of SPT

The last scenario where incremental SPF is useful is if you have a link failure in one of your branches of the SPT.  To demonstrate this, I will change the OSPF cost on one of my interfaces:

R1(config)#interface GigabitEthernet 0/1
R1(config-if)#ip ospf cost 10

If R1 now wants to reach the loopback on R2, it will use the path through R3. Here’s the new shortest path:

ospf incremental spf spt r1 to r2

When the link in between R2 and R3 fails, it will have to recalculate the shortest path which is the direct link from R1 to R2:

ospf incremental spf spt r1 to r2 new path

This is a good example where incremental SPF is interesting since it only affects a small part of the network. Let’s try another test with full SPF and incremental SPF…

Full SPF

Let’s see what happens when the link that connects R2 to R3 fails:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#shutdown

R1 will run SPF and figures out that it has to use its direct link to R2 now. Here’s the result of the final SPF calculation:

R1#show ip ospf statistics detail 

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

  Area 0: SPF algorithm executed 30 times

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

It took four milliseconds to run a full SPF calculation. Let’s restore the interface:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#no shutdown

Incremental SPF

Let’s do another test, let’s enable incremental SPF:

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

And shut the interface on R2 again:

R2(config)#interface GigabitEthernet 0/2
R2(config-if)#shutdown

Here’s the latest SPF calculation of R1:

R1#show ip ospf statistics detail 

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

  Area 0: SPF algorithm executed 35 times

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

This time it only took two milliseconds, twice as fast as our full SPF calculation.

Conclusion

OSPF is a link-state routing protocol that builds the SPT with the SPF algorithm. All routers within the same area have the same LSAs and the same LSDB, so they build the same SPT. Whenever there is a change in an LSA type 1 or 2, it has to re-run SPF and build a new SPT for the entire tree. Incremental SPF is a feature that stores the previous copy of the SPT; this allows the router to re-calculate the SPT not for the entire tree but only for the part that requires re-calculation. This saves CPU resources which improves convergence times while requiring a bit more memory.

In this lesson, you have learned:

  • There are three scenarios where incremental SPF increases convergence times:
    • Adding (or removing) a leaf node to a branch
    • Link failure in non-SPT
    • Link failure in branch of SPT
  • You can enable incremental SPF with the ispf command under the OSPF process.
  • You can enable this per router; it’s not required to enable this on all routers.

Unit 1: Introduction to OSPF

Unit 2: OSPF Neighbor Adjacency

Unit 3: OSPF Network Types

Unit 4: OSPF Stub Areas

Unit 5: Advanced OSPF Topics