动态路由算法的性能研究

[摘 要] 本文在分析静态和动态路由算法的基础上，重点研究了动态路由算法中的链路状态路由，提出了链路状态路由中路由选择的一种更简洁方法。Dijkstra路由选择算法适合于计算一个路由器到其他各个路由器的最短路径。但在计算机网络中更多的是点对点的连接，Floyd路由选择算法更适合计算两个路由器之间的最短距离，在计算机网络中更实用。

[关键词] 路由算法 迪杰斯特拉 弗洛伊德

一、动态路由算法

由于静态路由算法不考虑网络的当前负载情况，目前计算机网络通常使用动态的路由算法。通常的动态路由算法有两种：距离矢量路由算法和链路状态路由算法。

1.距离矢量路由算法

在这种算法中每个路由器维护一张表，它以子网中的每个路由器为索引，并且每一个路由器对应一个表项，表中列出了当前已知的到每个目标的最佳距离，以及所使用的线路。所使用的距离度量单位可以是跳数或者时间延迟或沿着路径排队的分组数目等。通过在邻居之间相互交换信息，路由器不断地更新它们内部的表。

在距离矢量路由算法中有一个很严重的缺陷：虽然这种算法总能得到正确的答案，但是它收敛得到正确答案的速度非常慢。原因是在这种算法中，同一个网络中相邻的两台路由器之间不知道是相邻的。这样就造成了在网络断开的时候，所有的路由器之间的交换次数会趋于无穷大的数值。问题的核心在于当X路由器告诉Y路由器它有一条路径的时候，Y无从知道它自己是否就在这条路径上。

2.链路状态路由算法

由于距离矢量路由算法中存在着两个问题：距离矢量路由算法需要很长时间才能收敛到稳定状态（无穷计算的问题）；选择路径的时候并没有考虑线路带宽。由于这些原因距离矢量路由算法被一个全新的算法所替代，该算法称为链路状态路由。每一个路由器必须完成的工作是：

（1)发现它的邻居节点，并知道其网络地址：发现邻居节点需要在每一条点到点线路上发送一个特殊的HELLO分组，线路另一端送回一个应答来说明它是谁。（2)测量到各邻居节点的延迟或者开销：用一个发送出去的ECHO到接收到ECHO分组的时间除以2，就可以得到一个合理的延迟估计值。（3)构造一个分组，分组中包含所有它刚刚知道的信息：每一个路由器创建一个由发送方标识序列号和年龄及一个邻居列表组成的分组。（4)将这个分组发送到所有其他的路由器：使用扩散法来链路状态分组。（5)计算出到每一个其他路由器的最短路径：在路由器得到了全部的链路状态分组之后，就可以构造出完整的子网图，在每一台路由器上运行Dijkstra算法，以便计算出到所有可能目标的最短路径。

二、路由算法的改进

由于动态的路由算法把计算机网络链路上的负载和流量考虑在内，所以与静态的路由算法相比适应性更强，应用范围也更广。而两种动态路由算法的区别就在于能否发现相邻的路由器，距离矢量路由算法中不能准确判断邻居节点造成了无穷计算问题，而链路状态路由算法中用一个特殊的HELLO分组可以做到这一点。

1.Dijkstra路由选择算法

下图中用ABCDE代表计算机网络中的路由器，每个路由器都连接到一个或者多个其他的路由器 上。用一个源路由器到其他路由器的最短路径来说明这种算法的思想。

假设路由器A到各路由器的距离如下面的所示的邻接矩阵（其中的距离可以是时间延迟或者跳数）∞代表两个路由器之间的距离不存在。运用Dijkstra算法可以依次找到从A到各路由器的最短路径是依路径长度递增的序列。

从A到各路由顶点运行Dijkstra算法的过程如下表2：S为已经求得的最短路径的集合然后在每个路由顶点运行一遍Dijkstra算法就会得到各个路由器到其他路由器的最短路径。

2.Floyd路由选择算法

在计算机网络中更常用的是两个路由器之间的点对点的连接。一个解决办法是在一个有n个顶点的网络中每次以一个顶点为源点，重复执行Dijkstra算法n次，就可以求得每一对顶点之间的最短路径。总的执行时间的时间复杂度为O（n3）。虽然时间复杂度相同但用Floyd算法要比Dijkstra算法形式更简单。

三个路由器的距离如下表3所示：

其中A、B、C的三个路由器的序号分别是0、1、2；D [i][j]代表从Vi 到Vj的中间顶点的序号不大于k的最短路径的长度。

则运用Floyd算法有如下表4的计算过程：

表中P代表路径，D(0) 表示从初始状态加入了路由器A，D(1) 表示加入了路由器B，D(2)

表示加入了路由器C

最终的各顶点路由器之间的最短路径和路径长度依次为：

A――C： ABC6

A――B： BCA5

B――C： CAB7

参考文献：

[1]计算机安全学．(美)Matt Bishop.电子工业出版社

[2]潘爱民:计算机网络.清华大学出版社