路由算法大概综述.pdfVIP

因特网的路由选择算法

摘要：路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。

路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终寻径

结果。本文主要讨论设计路由算法应具有的原则以及第一个得到广泛使用的路由

算法RIP和最短路径Dijkstra算法。

1路由算法概述

1.1路由算法的特点

路由选择协议的核心就是路由算法，即需要何种算法来获得路由表中的个项

目。一个理想的路由算法应该具有如下特点。

（1）算法必须是正确的和完整的。这里，“正确”的含义是指沿着各路由表

所指引的路由，分组一定能够最终到达目的网络和目的主机。

（2）算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的

额外开销。。

（3）算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。当

网络中的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等

某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也

能及时的改变路由。有时称这种自适应性为“稳健性”（robustness）。

（4）算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下，

路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。

（5）算法应是公平的。路由选择算法应对所有用户（除了少数优先级高的

用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考

虑其他的广大用户，这就明显的不符合公平性的要求。

（6）算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组

平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是

最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞

吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为

合理的选择而已。

一个实际的路由选择算法，应该尽可能接近于理想的算法。在不同的应用条

件下，对以上提出的六个方面也可有不同的侧重。

1.2路由算法的分类

路由选择算法是个非常复杂的问题，因为它是网络中的所有节点共同协调工

作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先

知道，例如，网络中出现了某些故障。此外，当网络发生拥塞时，就特别需要有

能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络中的各结点

获得所需的路由选择信息。

倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分，

则只有两大类，即静态路由选择策略与动态路由选择策略。静态路由也叫做非自

适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。对

于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态

路由选择也叫做自适应路由选择，其特点是能较好的适应网络状态的变化，但实

现起来较为复杂，开销也比较大。因此，动态路由选择适用于较复杂的大网络。

1.3路由算法的度量标准

路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可

能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度

量、再填入路由表中，作为寻径的标准。

通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本等。

路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人

工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其它路由

协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产品，如路由器

的个数。

可靠性，在路由算法中指网络链接的可依赖性（通常以位误率描述），有些

网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易

或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内，通常是由网管

给网络链接赋以metric值。

路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟，包

括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链接的

拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它是个比较常用且

有效的metric。

带宽指链接可用的流通容量。在其它所有条件都相等时，10Mbps的以太网

链接比64kbps的专线更可取。虽然带宽是链接可获得的最大吞吐量，但是通过

具有较大带宽的链接做路