（计算机应用技术专业论文）ip+qos路由算法的研究.pdf

摘要 信息时代的来临已经使i n t e r n e t 成为一个重要的、无处不在的基础 设施，与此同时，随着分布式多媒体应用需求的不断增长，以及i n t e r a c t 上商业化应用的飞速发展，对网络性能和服务质量提出了更高的要求。 但是“尽力而为( b e s t e f f o r t ) ”服务仍是目前i n t e r n e t 中主要的一种服务 类别，所有分组在网络中被同等对待，缺少有效的管理，局部的捌塞经 常发生，导致网络性能下降、应用的分组丢失和数据抖动。如何提高i p 网络的服务质量( q u a l i t yo f s e r v i c e ，q o s ) ，已经成为众多国际组织、网 络设备制造商和业务提供者研究和应用开发的焦点问题。 路由选择是i p 网络运行的核心问题，合理高效的路由选择方式不仅 可以保障全网的正常运行，还能够提高网络的接通率。而将i n t e m e t 的 接通率提高，既可以尽量避免交换机不堪重负甚至崩溃的情况，又能降 低网络的运营成本。提高网络的接通率相当大的程度上依赖于路由选择 策略的改变。随着i n t e r n e t 规模的扩大，i p 网络的动态路由选择问题变 得越来越重要。 q o s 路由是实现服务质量的重要手段，这方面的研究一直是i p 网络 研究领域的一个热点。 本文的研究工作主要集中在对i p 网络中的q o s 路由算法的研究上。 在遗传算法和蚁群算法的基础上，提出了两个改进的有效、实用的q o s 路由算法。取得的主要成果如下： ( 1 ) 针对多q o s 约束的路由问题，设计了一种基于可回溯遗传算法的 q o s 路由算法( q o sr o u t i n ga l g o r i t h mb a s e do nt h eg e n e t i ca l g o r i t h mw i t h b a c k t r a c k i n gs t r a t e g y ，g a b s ) 。在遗传进化过程中引入“非自然进化方 法”回溯机制，人为地对染色体的遗传操作进行一定的干预。在进 化过程中设立回溯检查点，探察有无陷入局部最优解，旦发现则及时 补救，将进化过程回溯到上一个检查点，以此为依据人为地对种群施加 定的影响，改善了遗传算法中未成熟收敛的难题。若整个进化过程中 不出现回溯，则退化为传统的遗传算法。通过和传统的遗传算法的比较， 迸一步说明了算法的有效性。 ( 2 ) 针对多q o s 约束的路由问题，借鉴遗传算法和蚁群算法，设计了一 种基于遗传算法和蚁群算法融合的q o s 路由算法( q o sr o u t i n ga l g o r i t h m a c c o r d i n gt ot h ec o m b i n a t i o no ft h eg e n e t i ca l g o r i t h ma n da n tc o l o n y a l g o r i t h m ，g a a c o _ q o s ) 。算法首先利用遗传算法生成若干组优化解， 将其转换成蚁群算法的信息索初值；然后利用蚁群算法来求取满足q o s 约束的最优解( 或非劣解) 。算法中设置了遗传算法控制函数c o ，在给 定的遗传迭代次数范围内，通过c g 值的变化动态地控制遗传算法的迭代 次数，当c o 的值连续若干次都相等时就退出遗传算法，转去执行蚁群算 法，进而确保遗传算法和蚁群算法在适当时机融合。算法既克服了遗传 算法和蚁群算法的缺点，又保留了它们各自的优点。通过和遗传算法以 及蚁群算法的比较，进一步说明了算法的有效性。 关键词：i p 网络，路由，q o s 约束，遗传算法，蚁群算法 i i a b s t r a c t i n t e m e th a sb e e n d e v e l o p e d i n t ot h em o s ti m p o r t a n ta n db a s i c i n f r a s t r u c t u r ei nt h ee r ao fi n f o r m a t i o n a tt h es a m et i m e w i t l lt h e i n c r e a s e i n g d e m a n d so fd i s t r i b u l e tm u l t i m e d i a a p p l i c a t i o n sa n d t h e d e v e l o p m e n to fi n t e r n e tb u s i n e s sa n da p p l i c a t i o n s ，b e t t e ri n t e m e tc a p a b i l i t y a n dq u a l i t yh a sb e e nr e q u i r e dm o r ea n dm o r e h o w e v e r ，t h em a i n s t r a t e g yo f s e r v i c ei ss t i l lb e s t - e f f o r ti nt h ei m e m e t e q u a l l yt r e a t i n ga l lp a c k s ，l a c k i n g e f f i c i e n tq u e u em a n a g e m e n ta n df r e q u e n tc o v e t o u sl e a d st on e t w o r k c a p a b i l i t y sd e c r e a s e ，p a c k e t s d r o p p i n ga n dt r a n s p o r t sj i t t e r i n e s s s o ，h o w t oi m p r o v ei pq u a l i t yo fs e r v i c e ( r pq o s ) h a sb e e nah o tt o p i cf o rm a n y i n t e r n a t i o n a lo r g a n i z a t i o n s ，c o m m u n i c a t i o ne q u i p m e n tp r o d u c e r sa n ds e r v i c e p r o v i d e r s r o u t i n gi st h en u c l e a rp a r to f t h ei pn e t w o r k t h er e a s o n a b l 9a n dh i g h l y e f f e c t i v er o u t i n gm a l m e rn o to n l yc a ns a f e g u a r dt h en o r m a lo p e r a t i o no f t h e e n t i r en e t w o r k ，b u ta l s oc a ne n h a n c et h ec o n n e c t i v er a t ew h o s ee n h a n c e m e n t c o u l da v o i ds w i t h e s d e a d w e i g h ta n ds a v et h eo p e r a t i n gc o s to f t h en e t w o r k i n c r e a s i n gc o n n e c t i v er a t em o s t l yd e p e n d so nt h ec h a n g i n go f t h er o u t i n g s t r a t e g y a l o n gw i t ht h eb r o a d e n i n go f t h ei n t e r a c t , t h ed y n a m i cr o u t i n g s e l e c t i o no f t h ei pn e t w o r kb e c o m e sm o r ea n dm o r ei m p o r t a n t q o sr o u t i n gi st h ee m p h a s i sm e a n st oc a r r yo u tt h eq u a l i t yo fs e r v i c e t h ei n v e s t i g a t i o no nt h i s a s p e c t i sa l w a y st h ef o c u so ft h ei p n e t 、v o r k r e s e a r c h i n gf i e l d t h i sd i s s e r t a t i o nc o n c e n t r a t e so nr e s e a r c h i n gi pn e t w o r k sq o sr o u t i n g a l g o r i t h m s o nt h e b a s i so fg e n e t i ca l g o r i t h m ( g a ) a n da n tc o l o n y a l g o r i t h m ( a c a ) ，i tp r o p o s e ss e v e r a lm o d i f i e dq o sr o u t i n ga l g o r i t h m st h a t p r o v e d t ob ee f f e c t i v ea n dp r a c t i c a l t h em a i na c h i e v e m e n t so f t h i sp a p e ra r e a sf o l l o w s ： ( 1 ) i na c c o r d a n c ew i t ht h eq o sr o u t i n gp r o b l e m ，aq o sr o u t i n ga l g o r i t h m b a s e do nt h eg e n e t i ca l g o r i t h mw i t l lb a c k t r a c k i n gs t r a t e g y ( g a b s ) i s p r o p o s e d i n t r o d u c i n gt h eb a c k t r a c k i n gs t r a t e g yi n t ot h ep r o c e s so fg e n e t i c i i i e v o l u t i o n ，p l a y i n ge f f e c to nt h ep o p u l a t i o na r t i f i c i a l l yb ys e t t i n go f b a c k t r a c e c h e c k p o i n ts e q u e n c e ( b c s ) ，t h ea l g o r i t h ma m e l i o r a t e sc r u d e l yc o n v e r g e n c e c o m p a r e dt ot h et r a d i t i o n a lg e n e t i ca l g o r i t h m ，o u ra l g o r i t h mi se f f e t i v e ( 2 ) p r o p o s eag a a c 0 - _ q o s ( q o sr o u t i n ga l g o r i t h ma c c o r d i n gt ot h e c o m b i n a t i o no ft h eg e n e t i ca l g o r i t h ma n da n t ) a l g o r i t h mb a s eo nt w o a l g o r i t h m sf o rt h eq o sm u t i n gp r o b l e m t a k i n ga d v a n t a g eo fg e n e t i c a l g o r i t h mt op r o d u c et h eo r i g i n a lr e s u l t s w et r a n s f o r mt h e mi n t ot h ei n i t i a l p h e r o m o n e sv a l u en e e d e db ya n tc o l o n ya l g o r i t h m ，t h e nu s ea n tc o l o n y a l g o r i t h mt og e tt h eb e s tr e s u l t s t h ed e f i n i t i o no ft h eg e n e t i ca l g o r i t h m c o n t r o lf u n c t i o ni st oc o n t r o lt h ea p p r o p r i a t ec o m b i n a t i o no p p o r u m i t yo ft h e t w oa l g o r i t h m s ，t h ev a l i d i t yo ft h ea l g o r i t h mi si l l u m i n a t e dw h e nc o m p a r e d t ot h eg e n e t i ca l g o r i t h ma n dt h ea n tc o l o n ya l g o r i t h m k e yw o r d s ：i pn e t w o r k ，r o u t i n g ，q o sc o n s t r a i n t s ，g e n e t i ca l g o r i t h m ， a n tc o l o n ya l g o r i t h m 刘萍：i pq o s 路由算法的研究 第1 章绪论 一般来说，基于存储转发机制的i n t c m e t ( i p v 4 标准) 只为用户提供了“尽力 而为( b e s t - e f f o r t ) ”的服务，不能保证数据包传输的实时性、完整性以及到达的顺 序性，不能保证服务的质量，所以主要应用在文件传送和电子邮件服务方面。随 着i n t e r n c t 的飞速发展，人们对于在i n t e m e t 上传输分布式多媒体应用的需求越来 越大，一般说来。甩户对不同的分布式多媒体应用有着不同的服务质量要求，这 就要求网络应能根据用户的要求分配和调度资源，传统的尽力而为的转发机制， 已经不能满足用户的要求川。因此，以提高网络资源和用率、为用户提供更高服务 质量( q u a l i t yo f s e r v i c e 。q o s ) 为目标的研究领域十分活跃1 2 3 j 。 1 1 o o s 技术 1 1 1 i p q o s 概述 为了解决在i n t e m e t 等计算机网络上高质量传输多媒体信息的问题，美国于 1 9 9 6 年底，开始了以提高网络服务质量研究为核心的i n t e m e t i i 以及n g i ( 下一代 i n t e m e t ) 等研究项目。i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 也成立了专门的工 作小组来研究多媒体服务质量的定义和相关的标准。 网络服务质量是网络与用户之间以及网络上互相通信的用户之问关于信息传 输与共享的“质”的约定，例如，传输延迟允许时间、最小传输画面失真度以及 声像同步等。在i n t e m e t 等计算机网络上为用户提供高质量的q o s 必须解决以下几 个问题： ( 1 ) q o s 的分类与定义 对q o s 进行分类和定义的目的是使网络可以根据不同类型的q o s 进行管理和 分配资源。例如，给实时服务分配较大的带宽和较高的c p u 处理时间等，另一 方面，对q o s 进行分类定义也方便用户根据不同的应用提出q o s 需求。 ( 2 ) 准入控制和协商 根据网络中资源的使用情况，允许用户进入网络进行多媒体信息传输并协商 其q o s 。 ( 3 ) 资源预约 为了给用户提供满意的q o s ，必须对端系统、路由器以及传输带宽等相应的 资源进行预约，以确保这些资源不被其他应用所抢用。 扬州大学碗上学位论文 ( 4 ) 资源调度与管理 对资源进行预约之后，是否能得到这些资源，还依赖于相应的资源调度与管 理系统。 i 1 2q o s 的关键指标 q o s 的关键指标主要包括：可用性、吞吐量、时延、时延变化( 包括抖动和 漂移) 和丢失。 可用性：是当用户需要时网络即能工作的时间百分比。可用性主要是设备可 靠性和网络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳 定性以及网络演进或升级时不中断服务的能力。 吞吐量：是在一定时间段内对网上流量( 或带宽) 的度量。对i p 网而言可以 从帧中继网借用一些概念。根据应用和服务类型，服务水平协议( s l a ) 可以规定 承诺信息速率( c i r ) 、突发信息速率( b i r ) 和最大突发信号长度。承诺信息速率 是应该予以严格保证的，对突发信息速率可以有所限定，以在容纳预定长度突发 信号的同时容纳从话音到视频以及一般数据的各种服务。一般讲，吞吐量越大越 好。 时延：指一项服务从网络入口到出口的平均经过时间。许多服务，特别是语 音和视频等实时服务都是高度不能容忍时延的。当时延超过2 0 0 2 5 0 毫秒时，交 互式会话是非常麻烦的。为了提供高质量语音和会议电视，网络设备必须能保证 低的时延。产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时 延。传播时延是信息通过铜线、光纤或无线链路所需的时间，它是光速的函数。 在任何系统中，包括同步数字系列( s d h ) 、异步传输模式( 删) 和弹性分组环 路( r p r ) ，传播时延总是存在的。 ， 时延变化：是指同一业务流中不同分组所呈现的时延不同。高频率的时延变 化称作抖动，而低频率的时延变化称作漂移。抖动主要是由于业务流中分组的排 队等候时间不同引起的，是对服务质量影响最大的一个问题。某些业务类型，特 别是语音和视频等实时业务是极不容忍抖动的。分组到达时间的差异将在语音或 视频中造成断续。所有传送系统都有抖动，只要抖动落在规定容差之内就不会影 响服务质量。利用缓存可以克服过量的抖动，但这将增加时延，造成其他问题。 漂移是任何同步传输系统都有的一个问题。在s d h 系统中是通过严格的全网分级 定时来克服漂移的。在异步系统中，漂移一般不是问题。漂移会造成基群失帧， 使服务质量的要求不能满足。 丢包：不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务 刘萍：i pq o s 路由算法的研究 的影响都大。在通话期间，丢失一个比特或一个分组的信息往往用户注意不到。 在视频广播期间，这在屏幕上可能造成瞬间的波形干扰，然后视频很快恢复如初。 即便是用传输控制协议( t c p ) 传送数据也能处理丢失，因为传输控制协议允许丢 失的信息重发。事实上，一种叫做随机早丢( r e d ) 的拥塞控制机制在故意丢失 分组，其目的是在流量达到设定门限时抑制t c p 传输速率，减少拥塞，同时还使 t c p 流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。但分组丢失多了， 会影响传输质量。所以，要保持统计数字，当超过预定门限时就向网络管理人员 告警。 1 1 3 q o s 的研究体系、现状及相关技术 q o s 的研究一方面主要着眼于分组调度、拥塞控制，另一方面的主要内容是 资源预留和q o s 路由。 ( 1 ) 关于分组调度、拥塞控制的q o s 研究 网络拥塞是导致网络性能下降的主要原因。控制网络的拥塞，一方面要设计 高效稳定的拥塞控制算法：源端根据网络拥塞状况调整数据发送速率，缓解网络 拥塞。t c p 拥塞控制在这方面发挥着重要作用。但是t c p 拥塞控制算法的一个重 要特点是假定下面的网络层和低层在指示拥塞和控制拥塞方面不提供任何支持。 无论t c p 数据流的始端和终端之间经历什么样的网络层以及网络层的协议如何， 它提供的只是端到端的控制。 由于带宽、缓存等资源相对日益缺乏，i n t e m e t 继续变得拥挤。这种情况下， 人们一方面继续改进己有的端到端的拥塞控制方法，另一方面，意识到仅仅靠端 到端的拥塞控制是不够的。在i n t e m e t 这样的复杂异构系统中，不能指望所有的 i n t e r a c t 应用兼容这种端到端的拥塞控制，网络本身应该参与到资源的管理和控制 中。这就是要在路由器中采用积极的队列管理( a c t i v eq u e u em a n a g e m e n t , a q m ) 技术，包括分组排队算法和分组丢弃策略，也就是说t c p 下层的i p 要参与处理拥 塞控制。分组调度算法决定哪些包可以传输从而分配带宽，分组丢弃策略决定哪 些包被丢弃从而分配缓存。 t c p 是基于窗口的端到端拥塞控制，它在感知到拥塞至采取行动之间有明显 的时延，在这个时延中，如果信息序列很短，也许在反馈信息到达源端后信源已 经传输完毕。而且它又依靠网络层的i p 协议来传输反馈，反馈信息本身也会给网 络造成额外的负担。t c p 拥塞控制不能对所有类型的数据流起作用，从而可能造 成不公平性。基于主动队列管理的拥塞控制则可以做到公平性，因为它不依赖信 源。但是它增加了路由器的复杂性。而基于t c p 的拥塞控制度复杂性可以随信源 4 扬州大学硕士学位论文 的负荷而不同，产生高负荷的信源需要更复杂的控制。基于主动队列管理的拥塞 控制能克服短时间的局部拥塞，但是没有办法根本解决拥塞。最终要通过源端的 流量减少来缓解长时间的网络拥塞。 ( 2 ) 关于资源预留和路由选择的q o s 研究 支持q o s 研究的另一方面是资源预留和q o s 路由f 4 - n 。值得一提的是，不管网 络设计得多么优化，路由都是对拓扑结构和网络状态变化作出响应的一个重要的 网络功能。网络设计通常依赖于对用户流量和负载的长期测量，其目标是产生最 小设备代价的网络拓扑结构，与路由相结合，容纳特定网络条件下预期的用户流 量。约束路由在寻径路由时会受到一定的约束，如带宽或时延的要求。传统的 i n t e m e t 中的路由算法主要是保证基本的连通性，路由协议基于单一的度量 ( m e t r i c ) 优化，如跳数( h o p ) ，其算法有b e l l m a n f o r d 和d i j k s t r a ，难以满足多 样的q o s 需求。所以，有必要用多个路由度量表示网络，如带宽、跳数、时延、 丢包率、时延抖动等，但是找到满足多个约束的路由是非常困难，甚至是不可行 的。 如图1 1 所示，拥塞控制和q o s 路由资源预留，构成了q o s 研究体系的基础 部分f s j 。 图1 1 网络中支持q o s 的研究体系 现在，i p 网络如何提供服务质量q o s 支持这一问题已经成为业界关注的焦点。 对于由q o s 控制来实现q o s 保证，国际上不同组织和团体提出了不同的控制机制 和策略，比较著名的有： i s o o s i 提出了基于o d p 分布式环境的q o s 控制，但至今仍只停留在给出了用 刘萍：i pq o s 路由算法的研究 户层的q o s 参数说明和集成接口阶段，具体实现q o s 的控制策略并未提出； a t m 论坛提出了q o s 控制的策略和实现，a t m 控制是连接预定( c o n n e c t i o n a n d r e s e r v a t i o n ) ”型，它的核心内容是在服务建立之前，通过接纳控制和资源预留来 提供服务的q o s 保证，而在服务交互的过程中，用户进程和网络要严格按照约定 的q o s 实现服务q o s 保证： i e t f 组织也已经提出了多种服务模型和机制来满足对q o s 的需求，其中比较典 型的有：r f c 2 1 1 5 ，r f c 2 1 1 7 以及1 9 9 8 、1 9 9 9 年提出的r f c 2 6 x x 系列中的综合业 务模型、差分业务模型、多协议标签m p l s 技术、流量工程和q o s 路由等，均用 于解决l m e m e t 网络的q o s 控制和管理。 ， ( 3 ) 主要的i p q o s 技术 当前主要的mq o s 技术有：集成服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 资源预留 协议( r s v p ) 5 1 ，区分业务( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v ) 1 1 6 - 2 0 1 ，多协议标 记交换( m u l t i p r o t o c o ll a b e ls w i t c h i n g ，m p l s ) ，流量工程( t r a m ce n g i n e e r i n g ) 2 1 , 2 2 1 ，q o s 路由( q o sr o u t i n g ，q o s r ) 2 3 1 等。 集成服务( i n t s e r v ) 集成服务的基本思想是在传送数据之前，根据业务的q o s 需求进行网络资源 预留，从而为该数据流提供端到端的q o s 保证。资源预留协议r s v p 是集成服务 的核心。这是一种信令协议，用来通知网络节点预留资源。如果资源预留失败， r s v p 协议会向主机发回拒绝消息。集成服务能够在i p 网上提供端到端的q o s 保 证。但是，集成服务对路由器的要求很高，当网络中的数据流数量很大时，路由 器的存储和处理能力会遇到很大的压力。因此，集成服务可扩展性很差，难以在 i n t e m e t 核心网络实施，目前业界普遍认为集成服务有可能会应用在网络的边缘上。 区分服务( d i f f s e r r ) 区分服务的基本思想是将用户的数据流按照服务质量要求来划分等级，任何 用户的数据流都可以自由进入网络，但是当网络出现拥塞时，级别高的数据流在 排队和占用资源时比级别低的数据流有更高的优先权。区分服务只承诺相对的服 务质量，而不对任何用户承诺具体的服务质量指标。i e t f 定义了区分服务的体系 结构。 在区分服务机制下。用户和网络管理部门之间需要预先商定服务等级合约 ( s l a ) ，根据s l a ，用户的数据流被赋予一个特定的优先等级，当数据流通过网 络时，路由器会采用相应的方式( 称为每跳行为p h b ) 来处理流内的分组。 区分服务只包含有限数量的业务级别，状态信息的数量少，因此实现简单， 6 扬州人学硕上学位论文 扩展性较好。它的不足之处是很难提供基于流的端到端的质量保证。目前，区分 服务是业界认同的i p 骨干网的q o s 解决方案，但是由于标准还不够详尽，不同运 营商的d i f f s e r v 网络之间的互通还存在困难。 服务质量路由( q o s r ) q o s r 根据多种不同的度量参数( 如带宽、费用、跳数、时延、可靠性等) 来 选择路由。 q o s r 包括三个主要功能：链路状态信息发布，路由计算和路由表存储。 q o s r 能够满足业务的q o s 要求，同时提高网络的资源利用率。但是q o s r 的计算十分复杂，增加了网络的开销，目前实用的q o s 路由算法还不多见。 ( 至) m p l s 多协议标签交换m p l s 并不是主要的q o s 机制，也不是q o s 的体系结构，但 m p l s 的显式路由功能大大增强了在i p 网络中实施流量工程的能力。对于骨干网 业务提供者来说，这是目前使用最普遍、可实现性最强的一种q o s 机制。 以上四种q o s 技术可以结合使用。例如i n t s e r v 和d i f f s e r v 结合，在核心网采 用d i f f s e r v ，在接入网采用i n t s e r v 。又如m p l s 和d i f f s e r v 结合，或m p l s 和q o s 路由结合。目前m p l s + d i f f s c r v 技术最有可能成为i p 网络运营商首选的q o s 方案。 1 2 o o s 路由 当前i n t e m e t 只提供尽力发送服务，网络层不区分用户业务的种类，而将网络 资源公平地提供给各类业务，在分组丢失、时延等方面公平地对待各类业务。这 种尽力发送的机制使网络层无法保证传输的参数，然而丢包率、带宽、时延、时 延抖动等对于应用业务往往是至关重要的。例如，文件传输业务要求丢包率尽可 能低，而传输时延不是关键因素；实时多媒体业务则更看重时延和时延抖动。这 就要求网络能够区别对待各种业务，并对它们提供不同的服务质量。由于i p 是无 连接的协议，不要求像a t m 网络那样在数据传输前从源到目标节点建立连接。这 种尽力发送的体系结构是无连接、与状态无关的，它既不能支持资源预留，也不 能预测传输参数，甚至还可能产生多媒体实时业务不希望的乱序等。由此，面向 服务质量的网络体系结构应运而生。 1 2 1o o s 路由概述 定义1 i 服务质量( q o s ) q o s 是网络在传输业务流时，业务流对网络服务需求的集合，其中业务流是 指与特定q o s 相关的从源到目的地的分组流【1 9 1 。 刘萍：i pq o s 路由算法的研究 7 q o s 是应用业务对网络传输服务提出的一组可度量的要求，主要包括带宽、 时延、丢包率、时延抖动、费用等。网络在传输相应的数据业务时，必须满足这 组要求。q o s 需求可以通过一个约束集来描述，包括链路约束、路径约束和树约 束【2 0 】。链路约束定义了从源到目的地的每一条链路的约束，如带宽约束：路径约 束定义了从源到目的地的一条路径上端到端q o s 需求，如时延；树约束定义了对 组播中整个组播树的约束，例如对组播树延迟的约束是对树中从源到所有目的地 的路径中最大时延的约束。 定义1 2 可行路径( 可行树) 可行路径( 可行树) 是网络中从源到( 所有) 目标节点的一条路径( 组播树) ， 并且该路径( 树) 具有足够的尚未分配的资源，能够满足特定的q o s 需求。 定义1 3 服务质量路由( q o s r ) q o s r 是一种基于数据流q o s 请求和网络可用资源进行路由的机制 5 1 。或者， q o s r 是一种动态路由协议，并且在其路径选择标准里可能包含可用带宽、链路和 端到端路径利用率、资源消费量、时延、跳数以及时延抖动等q o s 参数【2 5 1 。 当前i n t e m e t 的主要路由协议都是“尽力发送”的，选择路由时即便源到目的 节点之间存在“更好的”路径，只要不是最短路径就不会投入使用，因此可能导 致某些链路空闲时另外一些链路的拥塞。q o s r 就是将传统的最短路径变为一条更 好的路径，其主要目标包括以下两点1 5 j ： ( 1 ) 为每一个接纳的q o s 业务连接请求，找到满足其q o s 要求的可行路径( 组 播树) ( 2 ) 优化全局资源利用率，平衡网络负载，从而最大化网络接受其他q o s 请求的 能力 为了提供q o s 保证，数据传输前通常需要沿着计算好的路径，从源到目的地 传播一个消息，用来通知路径上的所有节点为这个q o s 业务保留相应的资源( 如 带宽、缓存等) ，而后续的数据传输则沿着这条已经预留了资源的路径。因此，q o s r 具有面向连接的特性。 根据计算可行路径的时刻，q o s r 可以分为预计算和在线计算两种。预计算 ( p r e - c o m p u t a t i o n ) 采用一个后台进程，根据网络状态信息来构造路由表，当q o s 请求时，只需通过查找路由表就能确定可行路径1 9 。在典型网络设置中，q o s 连接 请求的到达速率远大于网络的变化速度，因此可以使用预计算模式【“。由于q o s 业务的多样性，路由表为了包含每个可能的q o s 业务，其规模会相当庞大因而降 低了可扩展性。在线计算则是当q o s 请求到达时，再根据状态信息计算可行路径 扬州大学颁上学位论文 这种方式虽然不需要事先构造路由表，但每次路由计算延迟较大，并且路由器负 担很重。 q o s r 问题很难完全解决的原因包括：( 1 ) 寻找同时满足两个以上路径约束 ( 优化) 的可行路径，具有n p 完全( n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e ) 计 算复杂度 2 3 1 ；( 2 ) 为了提高可扩展性所使用的层次化模型产生了多种参数如何聚 集的闯题【“1 ；( 3 ) 网络状态信息的陈旧性极大地影响了q o s r 算法的性能【1 3 1 ：( 4 ) 将q o s r 融入到当前这种尽力发送的路由体系结构中，原有的尽力发送业务将受 到巨大的冲击。 1 2 2 q o s 路由的研究现状 q o s r 是保证网络和业务q o s 的优化路由。这种路由是以资源预留( r s v p ) 为前提，依据网络的资源状态决定是否接纳该业务的连接请求，若接纳，则为该 连接在保证端到端时延要求的路径上各节点预留带宽，实现对业务的接入控制。 在尽量减少资源消耗的基础上，合理分配网络的流量负荷，减少拥塞概率，同时 有利于系统在建立此连接之后，接入更多的业务。一般有两种方案：一种是负载 均衡( 1 0 a d b a l a n c i n g ) ，即将负载均匀地分布在各个链路上。另一种是称为 l o a d - p a c k i n g 的方法，即将带宽需求窄的呼叫全并到某些链路上，使其它链路剩下 足够的带宽以接入带宽需求大的连接，这样保证网络对宽带连接和窄带连接接入 的公平性。 q o s r 是未来互联网络的一个核心功能，其主要目标包括两个： ( 1 ) 为每个接受的q o s 业务流提供服务质量保证 ( 2 ) 达到网络全局资源的最佳利用 前者要求在多约束条件下计算可行路径；后者则要求在多条可行路径中进一 步优化。优化的方式通常是首先设计费用( c o s t ) 函数，然后求解函数值最优的可 行路径。然而，通常多约束下求解( 优化的) 可行路径属于n p 完全问题，不能在 多项式时间内精确求解，为此研究者们设计了很多启发式算法或近似算法。 按照所求解的问题类型和求解方法，q o s r 算法可以分成以下几类：多项式非 启发类、伪多项式非启发类、探测类、限定q o s 度量类、路径子空间搜索类、q o s 度量相关类、花费函数类和概率求解类。这些算法还具有以下3 方面的不足： ( 1 ) 计算复杂度过高而不能在网络中实际应用 ( 2 ) 算法性能过低而找不到实际存在的可行路径 ( 3 ) 大部分算法只是针对q o s r 问题中某些特殊情况 目前研究的几类热点q o s r 算法也存在以下问题：多项式非启发类的算法只 刘萍： i p q o s 路由算法的研究 9 能解决单一可加性约束( 优化) 的问题；基于q o s 度量相关的算法只能应用于基 于速率调度的特定网络环境下，而且不支持对传输延迟的考虑；伪多项式的e b f a 能够精确求解多重受限q o s r 问题，但由于其指数级别的复杂度因而也是不可取 的；基于探测的启发式算法路由时间长、通信开销大，还可能阻塞其他业务，中 间节点需要保存大量的状态；限定q o s 度量的算法复杂度与q o s 度量的粒度关系 密切；路径子空间搜索的算法需要较好的启发函数，它以增大路由失败概率和降 低路由性能为代价，减小了计算开销：基于特定费用函数的算法难以实现费用的 可扩充性，同时，费用的计算代价较高；基于概率求解的算法不易确定和传播链 路概率值，并且需要在费用和最大概率之间折衷。此外，很多算法使用优化的方 式，无形中增加了业务的q o s 要求。 1 2 3 q o s 路由研究需要解决的难点 q o s 路由研究中需要解决的主要难点包括以下几个方面： ( 1 ) n p 完全问题 同时对两个以上相互独立的参数提出要求时，这个问题就是一个n p 完全的问 题。实时应用往往会对时延、时延抖动、带宽、丢包率等多个参数同时提出性能 要求。例如，实时多媒体业务会对时延和时延抖动同时提出要求，这些参数相互 独立时，选择满足多个参数限制的路由就成为n p 完全问题，n p 完全问题直接关 系到路由算法的可实现性。 ( 2 ) 多业务并存 同时承载多种q o s 要求不同的业务时，网络性能优化困难，扩展困难，尤其 是q o s 和尽力而为( b e s t - e f f o r t ) 业务独立共存时，很难确定最优的操作点。 ( 3 ) 节点状态信息的存储量大 q o s 路由中，节点需记录的状态参量将增多，如状态信息的存储量随网络节 点个数的增加而指数性增加，将限制网络的扩展。 ( 4 ) 信息不准确 传输负荷的抖动、新连接的加入撤销等都可能导致网络状态变化，这些变化 因素直接影响全网状态信息的准确性，同时也直接影响算法的性能。 这几点中，“信息不准确”是路由信息不准确中主要解决的问题。 1 0 扬州大学硕士学位论文 1 2 4 q o s 路由研究存在的问题 随着网络和应用业务的快速发展，q o s r 日益成为网络研究的核心问题之一。 目前q o s r 研究还存在着以下几个问题： ( 1 ) 缺乏路由模型，理论研究困难 由于网络拓扑和业务特性复杂多样，协议数学描述困难，因此，目前多数路 由研究主要是针对某个问题设计启发式算法，而不是基于某种模型从理论上推导 算法特性和性能，这种情况下，为分折算法性能，需要大量仿真工作，由于缺乏 理论支持，在不同的拓扑结构和业务特性下，算法性能可能差异较大，而且仿真 得到的结果缺乏说服力。 ( 2 ) 优化目标不同，评估标准不一致 目前主要的优化目标包括费用和时延等加性参数，评估标准主要有：业务接 入率、阻塞率、数据丢包率、带宽利用率、节点队列长度、费用、信令开销等， 由于各个研究者解决的问题不同，优化目标往往不相同，评估标准也不一致，不 利于比较不同算法的性能，因此制定出统一的路由性能评估对路由研究具有重要 意义。 ( 3 ) 接入业务的变化对网络状态影响大 现有的q o s 路由依据用户业务对服务质量的要求进行寻路，一旦存在满足要 求的路径就会将业务接入，在业务接入时，没有考虑该业务的接入对网络状态有 多大的改变，因此，可以说目前的q o s 路由是基于服务质量要求的尽力而为的路 由，在这种情况下，如果业务特性变化过快，网络状态急剧变化，网络效率、阻 塞率等特性都会受到很大影响，因此，在今后的研究中网络的性能变化也应该作 为业务接入的一个参考。 ( 4 ) 节点控制与路由过程脱离 网络为业务提供q o s 服务时，节点控制和路由控制是相辅相成、缺一不可的。 1 3 论文研究内容和组织结构 1 3 1 论文研究内容 ( 1 ) 为了解决简单遗传算法对系统中的反馈信息利用不够，当求解到一定范围时 往往做大量无谓的冗余迭代，求精确解的效率低下，易于陷入局部最优解的问题， 如何引入生物学中的“回溯策略”，改善简单遗传算法中未成熟收敛的难题； ( 2 ) 如何将遗传算法和蚁群算法融合在一起，取长补短，提高求解效率，获得更 刘萍：i pq o s 路由算法的研究 好的求解效果。 l - 3 2 解决思路 ( 1 ) 以简单遗传算法为基础，在遗传进化过程中引入回溯机制，人为地对种群施 加一定的影响，通过修改遗传操作，使可能已经陷入局部最优的进化过程回退到 某个祖先状态，推动其向另一个可能的方向进化，改善了遗传算法中未成熟收敛 的难题。 ( 2 ) 利用遗传算法生成若干组优化解，将其转换成蚁群算法的信息素初值；然后 利用蚁群算法来求取满足q o s 约束的最优路由。设置遗传算法控制函数，在给定的 遗传迭代次数范围内，通过其值的变化动态地控制遗传算法的迭代次数，进而确 保遗传算法和蚁群算法在适当时机融合。 1 3 3 论文的组织结构 论文共分5 章： 第1 章，论述本文的研究背景，介绍i pq o s 技术背景知识，阐述现有的q o s 路由算法研究及其问题，对q o s 路由算法的研究中的几个问题进行了讨论，并对 全文的研究内容作了前瞻性的介绍。 第2 章，介绍了两种经典的用于求解n p 类问题的算法遗传算法和蚁群算 法。它是全文的理论基础。介绍遗传算法的基本原理和特点；介绍蚁群算法的基 本原理、模型和研究现状。 第3 章，通过对简单遗传算法的分析，面向多q o s 约束的路由问题，设计了一 种基于可回溯遗传算法的q o s 路由算法g a b s ( q o sr o u t i n ga l g o r i t h mb a s e do nt h e g e n e t i ca l g o r i t h mw i t hb a c k t r a c k i n gs t r a t e g y ，g a b s ) 。在遗传进化过程中引入回溯 机制，设立回溯检查点序列，以此为依据人为地对种群篪加一定的影响，改善了 遗传算法中未成熟收敛的难题。 第4 章，针对多q o s 约束的路由问题，借鉴遗传算法和蚁群系统，设计了一 种基于遗传算法和蚁群算法融合的q o s 路由算法g a a c q q o s ( q o sr o u t i n g a l g o r i t h ma c c o r d i n gt ot h ec o m b i n a t i o no ft h eg e n e t i ca l g o r i t h ma n da