Calculating IS-IS Routes with the SPF Algorithm

Annex C2 of ISO 10589 specifies use of the SPF algorithm for route calculation within the IS-IS protocol. Annex C of RFC 1195 specifies modifications of the SPF algorithm for supporting IP routing within the IS-IS protocol. Dijkstra's algorithm creates a shortest path tree of the network topology, from which the shortest (best) paths to various destinations in the network are determined and entered into the IP routing table. To obtain best paths for IP routes, IP subnets are considered as leaves in the shortest path tree. Therefore, network events resulting in changes in only IP reachability entries contained in link-state packets do not require computation of the entire shortest path tree. In such cases, the IS-IS protocol performs partial route calculation (PRC) rather than a full run of the SPF algorithm. The pervasiveness of PRC in IS-IS route computations optimizes performance for IP routing convergence in most situations.

The preceding section indicates that the computation time of 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 results from Step 2 in the operation of Dijkstra's algorithm (refer to Figure 6-2). The elements in the set T are presorted by cost to avoid the need for a linear search in selecting the element with the lowest cost. The processing time required by the binary search mechanism used in sorting T while inserting new entries introduces the logN factor. By using a finite path cost based on a 6-bit field (as specified by ISO 10589), it is possible to further optimize and reduce the order of complexity to just O(N), eliminating the logN factor. This is achieved using quick array sort data structures, which sort nodes by hashing them according to path cost rather than logical distance. Unfortunately, over time, the 6-bit metric field has proved insufficient for providing flexibility in designing IS-IS networks, as well as in other applications of IS-IS routing, such as MPLS traffic engineering. The adoption of larger path costs (wide metrics) in IS-IS (see Chapter 5, "The IS-IS Link-State Database") obviously takes away the optimization opportunity with small finite path costs (narrow metrics).

The modifications to the SPF algorithm introduced by RFC 1195 for use in IS-IS routing allows load balancing over multiple equal-cost paths. In general, however, the Dijkstra algorithm works as described in the preceding section. The operation of the SPF algorithm is described well in Annex C of RFC 1195. The following three lists are used in building the shortest path tree: Unknown or candidate list (UNK), Tentative (TENT) list, and known Paths (PATHS) list. At the start of the SPF process, all nodes are placed in the Unknown list. The source node is then moved to PATHS at initialization. Nodes examined for candidacy to the PATHS list are placed in the TENT list with their next-hop and metric information adjusted accordingly . IS-IS maintains an adjacency database for all neighbors, which feeds the SPF process with next -hop information for directly connected neighbors in the TENT list. For nondirectly connected hosts , the first hop is obtained from the parent in PATHS. Entries are stored in TENT and PATHS as triple sets, {n, d(n), Adj(n)}, where

• n = System ID

• d (n) = Distance of n from the root system, s

• Adj(n) = Set of valid adjacencies for n known by s

At each step of the algorithm, the TENT list is examined, and the node with the least cost from the source is moved into PATHS. When a node is placed in PATHS, all IP prefixes advertised by it are installed in the IS-IS Routing Information Base (RIB) with the corresponding metric and next hop. The directly connected neighbors of the node that just made it into PATHS are then added to TENT if they are not already there and their associated costs adjusted accordingly, for the next selection.

Note that IP internal and external prefixes are stored as 8 bytes consisting of the address and mask and are always leaves.