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

  现实生活中的网络拓扑,可以抽象成由节点(路由器)和边(路由器之间的链路)构成的有向连通图,链路的代价可以抽象成边的权函数。之所以称图为有向图,是因为同一条链路(边)不同方向的权值可能不一样。

  我们知道,对于有向连通图,以任意一个节点为起点,利用最短路径算法可以计算出到其他节点的最短路径。那么,对于能抽象成有向连通图的网络拓扑来说,也可以利用最短路径算法先计算出以任意一台路由器为起点,到达其他路由器的最短路径,然后根据各路由器的网络连接情况可以得到到各个网络的路由路径。

  OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样,都是相当经典的最短路径算法。本文将对Dijkstra算法及OSPF协议对Dijkstra算法的使用进行介绍。

  1Dijkstra算法介绍

  在数学上,以某个节点为起点,计算到其他节点的最短路径的算法,称为“单源最短路径” 算法。求“单源最短路径”的问题在数学上可以精确描述如下:

  “单源最短路径” 问题:已知一个有n个节点(V0..n)构成的有向连通图G=(V,E),以及图中边的权函数C (E),其中V代表节点集合,E表示所有边的集合,并假设所有权非负,求由G中指定节点V0到其他各个节点的最短路径。

  Dijkstra算法是很经典的求解上述问题的算法,其基本想法是设计一种最短路径树的构造方法,按非降次序逐条构造从V0到各个节点的最短路径,第一步找到和V0相距最短的节点以及到这个节点的路径,第二步找到和V0相距次短的节点以及到这个节点的路径,如此反复,最后找到V0到所有节点的最短路径,构造出整棵最短路径树。

  对上述构造方法的一个直观考虑是:和V0相距最短的节点应该在和V0直接相邻的节点中,和V0相距次短的节点要么在和V0直接相邻的节点中,要么在和这些相邻节点相邻的节点中,如此逐步扩散考虑,应该就可以找到和V0相距最短、次短、…….第n短的节点以及对应的路径,而且因为是连通图,最后肯定所有节点都能全部考虑到,也就能完成整棵最短路径树的构造。

  事实上,上述直观考虑是对的,Dijkstra算法是对上述过程的一个提炼和优化:和V0相距最短的节点是和V0直接相连的节点没错;相距次短的节点范围可以缩小为,和V0直接相邻的节点,加上跟刚选中的最短节点直接相邻的节点;相距第三短的节点的范围可以类推得到,即在上一步考察的节点的基础上,加上和次短节点直接相邻的节点。如此逐步构造,可以按非降次序找到到所有节点的最短路径。

  为了从数学上精确描述上述构造过程,引入了集合的概念对节点和路径进行分类。

  我们把节点分成两个集合:

  A:已经选入最短路径树的节点的集合。

  B:剩余的其他节点的集合。

  对于路径,我们分成三个集合:

  (1)已经选入最短路径树的路径的集合

  (2)候选路径集合:下一条加入最短路径树的路径将从这个集合中选入

  (3)剩余的其他路径的集合(被废弃的路径或者还未考虑的路径)

  为了更好的理解,有必要对这里的路径定义进行一下强调:路径是指以V0为起点,其他节点为终点的由一条或多条边组成的一个有序集。边,可以理解为路径中的一段,只有到和V0直接相邻的节点的路径才直接对应一条边。从V0到所有节点,都可能存在一条或多条路径,非最短路径在计算过程中将会被废弃,放入集合III。

 


[返回列表]

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