Microsoft Word - A doc

Size: px

Start display at page:

Download "Microsoft Word - A doc"

喜车
7 years ago
Views:

1 常用动态路由协议的算法分析与性能比较王彦坤 1 2, 宋茂强 1 北京邮电大学计算机科学与技术学院, 北京 ) 2 北京邮电大学软件学院, 北京 ) E-mal:perfectfr@na.com 摘要 : 动态路由能够随着网络运行情况和拓扑结构的变化而变化, 路由器根据路由协议提供的功能自动计算数据传输的最佳路径, 并由此动态地维护路由表本文主要介绍网络中几种动态路由协议 RIP,IGRP,OSPF,EIGRP) 的算法数学模型原理, 并对其在路由配置复杂度占用带宽收敛速度负载均衡能力适用范围等方面进行简要比较关键词 : 动态路由协议 ; 路由算法 ; 数学模型 ;OSPF;EIGRP 1. 引言无论是 Internet 还是 LAN, 其数据在网络上传输的过程不外乎路由选择和数据转发两个过程相对于路由选择来说, 数据转发功能单一, 实现方法简单所以在网络上数据传输的过程中, 最重要的一项工作就是路由的选择路由选择协议按其实现算法分为距离向量路由协议和链路状态路由协议路由算法是路由器设计基础, 其中 RIPRoute Informaton Protocol) IGRPInteror Gateway Routng Protocol) EIGRPEnhance Interor Gateway Routng Protocol) 是基于距离向量路由算法的, 而 OSPFOpen Shortet Path Frt) 是基于链路状态路由算法的 RIP 是 IETF 早在 1988 年 6 月提出来的一种在当时相对较较新的完全开放的距离向量形式的路由协议, 其最大的特点就是无论是其实现原理还是配置方法, 都非常简单 ;IGRP 是 80 年代中期由 Cco 公司开发的私有协议, 它是伴随着 Cco 路由器的普及和其自身的稳定性而逐渐被广泛应用的 ; EIGRP 也是由 Cco 公司开发的私有协议, 是对 IGRP 协议的有效扩展, 主要体现在收敛特性和操作效率两个方面 ;OSPF 是 IETF 在上世纪 80 年代末期通过的一个基于链路状态路由算法的公有协议, 能够适应大规模局域网络, 收敛速度快, 但由于本身的复杂性, 使得 OSPF 协议在执行的时候会占用较多的路由器资源和网络带宽 2. 算法分析众所周知, 计算机网络可以抽象为图论中的图 [7] 对于图 G =V,E,C),V 表示 G 中的节点的集合,E 表示 G 中有向边的集合,C 则是有向边对应的权值的集合每一条边都对应着两个节点 u, V 两个节点对应着两条边u,) 和,u) 当u,) 和, u) 的权相等时, 我们称图 G 是无向图 ; 反之当 u,) 和,u) 的权不相等时, 我们称图 G 为有向图对应于计算机网络,V 是网络中路由器的集合,E 是所有链路的集合,C 则是链路上的带宽时延数据丢失率等参数的并集由以上的分析可以得出 : 对于计算机网络中的路由选择问题, 可以抽象为图论中的关于单源最短路径的求解问题,V-D 算法和 Dktra 算法就是这样的两个经典算法 2.1V-DVector-Dtance) 算法数学模型 V-DVector-Dtance 距离向量 ) 算法又称为 Bellman-For 算法,RIP 协议 IGRP 协议 EIGRP 协议都是基于此 V-DVector-Dtance) 路由算法的为了简化问题的讨论, 我们将网络表示成为一个无向图, 故其算法思想的数学模型如下图 1 所示 -1-

