路由算法分类比较

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

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

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

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

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

6、路由选择协议的分组传送路由是根据到接收站的hop数或费用决定的， 这些信息由各相邻的路由器提供。技术上通常都遵循Bellman-Ford算法。一个路由器有几个端口，每个端口都有指定的价值，这些价值是由网络管理 员设定的。用使用一条线路实际费用的多少，作为一种衡量手段表明一条线路比 另一条好或坏。此外，相邻的那些路由器告诉它们把分组送往目的站要花费的代 价。路由器将端口的价值加到相邻路由器的价值上，如下面的例子：端口 1价值10 +相邻路由器价值17 = 27。端口 2价值20 +相邻路由器价值5 = 25。端口 3价值30 +相邻路由器价值7 = 37。在这种情况下，路由器将通过端口2传送分组

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

8、的距离向量路由选择协议。内部网关路由选择协议（IGRP）是由Cisco开发的距离向量路由选择协议。路由选择表维护协议（RTMP）是一个在两个AppleTalk区中选取最佳路径的 Apple协议，大约每10秒广播一次。距离向量路由选择不适合于有几百个路由器的大型网或经常要更新的网。在 大型网中，表的更新过程可能过长，以至于最远的路由器的选择表不大可能与其 它表同步更新。在这种情况下，链路状态路由选择更可取些。另外，链路状态协 议能够为安全起见把机密信息隔离在特殊区域，或避开网上正在进行计算机辅 助设计（CAD）、多媒体通讯等拥挤区域。并且，路由选择信息表在必要时进行 交换而不是规律性地交换，这样

9、可以减少网络上的信息流量。链路状态路由选择比距离向量路由选择需要更强的处理能力，但它可以对路由选 择过程提供更多的控制和对变化响应更快。路由选择可以基于避开拥塞区、线路 的速度、线路的费用或各种优先级别。Dijkstra算法用于计算路由，根据如下：分组到达目的站经过的路由器数量，这叫做路由中继（hop），并且hop数 越少越好。局域网间传输线路的速度。有些路由使用低速异步连接，而另一些路由使用 高速数字链路。信息拥塞将造成延迟。如果一台工作站传送一个大文件，路由器可以通过不 同的路径发送分组以避免交通阻塞。路由的费用路由的费用，网络管理员定义的一个度量，通常是根据传输介质确定的。最便宜 的路径

10、可能不是最快的，但对某些类型的传输却更为可取。最常用的链路状态路由选择协议是优先开放最短路径（OSPF），它和OSI的中间 系统到中间系统（IS IS）是类似的。OSPF的原型是Proten开发的，是从OSIIS -IS的一个早期版本中派生出来的。OSPF在Internet和TCP / IP网上IP通信 的路由选择中使用。IS IS既可在IP通信中使用，也可在OSI通信中使用。OPSF路由选择表OPSF路由选择表仅当在需要时更新，而不是定时更换。这有效地减少了通信 流量和节省了网络带宽。通过网络的路径由上述标准选定。一个网络管理员可以 根据信息传送的类型编制通过网络的路径。例如，当线路有较高数

11、据传输率时， 即使通过网络的那条路径有较多的hop数也是很可取的；另一方面，对于不大重 要的信息将安排在低速低值的线路上传送。Autonomous Environments 自治环境Internet路由选择（TCP/IP）和OSI路由选择使用了一个自治系统（AS）或管 理区域（AD）的概念，可以简单地理解成区域（domains）。一个区域是一些使 用相同路由选择协议的主机和路由器的集合，如图R-11中所示，它们使用相同 的路由选择协议和由单一机构管理。换句话说，一个区域可以是一所大学或其它 机构管理的一个互联网。例如Internet是一个由教育部门、政府机关和各个公 司管理的自治系统链接起来的

12、互联网络。每个机构都有自己的内部网络，通过外部网关与Internet网连接（Internet 网以前把路由器称作网关，但现在已把它们叫做路由器了）。Internet有内部 网关协议和外部网关协议。OSI协议也使用了自治系统的概念，但在一个区域内 的路由选择称为域内路由选择，区域之间的路由选择称为域间路由选择。内部/域内协议有许多种内部网关协议，并有几种在Internet网上常用，这些协议已在条目 “AppleTalk路由选择”，“Internet路由选择”和“OSI的路由选择”中讨论。地址解析协议（ARP）是一个Internet （TCP / IP）协议，它为内部路由器传递 数据报提供了一种方

13、法。路由选择信息协议（RIP）是一种距离向量路由选择协议。优先开放最短路径（OSPF）是一种链路状态路由选择协议，它优于RIP。OSPF 是Internet网中最常用的内部网关协议，但OSI IS-IS协议也用于Interneto 端系统到中间系统（ES-IS）是OSI公布的一种协议，它帮助端系统（如用户的 计算机）寻找定位路由器，并提供一种方法使路由器告知端系统旧S）它们的存 在。中间系统到中间系统（IS-IS）也是OSI的一种路由选择协议，它为一个域内两 个路由器之间传送信息分组提供动态路由。IS-IS是一种链接状态协议。内部网关路由选择协议（IGRP）是Cisco开发的一种距离向量路由选

