Chapter 6. The Shortest Path First Algorithm


Chapter 6. The Shortest Path First Algorithm

The essence of a routing protocol is to collect routing information about the networking environment and to determine the best paths to all known destinations. As discussed in Chapter 2, "Introduction to the IS-IS Routing Protocol," these functions are performed by two processes within the architecture of the IS-IS protocol: the update process and the decision process. The update process is responsible for building the IS-IS database and ensuring its integrity. The decision process uses the shortest path first (SPF) algorithm to calculate the best paths to all known destinations based on the information in the Link-State database. The SPF algorithm works by computing the shortest path tree from a specific node to all other nodes in the area, thereby, yielding the best routes to every known destination from that particular source.

The SPF algorithm is named after the Dutch mathematician , Edsger Wybe Dijkstra and is also known as Dijkstra's algorithm . E. W. Dijkstra was born in Rotterdam, Netherlands in 1930, where he studied physics and mathematics and later became a renowned computer scientist. Dijkstra discovered the SPF algorithm in 1956, while researching an algorithm to assist in finding the best way to travel between two points. Referring to it as the shortest subspanning tree algorithm, Dijkstra used his discovery to solve the problem of distributing electric current to all essential circuits of an early computer design, in a manner that optimized usage of expensive copper wire. This chapter focuses on the IS-IS route calculation process and operation of the SPF algorithm. The material in this chapter is organized into the following sections:

  • Overview of the SPF algorithm

  • Calculating IS-IS routes with the SPF algorithm

  • IS-IS SPF operation on Cisco routers

NOTE

The Open Shortest Path First (OSPF) protocol is another routing protocol that utilizes the Dijkstra algorithm for route calculation. OSPF is similar to IS-IS in many regards, even though they fundamentally differ in design and architecture.




IS-IS Network Design Solutions
IS-IS Network Design Solutions (Networking Technology)
ISBN: 1578702208
EAN: 2147483647
Year: 2005
Pages: 144
Authors: Abe Martey

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net