路由算法及比较路由算法及比较丁杰丁杰 0821105708211057 通信通信 08010801路由算法 是网络层的核心问题，其主要功能：第一是为不同的原节 点和目的节点对 (SD)选择一条传输路径；第二是在路由选择好以后，将 用户消息正确地送到目的节点。一一、路路由由算算法法的的设设计计目目标标 路由算法通常具有下列设计目标的一个或多个： (1) 正确性：算法必须是正确的。即沿着各节点（交换机或路由器） 中路由表所指引的路由，分组一定能够最终达到目的节点（交换机或路 由器）。并且，分组到达目的节点后不会再向其他节点转发该分组。(2) 简洁性： 算法 设计 简洁，路由协议必须高效地提供其功能， 尽量减少软件和应用的开销。实现路由算法的软件必须运行在物理资 源有限的计算机上时高效尤其重要。 (3) 自适应性：又可称为“稳定性 ”或“鲁棒性 ” （robustness）。即算法能够适应网络业务量的拓扑的变化。当网络的 总业务量发生变化时，算法能自适应地改变路由。当节点链路出现故障 或修复后重新开始工作时，算法应能及时找到一条替换路径。 (4) 快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的 过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信 息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所 有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网 络中断。 (5) 公平性：算法对所有用户必须是等同的。例如，仅考虑使某一 对用户的端到端时延为最小，它们就可能占用相对较多的网络资源，这 样就明显不符合公平性的要求。 (6) 最优性：路由选择算法应该能提供最佳路由，从而使平均分组 时延最小、吞吐量最大或可靠性最高。这里“最佳 ”可以是有多个因 素决定的，如链路长度、数据率、链路容量、传输时延、节点缓冲区被 占用的程度、链路的差错率、分组的丢失率等。 一个路由算法应当在高的业务负荷的情况下，在保证 相同的实验 条件下，可以增加网络的通过量；在轻负荷和中等负荷情况下，可以 减少每一个分组的 平均时延 。在实际中，其实是没有完全符合以上所 有目标的路由算法的，也正是因为如此，在设计路由算法的时候，选择 其中的最重要的几个目标来设计路由算法，以尽可能达到最好的效果。二二、路路由由算算法法的的分分类类 路由算法的 分类方法有很多，根据基本分类要素的不同，可以从 不同的角度来对路由算法进行分类：1、静态与动态 静态路由算法很难算得上是算法，只不过是开始路由前由网管建立的 表映射。这些映射自身并不改变，除非网管去改动。使用静态路由的算 法较容易设计，在网络通信可预测及简单的网络中工作得很好。由于静 态路由系统不能对网络改变做出反映，通常被认为不适用于现在的大型、 易变的网络。 2、单路径与多路径 一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同， 这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显： 它们可以提供更好的吞吐量和可靠性。3、平坦与分层 一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦 的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路 由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干 路由器，然后在主干上传输直到它们到达目标所在区域，在这里，它们 从最后的主干路由器通过一个或多个非主干路由器到达终点。路由系统 通常设计有逻辑节点组，称为域、自治系统或区间。 在分层的系统中，一些路由器可以与其它域中的路由器通信，其它的 则只能与域内的路由器通信。在很大的网络中，可能还存在其它级别， 最高级的路由器构成了路由主干。 分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持 其通信。多数的网络通信发生在小组中（域）。因为域内路由器只需 要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的 路由算法，路由更新的通信量可以相应地减少。 4、主机智能与路由器智能 一些路由算法假定源结点来决定整个路径，这通常称为源路由。在源 路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳。 其它路由算法假定主机对路径一无所知，在这些算法中，路由器基于自 己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智 能，后者则为路由器具有此能力。 主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡。主 机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有 可能的路径，然后基于特定系统对“优化 ”的定义来选择最佳路径。 然而确定所有路径的行为通常需要很多的探索通信量和很长的时间。 5、域内与域间 一些路由算法只在域内工作，其它的则既在域内也在域间工作。这两 种算法的本质是不同的。其遵循的理由是优化的域内路由算法没有必要 也成为优化的域间路由算法。 6、链接状态与距离向量链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每 个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做Bellman-Ford 算法）中每个路由器发送路由表 的全部或部分，但只发给其邻居。也就是说，链接状态算法到处发送较 少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。由于链接状态算法聚合得较快，它们相对于距离算法产生路由环的倾 向较小。在另一方面，链接状态算法需要更多的CPU 和内存资源，因 此链接状态算法的实现和支持较昂贵。虽然有差异，这两种算法类型在 多数环境中都可以工作得很好。在选择路由算法时，可以通过考虑一下几个要素来确定： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。三三、常常用用的的路路由由算算法法（一）广域网中的路由算法1、广播 广播是通信网中最常用的方式，它用来传播公共信息、拓扑变 化信息（包括节点和链路工作变化和故障等信息）。广播分组 的接受节点通常是全网所有成员。如果结合搜节点仅为一个组或部 分网络节点，则成为多播。广播采用泛红路由、生成树的方式。这 种方法的缺点是 可能 会浪费大量的网络资源，并且广播节点需要 知道全网所有节点的路由信息。但它并不是向每个主机发送信息， 所以有同时会降低网络负载。在信息的确需要送达大部分的主 机时，广播的确是一种很好的方式。2、最短路由 许多实际的路由算法如RIP，OSPF 都是基于最短路径这一 概念。 分组交换网络的各种路由算法实际上都是建立在某种形式 的最小费用准则的基础上。而“费用 ”则是与人们所关注的某个 参数有关，可以使时延，可以是跳数。因此，“最短 ”取决于 对链路长度的定义，即“费用 ”的定义 下面来介绍几种最短路由算法： （a） 集中式最短路由算法 Bellman-Ford 算法 最短（h）行走（ walk）程度用表示。采用下面方h iD式迭代：1minhh iijjjDdD具体如下图所示：Dijsktra 算法 Dijsktra 算法的思想是通过逐步标定到达目的节点的路径 长度的方法来求解最短路径。在每一步过程中都会确定一 个（节点 i 到达目的节点 1 的最短路径长度估计）的确iD定值，称节点 i 为永久节点。 设集合 P 为永久节点的集合，则循环执行： minijj PDD 具体如下（两种算法比较）：在最坏的情况下， Dijkstra 算法的复杂度是，2()O N而 B-F 算法的复杂度是。3()O N（b） 分布式最短路由算法 距离矢量路由算法 距离矢量路由算法其实是B-F 算法的具体实现。 它最初用于 ARPANET 路由选择算法，也用于RIP 一 级 DECnet 和 Novelld 的 IPX 的早期版本中。但是它 对好消息的反应速度快，对坏消息的反应却很迟钝， 本称为 “计数至无穷问题 ”或“坏消息现象 ” ，可以 通过水平分裂算法来解决这个问题。链路状态路由算法距离矢量算法时延的度量仅仅是队列的长度且 收敛速度较慢。链路状态路由算法的思想很简单，有 以下五个部分组成： 1)发现邻节点，并获取他们的地址； 2)测量到达每一个邻节点的时延或成本（每个节点都可以 用 Dijsktra 算法来求最短路径） ； 3)构造一个分组来通告它所知道的所有路由信息； 4)发送该分组到所有其他节点；5)计算到所有其他节点的字段路径。3、 最佳路由 最短路由关心的是一个节点对之间的一条路径的选择和求解，因此他有 两方面缺陷：一是每对节点之间仅提供一条路由，限制了网络通过量； 二是适应业务变化的能力受到防止路由振荡的限制。最佳路由从全网范 围寻找所有可能的传输路径，从而使得发送阶段到达接收节点的信息流 的时延最小、流量最大，而不是局限于一条最短路径。（二） 互联网中的路由算法 随着网络的增大，IPv4 的地址已经不够用而网络正逐步转向 IPv6，这将导致路由膨胀。专家认为，在 2020 年路由膨胀的速度将超 过 CPU 和存储器的发展。虽然已经采用了分级路由选择的方法来减少 路由条目的数量，但是对于核心路由器的路由表的处理仍然不容乐观。 而分层本身会使得所形成的路由对于整个网络而言并不是最佳的。（三） Ad Hoc 网络中的路由算法 目前单播的 Ad Hoc 路由算法分为以下三种： （1） 平面路由算法 （2） 分层路由算法 （3） 地理位置辅助的路由算法路由算法的选择和发展关系着网络的质量，对于路由算法的研究一直都在 进行中。本次对路由算法有了初步的了解，希望以后能有机会进一步深入学习 研究。参考文献： 1 李建东，盛敏编著.通信网络基础.北京：高等教育出版社.2004 2 www.baidu.com