LS路由算法与DV路由算法的比较

LS路由算法与DV路由算法的比较徐雄博20050830226信息安全2班摘要：当一个分组要从源主机带目的主机时，网络层必须确定从发送方到接受方的分组所采用的路径。选路算法的目的就是给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径，即具有最低费用的路径。根据算法是全局性的还是分散式的，选路算法可分为两种：具有全局状态信息的链路状态算法（linkstatealgorithm,LS）以及分散式的选路算法距离向量算法（distance-vector,DV）。本文将通过对这两种算法的比较来找出两个算法在不同的情况下，每种算法的适应环境。Abstraction：Whenapacketwanttorountfromsourcehosttodestinatinghost,thenetworklayermustnonethelessdeterminethepaththatpacketstakefromsenderstoreceivers.Thepurposeofaroutingalgorithmisthatgivenasetofrouters,withlinksconnectingtherouter,aroutingalgorithmfindsa“good”pathfromsourceroutertodestinationrouter.Typically,agoodpathisonethathastheleastcost.Accordingtowhetherthealgorithmsareglobalordecentralized,theroutingalgorithmcanbeclassifiedintotwotypes:algorithmswithglobalstateinformationareoffenreferredtoaslink-state(LS)algorithms,andthedecentralizedroutingalgorithmcalledadistance-vector(DV)algorithm.Throughthispassagewewillfindtheenvironmentwhichsuitseachalgorithmmost.关键词：路由算法RIP路由协议OSPF路由协议LS路由算法DV路由算法一、概述随着社会的发展，计算机技术已经越来越普及。不同的网络层提供的不管是数据服务还是虚电路服务，网络层都必须确定为从发送方到接受方的分组所采用的路径。我们看到选路的工作是从发送方到接受方通过路由器的网络决定的好路径。选路算法的目的是简单的，即给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径，。通常一条好的路径指具有最低费用的路径。对选路算法分类的一种方法是根据该算是全局性的还是分散式的可分为全局选路算法（globalroutingalgorithm）和分散式选路算法（decentralizedroutingalgorithm）。[1]而根据这两个路由选路算法，历史上曾有两个选路协议曾被广泛用于Internet上自治系统内的选路：选路信息协议（RoutingInformationProtocol，RIP）与开放最短路径优先（OpenShortestPathFirst，OSPF）[2]。二、路由算法路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标：——（1）最优化：指路由算法选择最佳路径的能力。——（2）简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能。——（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。——（4）快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。——（5）灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。路由算法按照种类可分为以下几种：静态和动态、单路和多路、平等和分级、源路由和透明路由、域内和域间、链路状态和距离向量。前面几种的特点与字面意思基本一致，下面着重介绍链路状态和距离向量算法。[3]三、链路状态算法（linkstatealgorithm,LS）链路状态算法（也称最短路径算法）发送路由信息到互联网上所有的结点，然而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。链路-状态路由选择算法的基本思想很简单，可以分成以下五个部分叙述：⑴每个节点必须找出它的所有邻居当一个节点启动后，通过在每一条点到点的链路上发送一个特殊的HELLO报文，并通过链路另一端的节点发送一个应答报文告诉它自己是谁。⑵每个节点测量到它的每个邻居的时延或其他参数链路-状态路由选择算法要求每个节点都知道到它的每个邻居的时延。测量这种时延的最直接的方法是在它们之间的链路上发送一个特殊的ECHO响应报文，并且要求对方收到后立即再将其发送回来。将测量得到的来回时间除以2，即可得到一个比较合理的估计。为了得到更准确的结果，可以将测试重复多次，取平均值。⑶建立链路-状态报文收集齐了用于交换的信息后，下一步就为每一个节点建立一个包含所有数据的报文。报文以发送者的标识符开始，随后为顺序号以及它的所有邻居的列表。对于每一个邻居，给出到此邻居的时延。建立链路-状态报文很容易，困难是决定何时建立它们。一种可行的方法是每隔一段规律的时间间隔周期性地建立它们。另一种可行的方法是当节点检测到了某些重要事件的发生时建立它们。例如，一条链路或一个邻居崩溃或恢复时，建立它们。⑷分发链路-状态报文基本的分发算法是使用顺序号的洪泛法。这种分发算法由于循环使用顺序号、某个节点曾经崩溃或某个顺序号曾经被误用过等原因，可能会使不同的节点使用不同版本的拓扑结构，这将导致不稳定、循环、到达不了目的机器及其他问题。为了防止这类错误的发生，需要在每个报文中包含一个年龄域，年龄每秒减1，当年龄减到0时，丢弃此报文。⑸计算新路由一旦一个节点收集齐了所有来自于其他节点的链路-状态报文，它就可以据此构造完整的网络拓扑结构图，然后使用Dijkstra算法在本地构造到所有可能的目的地的最短通路。链路-状态路由选择算法具有各节点独立计算最短通路、能够快速适应网络变化、交换的路由信息少等优点，但相对于距离向量路由选择算法，它较复杂、难以实现。[4]四、距离向量路由选择算法(DistanceVector，DV)各节点周期性地向所有相邻节点发送路由刷新报文，报文由一组(V，D)有序数据对组成，V表示该节点可以到达的节点，D表示到达该节点的距离(跳数)。收到路由刷新报文的节点重新计算和修改它的路由表。距离向量路由算法具有简单，易于实现的优点。但它不适用于路由剧烈变化的或大型的网络环境。因为某个节点的路由变化像波动一样从相邻节点传播出去，其过程是非常缓慢的，称之为“慢收敛”。因此，在距离向量路由选择算法的路由刷新过程中，可能会出现路由不一致问题。距离向量路由选择算法的另一个缺陷是它需要大量的信息交换，但很多都可能是与当前路由刷新无关的。[4]五、LS与DV的比较1.报文复杂性。LS算法要求每个节点知道网络中每条链路的费用。这就要求要发送O(|N||E|)个报文。而且无论何时一条链路的费用改变，必须向所有节点发送新的链路费用。DV算法要求在每次迭代时，在两个直接相连邻居之间交换报文。当链路费用改变时，DV算法仅当在新的链路费用导致与该链路相连节点的最低费用路径发生改变时，才传播已改变的链路费用。2.收敛速度。LS算法的实现是一个要求O(|N||E|)个报文的)|(|2NO算法。DV算法收敛较慢。且在收敛时会遇到选路环路。3.健壮性。LS算法下，路由计算是有些是孤立的，提供了一定程度的健壮性。DV算法中一个不正确的节点计算值会扩展到整个网络。六、路由协议根据是否在一个自治域内部使用，动态路由协议分为内部网关协议（IGP，InternalGatewayProtocol）和外部网关协议（EGP，ExternalGatewayProtocol）。常用路由协议（见表１）表一[5]（1）路由信息协议（RIP，RoutingInformationProtoco）RIP用更新（UNPDATES）和请求（REOUESTS）两种分组传输路由信息。更新信息用于广播路由表，其中每一项由两部分组成：局域网上能达到的IP地址和与该网络的距离。请求信息用于寻找网络上能发出RIP报文的其他设备。RIP使用UDP作为它的传输协议，端口是520。通过广播报文来交换路由信息，主要传递路由信息（路由表）来广播路由。每隔30秒，广播一次路由表，维护相邻路由器的关系，同时根据收到的路由表计算自己的路由表。在每30秒发送一次路由信息更新时。RIP提供跳跃计数(hopcount)作为尺度来衡量路由距离，跳跃计数是一个包到达目标所必须经过的路由器的数目。使用距离来决定最佳路径，如通过路由跳数来衡量。到这个路由器具有最低跳数的路径是被选中的路径。如果首选的路径不能正常工作，那么具有较高跳数的路径被作为备份。除到达目的地的最佳路径外，任何其它信息均予以丢弃。同时路由器也把所收集的路由信息用RIP协议通知相邻的其它路由器。这样，正确的路由信息逐渐扩散到了全网。[6]其优点是：它简单、可靠，便于配置，障碍修复非常容易。其缺点是：①．没有子网地址的概念，无法区分子网号；RIP协议的原始版本不能应用可变长子网屏蔽（VLSM，VariableLengthSubnetMasks），因此不能分割地址空间以最大效率地应用有限的IP地址。②．路由度量忽略了吞吐率、往返时间、可靠性、实际距离、通信延迟、网络速度及带宽等一些应该考虑的因素或性能。如果到相同目标有二个不等速或不同带宽的路由器，但跳跃计数相同，则RIP认为两个路由是等距离的。RIP协议的另一个基本问题是，当选择路径时它忽略了连接速度问题。例如，如果一条由所有快速以太网连接组成的路径比包含一个10Mbps以太网连接的路径远一个跳数，具有较慢10Mbps以太网连接的路径将被选定作为最佳路径。③．支持网络大小有限，只适用于小型网络。RIP最多支持的跳数为15，即在源和目的网间所要经过的最多路由器的数目为15，跳数16表示不可达。假定如果从网络的一个终端到另一个终端的路由跳超过15个，那么就认为一定牵涉到了循环。因此当一个路径达到16跳，将被认为是达不到的。对于规模较大的网络，或具有多余路径的网络，应该考虑使用其它路由协议。④．而且RIP每隔30秒一次的路由信息广播也是造成网络的广播风暴的重要原因之一。于1993年，RIP2是在RFC1388中对RIP定义进行完善扩充而产生的第二版本，它支持IPv6（InternetProtocolVersion6）规范的128位地址；通过引入子网屏蔽与每一路由广播信息一起使用实现了对可变长子网掩码（VLSM，VariableLengthSubnetMasks）的支持；除广播外还增加了多播功能，可以减少不收听报文的主机负载；提供简单的鉴别机制以及路由汇总功能。在有多重路径到相同目标的网络中，RIP确定使用一条可选择的路径将花费许多时间。在RIP协议认识到路径不能达到前，它被设为等待，直到它已错过6次更新，总共180秒时间。然后，在使用新路径更新路由表前，它等待另一个可行路径的下一个信息的到来。这意味着在备份路径被使用前至少经过了3分钟，这对于多数应用程序超时是相当长的时间。[5]（2）开放式最短路优先路由信