路由算法大概综述_第1页
路由算法大概综述_第2页
路由算法大概综述_第3页
路由算法大概综述_第4页
路由算法大概综述_第5页
已阅读5页,还剩1页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、加太多的额外开销。(3) 算法应能适应通信量和网络拓扑的变化,这就是说要有自适应性。当网络中的通信量发生变化时,算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作,或者修理好了再投入运行时,算法也能及时的改变路由。有时称这种自适应性为“稳健性”(robustness)。(4) 算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下,路由算法应收敛于一个可以接受的解,而不应使得出的路由不停的变化。(5) 算法应是公平的。路由选择算法应对所有用户(除了少数优先级高的用户)都是平等的。例如,若仅仅使某一对用户的端到端时延为最小,但却不考虑其他的广大用户,这就明显的

3、不符合公平性的要求。(6) 算法应是最佳的。路由选择算法应当能够找出最好的路由,使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法,但这并不是最重要的。对于某些网络,网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此,所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。一个实际的路由选择算法,应该尽可能接近于理想的算法。在不同的应用条件下,对以上提出的六个方面也可有不同的侧重。1.2 路由算法的分类路由选择算法是个非常复杂的问题,因为它是网络中的所有节点共同协调工作的结果。其次,路由选择的环境往往是不断变化的,而这种变化有时无法事先知道,例如,网络中

4、出现了某些故障。此外,当网络发生拥塞时,就特别需要有能缓解这种拥塞的路由选择策略,但恰好在这种条件下,很难从网络中的各结点获得所需的路由选择信息。倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分,则只有两大类,即静态路由选择策略与动态路由选择策略。静态路由也叫做非自适应路由选择,其特点是简单和开销较小,但不能及时适应网络状态的变化。对于很简单的小网络,完全可以采用静态路由选择,用人工配置每一条路由。动态路由选择也叫做自适应路由选择,其特点是能较好的适应网络状态的变化,但实现起来较为复杂,开销也比较大。因此,动态路由选择适用于较复杂的大网络。1.3 路由算法的度量标准路由算法使用

5、了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量、再填入路由表中,作为寻径的标准。通常所使用的度量有:路径长度、可靠性、时延、带宽、负载、通信成本等。路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人工赋以代价值,这种情况下,路由长度是所经过各个链接的代价总和。其它路由协议定义了跳数,即分组在从源到目的的路途中必须经过的网络产品,如路由器的个数。可靠性,在路由算法中指网络链接的可依赖性(通常以位误率描述),有些网络链接可能比其它的失效更多,网路失效后,一些网络链接可能比其它的更易或更快修复。任何

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

7、度。负载可以用很多方面计算,包括CPU使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。通信代价是另一种重要的metric,尤其是有一些公司可能关系运作费用甚于性能。即使线路延迟可能较长,他们也宁愿通过自己的线路发送数据而不采用昂贵的公用线路。2典型的路由算法2.1 内部网关协议RIP路由信息协议RIP(RoutingInformationProtocol)是内部网关协议IGP中最先得到广泛应用的协议。它最初于1980年使用在XNS中,现在主要应用在Unix中。RIP是一种分布式的基于距离向量的路由选择协议,是因特网的标准协议,其最大优点就是简单。RIP属于一类被称为距离矢量路

8、由的路由算法,即达到目的地的最佳路径是条数最少的路径,然而,最佳路径也可以由除跳数以外的其他度量指标决定。RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录(因此,这是一组距离,即“距离向量”)。RIP不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由(即最短路由),即使还存在另一条高速(低时延)但路由器较多的路由。RIP具有一下特点:(1) 仅和相邻路由器交换信息。如果两个路由之间的通信不需要经过另一个路由器,那么这两个路由器就是相邻的。RIP协议规定,不相邻的路由器不交换信息。(2) 路由器交换的信息是当前本路由器所知道的全部信息,即自己的

9、路由表。也就是说,交换的信息是:“我到本自治系统中所有网络的(最短)距离,以及到每个网络应经过的下一跳路由器”。(3) 按固定的时间间隔交换路由信息,例如,每隔30秒。然后路由器根据收到的路由信息更新路由表。当网络拓扑发生变化时,路由器也及时向相邻路由器通告拓扑变化后的路由信息。RIP的缺点:超过15跳便无法到达。协议以跳数,即报文经过的路由器个数为衡量标准,并以此来选择路由,这一措施欠合理性。该路由协议应用到实际中时,很容易出现“计数到无穷大”的现象,这使得路由收敛很慢。RIP采用的是D-V算法(距离矢量路由算法),下面是D-V算法的优缺点。优点:算法简单。缺点:交换的路径信息量大路径信息传

10、播慢,使得路径信息可能不一致。收敛速度慢,存在无穷计算问题。不适合大型网络。随着OSPFKIS-IS的出现,许多人认为RIP已经过时了。但事实上RIP也有它自己的优点。对于小型网络,RIP就所占带宽而言开销小,易于配置、管理和实现并且RIP还在大量使用中。但RIP也有明显的不足,即当有多个网络时会出现环路问题。为了解决环路问题,IETF提出了分割范围方法,即路由器不可以通过它得知路由的接口去宣告路由。分割范围解决了两个路由器之间的路由环路问题,但不能防止3个或多个路由器形成路由环路。触发更新是解决环路问题的另一方法,它要求路由器在链路发生变化时立即传输它的路由表。这加速了网络的聚合,但容易产生

11、广播泛滥。总之,环路问题的解决需要消耗一定的时间和带宽。若采用RIP协议,其网络内部所经过的链路数不能超过15,这使得RIP协议不适于大型网络。2.2 Dijkstra算法Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。3小结

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论