SPF events in OSPF and IS-IS

From CT3

Jump to: navigation, search

By Ivan Pepelnjak

Link-state algorithms select the best routes through a two-step process:

  1. The topology of the area is analyzed, resulting in a shortest-path tree. This tree contains the shortest paths from the current router to any other node (router or transit LAN) in the current area. This step performed with the Shortest Path First (SPF) algorithm.
  2. The best routes are selected based on the advertisements from all routers in the area (including inter-area and external routes in case of OSPF). The route selection is a simple distance-vector operation where the router selects the minimum-cost IP prefixes from the set of all advertised IP prefixes.

The SPF algorithm is CPU-intensive and is thus heavily throttled: the router will not execute the SPF algorithm until a predefined timeout has expired from the event triggering the SPF (goal: collect as many changes as possible in the topology database to prevent multiple SPF runs) and will not execute subsequent SPF run until the inter-SPF interval expires (goal: minimize CPU utilization in case of severe network instability).

Use the timers throttle spf router configuration command to adjust OSPF SPF timers and the spf-interval router configuration command to adjust IS-IS SPF timers.

The best route selection after the shortest path tree is built is not computationally complex and not as heavily throttled. The best route selection after the SPF tree has been built is called partial SPF in OSPF debugging printouts (although it has nothing to do with the SPF algorithm) and partial route calculation (PRC) in IS-IS. Partial SPF in OSPF is executed as soon as the change is noticed. Cisco IOS implementation of IS-IS supports PRC throttling with the prc-interval router configuration command.

To understand the impacts of a topology change (interface state change, router reload or configuration change) on the network and its individual areas, it’s of vital importance to understand which events trigger the SPF run (these events will cause high CPU utilization and delayed network convergence) and which events result in route selection process (partial SPF/PRC). The following table summarizes events that cause OSPF or IS-IS SPF algorithm to run:

Event OSPF IS-IS
Transit P2P interface change SPF SPF
Transit LAN interface change SPF SPF
Stub interface state change SPF no
Stub interface IP address change SPF no
Inter-area route loss/addition no no
Inter-area cost change no no
Redistributed route loss/addition no no
Redistributed route cost change no no
Notes:
  1. Interfaces over which the link-state routers have established adjacencies are transit interfaces. Interfaces with no link-state neighbors are stub interface (a LAN interface with multiple routers but no link-state adjacency is still a stub interface).
  2. IP address change on a stub interface causes SPF run in OSPF only if the changed IP address results in a different IP prefix being advertised by the OSPF router. For example, changing 10.0.0.1/24 to 10.0.0.2/24 on a stub interface will not cause an SPF run.
  3. Under certain circumstances, changing IP address on a transit interface does not trigger SPF event in IS-IS.
  4. When an OSPF area border router (ABR) experiences an interface state change, it floods new router LSA (and triggers SPF event) in all adjacent areas, regardless of the area in which the actual change has occurred.

Additional Resources  

Personal tools

CT3

Main menu