2 在讨论此算法之前, 我们先来看一个结论 : 结论一 : 一般情况下, 假设 S 为已求得最短路径的终点的集合, 则可证明 : 下一条最短路径设其终点为 x) 或者是弧,x) 为源点 ), 或者是中间只经过 S 中的顶点而最后到达顶点 x 的路径图 1 V-D 算法模型图已知图 G =V,E) 中不存在从源 V 出发的负回路, 求其到 V 的最短路径考虑到各条路径的随意性以及计算的方便性, 不妨设从任一点 V 到任一点 V 都有一条弧, 其权值为 W 相对于实际的网络情况, 如果相应的链路不存在, 则可在模型中添加对应的边 V, V), 且令 W= ) 显然, 从 V 到 V 的最短路径总是从 V 出发, 沿着一条路到某个点 V, 再沿 V,V) 到 V 的这里 V 可以是 V 本身 ), 由结论一可知, 从 V 到 V 的这条路必定是从 V 到 V 的最短路径, 所以 V,V) 必满足如下方程 :, ) = Mn{, ) + w } 1 其中表示两个顶点之间的最短路径,w 表示相邻两个顶点之间的边的权为了求得这个方程的解 V,V1),V,V2),,V,Vp) 这里 P 为图 G 中的顶点数目 ), 可用如下递推公式 : 开始时, 令对 t=2,3,... t), 1) ) =, ) = Mn { w t 1) = 1,2,,p) 2, ) + 若进行到某一步, 例如第 k 步时, 对所有 =1,2,...,p, 有 : 则 k { ), )} 不难证明 : k ), k 1) w } = 1,2,,p) 3 ) =, )...4 即为 V 到各点的最短路径的权 = 1,2,, p -2-

3 1) 如果图 G 是不含回路的正权有向图, 那么, 从 V 到任一个点的最短路径最多包含 P-2 个中间点 ; 2) 上述递推公式 3 就是在至多包含 t-1 个中间点的限制条件下, 从 V 到 V 的最短路径的权由 1)2) 可知 : 当 G 中不含负回路时, 上述算法最多经过 p-1 次迭代必定收敛, 即对所有的 =1,2,...,P, 均有 4 式成立, 从而求出从 V 到各个顶点的最短路径的权 2.2Dktra 算法数学模型 [6] OSPF 协议是基于 Dktra 算法的, 此算法是由迪杰斯特拉 Dktra) 于 1959 年提出来的一种按路径长度递增的次序产生最短路径的算法, 是目前被认为最好的求单源最短路径的算法其思想是首先引进一个辅助向量 D, 它的每个分量 D[] 表示当前所找到的从起始点 V 到每个终点 V 的最短路径的长度它的初态为 : 若从 V 到 V 有弧, 则 D[] 为弧上的权值 ; 否则 D[] 为显然, 长度为 D { [ ] Mn D[ V ] = }.5 的路径就是从 V 出发的一条长度最短的路径此路径为 V,V) 由 2.1 节提到的结论一可知, 下一条长度次短的最短路径的长度必是 D = { } [ ] Mn D[ V S 6 ] 其中 D[] 或者是弧 V,V) 上的权值, 或者是 D[k]Vk ) 和弧 Vk,V) 上的权值之和下面以一个例子来说明这个求解最短路径的过程如图 2 所示的含有 6 个顶点的有向图, 求 V0 到各终点的最短路径 [5] 图 2 Dktra 算法模型图关于上图的求解过程如表 1 所示终点表 1 图 2 求解过程表从 V0 到各终点的 D 值和最短路径的求解过程 = 1 = 2 = 3 = 4 = 5 V1 V

