首 页 | 兆通产品部 | 兆通工程部 | 兆通维护部 | 兆通销售站 | 天猫店铺 | 技术中心 | 方案中心 | 典型案例 | 兆通论坛
当前页面:首页>>OSPF算法详细说明 3
[2009-9-25]
 

  V0V2V3V1

  45

  V0、V2、V3、V4V0V0

  V0V2

  V0V2V3

  V0V4V0V4和V0V2V3V1路径值相等,任意选择V0V4放入最短路径树,V4放入集合A。考察所有以刚放入集合A的节点V4为起点的边的终点,其中不在集合A中的节点没有(虽然有边V4V3,但V3已经在集合A中了),所以不进行选择和计算。

  V0、V2、V3、V4、V1V0V0

  V0V2

  V0V2V3

  V0V4

  V0V2V3V1候选路径V0V2V3V1放入最短路径树,这时候选路径集合为空,并且所有节点已经放入了集合A。计算结束。

  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的设计目标是为一个较大的内部网络提供动态路由能力。如果内部网络较大的话,需要描述的链路会很多,存储、传播和计算这些链路信息将耗费大量内存和CPU资源。OSPF解决这个问题的办法是把较大的网络划分成多个Area,每个Area内部使用Router LSA和Network LSA把Area内部网络拓扑描述清楚,并据此使用Dijkstra算法计算出本Area内的最短路径树和路由。至于Area外的网络拓扑,区域边界路由器ABR并不把相邻Area的Router LSA和Network LSA传入本Area,而是把自己在相邻Area范围内计算得到的该Area内各个网段的路由进行汇总,把这些网段当做直接连接在自己上面,并生成Network Summary LSA来对这些网段进行描述,传入本Area。这样,对于一个有n个网段和多台路由器的相邻Area,ABR只需要生成n条网络描述信息并传入本Area即可,大大减少了进入本Area的链路描述信息,减少了存储、传播和计算消耗。需要注意的是,划分Area的做法导致了Area内部路由器中的链路状态数据库描述的Area外部分并不是真实的网络拓扑,从而计算时可能出现环路,为了避免环路出现,要求所有的Area之间的相连必须经过Backbone区域即Area 0。

  另外,OSPF被设计为一个IGP,所以除了处理本自治系统内的路由外,还需要处理自治系统外的路由,这类路由在ASBR处引入,可以看做是直接连接在ASBR上,OSPF引入AS External LSA来描述这类自治系统外路由。另外,因为AS External LSA在传入其他Area时并不在ABR上重新生成,所以从计算的角度看,其他Area还必须知道自治系统外路由从哪个节点引入,所以需要引入ASBR Summary LSA来描述外部路由从哪个节点引入,ASBR Summary LSA在ABR上生成,从其他Area看,可以认为于ASBR直接连在ABR上,自治系统外部路由对应的网段又直接连在ASBR上。

 


[返回列表]

首页 | 网络工程 | 综合布线 | 安防监控 摄像头 摄像机 | 方案中心 | 技术中心 | TOP | 典型案例
电话:025-83693855
Copyright © 2005-2006 All Rights Reserved
南京总部: 南京市珠江路成贤大厦7楼