7.3 IS-IS Operation  
  7.3.13

SPF algorithm

 
After the link-state database is updated, the router still needs to populate the routing table, or forwarding table. Just as with OSPF, IS-IS uses the Dijkstra algorithm, also known as the shortest-path-first algorithm, for computing the best path to a given destination in the link-state database. This is the critical decision making process that determines what routes, of those appearing in the link-state database, will populate the routing table as IS-IS routes.

Edsger Dijkstra's SPF algorithm is used for calculating routes with the IS-IS routing protocol, for support of both TCP/IP and OSI. This is based on an extension to the algorithm specified in ISO/IEC 10589.

The SPF algorithm computes the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. In the Cisco IOS implementation, the weight assigned to the branches of a tree is a configurable metric with 224 possible values for each link and 232 possible values for each path from the root to a leaf.

The SPF algorithm can also be applied to Intermediate System-to-Intermediate System (IS-IS), which is a link-state protocol. The main difference between link-state and distance vector routing protocols is that a link-state protocol provides full visibility of the network topology, and a distance vector protocol uses learned information to build forwarding tables. The visibility provided by a link-state protocol is achieved through the use of a flooding mechanism. This mechanism ensures that each router in a specified area of a network receives information that can be used to build a network map. In IS-IS this information is flooded through the use of link-state protocol data units. Each intermediate system, or router, then advertises information that pertains to itself and its links. After the information is flooded and all routers obtain the same information, the SPF algorithm is applied separately to each router. This is done to determine the topology and extract the shortest paths for each router from the root of the tree to all the leaves of the tree. This process is shown in Figure . The information derived from this process is used to create the forwarding table on the router.