14、择协议。外部/域间协议在自治域的边界是路由器（以前在Internet网上被称为网关）。这些路由器和 其它路由器用外部协议或Internet术语的外部网关协议（EGP）交换信息。外部网关协议（EGP）是Internet上最初的域间路由选择协议。现在它已被周边 网关协议（BGP）取代了。支持EGP的路由器也必须支持BGP。周边网关协议（BGP）提供有关相邻点可达性信息。BGP可以减低带宽需求，这 是因为路由选择信息是增量交换的，而不是在路由器间发送路由选择数据库信 息。BGP也提供了基于策略的算法，使网络管理者对路由选择有较多的控制权， 例如对某些信息传输实行优化的能力。域间路由选择协议(IDRP

15、)是一种OSI无连接分组(CLNP)的OSI路由选择协议。 IDRP包含路由选择的策略，但它不大可能在Internet上代替BGP。IDRP可用一 种协议进行IP和CLNP的域间路由选择来增加对IP的支持。距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法 (Ford-FulkersonAlgorithm)，其被距离向量协议作为一个算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个 一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离 表中的这个信息是根据

16、临近接点信息的改变而时时更新的。表中数据的量和在网 络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连 的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上 的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。 这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等 等。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备 份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。路由协议路曜提供了异构网互联的机制，实现将一个网络的数据包发送到另一个网 络。而路由就是指导IP数据包发送的路径

17、信息。路由协议就是在路由指导IP 数据包发送过程中事先约定好的规定和标准。路由协议通过在路由器之间共享路 由信息来支持可路由协议。路由信息在相邻路由器之间传递，确保所有路由器知 道到其它路由器的路径。总之，路由协议创建了路由表，描述了网络拓扑结构 路由协议与路由器协同工作，执行路由选择和数据包转发功能。路由协议主要运行于路由器上，路由协议是用来确定到达路径的，它包括 RIP,IGRP,EIGRP,OSPF。起到一个地图导航，负责找路的作用。它工作在网络层 路由选择协议主要是运行在路由器上的协议，主要用来进行路径选择。routed protocol (可被路由的协议)和routing proto

18、col (路由协议)经常被 混淆。可被路由的协议(Routed Protocol)由路由协议(Routing Protocol)传 输，前者亦称为网络协议。这些网络协议执行在源与目的设备的用户应用间通信 所需的各种功能。网络协议发生在OSI参考模型的上四层：传输层、会话层、表 示层和应用层。routed protocol 在网络中被路由，例如 IP、DECnet、AppleTalk、Novell NetWare、 OSI、Banyan VINES 和 Xerox Network System(XNS)。而路由协议是实现路由算 法的协议，简单地说，它给网络协议做导向。路由协议如：IGRP、EIG

19、RP、OSPF、 EGP、BGP、IS-IS 及 RIP 等。路由协议作用是产生路由表，维护路由表。路由协议是指为可路由协议提供路由选择服务的协议，路由协议的服务对象是可 路由协议，路由器节点通过路由协议实现路由表的自动维护，目前主要的路由协 议包括 RIP,IGRP,OSPF,BGP 等。可路由协议是指可以通过路由表来确定去向和路径的协议，是受路由协议服务的 协议，是实现在网络层设备之间进行通信的协议，它们能够完成不同网段间的通 信，可路由协议主要有IP/TCP协议栈中的IP协议，IPX/SPX协议栈中的IPX协 议，这些协议可以给网络设备分配网络号和主机号。可路由协议是定义数据包内各个字段

20、的格式和用途的网络层封装协议，该网络层 协议允许将数据包从一个网络设备转发到另一个网络设备。常见的可路由协议有 TCP/IP协议栈中的IP协议、Nover IPX/SPX协议栈的IPX协议。可路由协议也 可称为被路由协议，它是网络层协议的支撑，象IP，IPX等，同时一个协议被成 为可路由协议必须能够给每台独立的设备分配网络号和主机号。如IPX只要求分 配网络号，因为它使用主机的MAC作为物理地址，而IP是要求你提供一个地址 和子网掩码，通过它们的与运算得到网络号的，所以它们是可路由协议，NetBEUI 协议不是可路由协议，因为它不提供第三层的支持，它仅是一个小型的快速的高 效协议，仅限制在一个

21、网段中运行。同时可路由协议是根据上层协议将数据封装 到IP包里。路由协议是运行终端系统上的协议，主要用来进行相互通信。不可路由的传输协议，也就是传输协议可不可以路由（Routale or Nonroutable） 的意思，数据能不能使用这个传输协议，通过路由器将数据传送到其他网络网段。 换言之，可不可以路由，表示这个协议的信息包格式可否被路由器接受。TCP/IP、 IPX/SPX属于可路由的协议，NetBUEI则属于不可路由的协议。不可路由的协议通常通过网桥、集线器或中继器传送数据。路由可以静态配置，也可以通过路由协议自动生成。路由协议能够自动发现 和计算路由，并在拓扑变化时自动更新，无需人工

