《LS路由算法与DV路由算法的比较[1]》由会员分享，可在线阅读，更多相关《LS路由算法与DV路由算法的比较[1]（10页珍藏版）》请在金锄头文库上搜索。
1、LS 路由算法与 DV 路由算法的比较徐雄博 20050830226 信息安全 2 班摘要：当一个分组要从源主机带目的主机时，网络层必须确定从发送方到接受方的分组所采用的路径。选路算法的目的就是给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径，即具有最低费用的路径。根据算法是全局性的还是分散式的，选路算法可分为两种：具有全局状态信息的链路状态算法（link state algorithm, LS）以及分散式的选路算法距离向量算法（ distance-vector, DV） 。本文将通过对这两种算法的比较来找出两个算法在不同的情况下，每种算法的适应环境。
2、Abstraction： When a packet want to rount from source host to destinating host, the network layer must nonetheless determine the path that packets take from senders to receivers. The purpose of a routing algorithm is that given a set of routers, with links connecting the router, a routing algorithm f
3、inds a “good” path from source router to destination router. Typically, a good path is one that has the least cost. According to whether the algorithms are global or decentralized, the routing algorithm can be classified into two types: algorithms with global state information are offen referred to
4、as link-state (LS) algorithms, and the decentralized routing algorithm called a distance-vector (DV) algorithm. Through this passage we will find the environment which suits each algorithm most.关键词：路由算法 RIP 路由协议 OSPF 路由协议 LS 路由算法 DV 路由算法一、 概述随着社会的发展，计算机技术已经越来越普及。不同的网络层提供的不管是数据服务还是虚电路服务，网络层都必须确定为从发送方
5、到接受方的分组所采用的路径。我们看到选路的工作是从发送方到接受方通过路由器的网络决定的好路径。选路算法的目的是简单的，即给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径， 。通常一条好的路径指具有最低费用的路径。对选路算法分类的一种方法是根据该算是全局性的还是分散式的可分为全局选路算法（global routing algorithm）和分散式选路算法（decentralized routing algorithm） 。1 而根据这两个路由选路算法，历史上曾有两个选路协议曾被广泛用于 Internet 上自治系统内的选路：选路信息协议（Routing
6、Information Protocol，RIP）与开放最短路径优先（Open Shortest Path First， OSPF）2。二、路由算法路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标：（1）最优化：指路由算法选择最佳路径的能力。 （2）简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能。（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考
7、验，并在各种网络环境下被证实是可靠的。 （4）快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息 遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 （5）灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。 路由算法按照种类可分为以下几种：静态和动态、单路和多路、平等和分级、源路由和透明路由、域内和域间、链路状态和距离向量。前面几种的特点与字面意思基本一致
8、，下面着重介绍链路状态和距离向量算法。3三、链路状态算法（link state algorithm, LS）链路状态算法（也称最短路径算法）发送路由信息到互联网上所有的结点，然而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。链路-状态路由选择算法的基本思想很简单，可以分成以下五个部分叙述： 每个节点必须找出它的所有邻居当一个节点启动后，通过在每一条点到点的链路上发送一个特殊的 HELLO 报文，并通过链路另一端的节点发送一个应答报文告诉它自己是谁。 每个节点测量到它的每个邻居的时延或其他参数链路-状态路由选择算法要求每个节点都知道到它的每个邻居的时延。测量这种时延的最直接的
9、方法是在它们之间的链路上发送一个特殊的 ECHO 响应报文，并且要求对方收到后立即再将其发送回来。将测量得到的来回时间除以 2，即可得到一个比较合理的估计。为了得到更准确的结果，可以将测试重复多次，取平均值。 建立链路-状态报文收集齐了用于交换的信息后，下一步就为每一个节点建立一个包含所有数据的报文。报文以发送者的标识符开始，随后为顺序号以及它的所有邻居的列表。对于每一个邻居，给出到此邻居的时延。建立链路-状态报文很容易，困难是决定何时建立它们。一种可行的方法是每隔一段规律的时间间隔周期性地建立它们。另一种可行的方法是当节点检测到了某些重要事件的发生时建立它们。例如，一条链路或一个邻居崩溃或恢
10、复时，建立它们。 分发链路-状态报文基本的分发算法是使用顺序号的洪泛法。这种分发算法由于循环使用顺序号、某个节点曾经崩溃或某个顺序号曾经被误用过等原因，可能会使不同的节点使用不同版 本的拓扑结构，这将导致不稳定、循环、到达不了目的机器及其他问题。为了防止这类错误的发生，需要在每个报文中包含一个年龄域，年龄每秒减 1，当年龄减到 0 时，丢弃此报文。 计算新路由一旦一个节点收集齐了所有来自于其他节点的链路-状态报文，它就可以据此构造完整的网络拓扑结构图，然后使用 Dijkstra 算法在本地构造到所有可能的目的地的最短通路。链路-状态路由选择算法具有各节点独立计算最短通路、能够快速适应网络变化、
11、交换的路由信息少等优点，但相对于距离向量路由选择算法，它较复杂、难以实现。4四、距离向量路由选择算法(Distance Vector，DV)各节点周期性地向所有相邻节点发送路由刷新报文，报文由一组(V，D)有序数据对组成，V 表示该节点可以到达的节点，D 表示到达该节点的距离(跳数)。收到路由刷新报文的节点重新计算和修改它的路由表。距离向量路由算法具有简单，易于实现的优点。但它不适用于路由剧烈变化的或大型的网络环境。因为某个节点的路由变化像波动一样从相邻节点传播出去，其过程 是非常缓慢的，称之为“慢收敛”。因此，在距离向量路由选择算法的路由刷新过程中，可能会出现路由不一致问题。距离向量路由选择
12、算法的另一个缺陷是它需要 大量的信息交换，但很多都可能是与当前路由刷新无关的。4五、LS 与 DV 的比较1.报文复杂性。 LS 算法要求每个节点知道网络中每条链路的费用。这就要求要发送O(|N|E|)个报文。而且无论何时一条链路的费用改变，必须向所有节点发送新的链路费用。DV 算法要求在每次迭代时，在两个直接相连邻居之间交换报文。当链路费用改变时，DV 算法仅当在新的链路费用导致与该链路相连节点的最低费用路径发生改变时，才传播已改变的链路费用。2.收敛速度。 LS 算法的实现是一个要求 O(|N|E|)个报文的 算法。DV 算法收敛)|(2NO较慢。且在收敛时会遇到选路环路。3.健壮性。 L
13、S 算法下，路由计算是有些是孤立的，提供了一定程度的健壮性。DV 算法中一个不正确的节点计算值会扩展到整个网络。六、路由协议根据是否在一个自治域内部使用，动态路由协议分为内部网关协议（IGP，Internal Gateway Protocol）和外部网关协议（EGP，External Gateway Protocol）。常用路由协议（见表）表一5（1） 路由信息协议（RIP， Routing Information Protoco）RIP 用更新（UNPDATES）和请求（ REOUESTS）两种分组传输路由信息。更新信息用于广播路由表，其中每一项由两部分组成：局域网上能达到的 IP 地址和与
14、该网络的距离。请求信息用于寻找网络上能发出 RIP 报文的其他设备。RIP 使用 UDP 作为它的传输协议，端口是 520。通过广播报文来交换路由信息，主要传递路由信息（路由表）来广播路由。每隔 30 秒，广播一次路由表，维护相邻 路由器的关系，同时根据收到的路由表计算自己的路由表。在每 30 秒发送一次路由信息更新时。RIP 提供跳跃计数 (hop count)作为尺度来衡量路由距离，跳跃计数是一个包到达目标所必须经过的路由器的数目。使用距离来决定最佳路径，如通过路由跳数来衡量。到这个路由器 具有最低跳数的路径是被选中的路径。如果首选的路径不能正常工作，那么具有较高跳数的路径被作为备份。除到
15、达目的地的最佳路径外，任何其它信息均予以丢 弃。同时路由器也把所收集的路由信息用 RIP 协议通知相邻的其它路由器。这样，正确的路由信息逐渐扩散到了全网。6其优点是：它简单、可靠，便于配置，障碍修复非常容易。其缺点是： 没有子网地址的概念，无法区分子网号；RIP 协议的原始版本不能应用可变长子网屏蔽（VLSM ，Variable Length Subnet Masks） ，因此不能分割地址空间以最大效率地应用有限的 IP 地址。 路由度量忽略了吞吐率、往返时间、可靠性、实际距离、通信延迟、网络速度及带宽等一些应该考虑的因素或性能。如果到相同目标有二个不等速或不同带宽 的路由器，但跳跃计数相同，
16、则 RIP 认为两个路由是等距离的。RIP 协议的另一个基本问题是，当选择路径时它忽略了连接速度问题。例如，如果一条由所有快 速以太网连接组成的路径比包含一个 10Mbps 以太网连接的路径远一个跳数，具有较慢 10Mbps 以太网连接的路径将被选定作为最佳路径。 支持网络大小有限，只适用于小型网络。RIP 最多支持的跳数为 15，即在源和目的网间所要经过的最多路由器的数目为 15，跳数 16 表示不可达。假定如 果从网络的一个终端到另一个终端的路由跳超过 15 个，那么就认为一定牵涉到了循环。因此当一个路径达到 16 跳，将被认为是达不到的。对于规模较大的网络， 或具有多余路径的网络，应该考虑使用其它路由协议。 而且 RIP 每隔 30 秒一次的路由信息广播也是造成网络的广播风暴的重要原因之一。于 1993 年，RIP2 是在 RFC1388 中对 RIP 定义进行完善扩充而产生的第二版本，它支持 IPv6（Internet Protocol Version 6）规范的
