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:

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.

hostname R1
!
ip cef
!
interface Loopback0
 ip address 1.1.1.1 255.255.255.255
!
interface GigabitEthernet0/1
 ip address 192.168.12.1 255.255.255.0
 ip ospf cost 10
!
interface GigabitEthernet0/2
 ip address 192.168.13.1 255.255.255.0
!
interface GigabitEthernet0/3
 ip address 192.168.14.1 255.255.255.0
!
router ospf 1
 ispf
 network 1.1.1.1 0.0.0.0 area 0
 network 192.168.12.0 0.0.0.255 area 0
 network 192.168.13.0 0.0.0.255 area 0
 network 192.168.14.0 0.0.0.255 area 0
!
end

hostname R2
!
ip cef
!
interface Loopback0
 ip address 2.2.2.2 255.255.255.255
!
interface GigabitEthernet0/1
 ip address 192.168.12.2 255.255.255.0
!
interface GigabitEthernet0/2
 ip address 192.168.23.2 255.255.255.0
!
interface GigabitEthernet0/3
 no ip address
!
router ospf 1
 network 2.2.2.2 0.0.0.0 area 0
 network 192.168.12.0 0.0.0.255 area 0
 network 192.168.23.0 0.0.0.255 area 0
!
end

hostname R3
!
ip cef
!
interface Loopback0
 ip address 3.3.3.3 255.255.255.255
!
interface GigabitEthernet0/1
 ip address 192.168.13.3 255.255.255.0
!
interface GigabitEthernet0/2
 ip address 192.168.23.3 255.255.255.0
!
interface GigabitEthernet0/3
 ip address 192.168.34.3 255.255.255.0
!
router ospf 1
 network 3.3.3.3 0.0.0.0 area 0
 network 192.168.13.0 0.0.0.255 area 0
 network 192.168.23.0 0.0.0.255 area 0
 network 192.168.34.0 0.0.0.255 area 0
!
end

hostname R4
!
ip cef
!
interface Loopback0
 ip address 4.4.4.4 255.255.255.255
!
interface GigabitEthernet0/1
 ip address 192.168.14.4 255.255.255.0
!
interface GigabitEthernet0/2
 ip address 192.168.34.4 255.255.255.0
!
interface GigabitEthernet0/3
 ip address 192.168.45.4 255.255.255.0
!
router ospf 1
 network 4.4.4.4 0.0.0.0 area 0
 network 192.168.14.0 0.0.0.255 area 0
 network 192.168.34.0 0.0.0.255 area 0
 network 192.168.45.0 0.0.0.255 area 0
!
end

hostname R5
!
ip cef
!
interface Loopback0
 ip address 5.5.5.5 255.255.255.255
!
interface GigabitEthernet0/1
 ip address 192.168.45.5 255.255.255.0
!
router ospf 1
 network 5.5.5.5 0.0.0.0 area 0
 network 192.168.45.0 0.0.0.255 area 0
!
end

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:

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:

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…