22、维护，适用于复杂的网络。路由协议：路由器用来计算、维护网络路由信息的协议，通常有一定的算法， 工作在传输层或应用层。常见的路由协议：RIP、OSPF、BGP。可路由协议：可被路由器转发的协议，工作在网络层。常见的可路由协议有 IP、IPX 等。路由协议和可路由协议之间的关系：routing protocol负责学习最佳路径， 而routed protocol根据最佳路径将来自上层的信息封装在IP包里传输。动态路由协议在协议栈中的位置BGP（基于TCP，端口 号 179）RIP （基于UDP，端口号520）OSPF（基于ip，协议 号89）TCPUDPIPRaw IP链路层物理层从所有的源结点到

23、一个给定的目的结点的最优路由的集合形成了一个以目 的结点为根的树，称为汇集树；路由算法的目的是找出并使用汇集树。常见的路由选择算法静态路由算法最短路径法构建子网的拓扑图，图中的每个 结点代表一个路由器，每条弧代 表一条通信线路，为了选择两个 路由器间的路由，算法在图中找 出最短路径。Dijkstra 算法扩散法事先不需要任何网络信息；路由 器把收到的每一个分组，向除了 该分组到来的线路外的所有输出 线路发送。将来会有多个分组的 副本到达目的地端，最先到达的， 可能是走了“最优”的路径扩散法选择性扩散算法（能够消除多余的 分组）基于流量的路 由算法既考虑拓扑结构，又兼顾网络负荷；前 提：每对结点

24、间平均数据流是相对稳定 和可预测的；根据网络带宽和平均流 量，可得出平均包延迟，因此路由选择 问题归结为找产生网络最小延迟的路 由选择算法。提前离线（off-line）计 算动态路由算法距离向量路由算法（也称BellmanFord路由算法和FordFulkerson算法）每个结点通过测取与相邻结点的 距离，再依据与其相邻结点交换 的距离信息，间接地求出路由表； 各结点周期性地测取相邻结点的 距离；向相邻结点发送它到每个 目的结点的距离表，同时，它也 接收每个邻居结点发来的距离 表；结点中的老路由表在计算中 不被使用。算法的缺陷：对好消息反应迅速， 对坏消息反应迟钝。被RIP协议米 用距离向量路

25、由算法水平分裂算法（在发 送路由更新消息时 进行限制，结点不向 相邻结点报告那些 从该相邻结点学习 到的路由信息）链路状态路由 算法/链路状 态最短路由优 先算法SPF1.发现邻居结点，并学习它们 的网络地址；2 .测量到各邻居 节点的延迟或者开销；3 .创建 链路状态分组；4.使用扩散 法发布链路状态分组；5.计算 到每个其它路由器的最短路 径实用协议：OSPF、IS-IS使用Dijkstra算 法处理链路信息分级路由选择分而治之的思想；根据需要，将路由器分成区域（regions）、聚 类（clusters）、区（zones）和 组（group）移动主机的路 由选择广播路由选择完全发送法、扩

26、散 法、多目的地路由 选择、生成树法、 逆向路径转发组播路由选择（一）有类路由协议1、有类路由协议的特点是发送路由更新包的时候不携带路由条目的子网掩码2、有类路由协议在路由传递过程中使用路由发送和接收规则。有类路由协议更新发送规则：检查路由更新网络是否与发送端口同一主网1）.若否，路由更新自动汇总成主类网络2）.若是，继续检查更新的路由是否与发送接口的掩码一致是，发送更新否，忽略更新有类路由协议更新接收规则：将网络地址和接收接口的网络地址进行比较，判断是否处于同一主网络1）.处于同一主网络，直接赋予该网络地址接收接口的掩码并写入路由表2）.不处于同一主网络,首先查看路由表中是否存在该主网络的任

27、一子网a.不存在，接收该网络地址，并赋予该网络地址一个有类掩码，同时写入路由表b.存在，忽略该路由更新并丢弃3、有类路由协议的特性：1）同一个主网络下的子网若掩码不一致，则会出现子网丢失，即不支持VLSM2）在边界路由器上面会产生自动汇总，并且这个自动汇总是无法关闭的。对于不连续子网，必然导致多个路由器通告相同的路由更新（汇总后的），这样将导致网络不 正常，所以不支持不连续子网。对于连续子网，则是支持的。3）那么有类路由协议包括：RIPV1 IGRP（二）无类路由协议1、无类路由协议的特点是发送路由更新包的时候携带自己的子网掩码2、无类路由协的特性：1）因为发送子网掩码，可以支持VLSM，2）在边界路由器上面的自动汇总可以关闭，可以支持不连续子网。3）无类路由协议包括:RIPV2 EIGRP OSPF ISIS BGPV44）基于现在我们所使用的网段一般都是VLSM，所以，我们现在都会使用无类的路由协议。总结：有类路由协议和无类路由协议的本质区别就是在发送路由更新时是否发送子网掩码。所以有 类无类协议的不同就在于是否支持VLSM（可变长子网mask）。有类的不发送mask，不支持 VLSM，无类的反之。