![]() ![]() |
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
|