路由算法及比较(简单了解)

路由算法及比较丁杰08211057通信0801路由算法是网络层的核心问题，其主要功能：第一是为不同的原节点和目的节点对(SD)选择一条传输路径；第二是在路由选择好以后，将用户消息正确地送到目的节点。一、路由算法的设计目标路由算法通常具有下列设计目标的一个或多个：正确性：算法必须是正确的。即沿着各节点(交换机或路由器)中路由表所指引的路由，分组一定能够最终达到目的节点(交换机或路由器)。并且，分组到达目的节点后不会再向其他节点转发该分组。简洁性：算法设计简洁，路由协议必须高效地提供其功能，尽量减少软件和应用的开销。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。自适应性：又可称为“稳定性”或“鲁棒性”(robustness)。即算法能够适应网络业务量的拓扑的变化。当网络的总业务量发生变化时，算法能自适应地改变路由。当节点链路出现故障或修复后重新开始工作时，算法应能及时找到一条替换路径。快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。公平性：算法对所有用户必须是等同的。例如，仅考虑使某一对用户的端到端时延为最小，它们就可能占用相对较多的网络资源，这样就明显不符合公平性的要求。最优性：路由选择算法应该能提供最佳路由，从而使平均分组时延最小、吞吐量最大或可靠性最高。这里“最佳”可以是有多个因素决定的，如链路长度、数据率、链路容量、传输时延、节点缓冲区被占用的程度、链路的差错率、分组的丢失率等。一个路由算法应当在高的业务负荷的情况下，在保证相同的实验条件下，可以增加网络的通过量；在轻负荷和中等负荷情况下，可以减少每一个分组的平均时延。在实际中，其实是没有完全符合以上所有目标的路由算法的，也正是因为如此，在设计路由算法的时候，选择其中的最重要的几个目标来设计路由算法，以尽可能达到最好的效果。路由算法的分类路由算法的分类方法有很多，根据基本分类要素的不同，可以从不同的角度来对路由算法进行分类：1、 静态与动态静态路由算法很难算得上是算法，只不过是开始路由前由网管建立的表映射。这些映射自身并不改变，除非网管去改动。使用静态路由的算法较容易设计，在网络通信可预测及简单的网络中工作得很好。由于静态路由系统不能对网络改变做出反映，通常被认为不适用于现在的大型、易变的网络。2、 单路径与多路径一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同，这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显：它们可以提供更好的吞吐量和可靠性。3、 平坦与分层一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域，在这里，它们从最后的主干路由器通过一个或多个非主干路由器到达终点。路由系统通常设计有逻辑节点组，称为域、自治系统或区间。在分层的系统中，一些路由器可以与其它域中的路由器通信，其它的则只能与域内的路由器通信。在很大的网络中，可能还存在其它级别，最高级的路由器构成了路由主干。分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持其通信。多数的网络通信发生在小组中（域）因为域内路由器只需要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少。4、 主机智能与路由器智能一些路由算法假定源结点来决定整个路径，这通常称为源路由。在源路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳。其它路由算法假定主机对路径一无所知，在这些算法中，路由器基于自己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智能，后者则为路由器具有此能力。主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡。主机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优化"的定义来选择最佳路径。然而确定所有路径的行为通常需要很多的探索通信量和很长的时间。5、 域内与域间一些路由算法只在域内工作，其它的则既在域内也在域间工作。这两种算法的本质是不同的。其遵循的理由是优化的域内路由算法没有必要也成为优化的域间路由算法。6、 链接状态与距离向量链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。距离向量算法（也叫做Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。由于链接状态算法聚合得较快，它们相对于距离算法产生路由环的倾向较小。在另一方面，链接状态算法需要更多的CPU和内存资源,因此链接状态算法的实现和支持较昂贵。虽然有差异，这两种算法类型在多数环境中都可以工作得很好。在选择路由算法时，可以通过考虑一下几个要素来确定：1、 选择最短路由还是最佳路由；2、 通信子网是采用虚电路操作方式还是采用数据报的操作方式；3、 采用分布式路由算法还是采用集中式路由算法；4、 考虑关于网络拓扑、流量和延迟等网络信息的来源；5、 确定采用静态路由还是动态路由。三、常用的路由算法（一）广域网中的路由算法1、 广播广播是通信网中最常用的方式，它用来传播公共信息、拓扑变化信息（包括节点和链路工作变化和故障等信息）。广播分组的接受节点通常是全网所有成员。如果结合搜节点仅为一个组或部分网络节点，则成为多播。广播采用泛红路由、生成树的方式。这种方法的缺点是可能会浪费大量的网络资源，并且广播节点需要知道全网所有节点的路由信息。但它并不是向每个主机发送信息，所以有同时会降低网络负载。在信息的确需要送达大部分的主机时，广播的确是一种很好的方式。2、 最短路由许多实际的路由算法如RIP，OSPF都是基于最短路径这一概念。分组交换网络的各种路由算法实际上都是建立在某种形式的最小费用准则的基础上。而“费用”则是与人们所关注的某个参数有关，可以使时延，可以是跳数。因此，“最短”取决于对链路长度的定义，即“费用”的定义下面来介绍几种最短路由算法：（a）集中式最短路由算法Bellman-Ford算法

