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

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

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.

Configurations

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

R1

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

R2

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

R3

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

R4

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

R5

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:

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…

We're Sorry, Full Content Access is for Members Only...

If you like to keep on reading, Become a Member Now! Here is why:

  • Learn any CCNA, CCNP and CCIE R&S Topic. Explained As Simple As Possible.
  • Try for Just $1. The Best Dollar You've Ever Spent on Your Cisco Career!
  • Full Access to our 657 Lessons. More Lessons Added Every Week!
  • Content created by Rene Molenaar (CCIE #41726)

521 Sign Ups in the last 30 days

satisfaction-guaranteed
100% Satisfaction Guaranteed!
You may cancel your monthly membership at any time.
No Questions Asked!

Tags:


Forum Replies

  1. Hi Rene,

    Good Day :slight_smile: I want to know about convergence after topology change . My question is “After Topology change how a router know a prefix have to be remove from its database” ??

    br//zaman

  2. Hi Laz,

    What is the job of LS age ?? Thx

    br//zaman

  3. Hello Mohammad

    According to Cisco:

    After a default of 30 minutes the router that originated the entry resends the LSA, with a higher sequence number, in a link-state update (LSU), to verify that the link is still active.

    If however, an LSA is expected after 30 minutes and it doesn’t arrive, the information of the LSA is retained until the LS age or the LSA maximum age is reached. This by default is 60 minutes. So it’s kind of like a dead timer, where if no LSA is resent after 60 minutes, the specific LSA is removed from consideration by the OSPF routing cal

    ... Continue reading in our forum

  4. Hi Rene,

    So Incremental SPF works only on LSA-1 & LSA-2 . It doesnt work on other LSAs .Correct me if I am wrong .Thx

    br//zaman

  5. Hello Zaman

    This is a very good question! Shows you’re thinking very analytically. So, changes in LSA types 1 and 2 will always trigger a full SPF calculation unless the Incremental SPF is enabled. Changes in LSA types 3, 4, 5 and 7 will trigger what is called a partial SPF which is different than an incremental SPF calculation. A partial SPF calculation only involves the leaves of the SPF tree. Any changes in these LSAs indicate changes ONLY in the leaves. The SPF tree itself remains unchanged with changes to these LSAs. This is the default behaviour of

    ... Continue reading in our forum

1 more reply! Ask a question or join the discussion by visiting our Community Forum