Summary

This chapter introduces the reader to the theoretical foundations of the SPF algorithm. It explains how the SPF algorithm calculates routes in IS-IS and provides an overview of how SPF operates on Cisco routers running IS-IS.

The SPF algorithm is named after its inventor , Dutch mathematician and computer scientist Edsger W. Dijkstra. SPF is used in conjunction with the graph theory to find the shortest path between two points. This innovation is used with numerous applications, and certainly use in data communications networks for path determination is one of them. The routers and links (adjacencies) in a communications network can be modeled as the vertices and arcs of a directed graph, and the Dijkstra algorithm can be used to calculate the best paths between nodes in this model. The IS-IS protocol uses the Dijkstra algorithm in this manner to determine the best routes in a network.

Within the IS-IS architecture, the update process is responsible for the building and maintenance of the Link-State database whereas the decision process uses the information in the database to calculate routes. The SPF algorithm is at the core of the operation of the decision process. On Cisco routers, the IS-IS SPF process runs the SPF algorithm to calculate IS-IS routes. The processing time associated with the SPF algorithm depends on the number of nodes and links in the network; generally , it is of the order O(LlogN), where L is the number of links, and N is the number of nodes. The Dijkstra algorithm builds a shortest path tree of the routers in the network based on adjacency information advertised in IS-IS link-state packets. IP prefixes advertised by routers are grafted into the SPF tree as leaves . Any adjacency changes trigger a complete recalculation of the shortest path tree (that is, a full run of the SPF process). Only a partial route calculation is performed for changes in only IP information.