最短（＜h）行走（walk）程度用Dh表示。米用下面方i式迭代：Dh+i=min[d+Dh]i j ij j具体如下图所示：3-链舞快兰如图屮的标定所示忌多便用一条惟路的最矩爲径毘參使用3条链路的最短略徑(f)議终的嚴炬雜径3-链舞快兰如图屮的标定所示忌多便用一条惟路的最矩爲径毘參使用3条链路的最短略徑(f)議终的嚴炬雜径Dijsktra算法Dijsktra算法Dijsktra算法的思想是通过逐步标定到达目的节点的路径长度的方法来求解最短路径。在每一步过程中都会确定一个D（节点i到达目的节点1的最短路径长度估计）的确定值,i称节点i为永久节点。设集合P为永久节点的集合，则循环执行：D=minD'HPj具体如下（两种算法比较）：2对所有KJ)有d=dBellrwi-Fend算怯Dijkwtni算注jD$=2q二3 n严1,2.3,4.51D=4片｛2对所有KJ)有d=dBellrwi-Fend算怯Dijkwtni算注jD$=2q二3 n严1,2.3,4.51D=4片｛1,2)巳=3 D产2尸T3(cl在最坏的情况下，Dijkstra而B-F算法的复杂度是O(N3)。(b)分布式最短路由算法距离矢量路由算法距离矢量路由算法其实是B-F算法的具体实现。它最初用于ARPANET路由选择算法，也用于RIP一级DECnet和Novelld的IPX的早期版本中。但是它对好消息的反应速度快，对坏消息的反应却很迟钝，本称为“计数至无穷问题”或“坏消息现象”，可以通过水平分裂算法来解决这个问题。链路状态路由算法距离矢量算法时延的度量仅仅是队列的长度且收敛速度较慢。链路状态路由算法的思想很简单,有以下五个部分组成：发现邻节点，并获取他们的地址；测量到达每一个邻节点的时延或成本(每个节点都可以用Dijsktra算法来求最短路径)；构造一个分组来通告它所知道的所有路由信息；发送该分组到所有其他节点；5）计算到所有其他节点的字段路径。3、最佳路由最短路由关心的是一个节点对之间的一条路径的选择和求解，因此他有两方面缺陷：一是每对节点之间仅提供一条路由，限制了网络通过量；二是适应业务变化的能力受到防止路由振荡的限制。最佳路由从全网范围寻找所有可能的传输路径，从而使得发送阶段到达接收节点的信息流的时延最小、流量最大，而不是局限于一条最短路径。（二）互联网中的路由算法随着网络的增大，IPv4的地址已经不够用而网络正逐步转向IPv6，这将导致路由膨胀。专家认为，在2020年路由膨胀的速度将超过CPU和存储器的发展。虽然已经采用了分级路由选择的方法来减少路由条目的数量，但是对于核心路由器的路由表的处理仍然不容乐观。而分层本