4 V V V V V2 V4 V3 V5 S {V0,V2} {V0,V2,V4} {V0,V2,V3,V4} {V0,V2,V3,V4,V5} 3. 基于两种不同算法的协议分析 3.1 基于 V-D 算法的协议分析 RIP 协议是在 1988 年被 IETF 标准化的, 定义为 RFC1058, 紧接着的 RIP2 标准在 RFC1388 中被定义 [1] 由于 RIP 协议的简单性, 所以在很多相对比较简单的网络中被广泛采用但是其协议中规定, 一条有效的路由信息的度量不能超过 15, 这就导致该协议不能应用于大型网络另外, 当我们在实际的应用中,RIP 协议很容易出现计数到无穷大的现象, 从而使得路由收敛速度很慢, 即在网络的拓扑结构发生变化的情况下, 网络需要经过很长时间才能稳定下来最后,RIP 协议由于其设计思路的简单, 必然对一些网络因素考虑不周, 比如传输延时可靠性链路负荷等 IGRP 协议与 EIGRP 协议都是由 Cco 公司制定的私有协议同 RIP 协议一样也是基于 V-D 算法, 由于 EIGRP 协议是 IGRP 协议的加强版, 故我们在此只介绍 EIGRP 协议, 而 IGRP 协议只是在收敛速度和操作效率方面较 EIGRP 有所逊色 1)EIGRP 协议可以无缝连接数据链路层协议和拓扑结构, 因为 EIGRP 不要求对 OSI 参考模型的数据链路层协议做特别的配置, 比如以太网和帧中继 ; 2)EIGRP 协议使用 Dffung Upate 算法 DUAL) 来实现快速收敛, 路由器会存储所有从源到达目的地的备份路由, 以便进行快速切换如果没有合适的或备份路由在本地的路由表中的话, 路由器会向邻近的节点请求选择一条备份路由 ; 3)EIGRP 对于网络带宽不作周期性的更新, 只是在路由的链路和权发生变化的时候才做部分更新当路由信息改变以后, 路由器只发送那些改变了的路由信息, 而不是发送整个路由表, 这就相对较快的提高了路由器的收敛速度, 当要进行路由替换的时候,EIGRP 采用扩散算法, 即将要替换的路由在路由表中设置为活动状态, 并向周围节点发送查询请求, 然后根据相邻节点的应答建立应答状态表, 启动定时器, 跟踪相邻节点的应答在收到所有相邻节点的应答后, 将路由状态重新设置为被动状态, 从而进入本地计算更新路由表 ; 4)EIGRP 协议支持多种 OSI 参考模型中的网络层协议总之,EIGRP 协议能够有效的工作在各种网络中, 而且保证网络中不会产生回路, 配置起来相对简单, 可以对非对称的链路有效的做负载均衡 3.2 基于 Dktra 算法的协议分析 OSPF 协议由互联网网络工程部 IETF) 开发的一种内部网关协议 IGP), 即网关和路由器都在一个网络自治系统内 [2] OSPF 协议是基于 Dktra 算法的在 IP 网络上, 它通过收集和传递自治系统内的链路状态来动态的发现并更新路由信息网络中的每台路由器通过构建一棵以自己为根的最短路径树, 这棵树中的每个节点表示本路由器到其所在的网络中的其它各节点的路由信息显然, 由树的特性可知,OSPF 协议工作下的网络也不存在回路可以适应任意规模的网络系统 -4-

