（系统工程专业论文）基于改进蚁群算法的QoS路由研究.pdf

摘要 q o s 路由的基本任务是为一次连接寻找一条有足够资源、能满足q o s 要求 的可行路径。而现有很多算法只是针对一个或两个约束条件，在多种q o s 约束 下，这些算法具有一定的局限性。而蚁群算法是近年来对自然界蚂蚁的寻路方式 进行模拟得出的一种仿生启发式算法，其具有很强的全局优化能力和本质上的并 行性，同时比早期进化算法具有更强的鲁棒性、求解时间短、易于计算机实现等 优点。求解带有多约束的q o s 路由是其应用的一个重要领域。 本文分析了q o s 路由研究的意义，介绍了q o s 路由研究与蚁群算法研究的 现状，详细分析了目前对基本蚁群算法的改进机制。在此基础上，本文尝试对基 本蚁群算法引入自适应思想，通过调整算法在进行到不同阶段时挥发因子的大 小，以避免整个系统呈现早熟现象；同时，引入了变异思想使得解可以自行跳出 局部最优区域，从而向最优解方向继续进化。这样既可以利用自适应思想使算法 减少进入停滞状态的可能性，又能使算法在进入停滞时跳出局部最优解的区域， 保证全局搜索能力。改进算法在q o s 路由中的应用能够得到良好的效果，更能 满足q o s 路由中带宽、时延、分组丢失率等几个重要指标。 最后，本文在o p n e t 平台构建了网络仿真系统，改进算法在该仿真系统中 表现出良好的性能。同时，与基本蚁群算法在该仿真系统中的性能进行了对比， 对比结果显示，改进算法能够在自适应、不易陷入局部最优解及防止陷入停滞等 方面作出改进。 关键词：蚁群算法；o o s 路由；单播路由；o p n e t a b s t r a c t t h eb a s i cm i s s i o no fq o sr o u t i n gi sf i n d i n gar o u t et h a tm e e t st h en e e d s o fu s e r sq o sr e q u i r e m e n t b u tm o s to ft h ea r i t h m e t i ci sn o te q u a lt o m u l t i c o n s t r a i n t sq o s r o u t i n gp r o b l e m a n ta l g o r i t h m i san e wk i n d o f m e t a h e u r i s t i ca l g o r i t h m sf o rs o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m so r c o n t i n u o u sf u n c t i o n o p t i m i z a t i o np r o b l e m s t h ec h a r a c t e r i s t i co fp a r a l l e l ， p o s i t i v ef e e d b a c ka n dr o b u s ti ss t r o n g l ys h o w e dd u r i n ga n tc o l o n y sf o r a g e ， a n ta l g o r i t h ma l s oh a st h e s ec h a r a c t e r i s t i c s ，s ot h er e s e a r c ho ft h e o r ya n d u u l i t yo fa n ta l g o r i t h mh a sg r e a tm e r i t t h et h e s i s a n a l y z e st h eb a s i ct h e o r y a n dm o d e lo fa n ta l g o r i t h m ， i n t r o d u c e st h ef e a t u r e so fa n ta l g o r i t h ma n di t sr e s e a r c hs t a t e t h es l o w c o n v e r g e n c ea n ds t a g n a t i o nb e h a v i o ra r et h em a i nd r a w b a c ko fb a s i ca n t a l g o r i t h m ，s o t h et h e s i s p r o p o s e s t w om e t h o d st oo v e r c o m et h e s e s h o r t c o m i n g s f i r s t ，i m p r o v e m e n tb a s e do ns e l f - a d a p ta n t i l o g y ：c o m b i n e sw i t h l o c a la n d g l o b a lp h e r o m o n e sa d j u s t m e n tt ou p d a t er o u t e sp h e r o m o n e d y n a m i c a l l y , a l t e rs o m ec o r r e l a t i v ep a r a m e t e r so fp h e r o m o n ea d a p t i v e l y ； s e c o n d ，i m p r o v e m e n tb a s eo na b e r r a n c ea n t i l o g y ：w h e nt h ea l g o r i t h mg e ti n t o s t a g n a n c y , m u t a t et h ea l g o r i t h mt om a k et h eo p t i m i z a t i o nr e s u l tb r e a ka w a y f r o mt h el o c a lo p t i m i z a t i o na r e a t h ei m p r o v e da l g o r i t h mi se f f e c t i v ea n d f e a s i b l ef o rq o sr o u t i n gp r o b l e m f i n a l l y , t h et h e s i sf r a m e san e t w o r km o d e li no p n e t , d os i m u l a t i o na n d v e r i f yo nt h eu n i m p r o v e da n di m p r o v e da l g o r i t h m ，a n a l y z ea n dc o m p a r et h e i r d i f f e r e n tr e s u l t s t h er e s u l t ss i g n i f yt h ei m p r o v e da l g o r i t h mh a sb e t t e r c o n v e r g e n c ea n di s a b l et oi m p r o v et h eq u a l i t yo fp a c k e tt r a n s m i s s i o n 嘶e c l i v e l y m e a n w h i l e ，t h ei m p r o v e da l g o r i t h ms t i l lr e t a i n sa n ta l g o r i t h m s e x p a n s i b i l i t y k e y w o r d ：a n ta l g o r it h m ；q o sr o u t i n g ：u n i c a s tr o u t i n g ：o p n e t 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其它个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ：勘枷舰 v 口2 年 2 ) 个限制条件的启发式q o s 路由算法 【3 1 1 ：有限路径启发式算法和有限粒度启发式算法。这两种算法的基本思想是限制 在每个节点所记录的最优路径数的大小来减少释放操作的时间和空间复杂度。这 两种算法的关键在于如何限制每个节点的路径数，同时又保持求解的效率。 而改进蚁群算法在q o s 路由的应用研究方面，前人所做的工作主要有：冀 鑫泉的基于改进蚁群系统原理在q o s 单播路由中的应用【加1 ，其中提出了q r b a 算法及改进的q r b a 算法的应用分析；张聪提出的基于移动a g e n t 的q o s 组播 路由研究h 1 1 ，对蚁群算法进行扩展，采用一组协同工作的移动a g e n t 搜索网络， 寻找满足q o s 请求的路径，并对选定路径进行资源预留。其优点在于a g e n t 选 路具有一定的灵活性与适应性；朱玉平的融合蚁群优化算法与遗传算法的q o s 路由选择研究【4 2 l - 文中主要研究了将蚁群优化算法与遗传算法进行融合来解决 q o s 单播路由问题，先运用m m a s 改进传统蚁群算法的寻路，然后用遗传算法 将得到的有效路径进行选择、交叉、变异等优化过程，产生性能更优的下一代群 体；邵巍的加强信息利用率的改进蚁群算法解决路由选择优化问题【4 3 】一文提出 蚂蚁在拓扑图中转移的同时，在信息矩阵中同时转移的思想。改变了信息量的组 织形式，建立了新的信息矩阵，使多只蚂蚁协同工作成为可能。 1 3 本文的内容与创新 1 3 1 本文的组织结构 第一章为绪论，介绍了q o s 路由问题及蚁群算法在q o s 路由中应用的研究 背景、研究意义以及目前的研究情况。 第二章系统介绍了q o s 路由问题及其实现机制。首先给出了q o s 的定义， 解释了q o s 路由的基本概念和原理，给出了q o s 路由的分类、三种主要的q o s 路由策略及三种路由策略间的比较，最后在本章最后一节总结了q o s 路由研究 4 第一章绪论 过程中的主要难点和存在的问题。 第三章介绍了目前通用的基本路由算法，及常用的单播路由协议：路由信息 ( r w ) 协议、最短路径( o s p f ) 协议和边界网关协议( b g p ) ；在本章最后一节，介绍 了单播路由问题的具体描述及单播路由算法的主要分类。 第四章介绍了基本的蚁群系统原理和蚁群算法：介绍了蚁群算法的原理和发 展，对蚁群算法的优缺点进行了详细分析。 第五章首先针对当前基本蚁群算法的各种改进机制进行了系统的分析，分别 归纳了蚁群算法的改进思路、改进类型及不同改进类型的应用领域和性能比较。 并提出了一种基于变异特征的自适应蚁群算法，算法同时引入了自适应思想和变 异思想。既可以利用自适应思想使算法减少进入停滞状态的可能性，又能使算法 在进入停滞时产生变异跳出局部最优解的区域，保证了算法的全局搜索能力。在 本章最后，给出了基于变异特征的自适应蚁群算法的具体流程。 第六章对第五章提出的基于变异特征的自适应蚁群算法应用于实例仿真。首 先阐述了蚁群算法解决多约束q o s 路由问题的基本要点，简要介绍了本文的仿 真工具o p n e t ，然后详细阐述了本文仿真系统的构建过程。最后，对仿真的过 程进行了介绍并依据仿真结果对改进算法进行了性能分析，及与基本蚁群算法的 性能对比。 第七章是总结与展望，总结了本文对基于改进蚁群算法的q o s 路由的研究 工作，包括所取得的成绩与存在的不足，提出以后的主要研究方向。 1 3 2 本文的主要工作与创新 q o s 路由作为未来互联网络的重点攻关内容之一，它的提出与发展对引导未 来互联网络的改革具有重要意义，其研究工作具有很强的现实意义。随着研究工 作的不断深入，使用了众多先进理论和方法。本文尝试对新兴的智能算法一蚁群 算法进行改进，使其应用于q o s 路由研究工作中，并进行了仿真实验和性能分 析，最后作出了总结与展望。 本文的理论方法与技术应用上所作出的创新如下： ( 1 ) 提出了基于变异特征的自适应蚁群算法，该算法同时应用自适应思想与 变异思想对基本蚁群算法进行了改进，结合了两种思想的优点。既可以避免算法 第一章绪论 过早陷入局部最优解，又能使解在算法停滞时以一定概率跳出局部最优解，扩大 算法的全局搜索能力。并把算法引入到q o s 单播路由问题之中。 ( 2 ) 本文对o p n e t 这一世界著名网络仿真软件进行了研究与使用，目前这 一软件在中国的使用尚未普及，主要是由于软件安装困难，相关的教材仍然比较 有限造成的。希望本文对o p n e t 的介绍和使用能引起更多人对该软件的认知和 研究工作。 ( 3 ) 在o p n e t 仿真平台上成功构建了网络仿真模型，并在该模型上使用本 文的改进算法对节点间的通信进行了仿真，仿真效果表明算法具有良好的性能。 仿真达到了测试的目的。 6 第二章q o s 路由问题及实现机制 第二章o o s 路由问题及实现机制 2 1le t f 的o o s 定义 如何在i n t e m e t 上提供综合服务的关键是q o s 控制。早期在a t m 交换机及 其协议中开展的q o s 支持工作为后来口网络中的q o s 问题研究奠定了基础。进 一步地，对于i n t e m e t ，目前人们正在研究新的方法来实现q o s 控制和传输管理， 以迎接由于i n t e r n e t 规模日益扩展和业务流爆炸式增长而带来的挑战。 在r f c 2 2 1 6 中【4 5 1 ，q o s 定义为：用带宽、分组延迟和分组丢失率等参数描述 的关于分组传输的质量。传统的i n t e m e t 只提供单一的服务质量，即“尽力而为” ( b e s t e f f o r t ) 服务。在该服务中，可利用的带宽以及相应的延迟特性取决于网络中 的负载状况。为了进一步描述q o s 控制过程，服务模型与实现框架，r f c 2 2 1 6 还定义了网络元素( n e t w o r ke l e m e n t ) 、流( f l o w ) 、服务( s e r v i c e ) 、行为( b e h a v i o r ) ， 特性化( c h a r a c t e r i z a t i o n ) 及相应的流量规范( t r a f f i cs p e c i f i c a t i o n , t s p e e ) 、服务要求 规范( ( r e q u e s ts p e c i f i c a t i o n ，r s p e c ) 以及q o s 控制相关的其他词语定义。i e t f 规定， “网络元素 是指任何一个可在i n t e r n e t 网络中处理数据分组的构件，它具有在 数据通过时进行q o s 控制的能力。网络元素包括路由器、子网、端主机系统的 操作系统等。“流”则指具有相同q o s 要求和服从同一q o s 控制方法的通过某个 网络元素的分组集合。在一个给定的网络元素中，一个流的分组可以来自于某个 单一的应用，也可以来自于不同的应用。“服务与q o s 控制服务具有相同的意 义。它描述网络元素的q o s 控制能力。服务包括规范和功能两大部分。“行为” 是指与q o s 相关的端到端性能。行为是应用直接可见的由服务提供的最终结果 t s p e c 是要求服务提供的流量描述。t s p e c 实际上是一份数据流和网络元素提供 的服务之间的合同。r s p e c 则是用户对网络元素的q o s 要求。t s p e c 和r s p e c 都被资源预留协议r s v p 规定了相应的格式和定义。 基于上述定义，i e t f 把q o s 定义为一个两维空间：( 服务类型) 、( 参数类 型) 。服务类型与参数类型两者都用整数表示。 ( 服务类型) 的取值范围为【1 ，2 5 4 ，该取值范围被进一步划分为三个区。 即：1 ， 2 ，1 2 7 ， 1 2 8 ，2 5 4 。服务类型l 被保留下来用于指定通用参数。即当服务 类型值为1 时，参数类型中给出的任何参数都可以被所有服务所使用。服务类型 7 第二章q o s 路由问题及实现机制 2 ，1 2 7 表示i e t f 定义的各种服务。i e t f 的i n t s e r v 工作小组负责定义各种服务 的编号。例如，保证型服务的编号为2 ，可控负载型服务的编号为5 。目前，i e t f 还未定义更多的服务类型。如果研究人员开发和定义了新的服务类型，并准备提 交给公众使用的话，应从i e t f 的i n t s e r v 工作小组获得相应的服务编号。服务类 型_ j 1 2 8 ，2 5 4 是专为实验开发保留的。研究人员在实验阶段可任意选取服务号在 本地使用。 与( 服务类型) 相同，( 参数类型) 的取值范围也是 1 ，2 5 4 。区间 1 ，1 2 7 1 是保留 区间，专门用于指定那些供所有服务公用和共享的参数，例如，当前可利用的带 宽等。该区间的参数值与服务类型值l 一起组成公用共享参数，例如 1 ，5 】表示 一个可供各种服务共享的q o s 参数。 1 2 8 ，2 5 4 】由服务规范的设计人员给定，它 们不是共享的，只针对相应的服务类型。 2 20 0 s 路由的基本概念和原理 q o s 路由选择的任务就是从源端到目的端找到一条具有足够资源的路径来 满足端到端服务质量，包括收集网络状态信息并不断更新信息，以及根据己有信 息来为新的连接请求选择一条合适的路由。一个路由算法的性能主要取决于信息 收集的好坏。下面首先介绍一些q o s 路由的基本概念【4 5 】。 ( 1 ) j j h 权图模型 网络的拓扑结构和资源容量可以抽象为一个加权图( ve ) 。其中节点代 表网络中的交换设备，边( e ) 代表传输线路。如果传输线路是对称的，则对应的 边是无向的。因为对称线路对两个方向上的数据都有同样的特性。对于大多数实 际的网络而言，其链路一般都是非对称的，因而其每一条链路对应于模型中，就 是两条有向的加权边。每一条链路都有一个对应于与q o s 度量相关的状态。而 每一个节点也有相应的状态，它可以单独表示出来，或者也可以把它折算到与节 点相连的链路状态中去。 ( 2 ) 状态信息 本地信息 每一个节点都必须保持其最新的本地信息，包括链路传输时延、排队时延、 输出链路的剩余带宽以及其他网络资源的可用信息。 第二章q o s 路由问题及实现机制 全局信息 所有节点的本地信息总和就构成了全局信息。每一个节点可以用链路状态协 议或者距离向量协议来发布、取得全局信息。链路状态协议通过让各节点广播其 本地信息来确定网络的拓扑结构和各链路的状态。距离向量协议通过相邻节点定 期交换其距离向量来取得并扩散全局信息。每一个节点保持的全局信息，总是对 现有网络状态的一种近似这是由于信息传输时延造成的。而时延的不可避免性 表明这种不确定性会随着网络规模的增加而不断扩大 状态信息的聚合 因为任何物理设备的存储资源和处理能力都是有限的，所以对全局信息的精 确保存，会带来要求物理设备增加其存储资源或提高其处理能力的问题，于是降 低全局信息的规模就变得十分重要。这可以通过把一个具有层次性结构的大型网 络的局部信息进行聚合来完成，即把包含几个物理节点的组抽象为一个逻辑节 点，而逻辑节点又可以进一步聚合成更高一级的逻辑节点，如此反复下去。在聚 合过程中，必须把下层节点的网络度量特性聚集为本层逻辑节点的度量特性。这 种过程是复杂的，而不同的聚集方法对状态信息的影响差异很大的。本文限于篇 幅不做深入讨论。如i p 的内部网关路由算法o s p f 支持两层的聚合信息发布， 而a t m 可支持任意多层的聚合。必须注意的是聚合引入了额外的不确定性( 如网 络度量特性的更加不精确) ，并且不确定性会随聚合层次的增加而变大。聚合后 的两个逻辑节点间的链路有可能对应于多条物理链路，从而引入新的问题。 ( 3 ) q o s 度量特性 对于路径p = ( a ，b ，c ，曲，用d ( a b ) 表示对应链路仇b ) 的度量，则q o s 度 量可以按性质分为以下三类 4 6 1 ： 凸性q o s 度量 如果d ( a ，s ) = m i n d ( a , b ) ，d ( b ，c ) ，d ( eg ) ) ，那么度量由传输链路中的瓶颈 决定，即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩 余缓存区、链路速率等。 加性q o s 度量 如果d ( a ，亩= d 仇b ) 十d ( b ，c ) + + d ( e 曲，那么度量由传输通道中所有链路 9 第二章q o s 路由问题及实现机制 的特性共同决定，如时延、时延抖动、费用等。 乘性q o s 度量 如果d 乜b ) = d 伉b ) 木d ( b ，c ) 宰奉d ( 曲，即度量为所有链路对应度量的乘积， 如连接可靠性等。如取d ( 如b ) = l n d “b ) 】，其中，l n ( ) 为以e 为底的对数，则 乘性度量就转换为加性度量。对前述的q o s 度量都可以定义两种基本路由问题： 最优化问题和性能界约束问题。最优化问题就是寻找对应q o s 度量的最优路径。 而性能界约束问题就是寻找大于对应q o s 度量( 如带宽) 或小于对应q o s 度量 ( 如时延) 的一条路径，即在满足性能界要求的集合中选择一个解。优化问题要求 最优解，而对于约束问题，次优解就有可能满足需求。 对于具有上面所说的凸性特征的q o s 度量，可以定义两种基本的路由问题： 链路优化路由，如带宽优化路由问题，就是寻找一个路由使其瓶颈链路带宽最大； 链路约束路由，如带宽约束路由，就是寻找一条路由使其瓶颈带宽大于一个给定 值。链路优化问题可由改进的d i j k s t r a 算法或b e l l m a n - f o r d 算法来实现，而链路 约束问题可以比较容易地转化为链路优化路由问题。 对于具有所说的加性特征的q o s 度量，可以定义另外两种基本路由问题： 路径优化路由，如最小费用路由，就是寻找一条路由使其所通过的所有链路的费 用的和为最小；路径约束路由，如时延约束路由，就是寻找一条路由使其传输时 延小于给定的值。这两类路由问题都可以直接使用d i j k s t r a 或者b e l l m a n f o r d 算 法来解决t 媚。 很多组合路由问题都可以从上面的四种基本问题演化而来。如带宽约束最 小时延路由就属于链路约束。路径优化问题，要寻找满足带宽需求的最小时延路 由，此问题可以通过把不符合带宽需求的链路删除后，用最短路径算法来解决。 另外，用最短路径算法可以在多项式时间内求解的路由问题有以下四类：链路约 束一链路优化问题、链路多约束问题，链路约束路径约束问题，以及路径约束 链路优化问题。而涉及到两个或两个以上加性q o s 度量的优化或约束问题则属 于n p c o m p l e t e 问题。如路径约束路径优化问题、路径多约束问题等。其属于 n p c o m p l e t e 问题是基于以下两个假设：( 1 ) q o s 度量间相互独立，( 2 ) 其值可取实 数或无界整数。如果度量中只有一个取无界整数，而其他度量的取值空间为有界 l o 第二章q o s 路由问题及实现机制 整数，则此类问题不属于n p c o m p l e t e 问题，可以用扩展的d i j k s t r a 或 b e l l m a n f o r d 算法在多项式时间内求解。如果所有度量都与一个共同的度量相关 ( 即度量间是相关的) ，则其也非n p c o m p l e t e 问题，求解时间为多项式时间。例 如，在使用加权公平排队调度的网络中，最差情况的时延和时延抖动是网络带宽 的函数，因此，约束时延约束时延抖动路由属路径多约束问题，可以在多项式 时间内求解。 ( 4 ) q o s 路由粒度 当前因特网都是基于每个分组的目的地址进行传送。综合业务模型( i n t s e r v ) 和r s v p 允许为具有相同目的地址的业务流选路，这种路由粒度下，某中间路由 器到目的地路径的带宽可能不能满足到该目的地所有业务流的带宽总和，但全网 范围内却可能满足。文献 4 8 中建议，在a s 域问选路时，采用流汇聚技术减少 网络中转的a s 域( t r a n s i td o m a i n ) 要处理的流的状态的数量。也就是在入口边界 路由器把进入a s 的业务流( t r a f f i cf l o w ) 按出口节点和流的q o s 请求划分成粗粒 度的几个汇聚流( a g g r e g a t e ds t r e a m ) ，然后在该a s 域内把汇聚流选路到出1 3 边 界路由器，出口边界路由器再把汇聚流里不同的业务流传送到不同的相邻a s 中 去。相同的过程再每一个入口边界路由器中进行，也就是说，q o s 路由粒度可能 随着业务流在网络中的位置变化而变化。 2 30 0 $ 路由分类 网络数据传输主要有单播，组播和广播技术三种方式： 单播( u n i e a s t ) 传输：在发送者和每一接收者之间实现点对点网络连接。如果一 台发送者同时给多个的接收者传输相同的数据，也必须相应的复制多份的相同数 据包。如果有大量主机希望获得数据包的同一份拷贝时，将导致发送者负担沉重、 延迟长、网络拥塞，为保证一定的服务质量需增加硬件和带宽 组播( m u l t i c a s t ) 传输：在发送者和每一接收者之间实现点对多点网络连接。如 果一个发送者同时给多个接收者传输相同的数据，只需复制一份相同的数据包。 它提高了数据传送效率。减少了骨干网络出现拥塞的可能性。主要用于视频会议 等应用场合，这种应用需要将一份数据同时发送给多个用户。而组播技术具有带 宽利用率高、减轻主机路由器的负担、避免目的地址不明确所引起的麻烦。 第二章q o s 路由问题及实现机制 广播( b r o a d c a s t ) 传输：主机之间“一对所有”的通讯模式，网络对其中每一 台主机发出的信号都进行无条件复制并转发，所有主机都可以接收到所有信息 ( 不管你是否需要) ，由于其不用路径选择，所以其网络成本可以很低廉。广播 把数据包的c o p y 发给网络中所有用户，而有的用户此时并不需要数据包，这实 际上将造成带宽资源的一定浪费。 在此基础上，q o s 路由主要被分类为q o s 单播路由和q o s 组播路由。 ( 1 ) q o s 单播路由问题定义如下：给定一源节点s ，一目的节点d ，一个q o s 限制集合c 及可能的优化指标，发现满足c 的从s 到d 的最好可行路径。单播 路由问题包含四种基本的q o s 路由问题：链路约束问题、链路优化问题、路径约 束问题及路径优化问题。 ( 2 ) q o s 组播路由问题定义如下：给定一源节点s ，一目的节点集合r ，一个 q o s 限制集合c 及可能的优化指标，发现满足c 的并遍历s 和r 的所有节点最 优的路由树。组播路由问题的处理与单播路由相似。其区别仅在于，在单播路由 中对路径的优化或约束，变为在组播路由中对路由树的操作。例如，带宽优化路 由就是寻找瓶颈带宽最大的路由树；时延约束路由就是寻找路由树，使其从源节 点到任何一个目的节点。 2 40 0 s 路由策略 通过路由协议交互，每个节点收集到适当的网络状态信息后，需要据此采用 一种相应的路由策略实现路由。按照网络状态信息维护的方式和路径的搜索方式 分类，可把路由策略分为源路由( 集中式路l h ) 、分布式路由和层次化路由。源路 由中，每一个节点维护着完整的全局信息，包括网络拓扑结构和每一个链路的状 态信息，最优路径的计算基于这些全局信息在源节点进行；分布式路由机制中， 每一个节点无须维护全局信息，一般只要知道相邻节点的信息，路径通过在各个 节点之间进行分布式计算获得，控制信息在节点之间交换，综合使用每个节点保 存的状态信息来搜索路径，大部分分布式路由算法都需要一个距离矢量协议( 或 者链路状态协议) 在每一个节点处以距离矢量的形式维护和路由计算相关的信 息，基于这些距离矢量，路由过程一跳一跳地完成；层次化路主要是为了解决可 扩展性问题，把网络中的一部分节点聚合成一个逻辑节点，然后把一部分这样的 1 2 第二章o o s 路由问题及实现机制 逻辑节点聚合成再上一层的逻辑节点，形成一个树结构，路由过程先从最上层的 逻辑节点开始计算。 2 4 1 源路由 源路由【5 明的算法非常简单，易于实现和评价。源节点的集中式计算能够避免 分布式的各种缺点：如网络状态数据不一致所造成的死锁和回路等问题。但由于 每个可能的源节点都需要收集和维护完整的全局状态，因此源路由带来了以下几 个问题： ( 1 ) 由于源路由需要通过链路状态交互，因此维护全局状态的开销很大。 ( 2 ) 源节点根据全局状态计算可行路径，时间和空间开销很大。 ( 3 ) 源节点所维护的全局状态，其陈旧性对路由的性能影响很大。 随着网络规模扩大，以上三个问题越发突出。考虑到可扩展性，在支持q o s 的大型网络中直接使用这种源路由的策略是不可行的。 2 4 2 分布式路由 分布式路由刚中，每个节点并不知道完整的可行路径，甚至只知道可行路径 中的下一跳节点，至于下一跳节点再往后的路径则由下一跳节点计算和决定。当 前i n t e m e t 的路由策略就是这种分布式路由。分布式路由将计算分散在各个中间 节点，减少了计算复杂程度，甚至有的计算只要求节点具有本地状态，因而具有 很好的可扩展性。但是分布式处理较为复杂，尤其是在q o s 多约束时很难设计 良好的启发式算法。此外，由于各个节点依靠本地维护的全局信息独立计算可行 路径，因此由于信息不一致可能造成回路，这就需要额外的回路检测算法。 2 4 3 层次化路由 网络中的节点通过聚集形成多层次的拓扑结构，每个物理节点保存聚集状 态。为建立连接，源节点沿着可行路径发送控制信息，当一个组的边界节点作为 代表这个组的逻辑节点而收到控制信息时，使用源路由的方式将可行路径扩展， 直到通过这个组。层次化路由【5 2 】一直被用来解决大规模网络路由计算中的可扩展 性问题。层次化路由计算的过程通常都要结合源路由策略和分布式路由策略，因 为每一个节点只维护聚合后的一部分网络状态信息。一般来说，在同一层内可以 直接应用己有的源路由策略，分布在不同逻辑层之间的计算结果结合起来得到最 1 3 第二章q o s 路由问题及实现机制 终的路径。所以层次化路由同时具有源路由和分布式路由的优点。与源路由相比， 层次化路由以对数缩减了节点之间交互的信息和每个节点的计算复杂度，具有良 好的可扩展性。 但由于信息聚合会产生附加的不确定性，层次路由算法性能会随着网络规模 而急剧下降。因为q o s 路由对网络状态的不确定性比较敏感，因此，研究能适 应网络不确定性的路由算法就变得十分重要。另外，由于层次路由是把有复杂拓 扑结构的组用一个逻辑节点代替，因而在做本地计算时，远端节点的具体信息是 不可见的，从而使精确计算本地物理节点到远端物理节点的q o s 度量参数值变 为不可能。因此，如何对状态信息进行聚合、如何处理网络的不准确信息，有待 于更进一步的研究。 2 4 4 三种路由策略比较 三种路由策略的优缺点如下表2 1 所示。 表2 1 三种路由策略对比表 路由策略优点缺点待解决问题 源路由集中处理，简保存全局信可扩展性；信 单，不产生环路息，在大型网络中息不确定性；对选 有很大的传输开择路径的影响因 销，计算开销较大素的研究 分布式路由可扩展性好须引入环路多度量约束 控制机制和解决算法的研究；降低 分布式计算的终通信开销 止问题 层次路由可扩展性好，聚合q o s 参多种q o s 度 抑制环路的产生数的实用、有效算量参数的聚合问 法还有待研究 题 在实际网络中，q o s 数据和尽力而为数据是共存的。所以，必须注意q o s 数据和尽力而为数据的融合问题。q o s 数据由于不受资源预留的保护，因此不受 1 4 第二章q o s 路由问题及实现机制 尽力而为数据的影响。然而，如果对数据流动情况的判断失误，尽力而为数据的 吞吐量会极大地受q o s 数据的影响。如在很小q o s 流量而又大量尽力而为流量 的链路上，对于大多数q o s 路由算法，此链路是很好的待选链路，但由于资源 预留的作用，它将导致已经拥塞的尽力而为数据更加拥塞。 2 5o o s 路由算法主要特征 对于一个在实际中运行效果良好的q o s 路由算法。除了考虑路由的优化方 面以外，还要考虑其他问题，如整个网络的性能、路由表信息过时的可能性、链 路参数的频繁变化及信道建立时间的资源预留。 ( 1 ) 一般认为，路由算法在用于广域网实时信道建立的路由选择时，必须具 备下列特征： 算法必须在不牺牲任何呼叫所需条件的前提下，使整个网络性能最大化 算法在实现路由策略时必须设计成能够保证资源预留； 算法必须在几乎不具备全局状态信息的情况下能够正常运行； 算法必须适应链路状态( 如链路时延和可获得带宽) 的变化； 算法必须能够优化q o s 路由所需的多个约束条件。 ( 2 ) q o s 路由选择的两个基本目标： 所选择的路径必须是满足q o s 约束的可行路径； 所选择的路径必须尽量有效地使用网络资源并使网络资源利用率最大化。 ( 3 ) q o s 路由问题一般由三个部分组成： 获得满足应用q o s 请求所必须的q o s 路由计算信息； 建立一条满足q o s 请求的路径； 维护已建立的路径。 对于第部分，可以扩充现有的链路状态协议( 如o s p f ) ，目前的o s p f 协 议将q o s 编码位扩展为5 位，分别指示路由度量指标为费用代价、可靠性、带 宽和时延，全“0 表示无特殊要求。常用的路由算法对于第部分都使用基于 d i j k s t r a 或者b e l l m a n f o r d 的最短路径算法，以带宽、传播时延和跳数为主要度 量准则。目前尚无较好的方法来解决问题，一般认为，r s v p 可以充当q o s 路 由请求和路由维护的信令协议，采用预计算方式周期地计算几种类型的路由。 1 5 第二章q o s 路由问题及实现机制 2 60 0 s 路由研究要点嘲 2 6 10 0 s 路由研究中的主要难点 ( 1 ) n p - c o m p l e t e 问题 同时对两个以上相互独立的参数提出要求时，这个问题就是一个 n p c o m p l e t e 的问题，实时应用往往会对延时，延时抖动，带宽，丢失率，业务代 价等多个参数同时提出性能要求，例如，实时多媒体业务会对延时和延时抖动同 时提出要求，这些参数相互独立时，选择满足多个参数限制的路由就成为 n p c o m p l e t e 问题，n p c o m p l e t e 问题直接关系到路由算法的可实现性。 ( 2 ) 多业务并存 同时承载多种q o s 要求不同的业务时，网络性能优化困难，扩展困难，尤 其是q o s 和尽力而为b e s t - e f f o r t 业务独立共存时，很难确定最优的操作点。 ( 3 ) 节点状态信息的存储量大 q o s 路由中，节点需记录的状态参量将增多，如状态信息的存储量随网络节 点个数的增加而指数性增加，将限制网络的扩展。 ( 4 ) 信息不准确 传输负荷的抖动、新连接的加入等都可能导致网络状态变化，这些变化因素 直接影响全网状态信息的准确性，同时也直接影响算法的性能。 2 6 20 0 s 路由研究存在的问题 q o s 路由研究存在着以下几个问题： ( 1 ) 缺乏路由模型，理论研究困难 由于网络拓扑和业务特性复杂多样，协议数学描述困难。因此，目前多数路 由研究主要是针对某个问题设计启发式算法，而不是基于某种模型从理论上推导 算法特性和性能，这种情况下，为分折算法性能，需要大量仿真工作，由于缺乏 理论支持，在不同的拓扑结构和业务特性下，算法性能可能差异较大，而且仿真 得到的结果缺乏说服力。 ( 2 ) 优化目标不同，评估标准不一致 目前主要的优化目标包括代价和延时等加性参数，评估标准主要有：业务接 入率、阻塞率、数据丢包率、带宽利用率、节点队列长度、代价、信令开销等， 1 6 第二章q o s 路由问题及实现机制 由于各个研究者解决的问题不同，优化目标往往不相同，评估标准也不一致，不 利于比较不同算法的优越性，因此制定出统一的路由性能评估对路由研究具有重 要意义。 ( 3 ) 接入业务的变化对网络状态影响大 现有的q o s 路由依据用户业务对服务质量的要求进行寻路，一旦存在满足 要求的路径就会将业务接入，在业务接入时，没有考虑该业务的接入对网络状态 有多大的改变。因此，可以说目前的q o s 路由是基于服务质量要求的尽力而为 的路由，在这种情况下，如果业务特性变化过快，网络状态急剧变化，网络效率、 阻塞率等特性都会受到很大影响。因此，在今后的研究中网络的性能变化也应该 作为业务接入的一个参考。 ( 4 ) 节点控制与路由过程脱离 网络为业务提供q o s 服务时，节点控制和路由控制是相辅相成，缺一不可 的。 以上问题的解决对设计出高性能的路由算法、更好地满足业务对服务质量的 要求、提高网络资源利用率、实现用户级q o s 至关重要。 1 7 第三章路由算法与单播路由 第三章路由算法与单播路由 3 1 基本路由算法 3 1 1 距离矢量路由算法 距离矢量路由算法是一种基于少量网关信息交换的路由算法，使用此算法的 路由器要求保存系统内所有目的地的信息，通常每个a s ( a u t o n o m o u ss y s t e m 自 治系统) 被简化为一个单一的实体来代表，也就是被抽象为一个口层地址来表示。 在一个a s 肉的路由对另一个a s 内的路由器是不可见的，在路由表里的每一个 条目都含有一个数据报要转发的下一网关地址，同时还包括了由此到目的地的总 距离度量。这里的距离只是个概念意思上的，距离矢量路由算法的得名就是因为 它是通过交换路由表中的距离信息来计算最优路由，同时，信息的交换只是在相 邻的路由器间进行。采用该算法的路由器所拥有的路由信息库的每一条目都由以 下五个主要部分组成： ( 1 ) 主机或网络i p 地址； ( 2 ) 沿着该路由遇到的第一个网关； ( 3 ) 到第一个网关的物理接口； ( 4 ) 至l j 目的地所需的跳数； ( 5 ) 保存有关路由最近被更新时间的计时器。 另外还包含一些标志信息。路由数据库的更新是根据收到的邻居信息进行。 更新消息是主机与网关问进行信息交换最重要的消息之一。距离矢量路由算法就 是根据上面的路由信息库来找出某一数据分组到达目标的最优路径。这里，最优 路径是指分组所经过的实体数最少。具体说来，在每个实体( 主机或路由器) 中 进行着以下路由运算过程： ( 1 ) 在路由器中保存着一个到所有可能目的地的路由表，每一项表目里含有 到目的地的距离d 和到目的地要经过的第一个网关； ( 2 ) 每个路由器要向它的邻节点周期性地发送路由更新信息； ( 3 ) 接收到更新信息的路由器将新路由距离d 与原路由比较，如果d 比原来 的距离d 小，则用它替代原来的。 在上面的讨论中都是假定网络拓扑是固定不变的，如果是在网络结构变化的 l r 第三章路由算法与单播路由 情况下( 例如其中的一个网关或路由器出现故障) ，我们得对上面的算法做些校 正。具体的校正要根据所采用的协议而定。 基于距离矢量路由算法的路由协议具有一定的优点： ( 1 ) 简单、易于理解； ( 2 ) 由于其简易性，因此在路由器上配置这一协议是比较简单的。 同时，这一类的路由协议也有一定的缺点： ( 1 ) f l q 于在网络中，过时的路由不能及时的删除造成的不稳定； ( 2 ) 在大网络中需要很长收敛时间； ( 3 ) f l j 于最大跳数的强调，限制了网络的规模； ( 4 ) 展1 1 使它的数据库没有变化，它也需要周期发送它的距离向量表。 3 1 2 链路状态路由算法 距离矢量路由算法简单扼要，这是它在早期网络几乎无规模而言时能得到广 泛应用的主要原因。在网络拓扑结构相对简单且链路极少发生故障时，这种算法 的效果完全可以令人满意；然而，对于庞大而复杂的网络，该算法计算新路由的 收敛速度极慢，而且在它进行计算过程中，网络处于一种过渡状态，极可能发生 循环并造成暂时的拥塞。再者，当前网络底层链路技术多种多样，带宽各不相同， 而距离矢量算法对此则视而不见。链路状态路由算法就是为了克服这些缺点才提 出并发展起来的。链路状态路由算法的基本思想是：网络中各个节点不必交换通 往目的站点的距离，而是维护一张网络拓扑图，在网络拓扑结构发生变化时及时 更新拓扑图就行。隐藏在链路状态路由算法之后的思想十分简明，它由以下五个 步骤组成： ( 1 ) 发现它的邻居节点，并知道其网络地址； ( 2 ) 测量到它各邻居节点的延迟或开销； ( 3 ) 组装一个分组以告之它刚知道的所有信息； ( 4 ) 将这个分组发送给所有其他路由器； ( 5 ) 使用d i j k s t r a 算法( 又称s p f 算法) 计算到每个其他路由器的最短路径。 实际上，运行链路状态算法并非一定要采用d i j k s t r a 算法，唯一必须遵从的 要求是所有节点都应该使用完全相同的度量制式，也就是说，不论使用什么算法， 1 9 第三章路由算法与单播路由 只要能找出相同的最短路径就行。 链路状态路由算法具有如下一些优点： ( 1 ) 迅速、无环路的收敛性； ( 2 ) 支持精确的量度值，而且如果需要，还能支持多种度量制式； ( 3 ) 支持通往同一目的站点的多重路径； ( 4 ) 能区分内部路由与外部路由。 同时使用基于该算法的路由协议也会带来一些问题： ( 1 ) 与基于距离矢量的路由协议相比，基于链路状态算法的路由协议更加复 杂，更难理解： ( 2 ) 实现这一类的协议需要额外的计划和配置；