最短路径优先算法.PDF

6.1 SPF 算法概述 127 第 6 章 最短路径优先算法 路由选择协议的本质是收集网络环境中的路由选择信息，并选 择到所有已知目的的最优路径。如第 2 章中提到的，在 IS-IS 协议的体系结构中，这些功能是由两个进程实现的：更新进程 与决策进程。更新进程主要负责建立 IS-IS 数据库并维护其稳 定性；决策进程使用最短路径优先（Shortest Path First ，SPF） 算法基于链路状态数据库中的信息计算到所有已知目的的最优 路径。SPF 算法通过计算区域内一个特定的节点到其他所有节 点的最短路径树从而得出从这个特定源到每个已知目的的最优 路由。 SPF 算法也称为 Dijkstra 算法，是由荷兰数学家 Edsger Wybe Dijkstra 命名的。E. W. Dijkstra 于 1930 年出生于荷兰鹿特丹， 在这里他学习了物理和数学，并最终成为了一名著名的计算机 科学家。在研究一种在两点之间寻找最佳路径的算法的过程中， Dijkstra 于 1956 年发明了 SPF 算法。Dijkstra 最初称之为“最 短次生成树（Shortest Subspanning Tree Algorithm ）”算法，并 将其用于解决早期计算机设计中将电流分配到所有必要电路中 的问题，从而优化了昂贵的铜线的利用率。本章重点讨论IS-IS 路由的计算过程以及SPF 算法的操作机制。本章主要包括以下 小节：  SPF 算法概述；  利用SPF 算法计算IS-IS 路由；  Cisco 路由器上的IS-IS SPF 操作。 注 最短路径优先（Open Shortest Path First ，OSPF ）协议是另一种使用SPF 算法计算路 由的路由选择协议。虽然在协议设计和体系结构上有本质的区别，但OSPF 和IS-IS 在很多方面仍是相似的。 128 第 6 章 最短路径优先算法 6.1 SPF 算法概述 SPF 是路由选择协议用于确定最优路径的两种常用算法之一。另一种是 Bellman-Ford 算法，这种算法经常用于距离矢量路由选择协议。Bellman-Ford 算法 与SPF 算法的基本区别在于Bellman-Ford 算法的每一个节点基于直连邻居的开销加 上邻居通告的路由的开销进行路径计算的。与之相对，SPF 算法要求每个节点具有 关于整个拓扑的完整信息。因此，一个区域内的所有节点会获得关于此区域的一致 的链路状态数据库。链路状态数据库中包含区域内所有节点的链路状态信息（即来 自区域内每个节点的链路状态数据包）。 与基于Bellman-Ford 算法的路由选择协议相比，基于SPF 算法不容易产生路由环路。 由于Bellman-Ford 算法依赖邻居发来的信息，而这些邻居可能已经在发生错误