5 OSPF 协议将所在网络划分为不同的区域, 通过区域之间的路由信息摘要 [4], 可以在很短的时间内将更新的路由信息传递到整个网络中, 使得路由信息的更新不会随着网络规模的扩大而呈现出几何级数的增长趋势, 可见其收敛速度快 ; 另外,OSPF 协议可以将自身对网络的占用开销控制到最小, 这主要体现在, 用于维护和发现相邻节点之间的关系而发送的是不含路由信息的 hello 报文非常短, 故其对链路带宽占用率低而包含路由信息的报文是按事件触发的机制来发送的, 即当网络中的路由信息发生变化时才被请求发送同时为了增强 OSPF 协议的健壮性, 每 30 分钟将网络中所有路由重发一次 4. 基于两种不同算法的协议比较对于 RIP 协议 IGRP 协议 EIGRP 协议和 OSPF 协议来说, 由于 RIP 协议相对较为简单, 有很多没有考虑到的方面, 而 IGRP 协议是 EIGRP 协议的前期版本, 所以在此选取两个比较典型的协议, 即主要对 EIGRP 协议和 OSPF 协议进行比较配置复杂度 [3] : 使用 EIGRP 协议组建网络, 路由器配置方法比较简单, 并且对于不同的网络接口可以使用相同的配置方式, 整个配置过程只不过是在网络中起 EIGRP 协议后将相应的网络接口加入即可 ; 而使用 OSPF 协议, 由于网络区域划分和网络属性的复杂性, 需要网络分析员有较高的网络知识水平才能很好的配置和管理 OSPF 网络占用带宽 :OSPF 协议和 EIGRP 协议都是以发送 hello 报文来维护和发现相邻节点之间的关系的, 但是 OSPF 协议会每经过 30 分钟将网络中的所有路由信息重新发一次, 所以在此段时间内其网络链路的带宽占用是相对较高的负载均衡能力 : 根据我们以 Cco 3550 型交换机组成的具有一定规模的局域网络进行测试, 发现 OSPF 协议虽然可以根据接口的速率连接可靠性等信息, 自动生成接口路由优先级, 但对于要到达同一目的地的数据包来说,OSPF 只会选择优先级较高的链路来传输, 即不同优先级的两条链路不能实现负载均衡而 EIGRP 协议可以根据各条链路优先级的不同, 自动匹配流量, 从而很好的实现负载均衡收敛速度 :EIGRP 协议收敛过程是将网络中不确定的路由信息广播给其所有的相邻节点, 待得到所有相邻节点的确认信息后再收敛的过程, 这会在某些情况下造成多重计算, 从而降低其收敛速度 ; 而 OSPF 协议不会出现这种问题, 所以说在收敛速度上 OSPF 优于 EIGRP 协议适用范围 : 由于 EIGRP 协议是 Cco 公司制定的私有协议, 而 OSPF 是由 IETF 制定的标准, 故在适用范围上显然是 OSPF 协议的适用范围相对较广 5. 结论本文通过对这几种动态路由协议的分析和比较可以得出 :RIP 协议是相对较为简单的协议, 由于其自身天生的缺陷使其应用范围相对较小 ;IGRP 协议在升级为 EIGRP 协议后与 OSPF 协议都是收敛速度相对较快无回路使用灵活且安全性较好的协议, 但在配置复杂度占用带宽负载均衡能力方面 EIGRP 协议相对较优, 而在收敛速度和适用范围方面 OSPF 协议略胜一筹 -5-

6 参考文献 [1]Bellman, R. E. Braen, R. RFC1058 Routng Informaton Protocol RFC1058 June [2]RFC1131 OSPF pecfcaton. [3]Catalyt 3550 Multlayer Swtch Software Confguraton Gue. Cco IOS Releae 12.19)EA1 Aprl [4]John Moy RFC1583 OSPF Veron 2 March [5] 严蔚敏, 吴伟民数据结构 C 语言版 ) 清华大学出版社 1997 年 4 月. [6] 宁正元, 王秀丽算法与数据结构清华大学出版社 2006 年 1 月. [7] 卢开澄, 卢华明图论及其应用清华大学出版社 1995 年 8 月. Arthmetc Analyze an Capablty Compare of Seeral Dynamc Route Protocol Wang Yankun 1, Song Maoqang 2 1 School of Computer Scence an technology of BUPT, Beng ) 2 School of Software Engneerng of BUPT, Beng ) Abtract Dynamc route wll be change along wth the network run an tructure. Bae on the route protocol, router can chooe the bet way to tranmt ata, an ncate the route table. Th paper wll ntrouce ome ynamc route uch a RIP IGRP EOGRP an OSPF, analyze on the route arthmetc an prncple, an compare them n confguraton, banwth, conergence, the ablty to recoer from emergence quckly an range of applcaton. Keywor: ynamc route protocol; route arthmetc; mathematc moel; OSPF; EIGRP -6-

动态路由选择协议、RIP

动态路由选择协议、RIP 学习沉淀成长分享动态路由协议 RIP 红茶三杯 ( 朱 SIR) 微博 : t.sina.com/vinsoney Latest update: 2012-06-01 课程目标动态路由协议概述 RIP RIP 基础实验动态路由协议概述什么是路由什么是动态路由协议动态路由协议的分类什么是路由 192.168.10.0/24 172.16.1.0/24 e0 s0 Protocol Connected