（运筹学与控制论专业论文）路由算法中若干优化问题的研究.pdf

大连理工大学博士学位论文 摘要 互联网已成为现代社会最重要的信息基础设施和人们工作、生活的重要组成部 分但目前互联网中的传输模式“尽力而为”服务，无法满足多媒体应用和各种用户 对网络传输质量的要求因此，以提高网络资源利用效率、为用户提供高质量服务作 为目标的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 研究是当前i n t e r n e t 领域的热点之一近几 年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用本文 主要研究服务质量单播与组播路由问题，取得的主要结果概括如下： 1 第三章将禁忌搜索法引入多约束单播q o s r 计算中，首先通过能量函数把多个q o s 度量转化成单一能量然后在d i j k s t r a 算法基础上，构造出禁忌搜索法的候选集 与评价函数通过禁忌搜索法的迭代方法寻找出近似最优解仿真实验表明本算 法性能稳定，并具有成功率高、低代价等特点 2 第四章首先定义了带时延约束最小代价组播问题，然后给出了分别基于遗传禁忌 混合策略、蚁群算法的组播路由算法仿真实验结果表明算法稳定，具有收敛速 度快、代价性能良好等特性对组播路由问题提供了比较好的解决方法 3 第五章对带节点c p u ，缓冲区与带宽约束的最小代价组播路由问题，首先提出了 统一模型，然后给出了分别基于模拟退火法、遗传算法、禁忌搜索法的三种q o s 组播路由算法仿真实验表明本算收敛较快，具有能够满足多q o s 要求、低代价 等特点 4 第六章针对多约束最小代价s t e i n e r 树问题，提出了一种基于c b t 思想的多约束 组播算法( c m c m r a ) 与一种基于s p h 思想的多约束组播算法( s m c m r a ) 性能 分析表明这两种算法具有易于实现、复杂度比较低等特点最后，仿真试验说明 算法具有低代价性能，且能够满足多约束q o s 要求 5 第七章对基于核心节点的组播路由协议中带q o s 约束的核心节点选择问题，提出 了一种核心节点选择算法从核心节点候选集里选择最少量的核心节点，使得组成 员都满足端到端服务质量约束仿真结果表明提出的算法具有选出核心节点少、 能够满足端到端q o s 约束等性能，可行的且有效的 关键词：路由算法；路由协议；服务质量；单播；组播；核心节点；遗传算法；模拟退 火法；禁忌搜索法；蚁群算法；网络 路由算法中若干优化问题的研究 r e s e a r c ho ns o m eo p t i m a z a t i o ni s s u e si nr o u t i n ga l g o i r t h m s a b s t r a c t t h ei n t e r n e th a sb e c o m et h em o s ti m p o r t a n tm o d e r ni n f o r m a t i o ns o c i e t yi n f r a s t r u c - t u r ea n da ni m p o r t a n tp a r to fp e o p l e sl i f ea n dw o r k b u ti n t e r n e tt r a n s m i s s i o nm o d e l “b e s t e f f o r t ”s e r v i c ei su n a b l et om e e ta l lk i n d so fm u l t i m e d i aa p p l i c a t i o n sa n dt h e u s e r sn e t w o r kt r a n s m i s s i o nq u a l i t yr e q u i r e m e n t s t h e r e f o r e ，t oi m p r o v et h ee f f i c i e n c yo f n e t w o r kr e s o u r c eu t i l i z a t i o n ，t op r o v i d eah i g h - q u a l i t ys e r v i c ef o ru s e r sa r eah o tt o p i co f i n t e r n e tr e s e a r c ha r e a t h es t u d yi nr e c e n ty e a r ss h o w st h a tt h en e t w o r kr o u t i n ga l g o r i t h m p l a y sav e r yk e yr o l et oa c h i e v et h eq u a u 锣o fs e r v i c en e t w o r k t l 妇p a p e rm a i n l ys t u d i e s t h eq u a h t yo fs e r v i c e su n i c a s ta n dm u l t i c a s ta l g o r i t h m s ，i nw h i c ht h eq u i t es i g n i f i c a n t r e s u l t sa r es u m m a r i z e db e l o w ： 1 i nc h a p t e ri i i t a b us e a r c hi si n t r o d u c t e di n t om u l t i c o n s t r a i n e du n i c a s tq o s rc a l - c u l a t i o n f i r s ts e v e r a lq o sm e t r i c sa r et r a n s f o r m e di n t oas i n g l ee n e r g yb yu s i n ga n e n e r g yf u n c t i o n t h e nb a s e do nd i j k s t r aa l g o r i t h m ，t h ec a n d i d a t es e t sa n de v a l u a t i o n f u n c t i o na r ec o n s t r u c t e db yt a b us e a r c h t h ea p p r o x i m a t eo p t i m a ls o l u t i o ni sf i n d b yt h ei t e r a t i v em e t h o di nt a b us e a r c h s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h m p e r f o r m a n c ei ss t a b l ew i t hh i g hs u c c e s sr a t ea n dl o wp r i c e 2 c h a p t e ri vd e f i n e st h ed e l a yc o n s t r a i n tm i n i m u mc o s tm u l t i c a s tr o u t i n gp r o b l e m ， a n dt h e np r e s e n t sm u l t i c a s tr o u t i n ga l g o r i t h m s ，r e s p e c t i v e l yb a s e do nm i x e ds t r a t e g y o fg e n e t i ca n dt a b u ，a n dt h ea n ta l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a ta l g o r i t h mi s s t a b i l i t yw i t ha f a s tc o n v e r g e n c ea n dg o o dp r i c ep e r f o r m a n c e i tp r o v i d e sf a v o r a b l e s o l u t i o n st om u l t i c a s tr o u t i n gp r o b l e m s 3 i nc h a p e rv d e a l sw i t ht h em i n i m u mc o s tm u l t i c a s tr o u t i n gp r o b l e m sw i t ht h en o d e s c p u ，t h eb u f f e ra n db a n d w i d t hc o n s t r a i n t s i tg i v e sau n i f i e dm o d e la n dd i s c u s s e s t h r e em u l t i c a s tr o u t i n ga l g o r i t h m s ，r e s p e c t i v e l yb a s e do i lt h es i m u l a t e da n n e a l i n g ，t h e g e n e t i ca l g o r i t h m ，t h et a b us e a r c h s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h m sc o n - v e r g e n c ei sf a s ta n dl o wp r i c e ，a n dc a nb em e tt h eq o sr e q u i r e m e n t s 4 i nc h a p t e rv i c m c m r aa n ds m c m r aa l g o r i t h m sa r ep r e s e n t e df o rt h em u l t i c o n s t r a i n e dm i n i m u mc o s ts t e i n e rp r o b l e m r e s p e c t i v e l yb a s e do nt h ec b ti d e aa n d s p hi d e a t h ep e r f o r m a n c ea n a l y s i si n d i c a t e st h a tt h e s et w oa l g o r i t h m sa r ee a s y t oi m p l e m e n ta n dr e l a t i v e l yl o wc o m p l e x i t y f i n a l l y , t h es i m u l a t i o nr e s u l ts h o wt h a t a l g o r i t h m sh a v eal o wp r i c ep e r f o r m a n c e ，i nw h i c ha d d i t i o n a lc o n s t r a i n e dq o sr e q u i r e - m e r i t sc a nb em e t i i 5 i nc h a p t e rv i i ac o r es e l e c t i o na l g o r i t h mi sp r o p o s e df o rt h ec o r es e l e t i o np r o b l e m w i t hq o sr e q u i r e m e n t si nt h ec o r eb a s e dm u l t i c a s tr o u t i n gp r o t o c 0 1 i ts e l e c t sa m i n i m u mn u m b e rc o r e sf o r mc o r ec a n d i d a t es e t ，a n dm a k ea l lg r o u pm e m b e r s s a t i s f y e n d - t o - e n dq u a l i t yo fs e r v i c ec o n s t r a i n t s t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o - r i t h mi sf e a s i b l ea n de f f e c t i v ei ns e l e c t i n gc o r en o d e sa n d s a t i s f y i n ge n d - t o - e n dq o s c o n s t r a i n t s k e yw o r d s ：r o u t i n ga l g o r i t h m ；r o u t i n gp r o t o c o l ；q u a l i t yo fs e r v i c e ；u n i c a s t r o u t i n g ；m u l t i c a s tr o u t i n g ；c o r en o d e ；g e n e t i ca l g o r i t h m ；s i m u l a t e da n n e a l i n g ； t a b us e a r c h ；a n ta l g o r i t h m ；n e t w o r k i i i 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或其他单位的学位或证书所使用过的材料与我一同工作的同志对 本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：日期： 路由算法中若干优化问题的研究 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使 用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文 作者签名：耋越 导师签名：筮垄堡 大连理工大学博士学位论文 1 绪论 本章先阐述了服务质量( q u a l i t yo fs e r v i c e ，q o s ) 路由的研究背景，然 后概述了q o s 单播路由与q o s 组播路由的研究现状，最后给出了本论文研 究的主要内容 1 1 研究背景 随着计算机技术和通信技术的飞速发展，计算机网络正以越来越快的速度进入到 工业、商业、教育和科研领域，进入到人们的日常生活中，深刻影响和改变着人们的 工作和生活方式 计算机网络自1 9 6 2 年诞生以来到今天已经有几十年的历史，发展到现在形成了 一个大型的计算机网络一i n t e r n e t i n t e r n e t 的出现是人类通信发展史的一个里程碑， 它正在改变着人们的通信方式、工作和生活的方式传统的基于电路交换，通过电话 和电报进行联系的方式，正被基于i n t e r n e t 分组交换的通信方式所代替，例如电子邮 件、v o i p 等 i n t e r n e t 以其便捷、价廉的优势，吸引着越来越多的用户加入其中，它正向全世 界各个地方延伸和扩展，不断有新的成员加入其中，连网主机量每年翻一番，w e b 站 点每半年翻一番目前i n t e r n e t 已成为覆盖面最广、规模最大、信息资源最多的计算 机网络 用户和业务的增加也推动了i n t e r n e t 在各方面的发展在传输方面，由于光通信 技术的发展，基于d w d m 技术的光传输系统的带宽已达到1 6 t b i t s 传输带宽的增 加推动了网络体系结构、路由器、交换机技术的发展目前核心路由器的接口速率己 达到1 0 g b i t s 在网络层的协议方面，由于用户的增加，i n t e r n e t 地址资源面临枯竭，虽然n a t ( n e t w o r k sa d d r e s st r a n s l a t i o n ) 技术能暂时弥补网络地址资源的不足，但i p v 4 在q o s 和网络安全方面的缺陷决定它必然被更先进的i p v 6 代替i p v 6 不仅地址空间从3 2 位增加到1 2 8 位之外，还增加了安全功能和服务质量保证 带宽的增加、地址空间的扩大、用户数目的激增，带来的是应用和业务不断推陈 出新和网络吞吐量的急剧增加目前网络承载的业务包括数据、语音、视频等多种业 务，为实现多种业务共存，多种应用共存，服务质量控制机制是必需的i n t e r n e t 已逐 步由单一的数据传输网向多媒体综合传输网演进但目前 n t e r n e t 中的传输模式。尽 力而为”( b e s t e f f o r t ) 服务，无法满足多媒体应用和各种户对网络传输质量的要求 因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的q o s 研究是当前 1 路由算法中若干优化问题的研究 功i n t e r n e t 领域的热点之一q o s 问题本质上是研究网络资源的管理和控制问题，由 于计算机网络本身存在的缺陷和i n t e r n e t 的复杂性，使得i n t e r n e t 的q o s 研究存在极 大的困难但q o s 的研究对推动网络应用的发展，提高人们的工作效率，优化i n t e r n e t 的利用具有极其重要的意义 服务质量的概念已经用于定量和定性地描述服务的提供者和服务的接受者之间协 商的服务性能服务质量可以由一些特定的参数来描述，服务的提供者允许服务的使 用者在建立连接时对各种服务参数指定希望的、可接受的最低限度值，有些参数还可 以用于无连接的传输服务服务的提供者根据网络服务的种类或它能够获得的服务来 检查这些参数，决定能否提供所要求的服务一些典型参数如下：网络带宽、传输延 时、延时抖动、差错率等在i n t e r n e t 上对网络服务质量的要求也越来越高，例如， 视频会议、网络电话的实时和带宽要求，大数据量数据备份的完成时间要求等如何 在网络中实现多种服务质量是全世界通信领域竟相研究的重点课题团 q o s 的研究有多个方面，包括流量整形( t r a f f i cs h a p i n g ) 、包调度算法( p a r k e t s e h e d u l i n g ) 、路由算法( q o sr o u t i n g ) 、资源预留( r e s o u r er e s e r v a t i o n ) 、接入控制( c a l l a d m i s s i o nc o n t r 0 1 ) 等的研究在q o s 的早期研究中，主要的研究集中于网络节点的调 度策略、接入控制策略上，网络路由算法的研究一直被忽视近几年的研究表明网络 路由算法对实现网络保证质量的服务起到了非常关键的作用，同时网络路由算法也是 平衡网络负载和充分利用网络资源的重要保证【1 】 1 2 研究现状 路由选择问题可分为4 大类：单播( u n i c a s t ) 、组播( m u l t i c a s t ) 、广播( b r o a d c a s t ) 和选播( a n y c a s t ) 本论文主要研究了单播路由与组播路由问题 单播q o s 路由问题是最基本的q o s 问题，它要求建立源节点和目标节点之间的 一条路径满足目标节点的q o s 需求同时使得网络资源得到优化单播q o s 路由问题 是伴随着大规模网络应用程序的出现而产生的，关于单播q o s 路由问题的研究主要 包括：文献【2 ，3 】等研究其物理机制，即研究各种q o s 参数的物理机制和其对建立连接 的影响，以及各种q o s 参数之间的联系，例如链路带宽与链路延迟以及数据损失率之 间的联系其中，文献【2 1 考虑了所有相关的链路参数都依赖于一个共同的m e r t i c s 的 情况作为特例，考虑了链路排队延迟和延迟抖动都依赖于带宽的情况，证明此时的 以带宽，排队延迟以及延迟抖动作为约束条件的q o s 路由问题是多项式可解的更为 一般的情况是约束条件互相独立的q o s 路由问题文献1 4 , 5 】等研究此时单播q o s 路 由问题的数学机制，将各种q o s 参数抽象为两种主要类型，凹性参数和加性参数，带 宽为典型的凹性参数而延迟为典型的加性参数，要求寻找源节点和目标节点之间的一 条路径满足各种q o s 约束条件其中，文献【5 】最早指出包括两个以及两个以上加性 q o s 约束的路由问题是n p 完全问题，由此由两个以及两个以上加性q o s 约束构成的 路由问题成为研究核心其中文献【6 7 】等在理论上对该问题进行了研究，确定对于有 2 大连理工大学博士学位论文 向图的受约束最短路径问题r s p 属于f p a t s 类，文献 8 1 提出了关于该问题的线性 搜索算法，该算法利用不同的约束参数的线性组合作为搜索函数，其核心问题是如何 有效的调节搜索因子从而提高搜索效率而文献s , 9 等则提出了启发式近似算法启 发式算法的核心是路径调节机制，即在已知路径的基础上对其进行调节从而达到满足 端到端q o s 约束的目的 i p 组播是i p 的扩展i p 组播在局域网或广域网上将i p 数据包从一个发送者传 送到一组接收者而不是一个接收者，并且依靠网络将数据包只传送给需要接收它的网 络目前，启发式算法求解路由的策略一般有源路由、分布式路由和层次路由三种形 式，它们的求解能力均存在不同程度的限制在传统的电路交换网络上，一种典型的适 应性路由方案是可替代路由，它是一种逐跳的、基于目的地址的路由策略的，可替代 路由思想能较好地用于分组交换网络，但要建立相应的控制机制，以避免对重负载网 络的性能损害为了适应组播路由技术发展的需要，人们在2 0 世纪8 0 年代后期就已 提出并开发了组播开放最短路径优先m o s p f 1 0 1 、距离向量组播路由协议d v m r p e n l 和p i m d m 【1 2 l ，它们是已形成组播主干网( m b o n e ) 的重要基础然而，这些协议都属 于稠密型协议，即在组播组成员分布较稠密的场合扩展性较好，较适于局域网环境， 但它不易扩展到大型网络为克服此缺点，基于核心树的协议c b t 1 3 】和p i m - s m 1 4 等稀疏型协议也应运而生，它们可支持组成员分布较稀疏的应用环境，采用显式的加 入裁剪机制，可避免广播信息，可较好地解决可扩展性问题。稠密型协议需要维护 o ( s g ) 棵树( s 和g 分别表示源和组的数量) ，稀疏型协议则只需维护伏o ( g ) 棵共享 树，但它们也存在会聚点和核的选择及管理开销等问题，它们虽然无需借助单播路由 协议提供拓扑信息来构造组播树，但仍要依赖单播路由协议转发控制信息，从而导致 增加控制开销 ， 在基于q o s 的组播路由协议方面，2 0 世纪9 0 年代初，美国的一些大学、研究 所和公司在i n t e n r e t 之上构架了实验性的组播主干网，但对q o s 约束的支持仍很弱 近来有不少学者做了一定的研究和探索工作，c a x l b e r g 和c r o w c r o f t 提出了y a m 协 议 1 5 1 ，不需要全局状态信息并且支持节点的动态加入和离开，但是它仍采用洪泛法来 寻找新成员到组播树的合适路径，因此它的控制消息的代价很大m f a l o u t s o s 等人 对y a m 协议进行了改进，提出了一种q o s m i c 1 6 1 ，q o s m i c 可在资源预留并在共享树 的基础上按需切换到有q o s 竞争的有源树上，具有较好的可扩展性，但由于它仍属 p i m s m 和c b t 的变种，因此也存在稀疏型协议固有的缺陷与一般单播q o s 路由或 无q o s 约束的组播路由相比，基于q o s 的组播路由的研究目前在国内外仍处于初步 阶段，而且这方面的研究也大都集中在网络拓扑参数信息是确定的网络环境范围内， 对于非确定参数网络基于q o s 的组播路由协议的设计理论及方法的研究则更少 基于q o s 的组播路由算法方面，d i j k s t r a 提出了一种基于最短路径树 1 7 1 的方 法，其基本思想是从源节点到各目的节点分别计算各自最短路径，并将其组成为以源 3 路由算法中若干优化问题的研究 节点为根的树，该方法并不能保证所生成的树的总成本最低p r i m 提出了一种基于 m s t 的算法f 1 8 f ，其基本思想是从源节点开始，每次向树中增加一个离树最近且成本 最小的节点，直到所有目的节点全部加入到树中，该方法不能解决q o s 约束问题还 有一些通过在源节点的计算来寻找一个受限制的s t e i n e r 树的b s m a 1 9 】、k p p 2 0 】和 d d m p 2 1 】的算法，它们需要网络中的每个节点都保存全局的网络状态信息以及q o s 参数信息，当网络和组播组很大时算法的代价很大，并且不适于组成员的动态加入和 离开，因此它们不适合在i n t e r n e t 上使用 在基于q o s 的层次组播路由方面，随着i n t e r n e t 规模的迅速扩大，支持q o s 的组 播源路由和分布式路由都面临复杂性过高的问题，因此支持q o s 的层次路由的研究成 为新的热点层次路由的基本思想是在对网络进行层次划分后，同层次内部扩散网络 原始信息，而层次之间扩散聚集后的网络信息，从而显著减少路由器维护和交换的信 息，解决大规模网络所带来的可扩展性问题支持q o s 的层次路由需要解决的问题包 括如何根据路由算法的需要聚集网络信息，如何使得基于该信息与基于平面详细的网 络信息进行路由的效率具有可比性，聚集的信息作为路由算法的输入，简单有效地反 映低层网络的特性是非常关键的许多学者己在层次组播路由方面做了一些工作，比 较典型的是b e h r e n s 和g a r e i al u n aa e e v e s 的层次距离向量路由算法【2 2 1 ，它提供运行 在层次上利用d i j k s t r a 最短路径算法的分布式实现；t h y a g a r a j a n 和s d e e r i n g 2 3 】提 出了一种层次组播路由算法俐 现代优化算法自2 0 世纪8 0 年代初兴起，至今发展迅猛，它包括禁忌搜索( t a b u s e a r e h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i ea l g o r i t h m s ) 、神经网络 ( n e u r a ln e t w o r k ) 、拉格朗日松弛算法和蚁群算法这些算法涉及生物进化、人工智 能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础构造的算 法启发式算法的兴起与计算复杂性理论的形成有着密切的联系，当人们不满足常规 算法求解复杂问题时，现代优化算法开始体现其作用，这些算法主要是解决优化问题 中的难解问题，由于这些算法在求解时不依赖于梯度信息，因而特别适用于传统方法 解决不了的大规模复杂问题，很适合解决具有n p 一完全的问题 1 3 本文的主要工作 i n t e r n e t 已逐步由单一的数据传输网向多媒体综合传输网演进但目前i n t e r n e t 中的传输模式“尽力而为”服务，无法满足多媒体应用和各种户对网络传输质量的要 求因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的q o s 研究是 当前i n t e r n e t 领域的热点之一近几年的研究表明网络路由算法对实现网络保证质量 的服务起到了非常关键的作用，同时网络路由算法也是平衡网络负载和充分利用网络 资源的重要保证 4 大连理工大学博士学位论文 1 第二章先概述了经典路由算法和协议，然后给出了q o s 定义、基本原则、提供机 制与控制机制最后概述了单播服务质量路由( q o s r ) 算法与组播q o s r 算法 2 第三章将禁忌搜索法引入多约束单播q o s r 计算中，首先通过能量函数把多个q o s 度量转化成单一能量然后在d i j k s t r a 算法基础上，构造出禁忌搜索法的候选集 与评价函数通过禁忌搜索法的迭代方法寻找出近似最优解仿真实验表明本算 法性能稳定，并具有成功率高、低代价等特点 3 第四章首先定义了带时延约束最小代价组播问题，然后给出了分别基于遗传禁忌 混合策略、蚁群算法的组播路由算法仿真实验结果表明算法稳定，具有收敛速 度快、代价性能良好等特性对组播路由问题提供了比较好的解决方法 4 第五章对带节点c p u ，缓冲区与带宽约束的最小代价组播路由问题，首先提出了 统一模型，然后给出了分别基于模拟退火法、遗传算法、禁忌搜索法的三种q o s 组播路由算法仿真实验表明本算收敛较快，具有能够满足多q o s 要求、低代价 等特点 5 第六章针对多约束最小代价s t e i n e r 树问题，提出了一种基于c b t 思想的多约束 组播算法( c m c m r a ) 与一种基于s p h 思想的多约束组播算法( s m c m r a ) 性能 分析表明这两种算法具有易于实现、复杂度比较低等特点最后，仿真试验说明 算法具有低代价性能，且能够满足多约束q o s 要求 6 第七章对基于核心节点的组播路由协议中带q o s 约束的核心节点选择问题，提出 了一种核心节点选择算法从核心节点候选集里选择最少量的核心节点，使得组成 员都满足端到端服务质量约束仿真结果表明提出的算法具有选出核心节点少、 能够满足端到端q o s 约束等性能，可行的且有效的 5 路由算法中若干优化问题的研究 2 路由算法与路由协议概述 本章先概述了经典路由算法和协议，然后给出了q o s 定义，基本原则， 提供机制与控制机制最后概述了单播服务质量路由算法与组播服务质量 路由算法 2 1 引言 近十年来，随着计算机网络规模的不断扩大，大型互联网络( 如i n t e r n e t ) 的迅 猛发展，路由技术在网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网 络设备用户的需求推动着路由技术的发展和路由器的普及 路由包含两个基本功能：一是搜集网络的状态信息并不断更新；二是根据所搜集 的信息计算可行路径q o s 的概念用来刻画服务提供者与用户之间用数量或者质量 来定义的性能约定，一次连接的服务质量由一系列约束条件给出，如带宽约束，时延 约束，抖动约束等q o s 路由的基本任务是为一次连接寻找一条有足够资源，能满 足q o s 要求的可行路径q o s 路由不同于尽力而为( b e s te f f o r t ) 路由，因为q o s 路 由通常是面向连接，有资源预留功能，并且能够提供有质量保证的服务； 2 2经典路由算法和协议 2 2 1 路由算法概述 2 2 1 1 路由算法的作用 路由算法的主要功能是指引分组通过通信子网到达正确的目的节点它包括两个 方面的功能：第一是为不同的源节点和目的节点对( s d ) 选择一条传输路径；二是在 路由选好以后，将用户的消息正确地送到目的节点 路由算法既要试图使网络的通过量最大，又要试图使网络的平均时延最小路由 算法的复杂性通常表现在以下几方面；1 ) 路由算法要求子网中所有节点相互协调， 而不像数据链路层和高层那样仅涉及一对对等模块之间的协调；2 ) 路由算法必须处 理链路和节点的故障，要求对业务进行重新定向的对系统维持的数据库进行更新；3 ) 必须达到高的性能，当网络部分区域拥塞时，路由算法必须能够修正路由 一个路由算法通常应当在高的业务负荷的情况下，在保证相同的成本条件下，可以 增加网络的通过量；在轻负荷和中等负荷的情况下，可以减少每一个分组的平均成本 2 2 1 2 路由算法的特点 6 大连理工大学博士学位论文 ( 1 ) 正确性和完整性 每一个节点( 交换机或路由器) 中的路由表，都必须给出到所有可能的目的节点的 下一站应怎么走，并且，所给出的走法应是正确的这里“正确”的含义应该是：沿 着各节点( 交换机或路由器) 中路由表所指引的路由，分组一定能够最终到达目的节点 ( 交换机或路由器) 并且，分组到达目的节点后不会再向其它节点( 交换机或路由器) 转发该分组 ( 2 ) 简单性 由于在每个节点上都要进行路由选择的计算，因此必然要增加分组的时延此外， 路由选择的计算不应使网络通信量增加太多的额外开销若为了计算合适的路由必须 使用网络其他节点发来的大量状态信息时，额外开销就会较大 ( 3 ) 健壮性( 鲁棒性) 算法应能适应网络拓扑和通信量的变化当网络中的通信量发生变化时，算法能 自适应地改变路由，以均衡各链路的负载当某个或某些节点、链路发生故障不能工 作，或者修理好了再投入运行时，算法也能及时地改变路由，不致引起作业的天折 ( 4 ) 稳定性 算法应是可靠的不管运行多久，保持正确性而不发生振荡 ( 5 ) 公平性 算法应对所有用户( 除少数优先级高的用户外) 都是平等的若使某一对用户的端 到端时延非常大，这就明显地不符合公平性的要求 ( 6 ) 最佳性 这里的“最佳”通常是指以最低的费用( 成本) 来实现路由算法：费用可以是带宽、时 延、距离、跳数、链路利用率、节点缓冲区被占用程度、链路差错率、时延抖动、丢包率等 2 2 2 路由算法分类 路由选择算法一般可以分为下列几类； ( 1 ) 静态路由或动态路由 静态路由选择方法几乎不能称作一种算法静态路由表在开始选择路由之前就 被网络管理员建立，并只能由网络管理员更改，所以只适于网络传输状态比较容易预 见，以及网络设计较为简单的环境动态路由选择算法则能根据网络环境的改变而适 时进行路由表的刷新，以适应环境的变化 ( 2 ) 单路径或多路径路由 单路径路由只支持从源到目的的单条信息传输路径，而多路径路由能够支持多条 路径到达同一目标 ( 3 ) 非层次或层次式路由 7 路由算法中若干优化问题的研究 非层次的路由是指网络中所有路由器的地位相同，而层次式路由中，一些路由器 组成网络主干，一些路由则只能在小区域内作用相应地也就有了层次式的和非层次 式的路由算法 ( 4 ) 主机智能或路由器智能 主机智能是指由源端节点计算决定整个路由，路由器只负责存储转发；路由器智 能是指由路由器根据自身的计算结果来决定数据传输路径 ( 5 ) 域内路由或域问路由 一些路由方法只能用于域内；另外一些方法则用于域问路由的决定，由于两种路 由方法本质上有所不同，因此一个最佳的域内路由选择方法并不一定是最佳的域间路 由选择方法，反之亦然 ( 6 ) 链路状态或距离矢量路由 链路状态算法( 也称最短路径优先算法) 将路由选择信息发送给互连网的所有节 点，但是每个路由器只能发送路由表中描述自己链路状态的那部分信息距离矢量算 法则要求每个路由器将路由表的全部或部分发送给与之相邻的路由器路由技术作用 于o s i 参考模型的第三层，即网络层目前在因特网上最常用的路由协议有：路由信 息选择协议( r i p ) 、内部网关路由协议( i g r p ) 外部网关协议( e g p ) 、边界网关协议 ( b g p ) 、开放式最短路径优先协议( o s p f ) 、距离矢量组播路由协议( d v m r p ) 和协 议独立组播路由协议( p i m ) 等 2 2 3 经典路由算法 因特网上的路由选择算法尽管多种多样，但它们在本质上都可归属于两种基本的 算法：距离矢量路由( d i s t a n c ev e c t o rr o u t i n g ) 算法与链路状态路由( l s r ：l i n k ss t a t e r o u t i n g ) 算法 2 2 3 1 距离矢量路由算法 距离矢量路由算法是b f 算法的具体实现，它最初用于a 砒) a n e t ，也用于i n t e r n e t 网中以及d e c n e t 和n o v e l l 的i p x 的早期版本之中在a p p l e t a l k 和c i s c o 路由器中 使用了改进型的距离矢量法 在距离矢量路由中，每个节点维持一个路由表在该路由表中，到达网络的每一 个目的节点都有一项每一项包括两部分；一部分是到达该达目的节点使用的输出链 路( 或者与该链路关联的下一个节点) ；另一部分是到达该目的节点距离的估计值表 中使用的距离量度可以是跳数、时延、某一路径排队的总分组数或其它类似的量度 距离矢量路由算法在理论上是可以正常工作的，但在实际中有一个很严重的缺 8 大连理工大学博士学位论文 陷；尽管它可以收敛到正确的路由，但收敛的时间可能太慢特别是它对好消息反映 迅速，对坏消息反映迟钝 2 2 3 2 链路状态路由算法 距离矢量路由算法简单扼要，适用于网络拓扑结构相对简单且链路极少发生故 障对于庞大而复杂的网络，该算法计算新路由的收敛速度极慢，而且在它进行计算 过程中，网络处于一种过渡状态，极可能发生循环并造成暂时的拥塞再者，时延的 度量主要考虑的是队长，并没有考虑后来链路带宽的增长而当前网络底层链路技术 多种多样，带宽各不相同，链路状态路由算法就是为了克服这些缺点才提出并发展起 来的 链路状态路由算法的基本思想是；网络中各个节点不必交换通往目的站点的距 离，而是维护一张网络拓扑图，在网络拓扑结构发生变化时及时更新拓扑图就行在 每个节点( 路由器) 中运行的链路状态路由算法包括五个部分： ( 1 ) 发现它的邻节点和取得它们的地址； ( 2 ) 测量到它各邻居节点的延迟或成本； ( 3 ) 构造一个分组来通知它所知道的所有路由信息； ( 4 ) 将这个分组发送给所有其他节点( 路由器) ； ( 5 ) 计算到达每一个节点( 路由器) 的最短路由 链路状态路由算法具有如下一些优点： ( 1 ) 迅速、无环路的收敛性； ( 2 ) 支持精确的量度值，而且如果需要，还能支持多种度量制式； ( 3 ) 支持通往同一目的站点的多重路径； ( 4 ) 能区分内部路由与外部路由 目前多种链路状态算法己被广泛应用 2 2 4 经典路由协议 路由协议的演进过程按时间顺序排列先后为；域内路由( r i p 、i g r p 、e i g r p 、 o s p f ) ；域间路由( e g p 、b g p ) ：组播路由( d v m r p 、p i m 、c b t ) 2 2 。4 。1 路由信息协议( r i p ) r i p 是一个采用距离矢量路由算法的协议它描述的是网关和主机间的路由信息 交换，是开发i n t e r n e t 网关软件的基础之一r i p 使用一种非常简单的度量制式。 9 路由算法中若干优化问题的研究 “距离”为到达目的网络所经过的路由器数( 即跳数) ，r i p 中允许一条通路最多只能包 含王5 个路由器，因丽“距离”的最大值为1 6 。每个路由器每隔3 0 秒向摆邻路由器广 播一次自已的路由信息若一个路由器3 分钟没有收到相邻路由器的更新路由表，则 认为此路幽器不可达，其距离值为1 6 葡p 协议的常规操作是通过对响应的广播来完成运行r i p 协议的路出器如果 收到一个响应报文，它首先对报文进行一系列的合法性检查，只有在合法性检查通过 后，才能根据r i p 处理程序去更薪它的路由表。路由表的每个表星通常包含有目的节 点地址、通往目的节点的度量值、下一跳路由器地址、各种定时器和文基于t c p i p 的q o s 路由算法的研究最近更新标志 2 2 4 2 内部网关路由协议( i g r p ) 内部网关路由协议( i g r p ) 是由美国c i s c o 公司在2 0 世纪8 0 年代中期开发成功 的路由选择协议该协议主要是为具有任意复杂网络拓扑结构的自主系统提供一个强 壮的路由选择，以解决r 薹p 协议只能适用予丽类型的孛小型a s 的缺点。 类似于r i p ，i g r p 也周期性地广播路由选择刷新消息但与r i p 不同，i g r p 支 持多种度量铡式；延迟i 带宽、可靠性、负载，使其可适用予不同的网络拓扑结构、 不同网络带宽和不同延迟特性的介质。 i g r p 的多路径选择方案是在内存中为每个目的站点保存一个可用路径表，每条 路径都用邻机以及访问该邻枕的接滋来标识这样，在两个路毒器间就允许有多重链 路，从而可在一定程度上实现负荷均衡，提高网络传输效率 2 2 4 3 增强型内部网关路由协议( e i g r p ) 随着网络规模的扩大和用户需求的多榉性变化，原来的i g r p 协议邑显得力不从 心，于是c i s c o 公闭又推出了增强的i g r p 协议增强的i g r p 协议集成了链路状态 矢量路由算法帮距离矢量路由算法的长处，同时还将j 。j 。g a r c i al u n aa c e v e s 博士开 发的距离矢量扩散刷新算法d u a l 揉合进来 增强的i g r p 协议具有如下一些新特性；快速收敛性；支持可变长的子网掩码； 支持路由部分剥薪；支持多种网络层协议与原i g r p 裙圪，增强的i g r p 采纳了如 下些新技术： ( 1 ) 楣邻节点的发现与恢复； ( 2 ) 可靠的