路由算法大概综述23987

《路由算法大概综述23987》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、因特网的路由选择算法摘要：路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。路出算法在路出协议中起着至关重要的作用，采用何种算法往往决定了最终寻径结果。本文主耍讨论设计路由算法应貝有的原则以及第一个得到广泛使用的路由算法RIP和最短路径Dijkstra算法。1路由算法概述1.1路由算法的特点路市选择协议的核心就是路市算法，即需耍何种算法来获得路rti表中的个项目。一个理想的路由算法应该具有如下特点。(1)算法必须是正确的和完整的。这里，“正确”的含义是指沿着齐路由表所指引的路由，分组一定能够最终到达

2、目的网络和目的主机。(2)算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。。(3)算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。当网络小的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时的改变路由。有时称这种口适应性为“稳健性”(robustness)。(4)算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下,路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。(5)算

3、法应是公平的。路由选择算法应对所有用户(除了少数优先级高的用户)都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显的不符合公平性的要求。(6)算法应是最佳的。路rti选择算法应当能够找出最好的路市,使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。一个实际的路由选择算法，应该尽可能接近丁理想的

4、算法。在不同的应用条件下，对以上提出的六个方面也可有不同的侧重。1.2路由算法的分类路由选择算法是个非常复杂的问题，因为它是网络屮的所冇节点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络屮出现了某些故障。此外，当网络发生拥塞吋，就特别需要有能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络屮的各结点获得所需的路由选择信息。倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分，则只冇两人类，即静态路由选择策略与动态路出选择策略。静态路出也叫做非

5、自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。对于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态路由选择也叫做口适应路由选择，其特点是能较好的适应网络状态的变化，但实现起来较为复杂，开销也比较大。因此，动态路由选择适用于较复杂的大网络。1.3路由算法的度量标准路出算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量來选择路曲，通过一定的加权运算，将它们合并为单个的复合度量、再填入路由表中，作为寻径的标准。通常所使用的度量有：路径长度、可靠性、时

6、延、带宽、负载、通信成本等。路径长度是最常用的路出metrico一些路由协议允许网管给每个网络链接人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其它路由协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产品，如路出器的个数。可靠性，在路由算法中指网络链接的可依赖性（通常以位误率描述），冇些网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易或更快修复。任何可靠性因索都可以在给可靠率赋值吋计算在内，通常是出网管给网络链接赋以metric值。路由延迟指分组从源通过网络到达廿的

7、所花时间。很多因索影响到延迟，包括中间的网络链接的带宽、经过的每个路出器的端口队列、所冇中间网络链接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它是个比较常用且有效的metric。带宽指链接可用的流通容量。在其它所有条件都相等时，10Mbps的以太网链接比64kbps的专线更口J取。虽然带宽是链接可获得的最大吞吐量，但是通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。例如，如果-•条快速链路很忙，分组到达目的所花时间可能要更长。负载指网络资源，如路由器的繁忙程度。负载口J以用很多方面让算，包

8、括CPU使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。通信代价是另一种垂耍的metric,尤其是有-•些公司可能关系运作费用其于性能。即使线路延迟可能较长，他们也宁愿通过自C的线路发送数据而不采用昂贵的公用线路。2典型的路由算法2.1内部网关协议RIP路由信息协议RIP（RoutingInformationProtocol）是内部网关协议IGP中最先得