（计算机应用技术专业论文）多宇宙量子遗传算法在qos组播路由中的应用研究.pdf

摘要 近年来，网络上多媒体通信和分布式环境中的协同工作等应用越来越广泛， 这些应用对网络提出了不同的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 以及组播要 求。因此，如何保证在应用中服务质量的要求以及实现多媒体组播通信成为研 究的热点方向。q o s 中最敏感的指标是时延、带宽以及代价，网络上时延受限 且满足带宽要求的最小组播树问题是个典型问题。由于该问题是经典计算一p 的n p 难度问题，难以用传统优化方法求解。目前常采用启发式方法求解，如遗 传算法( g e n e t ica l g o r i t h m ，g a ) 、蚁群算法等。但这些算法存在收敛慢，且 容易陷入局部收敛等缺陷，如何找到能够克服上述算法缺陷的新型启发式智能 优化算法是目前的研究热点。 本文研究了一种新型的癌发式方法量子遗传算法( q u a n tl i r ag o n e i i c a l g o r i t h m ，q g a ) ，该方法将量子计算引入到遗传算法中，利用量子技术的并 发特征使算法性能得到了提高。在此基础上，本文提出了求解q o s 组播路由问 题的多宇宙量子遗传算法( m u i t i u n iv e f s ep a r a 1 e lq u a n t u mg e n e t jc a l g o r it h m ，以下简称m p q g a ) 实现方案，在方案中对量子旋转门调整策略提 h 了改进措施一采用动态旋转角的调整策略。仿真实验表明：本文的实现方案在 解决q o s 组播路由问题上的性能优于采用常规遗传算法( c g a ) 以及采用静态旋 转角的q g a 算法。 关键字：组播路由：遗传算法；量子计算；多宇宙量子遗传算法 一卜一 a bs t r a c t r e c e n t l y , n e t w o r ka p p l i c a t i o n so fm u l t i - m e d i u mc o m m u n i c a t i o na n d c o o p e r a t i v ew o r ki nt h ed i s t r i b u t e de n v i r o n m e n tb e c o m em o r ea n dm o r ew i d e l yu s e d ， t h e s ea p p l i c a t i o n sd e m a n dt h en e t w o r kt op r o v i d ed i f f e r e n tq o s ( q u a l i t yo fs e r v i c e ) a n dm u l t i c a s tr o u t i n gr e q u e s t s a sar e s u l t ，i tb e c o m e sah o tr e s e a r c hd i r e c t i o no f h o wt oa s s u r et h ed e m a n d so fq o sa n da c c o m p l i s hm u l t i m e d i u mm u l t i c a s t c o m m u n i c a t i o n s t h em o s ts e n s i t i v ep a r a m e t e r si nt h eq o sa r ed e l a y , b a n d w i d t ha n d c o s t ，t h em i n i m u m c o s tm u l t i c a s tt r e e s ，w h i c hs a t i s f i e sb a n d w i d t h sr e q u e s ta n d d e l a y c o n s t r a i n e di nt h en e t w o r ki sat y p i c a lp r o b l e m b e c a u s et h i sp r o b l e mi sa c l a s s i c a ln ph a r dp r o b l e m ， i ti sh a r dt ob es o l v e db yt r a d i t i o n a lm e t h o d s n o wi t o f t e nc a nb es o l v e db yh e u r i s t i cm e t h o d s ，s u c ha sg a ( g e n e t i ca l g o r i t h m ) ，a n t c o l o n ya l g o r i t h me t c b u tt h e s ea l g o r i t h m sm e n t i o n e da b o v ec o n v e r g es l o w l y 、 a n dt r e n dt ol o c a lc o n v e r g e n c e ，i tb e c o m e sah o ts t u d yo nh o wt of i n dan e wt y p eo f h e u r i s t i ci n t e l l e c t i v eo p t i m i z e da l g o r i t h mt h a tc a na m e n dt h ed e f e c t so ft h e s e a l g o r i t h m sm e n t i o n e da b o v ec u r r e n t l y t h i sp a p e rm a k e sas t u d yo fan e wt y p eh e u r i s t i cm e t h o d - - q g a ( q u a n t u m g e n e t i ca l g o r i t h m ) t h a ti n t r o d u c e sq u a n t u mc a l c u l a t i o ni n t og aa n du s eq u a n t u m t e c h n i q u e si n t e r c u r r e n tc h a r a c t e rt oi m p r o v ea l g o r i t h m sp e r f o r m a n c ef u r t h e r m o r e ， t h ep a p e rp r o p o s e st h ee x c o g i t a t i o nt h a tu s e sm p q g a ( m u l t i u n i v e r s ep a r a l l e l q u a n t u mg e n e t i ca l g o r i t h m ) t os o l v eq o sm u l t i c a s tr o u t i n gp r o b l e m ，a n da d o p t s a d j u s t m e n ts t r a t e g y o fd y n a m i cr o t a t i n ga n g e lt oi m p r o v et h eb e h a v i o ro ft h e a l g o r i t h m e x p e r i m e n t ss h o w t h a tt h ea l g o r i t h mo f t h i sp a p e rb e h a v e sb e t t e rt h a ng a a n dq g at h a ta d o p t ss t a t i cr o t a t i n ga n g e lt os o l v eq o sm u l t i c a s tr o u t i n gp r o b l e m k e y w o r d s ：m u l t i c a s tr o u t i n g ；g a ；q u a n t u mc a l c u l a t i n g ；m p q g a 南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机在通信中的应用 作 者：2 0 0 3 级研究生刘春林指导教师逊左塑 题目：多宇宙量子遗传算法在q o s 组播路由中的应用研究 英文题目：r e s e a r c ha n da p p l i c a t i o no ft h em u l t i - u n i v e r s ep a r a l l e l q u a n t u mg e n e t i ca l g o r i t h mo nq o sm u l t i c a s tr o u t i n g 主题词：多宇宙量子遗传算法q o s缀播路由 k e y w o r d s ： m u l t i u n i v e r s e q u a n t u mg e n e t i ca l g o r i t h m q o s m u h i c a s tr o u t i n g 塑基出! 虹厶堂塑土塑f 煎生芏照迨塞 引言 课题背景： 随着i n t e r n e t 的飞速发展，涌现出许多新型的通信需求1 1 ，如视频点播、 多媒体会议、远程教学、远程医疗、网络游戏等。这类应用般涉及多个片1 户， 需要网络提供组播( m u l t i c a s t ) 支持，并且保证服务质量( q o s ：( _ u a l i ty 。f 、 s e r v i c e ) 。o o s 组播路由是实现这类应用的关键技术之一，因而成为研究热点， 其目标是寻找一棵连接源节点和多个目的节点的组播树，使得该树在满足所需 q o s 的前提下代价晟小哺1 。性能出色的组播路由算法为数掘准确及时的传递、 新业务的应用和服务质量的保证提供了必要的保障。 目前常用的用于解决q o s 组播路由的启发式算法 4 5 1 有多种，如遗传算法 1 6 1 和蚁群算法1 7 i 等。但这些算法存在收敛慢，易陷入局部收敛等缺陷，如何找到 新型的、能够克服上述算法缺陷的启发式智能优化算法是目前研究热点。 本文研究了新型的启发式方法量子遗传算法f 8 1 f 9 1 ，该方法将量子计算引 入遗传算法中，利用量子技术的并行特征、量子比特的叠加态表示方法及量子 旋转门调整策略进行更新使算法性能得以提高。在此基础上，本文提出了用多 宇宙量子遗传算法求解q o s 组播路由问题的实现方案，并对量予旋转门调整策 略进行了改进一采用动态旋转角的调整策略1o 】f 。”。仿真实验表明本文实现方案 相比传统遗传算法( c g a ) 及采用静态旋转焦调整策略的q g a ! ”i 算法，具 有收敛迅速、全局优化效能好的特点。 本人i 箨： 量子遗传算法的研究尚处于起步阶段。理论上讲，儿是可以采用遗传算法 进行优化求解的问题都可以采用量子遗传算法进行求解。 在整个课题的研究期间，本人对该课题所涉及的相关背景、专q k 知识、削 内外研究现状进行了定的研究，提出了将量子遗传算法应用于求解q o s 组播 路出问题的解决方案，在方案中采用量子旋转门的动态旋转角调整策略，并且 利用量子计算的并发特征将多宇宙分而治之的思想引入到实现方案中，最后在 直星型生厶芏塑：蜮嚣生堂僮监塞 动态随机生成的网络拓扑图上进行了仿真实验。仿真实验结果表明本文实现方 案在解决q o s 组播路由问题上的性能优于采用c g a 算法及静态旋转调整策略 的q g a 算法。 本文组织： 全文共分四个章节，内容组织如下： 第一章首先介绍了组播的工作原理、组播树的概念。然后介绍了o o s 蹄d j 的约束条件及q o s 路由算法。最后阐述了随机动态网络拓扑图的生成算法及深 度优先递归求解各选路径的算法。 第二章研究了量子遗传算法，包括遗传算法的基本原理、量子遗传劈法的 基本原理及算法的流程。 第三章提出了一种采用动态调整旋转角策略的多宇宙量子遗传算法 3 】求 解q o s 组播路由问题的算法实现方案，并对该方案进行了仿真试验，结果表明： 本文的实现方案同采用c g a 和静态旋转角调整策略的q g a 对同样问题的求解 结果相比，收敛更快，性能更佳。 笫四章总结和展望。 2 一 应塞i l 蝤坐盘堂! 吐型l 窭生望填逢室 第一章纽捅通佑成q o s 埔由 1 1引言 第一章组播通信及q o s 路由 随着多媒体应用的急剧发展，网络带宽资源短缺情况已经越来越明碌，特 别是网络很难同时满足应用的大数据量传输和实时要求，这就要求嘲络系统能 够更加合理地利用有限的网络带宽资源，尽量满足客户应用的各种需求。针列 这个问题提出了组播通信和服务质量( q u a l 崎o f s e r v i c e ，) 的概念。组播通信是 指多个参与者之间的通信。它的特征是源节点发送的信息被组接受者接收， 所有接受者构成了组播组。而随着网络多媒体技术的飞速发展，i n t e r n ecl 的 多媒体应用层出不穷，如i p 电话、视频会议、视频点播( v o d ) 、远程教育等多 媒体实时业务、电子商务在i n t e r n e t 上传送等。i n t e r r i e r 已逐步从单一的数 据传送网向数据、语音、图像等多媒体信息的综合传输网演化。这些不同的应 用需要有不同类型的服务，针对这些问蹶提出了服务质量( q o s ，q u a l i t yo f l s e r v i c e ) 的概念和利用q o s 机制来解决的方法【l 。 1 2 组播通信 1 21 组播通信产生原因 传统的i p 通信有两种方式：第一种是在一台源i p 主机和台目的i p 主 机之间进行即单播( u n i c a s t ) ；第：二种是在一台源i p 主机和网络中所有其它 的i p 主机之间进行，即广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个 主机而非所有主机则要么采用广播方式，要么由源主机分别向网络中的多台目 标主机以单播方式发送i p 包。采用广播方式实现对不仅会将信息发送给不需要 的主机而浪费带宽，也可能由于路由回环引起严重的广播风暴。采用单播方式 实现时由于i p 包的重复发送，会白白浪费掉大量带宽，也增加了服务器的负 载，所以传统的单播和广播通信方式不能有效地解决单点发送多点接收的问题。 i p 组播是指在i p 网络中将数据包以尽力传送( b e s t e f f o r t ) 的形式发送 到网络中的某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。j p 堕垒型些尘鐾堡生些錾塞耋燮 鱼二童坐塑塑篁丝里! ! 堕t i 1 1 引言 第一章组播通信及o o s 路由 随着多媒体应用的急剧发展，嘲络带宽资源短缺情况已经越来越明耀，特 别是网络很难同时满足应用的大数据量传输和实时要求，这就要求网络系统能 够更加合理地利用有限的网络带宽资源，尽量满足客户应用的各种需求。针对 这个问题提出了组播通信和服务质量( q u a l i t yo f s e r v i c e ，) 的概念。组播通信是 指多个参与者之间的通信。它的特征是源节点发送的信息被组接受者接收， 所有接受者构成了组播组。而随着网络多媒体技术的飞速发展i n t e r a el 上的 多媒体应用层出不穷，如i p 电话、视频会议、视频点播( v o d ) 、远程教育等多 媒体实时业务、电子商务在i n t e r n e t 上传送等。! n t e r n e t 已逐步从单的数 据传送网向数据、语音、图像等多媒体信息的综合传输网演化。这魑不同的应 用需要有不同类型的服务，针对这些问题提出了服务质量( q o s ，q u a l i t yo f s e r v i c e ) 的概念和利用q o s 机制来解决的方法“。 1 2 组播通信 1 2 1 组播通信产生原因 传统的i p 通信有两种方式：第一种是在一台源i p 主机和一台日的i p 主 机之间进行即单播( u n i c a s t ) ：第二种是在一台源i p 主机和网络中所有其它 的i p 主机之闻进行，即广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个 主杌而非所有主机则要么采用广播方式，要么由源主机分别向网络中的多台目 标丰机以革播方式发送i p 包。采用广播方式实现时不仅会将信息发送给不需要 的毛机而浪费带宽，也可能由于路由回环引起严重的广播风暴。采用单播方式 实现时，由于i p 包的重复发送，会白白浪费掉大量带宽，也增加了服务器的负 载，所以传统的单播和广播通信力式不能有效地解决单点发送多点接收的问题。 i p 组播足指在i p 网络中将数据包以尽力传送( b e s te f f o r t ) 的形式发送 到网络中的某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。j p 到网络中的某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。j p 煎j 亟世山立厶坐熊! ：婴红生堂笪焦生第一章雒【插通f 。i 及q o s 路由 组播的基本思想是源主机只发送一份数据，这份数据中的目的地址为组播组地 址，组播组中的所有接收者都可接收到同样的数据拷贝，并且只有组播组内的 主机目标主机可以接收该数据，网络中其它主机不能收到。 1 2 2 组播工作原理 组播是一个发送者或多个发送者将数据同时发送给一组( 多个) 接受者1 i j 且只用发送一份数据，数据在传送过程中组播路出器会将数据复制传送给需要 数据的主机。相比较，单播是一个发送者将数据发送给一个接受者，如果要发 给多个接收者，就要将数据同时发送多份，显然这将占用大量带宽。而广播虽 然也能同时发送给多个接收者并且数据也是单一发送的，但接受者h 能是全体 网络，而且路由器和交换机都不会转发广播，所以组播既可以发送给特定的一 组成员，也可以在大型网络中使用，而且对带宽的占用也是很小的。 1 2 3 组播树 在单播模型中，数据包通过网络沿着单一路径从源主机向目标主机传递， 但在组播模型中，组播源向某一组地址传递数据包，而这一地址卸代表个t 机组。为了向所有接收者传递数据，一般采用组播分布树描述i p 组播在网络单 经过的路径。 组播分布树有四种基本类型；泛洪法、有源树、有核树和s t e ir | m v 树。 1 泛洪法( f l o o d i n g ) 是最简单的向前传送组播路由算法，并不构造所谓 的分稚树。其基本原理为：当组播路由器收到发往某个组播地址的数据包后， 首先判断是否是首次收到该数据包，如果是首次收到，那么将其转发到所有接 口上，以确保其最终能到达所有接收者；如果不是首次收到，则抛弃该数据包。 泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数掘包 列表，但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即 使传输出现错误，只要还存在一条到接收者的链路，则所有接收者都能接收到 组播数据包。然而，泛洪法不适合用于i n t e r n e t ，因为它不考虑链路状态，并 产生大量的拷贝数据包。此外，对于高速网络丽言，“首次收到”列表将会很 长，占用相当大的内存；尽管它能保证不对相同的数据包进行二次转发，但不 能保证对相同数据包只接收次。 直立业l 丛厶堂塑l ：堡 缝生鲎焦逾皇第一章纵捅通信殷q o s 路由 2 有源树也称为基于信源的树或最短路径树( s h o r t e s tp a t ht r e e ：s p t ) 。 它是以组播源为根构造的从根到所有接收者路径都最短的分布树。如果组巾有 多个组播源，则必须为每个组播源构造一棵组播树。由于不同组播源发出的数 据包被分散到各自分离的绍播树h ，因此采用s p t 有利于网络中数槲流罱的均 衡。同时，因为从组播源到每个接收者的路径最短，所以端到端( e n d t o - e n d ) 的时延性能较好，有利于流量大、时延性能要求较高的实时媒体应用。s f r r 的 缺点是：要为每个组播源构造各自的分布树，当数据流量不大时，构造s p t 的 开销相对较大。 3 共享树也称r p 树( r p r ) ，是指为每个组播组选定一个共用根( 汇台f r p 或核心) ，以r p 为根建立的组播树。同一组播组的组播源将所要组播的数 据单播到r p ，再由r p 向其它成员转发。目前，讨论最多n h , j 也是最具代表性 的两种共享树是s t e i n e e 树和有核树( c b t ) 。 s t e ih e r 树是总代价最小的分布树，它使连接特定图( g r a p h ) 中的特定组成 员所需的链路数最少。若考虑资源总量被大量的组使用的情况，那么使用资源较 少最终就会减少产生拥塞的风险。s t e i n e r 树相当不稳定，树的形状随组中成员 关系的改变而改变，且对大型网络缺少通用的解决方案。所以s t e i n e r 树只是 种理论模型，而非实用工具。目前，出现了许多s t e i h e r 树的次优启发式生成算 洮。有核树是由根到所有组成员的最短路径合并而成的树。 共享树在路由器所需存储的状态信息的数量和路出树的总代价两个方面具 有较好的性能。当组的规模较大，而每个成员的数据发送率较低时，使用若享树 比较适合。但当通信量大时，使用麸享树将导致流量集中及根( r p ) 附近的瓶颈。 1 2 4 组播转发 单播只关心下一跳在那里，而组播只关心数据从那早来的，所以r o l l t e r 用 r p f ( r e v e r s ep a t hf o r w a r d ：r p f ) 对数据进行检查看是否进行转发，如果r o u t e r 的接收数据端口是数据源到该端口的最短路径，则转发该数据，如果不是，则 丢掉。 塑盟i 唑缸厶生堡! ：i 盟丛生堂僮逾塞 第一章组橘通信及q o s 蹄由 1 2 5 组播的应用前景 i p 组播技术有效地解决了单点发送多点接收的问题，实现了i p 网络中点 到多点的高效数据传送，能够大量节约网络带宽、降低网络负载。作为一种与 单播和广播并列的通信方式，组播的意义不仅在于此，更重要的是，可以利用 网络的组播特性方便地提供一些新的增值业务，包括在线直播、网络电税、远 程教育、远程医疗、网络电台、实时视频会议等互联网的信息服务领域。 组播从1 9 8 8 年提出到现在已经经历了卜几年的发展，许多国际组织对组播 的技术研究和业务开展进行了大量的工作。随着互联网建设的迅猛发展和新业 务的不断推出，组播也必将走向成熟。尽管目前端到端的全球组播业务还未大 规模丌展起来，但是具备组播能力的网络数目在增加。一些主要的i s p 已运行 域叫组播路由协议进行组播路出的交换，形成组播对等体。在i p 孙络中多媒 体业务日渐增多的情况下，组播有着巨大的市场潜力，纽播业务也将逐渐得到 推“和普及。 1 3q o s 组播通信 1 3 1q o s 介绍及关键指标 目前的i n t e r n e t 仅提供尽力而为( b e s t e f f o r ts e r v i c e ) 的传送服务，业 务尽快传送，没有明确的时间和可靠性保障。随着网络多媒体技术的飞速发展， i n t e r n e t 上的多媒体应用如i p 电话、视频会议、视频点播( v o d ) 、远程教育等 多媒体实时业务、电子商务等都使i n t e r n e t 逐步从单一的数据传送网向数据、 语音、图像等多媒体信息的综合传输网演化。这些不同的应用需要有刁i 同类型 的服务质量( q o s ，q u a l i t yo f s e r v i c e ) 以及利用q o s 机制来解决的方法。所谓q o s 机制是包括q o s 参数定义、q o s 参数映射、q o s 管理和维护、q o s 狮商、q o s l 氍控等一系列机制的综合，它贯穿于t s o o s i 所定义的七层模型之中，能够在 应用交付给网络系统之时开始，全面把握和保证应用以及网络系统一致确认的 网络服务质量的实现，使得网络系统在高效平稳的良性环境下运行。而q o s 参 数定义是其重要的组成部分。q o s 通常用带宽、时延、时延抖动和分组丢失率 来衡量。各种应用对服务质量的需求在迅速增长。 豆王盛删l 廷本坐墅二! ：鲤嚣生堂焦鹭竖笫一章组捕通信及q o s 髂 i n t e r n e t 上一些主要应用的业务特征及其q o s 如表1 1 所示。 表l ，1i n t e r n e t 上主要应用的业务特征及q o s 需求表 应用业务特征日o s 需求 电子邮件艾件数据量小、批文件的传输容许时延，带宽需求低：尽力而为传 送 信输远程终端 耵m l 网页浏览一序列小的、突发的文件传输 容许适当的延时；带宽需求：变化 的：尽力而为传送 客户服备器许多小的双自传输 对时延、丢失辜敏感：带宽需求适 当：必绣可靠传送 电子商务 基于i p 协议的连续或变化的馈送对时延、抖动非常敏感：繁宽需求 抵；需妻可颈计的时延和丢失率 语音实时音频 流攥体 变化的1 立速对时髦、抖动非章敏感；带宽需求 高；需要可鞠计的时延和丢失率 显然，现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要 求，需要 n t e r n e t 提供多种服务质量类型的业务。而尽力而为的服务仍将提供 给那些只需要连通性的应用。 服务质量q o s 系指用来表示服务性能之属性的任何组合。为了使其具有价 值，这些属性必须是可提供的、可管理的、可验证和计费的，而且在使用时它 们必须是始终如一的、可预测的、有的属性甚至是起决定性作用的。为满足 各种用户应用的需要，构建对i p 最优并具备各种服务质量机制的网络是完全必 要的。专线服务、语音、文件传递、存储转发、交互式视频和广播视频是现有 应用的一些例子。 q o s 的关键指标主要包括：可用性、吞吐量、时延、时延变化( 包括抖动和 漂移) 和丢失。下面详细叙述。 1 可用性 是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠性和 网络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳定性 以及网络演进或升级时不中断服务的能力。 2 吞吐量 是在一定时划段内对网上流量( 或带宽) 的度量。对i p 网而言可以从i 陨中继 嘲借用一些概念。根据应用和服务类型，服务水平协议( s l a ) 可以规定承诺信患 盎复幽! u 厶堂型 ：! ：型嚣生堂焦喧堂第章纰捅通f j 发q o s 路山 速率( c i r ) 、突发信息速率( b i r ) 和最大突发信号长度。承诺信息速率是应法予 以严格保证的，对突发信息速率可以有所限定，以在容纳预定长度突发信号的 同时容纳从话音到视像以及一般数据的各种服务。一般讲，吞吐量越人越好。 3 时延 指一项服务从网络入口到出口的平均经过时间。许多服务，特别是话音和 图像等实时服务都是高度不能容忍时延的。当时延超过2 0 0 - 2 5 0 毫秒时，交1 1 式会话是非常麻烦的。为了提供高质量话音和会议电视，网络设备必须能保l l f 低的时延。 产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时筵。 传播时延是信息通过铜线、光纤或无线链路所需的时间它是光速的函数。扫： 任何系统中，包括同步数字系列( s d h ) 、异步传输模式( a t m ) 和弹性分组环路 ( r p r ) ，传播时延总是存在的。 4 时延变化 是指同一业务流中不同分组所呈现的时延不同。高频率的时延变化穗作抖 动，而低频率的时延变化称作漂移。抖动主要是由于业务流中相继分组的排队 等候时间不同引起的，是对服务质量影响最大的一个问题。某些业务类型，特 别是话音和图像等实时业务是极不容忍抖动的。分组到达时间的差异将在话音 或图像中造成断续。所有传送系统都有抖动，只要抖动落在规定容差之内就不 会影响服务质量。利用缓存可以克服过量的抖动，但这将增加时延，造成其他 问题。 漂移是任何同步传输系统都有的一个问题。在s d h 系统中是通过严格的令 网分级定时来克服漂移的。在异步系统中，漂移一般不是问题。漂移会造成基 群失帧，使服务质量的要求不能满足。 5 丢包 不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务的影 晌都大。在通话期间，丢失一个比特或一个分组的信息往往用户注意不到。在 视像广播期间，这在屏幕上可能造成瞬间的波形干扰，然后视像很快恢复如初。 即便是用传输控制协议( t c p ) 传送数据也能处理丢失，因为传输控制协议允许丢 失的信息重发。事实上，一种叫做随机早丢( r e d ) 的拥塞控制机制在故意丢失分 煎室蜓! 垫厶堂塑上盟嚣生堂焦监塞鹕一章组橘通情搜q o s 路由 组，其目的是在流量达到设定门限时抑制t c p 传输速率，减少拥塞，同时还使 f o p 流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。但分组丢失多了， 会影响传输质量。所以要保持统计数字，当超过预定门限时就向网络管理人员 告警。 1 3 2q 0 8 路由的约束条件 l ，约束条件的选择 约束条件代表了网络的特征，这是决定q o s 路由算法的复杂性，也是提供 不同服务质量( q o s ) 保证互联网络可行路径范围的主要因素。需要考虑的阏素主 要有： ( 1 ) 对任何选择的约束条件而言，必须存在计算路径的有效算法，以保汪路 山协议能够扩展至i n t e r n e t 等大型网络 ( 2 、约束条件必须反映网络的基本特性，并应当包含支持摹本q o s 需求的 信息 ( 3 ) 约束条件之间必须是相互的以保证约束条件不包含冗余信息 2 约束条件的性质 q o s 路由中算法复杂度关系至u o o s 路由算法的可实现性。度量参数选择直 接关系到算法复杂度问题。 合理解决多参数问题，在没计低复杂度的q o s 路【如 算法中占有重要地位。另外，网络支持的度量参数反映并影响路由选择算法的 性能。支持的度量参数越多。越能有效保证提供给接入业务的服务质量，但是 路由选择算法复杂度增大，存在完全满足参数限制的路由的概率减小，业务接 入率降低。 q o s 路由问题包含多个约束条件，如：时延、带宽、成本、抖动和分组 丢失率等。本文在设计q o s 路由算法时主要考虑时延、带宽、成本三个约束条 件。根据运算规则，这些度量参数可以分为加性度量参数、乘性度量参数和凹 一陛度量参数。时延、时延抖动、成本为可加约束条件，分组丢失率为可乘约束 条件，带宽为凹性约束条件。假设路径p 包含r l 条链路 1 1 ，1 2 ，1n j ，r ( 1 i ) 为是链路1 i 的参数值，f ( p ) 为路径p 的参数值，各种度量参数特性如下： 加性度量参数：f ( p ) 2 f o ，) 塑复衄生厶堂熊土班盥生堂趣途皇： 第一章纰捕通1 芹段q o s 路由 乘性度量参数：f ( p ) 凹性度量参数：f ( p ) 根据度量参数的组合方式可以将路由选择算法分为单混合度量参数路由算 法和多度量参数路由算法。本文算法考虑的是一种多度量参数路由算法，即满 足带宽条件的时延受限的代价最小组播路由问题。这样考虑到减小算法的运算 量，有必要先修剪不满足q o s 需求的所有链路。带宽为瓶颈约束条件，时延为 可加约束条件，不满足带宽时延条件的路径可以在预处理步骤删除掉，这样最 后只需考虑剩下的满足带宽时延条件的路径。 1 3 3o o s 路由算法 从2 0 世纪9 0 年代开始，传统的i n t e r n e t “尽力而为”服务机制受到网络上 呈几何级增长的信息流量和越来越多的信息类型的冲击，尤其是各种实叫多媒 体应用程序使原有的协议模式难以满足网络用户的需求。对网络服务质量算法 的研究逐步发展起来。 q o s 算法所考虑的主要参数包括带宽、延时、延时抖动、速率、可靠性、 丢报率、缓存空间、代价等。按照算法所解决的问题，现有的q o s 路由算法i ；3 以分为链路优化、链路约束、路径( 或组播树) 最优化、路径( 或组播树) 约束等相 关问题以及它们的组合问题；按照算法的性质，可以分为单播源路出、单撂分 稚式路由、组播源路由、组播分布式路由、分层路由等。为了解决容错性问题， 还需要诸如多路路由、重路由等算法。各种路由策略的特点按照网络状态信息 维护的方式和路径的搜索方式分类，可把路由策略分为源路由( 集中式路由) 、分 前j 式路由和层次路由。 源路出中，每一个节点维护着完整的全局信息，包括网络拓扑结构和每 个链路的状态信息，摄优路径的计算基于这些全局信息在源节点进行源路 f 。 由于源路由的路径计算在同个节点进行，所以它避免了分布式计算中死锁检 测、分布计算终止检测等问题，并且可以保证计算出来的路径不出现凹环。当 然源路由也有如下四个缺点： ( 1 ) 会聚信息量大。由于每一个节点都需要维护整个网络的状态信息，所以 m 矿，。兀h试蛆 r n 逝盛唑! 缝厶堂蜒丛窭生望焦逾塞籀一帝纰插通信发q o s 路由 网络中会聚的信息量很大，因而导致网络的整体效率也相应降低。 ( 2 ) 状态不完全精确。由于整个网络的大量状态信息需要会聚到每一个节 点，而会聚需要一定的时| 白j ，导致节点所使用的网络状态信息并不能精确地反 映网络的实时状念。 ( 3 ) 源点的计算量大。节点接收到会聚的网络状态信息之后，需要启动个 最短路径算法，根据整个网络的拓扑信息来计算本节点到所有其它节点的最短 路径，据此生成路由表。这样的计算在每一个节点都要进行一次，计算量非常 大。 ( 4 ) 具有可扩展问题。由于每个路由器的存储量是有限的，因此随着网络规 模扩大，支持源路由的路由器所维护的网络状态信息量也随之增大，对】：人姒 模的网络，路由器的存储空间就很难满足源路由策略的要求。 分布式路由机制中，每一个节点无须维护全局信息，一般只要知道相邻节 点的信息，路径通过在各个节点之间进行分布式计算获得，控制信息在节点之 问交换，综合使用每个节点保存的状态信息来搜索路径。大部分分布式路由算 法都需要一个距离矢量协议( 或者链路状态协议) 在每一个节点处以距离矢量 的形式维护和路由计算相关的信息，基于这些距离矢量，路由过程一跳一跳地 完成。分布式路由在分布式路由过程中，路径的计算分却在路径上的节点之问， 所以对路由要求的计算量小、晌应快。由于节点不需要保存全局信息，所以可 扩展性好。但是这种分布式计算也导致了以下一些问题： ( 1 ) 会聚信息种类多，不易管理。 f 2 ) q t l 难对一些n p 或者n p 难的路由问题，尤其是q o s 路d _ 问题设计启发 式路由算法。 ( 3 ) 状态信息不精确时会产生回环，由于节点所维护的信息来选择其它的路 径，回环问题的出现通常会导致路由过程的失败。 层次路由主要是为了解决可扩展性问题，把网络中的一部分节点聚合成一 个逻辑节点，然后把一部分这样的逻辑节点聚合到上一层的逻辑节点，形成 个树结构，路由过程先从最上层的逻辑节点开始计算。分层路由一直被用来解 决大规模网络路由计算中的可扩展性问题。分层路出计算的过程通常都要结合 源路由策略和分布式路由策略，因为每一个节点只维护聚合后的一部分网络：状 塑星l l 业竖厶堂塑婴童生堂丝迨塞第一章纰播通信搜q o s 路m 态信息。一般来说，在同一层内可以直接应用已有的源路由策略，分布在不同 逻辑层之洲的计算结果结合起来得到最终的路径。所以分层路由同时具自源路 山和分布式路由的优点。但是这种机制也导致了以卜- 一些缺陷： ( 1 ) 状态信息的不精确性增强。把部分节点的状态聚台成一个节点，j j 条逻辑链路的信息来表示多条链路路径的综合信息，这个过程增加了网络节点 中维护的状态信息的不精确性。 ( 2 ) 多个q o s 参数的节点组的无法会聚成一个。对于c o s 路由而苦，不i 刊 的q o s 参数要求不同的节点链路聚合方式，而这些方式通常都是：f j 相矛盾的， 因此，要在多个节点聚合成一个逻辑节点的同时聚合这些节点的多个q o s 参数， 在很多情况下都比较困难，i f l 前还没有较好的方法。 单播路由根据对q o s 需求的不同，常见的单播q o s 路由算法可以分为链路 约束一链路优化( 如带宽约束、缓存优化) 路由、链路约束路径优化( 如带宽约束、 延时最小) 路由、组合链路约束( 如带宽、缓存联合约束) 路由、链路约束路释约 束( 如带宽、延时联合约束) 路由、路径约束一链路优化( 如延时约束、带宽优化) 路由、路径约束路径优化( 如延时约束、最小耗费) 路由、组合路径优化( 如延时、 延时抖动联合约束) 路由共七个问题，其中后两个问题属于n p 完全问题。多个 相互独立的q o s 参数的约束优化问题一般都是n p 完全问题。 组播路由按照所解决的问题，组播q o s 路由算法大致可以分为链路约束 链路优化( 如带宽约束、缓存优化) 路由、链路约束组播树优化( 如带宽约束、最 小耗费) 路由、组合链路约束( 如带宽、缓存联合约束) 路由、链路约束组播树约 束( 如带宽、延时联合约束) 路由、组播树约束链路优化( 如延时约束、带宽优化) 路由、组播树约束组播树优化( 如延时约束、最小耗费) 路由、组播树组合优化( 如 延时、延时抖动联合约束) 路由共七个问题，其中第二个问题和最后两个问题属 于n p 难度的问题【3 】【郇。 o o s 组播路由的数学模型定义： 以上主要研究了一些q o s 组播路由问题的基本概念，下- 面讨论建立o o s 组描 路由问题的数学模型所需的一些重要定义。 定义卜1 有向图g = ( v e ) ，其中v 是节点集，可以表示交换机、路由器 和主机，或者予网；e 是边集，代表通信链路，n = lvl ，m = lel ，边e 。e ， 塑基业啦点掌塑上班嚣生堂焦适皇 第一章组l 插通信肢q o s 路由 标识为e i j = ( v i ，v j ) ，表示从结点v i 到v j 之间的一条直通的链路，i ，ji ，2 ，n ， v i ，v j v ，s v 为组播源节点，m v s ) ) 为组播终点集，r + 表示f 实数集， r 十表示非负实数集。 定义1 2 边e i j 有三个属性：长度l e n g t h ( k m ) ，媒体传播速度t r ( k m s ) 和误码e f 。 定义卜3 结点v i 的褐性：di n 一表示每个结点v 一的入度，即以v 。为尾的边 数：do u t i 表示为每个结点v i 的出度，即以v ，为头的边数：d 产( di n 、+ ( 1o u t i ) 薹m 为每个结点的度数；v i 的服务速率为s f ( b i t s ) ，v i 一 p t i l ，p t i2 ， p t k = d i ，i = l ，2 ，n ，p t t k 表示v 连接第k 个边的端阳，端口有两个属性： 端口吞吐率t p ( b i t s ) ，端口缓冲空间b f ( b y t e ) 。 定义i - 4 每条边有4 个函数：延迟函数d e l a y ( e ) ： e r ： 代价函数 c o s t ( e ) ：e r + ：可干i 用的剩余带宽函数：b a n d w i d t h ( e ) ：e r + ；延时抖动 函数d e l a y jit t e r ( e ) ：e r + 0 定义1 5 对于任一网络结点n v ，也定义了4 个函数：延时函数d e a y ( n ) ： v r + ；代价函数c o s t ( n ) ：v r + ；结点分组丢失率p a c k e t l o s s ( r ) ：v i + ) ； 与调度机制相关的结点延迟抖动d e l a y j i t i e r ( n ) ：v r + o 定义卜6 根据以上定义，对于给定的源节点s v 。，终点集m ，s 和m 组成 的组播树t ( s ，m ) 存在下列关系： d e l a y ( p ts ，t ) ) = d e l a y ( e ) + d e l a y ( n ) e e p t ( s ，i )n e p 7f f ) c o s t ( r ( s ，m ”= c o s t ( e ) + c o s t ( n ) e e p t ( s j )n e p f ( s ，f ) b a n d w i d t h ( p t ( s ，t ) ) = m i n ( b a n d w i d t h ( e ) ，e p t ( s ，t ) ) d e l a y j i u e r ( p ts ，t ) ) = d e l a y _ i i t t e r ( e ) + d e l a y j i t t e r ( n ) c e p t ( s ，t )n e n 5 ，f ) p a c k e t l o s s ( p ts ，t ) ) = 1 n ( 1 - p a c k e t l o s s ( n ) ) n e p r ( s ，t ) l1 1 ) ( 1 2 ) ( l 3 ) ( 1 4 ) ( 1 5 ) 其中，p r ( s ，t ) 为组播树，t ( s ，m ) 上源节点s 到终点t 的路由路径。可见本 模型只考虑网络结点的包丢失率( 因缓冲溢出) ，而忽略链路的包丢失率，这与 壶基唑丝厶坐熊! ：盟盔生空焦迨塞 第一章组捕调f ? i 及q o s 鼢l i 实际情况相符。 定义卜7 o o s 组播路由问题可以定义为：给定有权图g = ( v ，f ) ，定义 了边函数和节点函数，源节点s ，目的节点集d ，节点之间存在通路，求有权图 中的一个子图，包含所有的组播节点( 包括源节点和目的节点) ，并f l 满足边函 数和节点函数的约束。 q o s 路由算法发展趋势： 传统的计算机互联网络路由理论把