路由算法分类比较

《路由算法分类比较》由会员分享，可在线阅读，更多相关《路由算法分类比较（11页珍藏版）》请在金锄头文库上搜索。

1、路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两 种主要的路由算法： 总体式路由算法和分散式路由算法。采用分散式路由算法 时，每个路由器只有与它直接相连的路由器的信息而没有网络中的每个路 由器的信息。这些算法也被称为 DV（距离向量）算法。采用总体式路由算法时， 每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这 些算法也被称为 LS（链路状态）算法。收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起 路由可用或不可用时，路

2、由器就发出更新信息。路由更新信息遍及整个网络， 引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的 路由算法会造成路径循环或网络中断。路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机 智能与路由器智能、域内与域间、链接状态与距离向量。链接状态算法（也叫做短路径优先算法）

3、把路由信息散布到网络的每个节 点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford 算法）中每个路由器发送路由表的 全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向 相邻的路由器发送较多的更新信息。 metric 是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。路由选择协议（路由选择协议（Routing protocol）当两台非直接连接的计算机需要经过几个网络通信时，通常就需要路由器。路 由器提供一种方法来开辟通过一个网状联结的路径。路由选择协议的任务是， 为路由器提供他们建立通

4、过网状网络最佳路径所需要的相互共享的路由信息。当一个计算机发送一个分组时，在网络上网络协议栈的每一层都附加一些信息 给它。在接收方的对等层协议可以读出这些信息。这些信息类似于通信会话的 某些部分。网络层的协议附加路由选择信息，这可能是通过一个网络的完整的 路径或是一些指示分组应该采用那条路径的优先值。发送方添加的网络层信息 只能由路由器或接收方的网络层协议读取。中继器和桥接器不能识别网络层信 息，只能传送和转发分组。Routing Algorithms 路由选择算法路由选择算法一个路由器设备可能有两个或多个可以发送数据分组的端口。它必须有一张转 发表（forwarding table）为每一个

5、端口标明一个特定地址。早期路由器不和 其它路由器交换网络上有关路由器的信息，因此，一个路由器通常沿着每条路 径发送数据分组，分组 充满网络，并且发送的一些分组在网络上无休止地循环。为了避免这些问题，路由器可以依赖人工编程把选择的路径输进设备。这 被称为静态路由选择。动态路由选择是一个更好的方式，它依靠路由器收集网 络信息和建立自己的路由表。路由器相互交换路由表，并且归并这些路由信息 建立更新的路由表。从其它路由器上获得的信息，提供到网络上目的站点的路 由中继（hop）数或与路径相关的费用。同时，每个路由选择设备上的路由表， 应该包含大体上一致的路由选择信息。 路由选择协议基本上有两类：距离向量

6、和链路状态，将在下面用两段文字 介绍这两类协议。 距离向量路由选择协议距离向量路由选择协议的分组传送路由是根据到接收站的 hop 数或费用决定的， 这些信息由各相邻的路由器提供。技术上通常都遵循 BellmanFord 算法。 一个路由器有几个端口，每个端口都有指定的价值，这些价值是由网络管 理员设定的。用使用一条线路实际费用的多少，作为一种衡量手段表明一条线 路比另一条好或坏。此外，相邻的那些路由器告诉它们把分组送往目的站要花 费的代价。路由器将端口的价值加到相邻路由器的价值上，如下面的例子： 端口 1 价值 10 + 相邻路由器价值 1727。 端口 2 价值 20 + 相邻路由器价值 5

7、25。 端口 3 价值 30 + 相邻路由器价值 737。 在这种情况下，路由器将通过端口 2 传送分组，因为它表明到接收站的代 价最少。假如有必要，用邻接端口 2 的路由器再计算到下一个路由器的路径价 值。 路由信息，如下一个 hop 的地址等都存在表中，并且路由器大约每隔 30 秒 互相交换表。初始时，每一个网络只知道直接相连的路由器。当一个路由器得 到一张表，它将表项与自己的表进行比较。根据这些信息，它用新增路由或删 除路由来修改表。表中信息包含：网络号；端口号；价值度量；下一个 hop 的 地址。 价值度量是路由器向前传送分组到网中下一个路由器时选择路径所用的量 值。通用距离向量路由选

8、择协议有： 路由选择信息协议（RIP）是一个首先在 Xerox 网络系统（XNS）中实现， 而后又在 Novell 的 NetWare 中实现的距离向量路由选择协议。 内部网关路由选择协议（IGRP）是由 Cisco 开发的距离向量路由选择协议。路由选择表维护协议（RTMP）是一个在两个 AppleTalk 区中选取最佳路径 的 Apple 协议，大约每 10 秒广播一次。 距离向量路由选择不适合于有几百个路由器的大型网或经常要更新的网。 在大型网中，表的更新过程可能过长，以至于最远的路由器的选择表不大可能 与其它表同步更新。在这种情况下，链路状态路由选择更可取些。另外，链路 状态协议能够为安

