IS-IS SPF Operation on Cisco Routers

The actual implementation of a protocol on a specific router platform is mostly transparent to the network operator, and interoperability between products from different vendors is guided by compliance to standards. The details of a specific vendor implementation and software coding also are frequently proprietary information. However, a network engineer seeking a better understanding of IS-IS and the mechanics of operation on a specific platform might benefit significantly from studying various parameters, such as default timers, flags, and other default constants, and how they are configured. Additionally, specifications such as ISO 10589 and RFC 1195 provide useful guidance. This section provides some insights into the operation of IS-IS, and specifically the operation of the SPF algorithm, on Cisco routers.

The SPF process works on Cisco routers as described in the preceding section. Three separate lists (UNK, TENT, and PATH) are used in the algorithm for calculating the shortest path tree for an area. The computation is based on the contents of the Link-State database and the configuration of the routers. The SPF algorithm is executed on the route processor by the SPF process, which is controlled by the IS-IS decision process from an architectural standpoint of IS-IS. The decision process liaises with the update process, which manages the Link-State database. Any changes in the Link-State database triggers the SPF process and can result in a full run of the SPF algorithm or a PRC. As specified by ISO 10589, the SPF process runs no more frequently than every 10 seconds by default. Events that trigger the SPF process can be viewed with the command show isis spf-log (see Example 6-1). In a dynamic environment, a sequence of consecutive events can take place within the 10 seconds between runs of the SPF process. Only the first trigger is stored in the SPF event log in current releases of IOS. Some older IOS releases store the last trigger.

Example 6-1 show isis spf-log command

 #  show isis spf-log  Level 2 SPF log When     Duration     Nodes    Count    First trigger    LSP Triggers 08:52:29  4            72        4         RTA.00        TLVCONTENT 

On a Cisco 7500 router, with the RSP4 processor, the duration of the SPF process is normally less than 1 second for a network with fewer than 1000 nodes. A 200 MHz processor, executing one instruction per cycle, performs 200 million instructions per second. Considering that an average of approximately 100,000 instructions are expended per node to calculate the SPF tree, this translates into computing the shortest path tree for 2000 nodes in a second. Therefore, for a reasonably large network of about 500 nodes in a single all Level 1 IS-IS area, it takes about 250 milliseconds to compute the shortest path tree. Note that this number is not a hard figure, and several factors, such as the following, can influence the outcome:

• Actual topology of the network (highly meshed or not).

• Type of operating systems (preemptive or nonpreemptive processing).

• The actual number of instructions executed per cycle. (Some processors can perform two instructions per cycle.)

• Inherent optimizations in the code.

As previously noted, the processing time required by the SPF algorithm is of the order O(LlogN), where L is the number of links, and N is the number of nodes. The logN factor exists because of the sorting of the TENT list during each iteration in the SPF algorithm. In addition, the complexity of the sorting process depends on the extent of interconnectivity between nodes. Note that when a node moves from the TENT list into the PATHS list, all directly connected nodes still in the UNK list move into the TENT list, where sorting is performed during insertion.

The entries on the PATHS lists at the end of each run of the SPF process are only candidates for the routing table on the router. The route processor expends some more cycles comparing the IS-IS routes with similar routes (same prefixes) from other sources, such as BGP, static routes, OSPF, and so on, and installs the prefixes from the source with lowest administrative distance in the routing table. The SPF tree computed by the Dijkstra algorithm considers the routers as vertices with IP addresses advertised by the routers as leaves . As a result, the entire shortest path tree for network changes related only to IP prefixes does not need to be recalculated. Instead, the router runs a partial computation to find an alternative IP prefix if one exists. Also, when best paths are selected, two or more similar routes with worse metrics are kept as backup elements for use as alternative routes in case the selected primary goes away. This allows Cisco IOS to quickly find an alternative path when any route change occurs. Because the topology of the network is determined by the adjacencies advertised in the LSPs, the loss of an adjacency implies a change in topology and, therefore, subsequent scheduling of a complete SPF run. When a point-to-point link goes down, for example, a router loses the adjacency to the neighbor at the other end. This signals a change in topology and, therefore, scheduling of a full SPF. However, a broadcast interface, such as Ethernet, might have only an IP subnet connecting to IP workstations, so losing that interface can imply losing only the IP subnet and not necessarily an adjacency because there might not be another IS-IS router on the link. Because the IP subnet is only a leaf of the SPF tree, this does not flag a change in network topology, and, therefore, only PRC is run to find an alternative path.

The three costly activities for the route processor of an IS-IS router are SPF, PRC, and LSP generation. Delays are employed between successive occurrences of any of these activities to help control processor utilization. The initial wait and minimum interval between successive runs of the SPF and PRC process and consecutive LSP transmissions over the same link are shown in Table 6-2.

Table 6-2. Delays Between Processing-Intensive IS-IS Events

Process	Initial Wait (seconds)	Interval (seconds)
SPF	5.5	10
PRC	2	5
LSP generation		5

An LSP is generated and flooded as soon as possible without any delay. However, an interval of at least 5 seconds occurs between two consecutive LSPs. When a router receives an LSP, which indicates an adjacency change, a 5.5-second delay is imposed before running the SPF process. Periodic SPF runs are scheduled at least 10 seconds apart. Running of the SPF process stalls transmission, as well as processing of LSPs received from neighbors. Because PRC runs are involved only with calculating leaf information, they are held up when a full SPF is scheduled. This is because a new topology might emerge after running the full SPF process, which might impact the IP path resolution. Cisco IOS provides commands to modify the default intervals, shown in Table 6-2. You can use the following commands to modify the SPF interval, PRC interval, and LSP generation interval, respectively:

• isis spf-interval

• isis prc-interval

• isis lsp-gen-interval

Chapter 7, "General Network Design Issues," discusses network design recommendations for the IS-IS protocol and covers in-depth adjustment of these timers to provide optimal performance of the IS-IS protocol. Also, a recent IETF draft studies convergence characteristics of IS-IS implementations and recommends changes in the current specifications and implementation approaches to attain convergence times in the order of milliseconds rather than the order of seconds achievable today.