最短路径优先算法

《最短路径优先算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.1SPF算法概述127第6章最短路径优先算法路由选择协议的本质是收集网络环境中的路由选择信息，并选择到所有已知目的的最优路径。如第2章中提到的，在IS-IS协议的体系结构中，这些功能是由两个进程实现的：更新进程与决策进程。更新进程主要负责建立IS-IS数据库并维护其稳定性；决策进程使用最短路径优先（ShortestPathFirst，SPF）算法基于链路状态数据库中的信息计算到所有已知目的的最优路径。SPF算法通过计算区域内一个特定的节点到其他所有节点的最短路径树从而得出从这个特定源到每个已知目的的最优路由。SPF算法也称为Dij

2、kstra算法，是由荷兰数学家EdsgerWybeDijkstra命名的。E.W.Dijkstra于1930年出生于荷兰鹿特丹，在这里他学习了物理和数学，并最终成为了一名著名的计算机科学家。在研究一种在两点之间寻找最佳路径的算法的过程中，Dijkstra于1956年发明了SPF算法。Dijkstra最初称之为“最短次生成树（ShortestSubspanningTreeAlgorithm）”算法，并将其用于解决早期计算机设计中将电流分配到所有必要电路中的问题，从而优化了昂贵的铜线的利用率。本章重点讨论IS-IS路由的计算过程以及SPF

3、算法的操作机制。本章主要包括以下小节：SPF算法概述；利用SPF算法计算IS-IS路由；Cisco路由器上的IS-ISSPF操作。注最短路径优先（OpenShortestPathFirst，OSPF）协议是另一种使用SPF算法计算路由的路由选择协议。虽然在协议设计和体系结构上有本质的区别，但OSPF和IS-IS在很多方面仍是相似的。128第6章最短路径优先算法6.1SPF算法概述SPF是路由选择协议用于确定最优路径的两种常用算法之一。另一种是Bellman-Ford算法，这种算法经常用于距离矢量路由选择协议。Bellman-Fo

4、rd算法与SPF算法的基本区别在于Bellman-Ford算法的每一个节点基于直连邻居的开销加上邻居通告的路由的开销进行路径计算的。与之相对，SPF算法要求每个节点具有关于整个拓扑的完整信息。因此，一个区域内的所有节点会获得关于此区域的一致的链路状态数据库。链路状态数据库中包含区域内所有节点的链路状态信息（即来自区域内每个节点的链路状态数据包）。与基于Bellman-Ford算法的路由选择协议相比，基于SPF算法不容易产生路由环路。由于Bellman-Ford算法依赖邻居发来的信息，而这些邻居可能已经在发生错误后不可用了，所以基于Be

5、llman-Ford算法的路由选择协议更容易产生环路。因此，此类协议会使用复杂的抑制机制和例如水平分割、毒性逆转和跳数无限大等其他手段来防止环路。另外基于Bellman-Ford算法的协议的抑制机制会导致较长的收敛时间，这也是距离矢量路由选择协议典型的缺点。链路状态路由选择协议的收敛时间更快是因为每个节点基于收到的链路状态数据包（LSP）重新计算路由选择信息，当网络发生变化时，LSP会立即产生并泛洪出去。不过，基于SPF算法的协议对网络资源更为敏感，每台路由器需要更高的内存和CPU资源以保存链路状态数据库及运行SPF算法。6.1.1基

6、本原理图Dijkstra的算法提供了一个通用的解决方案，该方案适用于任何可以被模拟成有向图（Digraph）的问题。有向图是由一组通过直线或弧线（链路）相互连接的顶点（节点）构成的。图6-1显示了一个图例，数字表明的圆圈代表节点，其可以表示为{1,2,3,4,5}的集合。弧线是一条规划好的箭线。例如，顶点1和2之间的弧线是从顶点1指向顶点2的一个箭头，可以表示为(1,2)。顶点2和3之间的弧线是对向互指的，并表示为(2,3)和(3,2)，与顶点2和3之间的链路方向一致。图6-1有向图6.1SPF算法概述129图6-1中弧线的集合可以被

7、表示为{(1,2),(1,3),(2,3),(2,4),(3,2),(3,4),(4,5),(5,3)}。顶点的集合与弧线的集合可以被分配一个字母名称，如下：N={1,2,3,4,5}，代表顶点的集合。L={(1,2),(1,3),(2,3),(2,4),(3,2),(3,4),(4,5),(5,3)}，代表弧线的集合。同时，该图可以被命名为G，表示为G=（N,L），其中N为顶点的集合，L为弧线的集合。一条路径是图中任意两个顶点之间有向弧线的序列。例如，在图6-1中，顶点1到顶点4的路径可以被表示为(1,2),(2,4)或(1,3),

8、(3,2),(2,4)。SPF算法的目标是确定从图中任一参考顶点到所有其他顶点的最短路径。SPF算法使用一种迭代机制来解决这一问题。下一节将讨论在一个表示为G=(N,L)的有向图中SPF算法的操作，在一个固定的顶点s，顶