9、全起见把机密信息 隔离在特殊区域，或避开网上正在进行计 算机辅助设计（CAD）、多媒体通讯等拥挤区域。并且，路由选择信息表在必要 时进行交换而不是规律性地交换，这样可以减少网络上的信息流量。链路状态路由选择链路状态路由选择比距离向量路由选择需要更强的处理能力，但它可以对路由 选择过程提供更多的控制和对变化响应更快。路由选择可以基于避开拥塞区、 线路的速度、线路的费用或各种优先级别。Dijkstra 算法用于计算路由，根据 如下： 分组到达目的站经过的路由器数量，这叫做路由中继（hop），并且 hop 数 越少越好。 局域网间传输线路的速度。有些路由使用低速异步连接，而另一些路由使 用高速数字链

10、路。 信息拥塞将造成延迟。如果一台工作站传送一个大文件，路由器可以通过 不同的路径发送分组以避免交通阻塞。路由的费用路由的费用路由的费用，网络管理员定义的一个度量，通常是根据传输介质确定的。最便 宜的路径可能不是最快的，但对某些类型的传输却更为可取。 最常用的链路状态路由选择协议是优先开放最短路径（OSPF），它和 OSI 的中 间系统到中间系统（ISIS）是类似的。OSPF 的原型是 Proten 开发的，是从 OSIISIS 的一个早期版本中派生出来的。 OSPF 在 Internet 和 TCPIP 网上 IP 通信的路由选择中使用。ISIS 既可在 IP 通信中使用，也可在 OSI 通

11、信中 使用。OPSF 路由选择表路由选择表OPSF 路由选择表仅当在需要时更新，而不是定时更换。这有效地减少了通信 流量和节省了网络带宽。通过网络的路径由上述标准选定。一个网络管理员可 以根 据信息传送的类型编制通过网络的路径。例如，当线路有较高数据传输率 时，即使通过网络的那条路径有较多的 hop 数也是很可取的；另一方面，对于 不大重要的 信息将安排在低速低值的线路上传送。Autonomous Environments 自治环境自治环境Internet 路由选择（TCPIP）和 OSI 路由选择使用了一个自治系统（AS）或 管理区域（AD）的概念，可以简单地理解成区域 （domains）。

12、一个区域是一 些使用相同路由选择协议的主机和路由器的集合，如图 R11 中所示，它们使 用相同的路由选择协议和由单一机构管理。换句话说，一个区域可以是一所大 学或其它机构管理的一个互联网。例如 Internet 是一个由教育部门、政府机关 和各个公司管理的自治系统链接起来的互联网络。 每个机构都有自己的内部网络，通过外部网关与 Internet 网连接 （Internet 网以前把路由器称作网关，但现在已把它们叫做路由器了）。 Internet 有内部网关协议和外部网关协议。OSI 协议也使用了自治系统的概念， 但在一个区域内的路由选择称为域内路由选择，区域之间的路由选择称为域间 路由选择。内

13、部域内协议内部域内协议有许多种内部网关协议，并有几种在 Internet 网上常用，这些协议已在条目 “AppleTalk 路由选择”，“Internet 路由选择”和“OSI 的路由选择”中讨 论。 地址解析协议（ARP）是一个 Internet（TCPIP）协议，它为内部路由器传递 数据报提供了一种方法。 路由选择信息协议（RIP）是一种距离向量路由选择协议。 优先开放最短路径（OSPF）是一种链路状态路由选择协议，它优于 RIP。OSPF 是 Internet 网中最常用的内部网关协议，但 OSI ISIS 协议也用于 Internet。 端系统到中间系统（ESIS）是 OSI 公布的一

14、种协议，它帮助端系统（如用户 的计算机）寻找定位路由器，并提供一种方法使路由器告知端系统（ES）它们 的存在。 中间系统到中间系统（ISIS）也是 OSI 的一种路由选择协议，它为一个域内 两个路由器之间传送信息分组提供动态路由。ISIS 是一种链接状态协议。 内部网关路由选择协议（IGRP）是 Cisco 开发的一种距离向量路由选择协议。外部域间协议外部域间协议在自治域的边界是路由器（以前在 Internet 网上被称为网关）。这些路由器和 其它路由器用外部协议或 Internet 术语的外部网关协议（EGP）交换信息。 外部网关协议（EGP）是 Internet 上最初的域间路由选择协议。

15、现在它已被周 边网关协议（BGP）取代了。支持 EGP 的路由器也必须支持 BGP。 周边网关协议（BGP）提供有关相邻点可达性信息。BGP 可以减低带宽需求，这 是因为路由选择信息是增量交换的，而不是在路由器间发送路由选择数据库信 息。BGP 也提供了基于策略的算法，使网络管理者对路由选择有较多的控制权， 例如对某些信息传输实行优化的能力。 域间路由选择协议（IDRP）是一种 OSI 无连接分组（CLNP）的 OSI 路由选择协 议。IDRP 包含路由选择的策略，但它不大可能在 Internet 上代替 BGP。IDRP 可用一种协议进行 IP 和 CLNP 的域间路由选择来增加对 IP 的

16、支持。距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算 法(Ford-FulkersonAlgorithm)，其被距离向量协议作为一个算法其被距离向量协议作为一个算法，如 RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它 是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。 在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的 量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直 接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包 到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个 为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数 据包的数量，等等。在距离向量路由算法中，相邻路由器之间周期性地相互交 换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相 互通知有关变更信息。路由协