OSPF算法详细说明
V0、V2、V3、V4、V1
V0V0
V0V2
V0V2V3
V0V4
V0V2V3V1
候选路径V0V2V3V1放入最短路径树，这时候选路径集合为空，并且所有节点已经放入了集合A。计算结束。
上一页 [1] [2] [3] [4] 下一页
2 OSPF协议中对Dijkstra算法的使用 从理论上来说，只要描述清楚了节点之间的连接和边的属性，就描述清楚了有向图，也就可以使用Dijkstra算法计算出最短路径树。 对于使用基于Dijkstra算法的路由协议来说，如果能描述清楚整个网络拓扑（对应有向图），并让区域内的每台路由器都清楚的知道整个区域的网络拓扑，则每台路由器都可以独立的计算出最短路径树。从这个意义上说，对于一个使用Dijkstra算法的路由协议来说，需要要解决以下问题： l 网络拓扑的描述问题。 l 网络拓扑描述信息的传播问题。 l 效率问题：路由协议的目的是在耗费最少资源的情况下，在最短时间内动态发现到其他网段的最优路径。 l 另外，还需要考虑路由协议的网络应用位置（IGP或者EGP，适合于多大网络等）以及和其他路由协议的互操作等问题。 以上几个问题有一定的关联性，互相影响。例如，网络拓扑描述的优化可以减少描述信息，从而减轻传播和计算过程的消耗，提高了效率。 本文的着力点是Dijkstra算法及其在OSPF中的应用，所以这里只说明与之相关的网络拓扑的描述和最短路径计算两个内容，网络拓扑的描述也只涉及的几类基本LSA。 2.1 OSPF对网络拓扑的描述 OSPF中使用链路状态通告（LSA）来描述网络拓扑（即有向图）。 OSPF中，Router LSA被用来描述路由器（节点）之间的连接和链路（边）的属性，具备了理论上计算最短路径的可能。但是仅仅是理论而已，从实践的角度，针对特殊的网络情况和应用场景，需要作一些优化工作。 先考虑一个有n个节点的广播网，如果使用Router LSA来描述的话，需要描述n个节点两两相连的n*(n-1)/2条链路，而且n个节点间需要建立建立n*(n-1)/2个邻接关系，描述信息需要在这些建立了邻接关系的节点间传播。如果换一种思路，我们把这个广播网虚构成一个伪节点，其他n个节点均和伪节点相连，那么就只要描述n条链路，n个节点只需要和伪节点建立总共n个邻接关系即可，能大大减少了信息描述量和信息传播量。依据这种想法，OSPF中针对广播网的描述进行了优化，使用指定路由器DR来承担这个伪节点的角色，并使用Network LSA来描述广播网内DR和各个路由器的连接情况。 对于NBMA网络的描述，处理方式和广播网基本相同。 其次，OSPF的设计目标是为一个较大的内部网络提供动态路由能力。如果内部网络较大的话，需要描述的链路会很多，存储、传
天下网吧·网吧天下
闽公网安备35010202000238号