文档介绍：因特网的路由选择算法
摘要:路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。路由算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终寻径结果。本文主要讨论设计路由算法应具有的原则以及第一个得到广泛使用的路由算法RIP和最短路径Dijkstra算法。
1 路由算法概述
路由算法的特点
路由选择协议的核心就是路由算法,即需要何种算法来获得路由表中的个项目。一个理想的路由算法应该具有如下特点。
(1)算法必须是正确的和完整的。这里,“正确”的含义是指沿着各路由表所指引的路由,分组一定能够最终到达目的网络和目的主机。
(2)算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。。
(3)算法应能适应通信量和网络拓扑的变化,这就是说要有自适应性。当网络中的通信量发生变化时,算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作,或者修理好了再投入运行时,算法也能及时的改变路由。有时称这种自适应性为“稳健性”(robustness)。
(4)算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下,路由算法应收敛于一个可以接受的解,而不应使得出的路由不停的变化。
(5)算法应是公平的。路由选择算法应对所有用户(除了少数优先级高的用户)都是平等的。例如,若仅仅使某一对用户的端到端时延为最小,但却不考虑其他的广大用户,这就明显的不符合公平性的要求。
(6)算法应是最佳的。路由选择算法应当能够找出最好的路由,使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法,但这并不是最重要的。对于某些网络,网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此,所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
一个实际的路由选择算法,应该尽可能接近于理想的算法。在不同的应用条件下,对以上提出的六个方面也可有不同的侧重。
路由算法的分类
路由选择算法是个非常复杂的问题,因为它是网络中的所有节点共同协调工作的结果。其次,路由选择的环境往往是不断变化的,而这种变化有时无法事先知道,例如,网络中
出现了某些故障。此外,当网络发生拥塞时,就特别需要有能缓解这种拥塞的路由选择策略,但恰好在这种条件下,很难从网络中的各结点获得所需的路由选择信息。
倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分,则只有两大类,即静态路由选择策略与动态路由选择策略。静态路由也叫做非自适应路由选择,其特点是简单和开销较小,但不能及时适应网络状态的变化。对于很简单的小网络,完全可以采用静态路由选择,用人工配置每一条路由。动态路由选择也叫做自适应路由选择,其特点是能较好的适应网络状态的变化,但实现起来较为复杂,开销也比较大。因此,动态路由选择适用于较复杂的大网络。
路由算法的度量标准
路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量、再填入路由表中,作为寻径的标准。
通常所使用的度量有:路径长度、可靠性、时延、带宽、负载、通信成本等。
路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人工赋以代价值,这种情况下,路由