（计算机应用技术专业论文）计算机网络中的多qos约束组播路由算法.pdf

山东大学硕士学位论文 摘要 q o s 组播路由是给定一个源节点s ，一组目的节点集d ，一系列q o s 限制条件c ， 以及可能的优化目标，寻找满足c 的覆盖s 和d 中所有节点的最好的有效树，这是一 个n p 完全问题。 当前多数q o s 组播路由研究集中在下面的几个问题：带宽受限组播路由：延迟 受限组播路由；延迟受限最小代价组播路由；时延一时延抖动受限组播路由。求解 该类问题是一个n p 完全问题，不存在确定型多项式复杂性解法。目前都采用启发 式算法来解决，当前提出的启发式算法十分复杂而难以求解，该类问题是学术界 的研究热点。 本文提出了用正交试验，找出蚁群算法各个参数最佳组合。从蚁群搜索最短 路径的机理看到，算法中有关参数的不同选择对蚁群算法的性能有至关重要的影 响，但其选取的方法和原则，目前尚没有理论上的依据，通常都是根据经验而定。 本文通过一系列的对比实验研究，来探讨蚁群算法中参数的最佳设定原则。首先， 让一个参数变化其他参数不变，进行仿真实验，找出这个参数最佳值范围；然后， 各个参数在其最佳值范围内，选取若干个值，进行正交试验，找出最佳组合。 本文提出了一种新的改进蚁群算法，通过构建确定性选路概率函数和基于交 叉变异的变异操作，加速算法的收敛速度；对信息素实行多个独立q o s 约束的惩罚 性更新策略，使算法满足用户的q o s 要求；考虑到网络实际应用，算法设计中引进 了基于链路利用率的负载均衡和拥塞规避重路由策略，提高算法的鲁棒性。实验 表明，应用这种改进型蚁群算法于多播路由问题，可以得到比现有启发式算法更 好的结果。 本文同时提出将改进的蚁群算法和免疫遗传算法的融合而得到的一种启发式 算法蚁群遗传算法( a n tc o l o n yg e n e t i ca l g o r i t h m ) ，其具有蚁群算法的求 解精度又具有遗传算法的全局收敛性，同时具有免疫算法的群体多样性，考虑负 载均衡，以满足多q o s 约束组播路由要求，减少拥塞发生。在做理论研究的基础上 进行实验研究。一 关键词：组播路由：服务质量；蚁群算法：遗传算法：参数选择 山东大学硕士学位论文 a b s t r a c t m u l t i c a s tr o u t i n gc a nb ed e s c r i b e da sf o l l o w ：a c c o r d i n gt oas o u r c e n o d es ，ag r o u po fd e s t i n a t i o nn o d es e td ，as e r i s e so fl i m i t e dc o n d i t i o n ca n ds o m eo p t i m a lo b j e c t s ，at r e ec a nb ef o u n dt oc o v e ru psa n dda n d i ss a t i s f i e dw i t hc n o w a d a y st h es t u d yo fm u l t i c a s ti sc o n s e n t r a t e da sf o l l o w s ：b a n d w i d t h c o n s t r a i n tm u l t i c a s tr o u t i n g ，d e l a yc o n s t r a i n tm u l t i c a s tr o u t i n g ，d e l a y c o n s t r a i n ta n dl e a s tc o s t m u l t i c a s tr o u t i n g ，d e l a ya n dd e l y j i t t e r c o n s t r a i n tm u l t i c a s tr o u t i n g t h es o l u t i o nf o rt h i sk i n do fp r o b l e mi s n p c o m p l e t e i tm e a n st h a tt h e r ei sn od e f i n i t i o np o l y n o m i a l c o m p l e x i t y s o l u ti o n t h i sp a p e rp r e s e n t st h ep r i n c i p l e ，t h ec h a r a c t e r i s t i c s ，t h e c o n s t r u c t i o na n dr e a l i z a t i o nm e t h o da b o u tt h eb a s i cm o d e la s ( a n ts y s t e m ) o ft h ea n t c o l o n ya l g o r i t h m e x p e r i m e n t a la n a l y s e sa r ec a r r i e do u to nt h e r e a s o n a b l es e l e c t i o no nt h ep a r a m e t e r so ft h i sa l g o r i t h m ，a n db a s i c p r i n c i p l e sf o rt h ep a r a m e t e rs e l e c t i o na r ep r o v i d e d t h ep a p e rp r o p o s e s a no r t h o g o n a l ，o r t h o g o n a ld e s i g nm u l t i c a so p t i m a l i na c c o r d a n c ew i t hm u l t i p l ec o n s t r a i n e dq o sm u l t i c a s tr o u t i n g p r o b l e m ，an e wa l g o r i t l m l m m r - a c oi sp r o p o s e d m m r - a c oa c c e l e r a t e st h e s p e e do fc o n v e r e r g e n c et h r o u g hs t r u c t u r i n gd e f i n i t es e l e c t i n g p r o b a b i l i t yf u n c t i o na n dm u t a t i o no p e r a t o r ；i no r d e rt om e e t i n gu s e r sq o s d e m a n d ，m m r - a c oi m p l e m e n t sp u n i s h m e n tp h e r o m o n eu p d a t i n gt a c t i c sb a s e d o nm u l t i p l ei n d e p e n d e n tq o sc o n s t r a i n t s ；c o n s i d e r i n gp r a c t i c a l a p p l i c a t i o no fn e t w o r k ，t h el o a db a l a n c i n gb a s e do nu t i l i z a t i o nr a t i oo f t h e1i n ka n dt h et a c t i c so fc o n g e s t i o na v o i d a b l er e r o u t i n gh a v eb e e n i n t r o d u c e di nt h ea l g o r i t h md e s i g n ，wh i c hc a ni m p r o v et h er o b u s t n e s so f a l g o r i t b a n t h ee x p e r i m e n t a lr e s u l ti n d i c a t e sh 叫t a c oi sak i n do fc o r r e c t ， e f f e c t i v eo o sm u l t i c a s tr o u t i n ga l g o r i t h m i nt h i sp a p e r ，ip r o p o s ean e wa l g o r i t h m - a c g at os o l v eq o sm u l t i c a s t r o u t i n gp r o b l e m ，w h i c hi sc o m b i n e dw i t ht h ea n ta l g o r i t h ma n dt h eg e n e t i c a 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 c g ai ss u p e r i o rt ot h eg e n e t i c a l g o r i t h ma n dt h ea n ta l g o r i t h mi nq u a l i t ya n de f f i c i e n c y k e yw o r d s ：m u l t i c a s tr o u t i n g ；q u a l i t yo fs e r v i c e ；g e n e t i ca l g o r i t h m ；a n ta l g o r i t h m ； o 砸i n a ls e l e c t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：虞童毛 e t 期：圣避咝一 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蟑导师签名： 山东大学硕士学位论文 第一章绪论 随着宽带化成为建设信息高速网络架构的重点，许多城市的城域网接入到核 心各个部分都实现了宽带化，架构了以口为基础的无阻塞数据承载平台。 网络的宽带化不仅是为了让人们在宽阔的信息高速公路上更顺畅地进行交 流，而且人们越来越希望宽带网络带来更直观更丰富的多媒体信息表现。组播技 术为多媒体业务的开展提供了传送技术的基础。 组播技术涵盖了从地址方案、成员管理、路由和安全等各个方面。从目前的 情况看，组成员管理普遍采用i g m p v 2 ；p i m s m 因其良好的扩展性和从共享树 向信源树转换的能力而成为域内组播路由的首选协议：域问路由技术现阶段普遍 采用p i m s m m b g p m s d p 协议组合的方案。 组播技术可以提供包括流媒体、视频会议在内的各种宽带增值业务，业务的 顺利开展还依赖于有效的业务管理、监控及安全控制。 1 1 组播技术的产生原因 传统的d 通信有两种方式：第一种是在一台源口主机和一台目的口主机 之间进行，即单播( u n i c a s t ) ；第二种是在一台源主机和网络中所有其它的口 主机之间进行，即广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而非 所有主机，则要么采用广播方式，要么由源主机分别向网络中的多台目标主机以 单播方式发送口包。采用广播方式实现时，不仅会将信息发送给不需要的主机 而浪费带宽，也可能由于路由回环引起严重的广播风暴；采用单播方式实现时， 由于口包的重复发送会白白浪费掉大量带宽，也增加了服务器的负载。所以， 传统的单播和广播通信方式不能有效地解决单点发送多点接收的问题。 组播是指在口网络中将数据包以尽力传送( b e s t - e f f o r t ) 的形式发送到网络 中的某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。i p 组播的基本 思想是，源主机只发送一份数据，这份数据中的目的地址为组播组地址；组播组 中的所有接收者都可接收到同样的数据拷贝，并且只有组播组内的主机( 目标主 机) 可以接收该数据，网络中其它主机不能收到。 山东大学硕士学位论文 单播发送 组播技术有效地解决了单点发送多点接收的问题，实现了网络中点到多点的 高效数据传送，能够大量节约网络带宽、降低网络负载。作为一种与单播和广播 并列的通信方式，组播的意义不仅在于此。更重要的是，可以利用网络的组播特 性方便地提供一些新的增值业务，包括在线直播、网络电视、远程教育、远程医 疗、网络电台、实时视频会议等互联网的信息服务领域。 组播从1 9 8 8 年提出到现在已经经历了二十年的发展，许多国际组织对组播 的技术研究和业务开展进行了大量的工作。随着互联网建设的迅猛发展和新业务 的不断推出，组播也必将走向成熟。尽管目前端到端的全球组播业务还未大规模 开展起来，但是具备组播能力的网络数目在增加。一些主要的i s p 已运行域间组 播路由协议进行组播路由的交换，形成组播对等体。 1 2 组播技术的基本原理 根据协议的作用范围，组播协议分为主机路由器之间的协议，即组播成员管 理协议，以及路由器路由器之间协议，主要是各种路由协议。组成员关系协议包 括i g m p ( 互连网组管理协议) ；组播路由协议又分为域内组播路由协议及域间 组播路由协议两类。域内组播路由协议包括p i m s m 、p i m - d m 、d v m r p 等协 议，域间组播路由协议包括m b g p 、m s d p 等协议。同时为了有效抑制组播数 2 山东大学硕士学位论文 据在二层网络中的扩散，引入了i g m ps n o o p i n g 等二层组播协议。 通过i g 和二层组播协议，在路由器和交换机中建立起直联网段内的组 成员关系信息。域内组播路由协议根据i g 维护的这些组播组成员关系信息， 运用一定的组播路由算法构造组播分发树，在路由器中建立组播路由状态，路由 器根据这些状态进行组播数据包转发。域间组播路由协议根据网络中配置的域间 组播路由策略，在各自治系统( a s ，a u t o n o m o u ss y s t e m ) 间发布具有组播能力 的路由信息以及组播源信息，使组播数据能在域间进行转发。 1 3 组播路由的分类 组播路由可以分为两大类：信源树( s o u r c et r e e ) 和共享树( s h a r e dt r e e ) 。 信源树是指以组播源作为树根，将组播源到每一个接收者的最短路径结合起来构 成的转发树。由于信源树使用的是从组播源到接收者的最短路径，因此也称为最 短路径树( s h o r t e s tp a t ht r e e ，s p t ) 。对于某个组，网络要为任何一个向该组发送 报文的组播源建立一棵树。共享树以某个路由器作为路由树的树根，该路由器 称为汇集点( r e n d e z v o u sp o i n t ，i 心) ，将r p 到所有接收者的最短路结合起来构 成转发树。使用共享树时，对应某个组，网络中只有一棵树。所有的组播源和接 收者都使用这棵树来收发报文，组播源先向树根发送数据报文，之后报文又向下 转发到达所有的接收者。 山东大学硕士学位论文 最短路径或源分布树最短路径或源分布树 镶魄囊l镶杖2曩收i 爱孽2 信源树的优点是能构造组播源和接收者之间的最短路径，使端到端的延迟达 到最小；缺点是在路由器中必须为每个组播源保存路由信息，这样会占用大量的 系统资源，路由表的规模也比较大。共享树的优点是路由器中保留的状态数可以 很少，缺点是组播源发出的报文要先经过r p ，再到达接收者，经由的路径通常 并非最短，而且对r p 的可靠性和处理能力要求很高。 共享的分布树 共享的分布树 檬记j 叠：i 6 ) 所蠢誉l 1 4 组播路由协议 1 4 1 域内组播路由协议 域内组播路由中，d v m r p ( 距离矢量组播路由协议) 、p i m d m ( 密集模式 协议无关组播) 和p i m - s m ( 稀疏模式协议无关组播) 是目前应用最多的协议。 、d v m r p ( d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 ) d v m r p 协议首先通过发送探测消息来进行邻居发现，之后通过路由交换来 进行单播寻径和确定上下游依赖关系。 d v m r p 采用逆向路径组播( 砒，m ) 算法进行组播转发。 二、p i m - d m ( p r o t o c o li n d e p e n d e n tm u l t i c a s td e n s em o d e ) 4 山东大学硕士学位论文 在p i m - d m 域中，运行p i m d m 协议的路由器周期性的发送h e l l o 消息， 发现邻接的p i m 路由器，进行叶子网络、叶子路由器的判断，并且负责在多路 访问网络中选举指定路由器( d r ) 。 三、p i m - s m ( p r o t o c o li n d e p e n d e n tm u l f i c a s t s p a r s em o d e ) 在p i m s m 域中，运行p i m s m 协议的路由器周期性的发送h e l l o 消息， 用以发现邻接的p i m 路由器，并且负责在多路访问网络中进行d r 的选举。这 里，d r 负责为与其直连的组成员向组播树根节点的方向发送“加入剪枝”消息， 或是将直连组播源的数据发向组播分发树。 1 4 2 域间组播路由协议 m b g p ( 组播边界网关协议) ，用于在自治域之间交换组播路由信息；m s d p ( 组播信源发现协议) ，用于在i s p 之间交换组播信源信息；p i m s m ，用作域内 的组播路由协议。 、m b g p ( m u l t i p r o t o c o lb o r d e rg a t e w a yp r o t o c 0 1 ) 域问路由的首要问题是路由信息( 或者说可达信息) 如何在自治系统之间传 递，由于不同的a s 可能属于不同的运营商，因此除了距离信息外，域问路由信 息必须包含运营商的策略，这是与域内路由信息的不同之处。 二、m s d p ( m u l t i c a s ts o u r c ed i s c o v e r yp r o t o c 0 1 ) 对于i s p 来说，不希望依靠竞争对手的r p 转发组播流量，但同时又要求无 论信源的r p 在哪里，都能从信源获取信息发给自己内部的成员。m s d p 就是为 了解决这个问题而提出的。在m s d p 里使用的是域间信源树而不是公共树，而且 要求域内组播路由协议必须是p i m - s m 。 在m s d p 中，某个域内的r p 使用t c p 连接与其它域内的r p 建立 m s d p 对等关系，用这些对等关系交换信源信息。如果本地的接收者要接收其它 域的信源发出的报文，则使用与p i m - s m 中同样的方法构造信源树。 1 5 论文的组织和创新点 山东大学硕士学位论文 随着在线直播、网络电视、近程教育、远程医疗、网络电台、实时视频会议 等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 ) 提出了不同的需求，即网络费用低、时延小、可延伸性、支持动态多播、可生存 性、公平性等，其中时延、嬲络费用等因素跑其它因素更重簧。 q o s 组播路由技术是网络中解决q o s 问题的一项关键技术，它是一种源节点可 以翼露向多个嚣豹节点发送信息的通信方式。带q o s 约束组播路由问题的基标是 寻求一棵满足q o s 要求的组播树，使该树覆盖所有的组成员( 包括发送者与接收 者) ，圊时使网络时延达到最小。这等价子求解带约束豹最小s t e i n e r 树闽题】。已经 证明，求解带约束的最小s t e i n e r 树是n p _ c 问题，因而用近似求解方法解决。 用模拟退火算法s s a ( s i m u l a t e da n n e a l i n g d g o r i t h m ) 、微粒群算法p s o ( p a r t i c l e s w a r mo p t i m i z a t i o n ) 、遗传算法g a ( g e n e t i ca l g o r i t h m ) 、蚂蚁算法a c o ( a n tc o l o n y o p t i m i z a t i o n ) 等智能优化算法求勰带q o s 组擢路由闯题的研究已有许多，但是存在 易于陷入早熟收敛和局部求精能力不足等明显的缺点。蚁群算法是一种新型的模 拟生物算法，研究表鹞该算法比遗传算法、模拟退火算法等晕期智能计算方法具 有更强的鲁棒性、求解时间短、易于计算机实现等优点，是解决n p 完全问题的 有效方法。 1 5 1 论文的组织结构 本文分为六章。 第二章介绍了s 组援路由阀题的相关理论和基础知识。包括王p 网络的服务质 量、0 0 s 定义、组播机制中q o s 的必要性、服务质量要求、o o s 组播路由问题的分类 s 组播路由基本概念、s t e i n e r 树问题及算法、q o s 约束的s t e i n e r 树问题及算法 等。 第三章介绍了组播路由选择方法、传统的组播路由选择方法、计算复杂性、 n p 问题、蚂蚁算法的起源、发展、应用，蚂蚁算法求解组播路由问题的原理、基 本流程、经典设计模型。 第四章对基于蚂蚁算法的多q o s 约束的组播路由算法，单个参数选择问题， 6 山东大学硕士学位论文 进行了详细地描述和试验，并在此基础上提出了运用正交实验来求解“基于蚁群 算法的q o s 约束组播路由算法 参数的最佳组合的方法。 第五章给出了多q o s 约束组播路由问题的网络模型，提出了基于改进的蚁群 系统的多q o s 约束组播路由算法，描述算法基本原理、算法步骤、算法流程，并 进行了实验验证。 第六章介绍了遗传算法的基本原理、特点、基本操作，基于免疫遗传算法的 多q o s 组播路由算法的基本思想、选择方法、算法步骤，基于改进的蚁群系统的 多q o s 约束组播路由算法，提出了改进的蚁群算法和免疫遗传算法的融合而得到 的一种启发式算法蚁群遗传算法( a n tc o l o n yg e n e t i ca l g o r i t h m ) ，并在前 面用到的网络环境上进行了对比仿真。 1 5 2 论文的创新之处 提出了通过正交实验求得蚁群算法的各个参数的最佳组合的方法。通过一 系列的对比仿真实验研究，来探讨蚁群算法中参数的最佳设定原则，以利于蚁群算 法在实际中的应用和推广。首先，让一个参数变化其他参数不变，进行仿真实验， 找出这个参数最佳值范围：然后，各个参数在其最佳值范围内，选取若干个值， 进行正交试验，找出最佳组合。因为各个参数的最佳值组合在一起，未必是最佳 组合，所以需通过正交实验求得蚁群算法的各个参数的最佳组合，并进行验证。 针对多q o s 约束的组播路山问题，借鉴改进的蚁群系统，提出了种基于改 进蚁群系统的多q 0 5 约束组播路由算法m m r - a c 0 ，通过动态调整信息素，加快搜索 的收敛速度和防止早熟、停滞现象之间取得很好的平衡；通过加入与时延、时延 抖动、丢包率相关负载因子，降低拥塞的可能性；通过分散度调节、交叉变异， 保证了解的多样性；通过全局扰动，避免了陷入局部最优；通过优化选路，降低 了算法的时间复杂度，加快了收敛速度。最终求得满足q o s 要求的最佳解或非劣 解。实验结果表明m m r - a c 0 的可行性和效率性。 针对多维q o s 约束的组播路由问题，提出的蚁群遗传算法a c g a ( a n tc o l o n y g e n e t i ca l g o r i t h m ) 是将改进的蚁群算法和免疫遗传算法的融合而得到的一种启发 式算法，其具有蚁群算法的求解精度又具有遗传算法的全局收敛性。在传统遗传 7 山东大学硕士学位论文 算法的全局随机搜索基础上，借鉴人工免疫中抗体的多样性保持策略，大大提高 了算法的群体多样性，避免了遗传算法的过早收敛和局部搜索能力差的缺点。通 过动态调整信息素，加快搜索的收敛速度；通过加入与时延、时延抖动、丢包率 相关负载因子，降低拥塞的可能性；通过全局扰动，避免了陷入局部最优；通过 优化选路，降低了算法的时间复杂度。实验结果表明a c g a 的正确性和有效性。 山东大学硕士学位论文 第二章q o s 组播路由 2 1i p 网络的服务质量 2 1 1o o s 定义 随着网络技术的迅速发展，交互式电视会议，协同文档编辑，视频点播，远 程教育等已经开始应用。这些实时性应用涉及到网络的服务质量( q o s ) f 司题，q o s 包括很多方面，例如端到端时延是实时通信应用中最基本部分。对于组播实时通 信来说，如果时延过长，就会引起用户视觉和听觉上的不舒服，甚至引起语意无 法理解。对于组播实时通信，端到端的时延波动则很重要。例如，电视会议中， 要保证各地的与会者要同时听到发言者的讲话，从会场到各地的消息传输的时延 必须限制在一定范围内，时延值只能在这个范围内波动。 一般来说，求解q o s 组播路由问题是非常困难的。首先，分布式多媒体数据 传输的q o s 要求很苛刻。其次，网络的状态是动态变化的，网络负载是波动、连 接的建立和撤除、链路的中断和接通，都影响到q o s 路由的确定。随着网络规模 日益扩大和无线链路的接入增加了网络状态的不确定性，从而降低了组播算法的 寻径性能。 i n t e m e t 己成为一个重要的和无处不在的商业基础设施，这大大改变了消费者 对网络性能、安全性和服务的期望。但是“尽力而为”( b e s t - e 懿r t ) 服务仍是目前 i n t e m e t 中主要的一种服务类别，所有分组在网络中被同等对待，任何拥塞链路都 会增加分组传输时间，从而导致性能下降、数据抖动、或者分组丢失不能保证 服务质量。随着分布式多媒体应用需求的不断增长，以及i n t e m e t 上商业化应用的 飞速发展，对服务质量( q u a i l i t yo f s e r v i c e ，q o s ) 提出了更高的要求，高效的q o s 支 持显得越来越重要。 简单地说，q o s 能够对数据包进行合理的排队，对含有内容标识的数据包进行 优化，并对其中特定的数据包赋以较高的优先级，从而加速传输的进程。q o s 直接 表现为p 数据流通过网络时的性能，它有一套度量指标，包括业务可用性、延迟、 9 山东大学硕士学位论文 可变延迟、吞吐量和丢包率等。 不同的应用要求不同的q o s 某些应用要求严格的端到端延时，某些应用要求 传输速率保证，而有些应用没有严格的延时和或带宽需求，只要求较高的吞吐量。 2 1 2 组播机制中q o s 的必要性 在实际的网络中，使用组播机制，q o s 路由技术是必需的。在组播中，需要消 耗比最大努力的单播多得多的路由器资源。然而，目前此方面的讨论还不多，也 没有提出有效的协议。可是，预支持组播的供应商迫切需要一种合理的计费系统。 对于组播通信而言，从经济的角度看，提供一种允许用户选择一条较少费用的路 径也是必需的。否则，组播供应商可能会选择较高费用的路径，因而给用户带来 不必要的费用。选择满足用户q o s 要求的路径的方法是不可避免的。沿着满足q o s 要求的路径，通过信令的方法( 也就是q o s 路由技术) 可以找到这样的路径。正如前 面所述的，组播中除了资源预留功能外，合并功能和复制功能也是必需的。假定 一个未授权的接收者向发送者发出一个q o s 请求，因为对路径上的路由器而言，要 判断一个请求授权与否比较困难，故而q o s 请求被执行。因此，从发送者到一个未 授权接收者之间的路径上，q o s 也被实现。 2 1 3 服务质量要求 多媒体应用对服务质量的要求可归纳为下述几个主要方面。 1 ) 通信带宽 时间相关媒体对网络的通信带宽有最低要求。原理上，时间无关媒体对网络 带宽不应提出最低通信带宽要求，但是为了保证媒体流之间同步，多媒体中的时 间无关媒体也存在最低通信带宽问题。例如，当电视上的字幕是独立于电视信号 传输的，那么字幕信息的传输必定有通信带宽的最低要求，否则字幕和电视信号 的同步就无法保证。 多媒体的数据速率是各个媒体流数据速率之和。多媒体的数据速率分平均速 率和峰值速率两种。网络的通信带宽应达到或超过给定多媒体的数据速率。非压 缩媒体的传输要占用极大的通信带宽，因此，信息压缩是分布式多媒体系统的一 种关键技术。压缩媒体的带宽呈波峰状变化，对网络提出了最高通信带宽和最低 1 0 山东大学硕士学位论文 通信带宽的要求，因此，0 0 s 控制就成为分布式多媒体系统的一种非常复杂的技术。 2 ) 延时 不同多媒体应用对延时有不同的要求。对于视频点播系统，视频流从视频服 务器传送到用户的机项盒，其延时的大小对用户观看节目没有多大影响。但是， 对于交互多媒体系统( 如视频会议和协同计算环境) ，延时是一项重要指标，延时过 大将影响交互效果。 网络延时由两部分组成：第一部分为信号传播时间；第二部分为网络设备( 交换 机，路由器) 排队调度时间。信号传播延时是固定的、不可改变的，但排队调度时 间可通过服务质量控制来保证。延时要求一般以延时上界( 最大延时) 的形式给出， 网络通过服务质量控制保证媒体流的传输不超过延时上界。 3 ) 延时抖动 延时抖动( j i t t e r ) 对时间相关媒体来说是一项极重要的传输性能参数。延时抖 动指媒体流各单元之间的时间差异。例如，数字声音采样间隔为1 2 5 u s ，通过网络传 输之后，如果它们之间的时间在1 1 0 u s 1 4 0 u s 之间，那么延时抖动为1 5 u s 延时抖动 可在输出端设置缓冲器来消除，抖动越大，缓冲器要求越多。用这种方法消除延 时抖动将增加媒体流的端到端延时，因此，网络应通过服务质量控制来最大可能 的抑制延时抖动。 4 ) 包丢失率 包丢失率( p a c k e tl o s sr a t e ) ：是指特定的时间段丢失的包占传输包的总数的比 例。丢包主要是由于网络拥塞引起的。某些应用程序在包丢失后无法正常工作， 因此要求网络提供传输保障，这方面的典型例子就是t c p 。而某些多媒体业务如p 电话，个别包的丢失虽然会影响视频的质量，但用户往往可以容忍这种质量的暂 时下降。因此，只要包丢失率在一定的范围内，就不会影响业务的正常进行。 5 ) 可用性 可用性是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠 性和网络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳定 性以及网络演进或升级时不中断服务的能力。 6 ) 吞吐量 吞吐量是在一定时间段内对网上流量( 或带宽) 的度量。对i p 网而言可以从帧 山东大学硕士学位论文 中继网借用一些概念。根据应用和服务类型，服务水平协议( s l a ) 可以规定承诺信 息速率( c i r ) 、突发信息速率( b i r ) 和最大突发信号长度。承诺信息速率是应该予 以严格保证的，对突发信息速率可以有所限定，以在容纳预定长度突发信号的同 时容纳从活音到视频以及一般数据的各种服务，一般讲，吞吐量越大起好。 2 2 q o s 组播路由问题的分类 依据不同的q o s 约束和不同的优化目标函数，多播路由问题可分为以下几类： ( 1 ) 单链路约束问题：在寻找可行的多播树过程中加以单个链路约束( 如基于带 宽约束路由问题) ； ( 2 ) 多链路约束问题：在构建可行的多播树过程中加以多个链路约束( 如基于带 宽及缓存约束的路由问题) ； ( 3 ) 单树约束问题：在构建可行的多播树时加以单个树约束( 如基于端到端延时 约束的路由问题) ： ( 4 ) 多树约束问题：在构建可行的多播树时加以多个树约束( 如基于延时及延时 抖动约束的路由问题) ； ( 5 ) 链路及树约束问题：在构建可行的多播树时加以一个链路约束及一个树约 束( 如基于延时及带宽约束的路由问题) ； ( 6 ) 链路最优化问题：使用链路最优化函数构建最优的多播树( 如求多播树上链 路带宽最大的路由问题) ； ( 7 ) 树最优化问题：使用树最优化函数构建最优的多播树( 如多播树费用最小化 问题1 ，这类问题又称为s t e i n e r 树问题； ( 8 ) 链路约束链路最优化问题：使用链路最优化函数构建满足一个链路约束的 最优化多播树( 如基于带宽约束的缓存最优化问题) ； ( 9 ) 链路约束树最优化问题：使用树最优化函数构建满足一个链路约束的最优 化多播树( 如基于带宽约束s t e i n e r 树问题) ； ( 1 0 ) 树约束链路最优化问题：使用链路最优化函数构建符合一个树约束条件的 最优化多播树( 如基于延迟约束的带宽最优化问题) ； ( 1 1 ) 树约束树最优化问题：使用树最优化函数构建符合一个树约束条件的最优 化多播树( 如基于延迟约束的s t e i n e r 树问题) ； ( 1 2 ) 链路约束及树约束树最优化问题：使用树最优化函数构建符合一个链路约 山东大学硕士学位论文 束和一个树约束条件的最优化多播树( 如基于带宽及延迟约束s t e i n e r 树问题) 。 第( 1 ) 、( 2 ) 类问题是容易处理的，因为我们可以通过从网络拓扑中删除那些不 合要求的链路来满足链路约束。w a n g 和c r o w c r o f i 己证明寻找一条路径使之满足两 个或多个相互独立的可加性或可乘性的约束条件以及它们的任意组合是n p 完全问 题。只有凹性约束和其它可加性何乘性约束的组合问题是容易处理的。因此，问 题( 3 ) 和( 5 ) 在多项式时间内是可解的，而问题( 4 ) 是n p 完全问题。s h a c h a m 提出了解 决问题( 6 ) 的一个多项式时间复杂度的算法。如果从网络拓扑中删除那些不满足约 束条件的链路，则问题( 8 ) 和( 1 0 ) 可转化为问题( 6 ) ，因此它们在多项式时间内是可 解的。问题( 7 ) ( s t e i n e r 树问题) 和问题( 9 ) ，( 1 1 ) 以及( 1 2 ) ( 约束的s t e i n e r 树问题) 已被证 明是n p 完全问题。 2 3q o s 组播路由基本概念 q o s 组播路由就是根据给定的q o s 参数，选择有足够网络资源的链路来传送组 播数据。路由有两方面的基本内容：一是收集网络状态信息并不断更新信息，另 一是根据己有信息来为新的连接请求选择一条合适的路由。一个路由算法的性能 极大地取决于信息收集的好坏。 2 3 1 加权图模型 网络的拓扑结构和资源容量可以抽象为一个加权图( v e ) 节点代表网络中的 交换设备，边( e ) 代表传输线路。如果传输线路是对称的，则对应的边是无向的。 因为对称线路对两个方向上的数据都有同样的特性。对于大多数实际的网络而言， 其链路一般都是非对称的，因而其每一条链路对应于模型中，就是两条有向的加 权边。每一条链路都有一个对应于相关q o s 度量的状态。而每一个节点也有相应的 状态，它可以单独表示出来，或者也可以把它折算到与节点相连的链路状态中去。 2 3 2 状态信息 ( 1 ) 本地信息 每一个节点都必须保持其最新的本地信息，包括链路传输时延、排队时延、输 出链路的剩余带宽以及其他网络资源的可用性信息。 1 3 山东大学硕士学位论文 ( 2 ) 全局信息 所有节点本地信息的总和就构成了全局信息。每一个节点可以用链路状态协 议或者距离一向量协议来发布、取得全局信息。链路状态协议通过让各节点广播 其本地信息来确定网络的拓扑结构和各链路的状态。距离一向量协议通过相邻节 点定期交换其距离向量来取得并扩散全局信息。每一个节点保持的全局信息，总 是对现有网络状态的二种近似。这是由于信息传输时延造成的。而时延的不可避 免性表明这种不确定性会随着网络规模的增加而不断扩大。 ( 3 ) 状态信息的聚合 因为任何物理设备的存储资源和处理能力都是有限的，所以对全局信息的精 确保存，会带来扩容性问题，于是降低全局信息的规模就变得十分重要。这可以 通过把一个具有层次性结构的大型网络的局部信息进行聚合来完成，即把包含几 个物理节点的组抽象为一个逻辑节点，而逻辑节点又可以进一步聚合成更高一级 的逻辑节点，如此反复下去。在聚合过程中，必须把下层节点的网络度量特性聚 集为本层逻辑节点的度量特性。这种过程是复杂的，而不同的聚集方法对状态信 息的影响也是一个开放性的问题。本文限于篇幅不做深入讨论。如口的内部网关路 由算法o s p f 支持两层的聚合信息发布，而a t m 可支持任意多层的聚合。必须注意 的是聚合引入了额外的不确定性，并且不确定性会随聚合层次的增加而变大。聚 合后的两个逻辑节点间的链路有可能对应于多条物理链路，从而引入新的问题。 2 3 3q o s 度量 q o s 要求需要通过可测量的q o s 度量来实现，不同的q o s 参数具有不同的特征， 一般有四种类型的q o s 参数：加性、乘性、凸性和凹性，定义如下： 定义2 1 1 度量( m e t r i c ) 在网络n 中，令链路e e e 具有一组有序数列 ( w 1 ，w 2 ，w 3 ，w k ) 作为e 的属性，则( w 1 ，w 2 ，w 3 ，w k ) 称为链路e 的度量，也称为 权值( w e i g h t ) 。 q o s 要求通过可测量的q o s 度量来实现，常用的几种q o s 度量主要包括代价、 带宽、端到端时延、丢包率、时延抖动等。下面给出各度量的数学描述。 设n 表示网络，表示正实数集，r + 表示非负实数集，。e e 表示任意 一条链路，则： 1 4 山东大学硕士学位论文 代价c o s “e ) ：e 一- r + 时延d e l a y ( e ) ：e r 十 带宽b a n d w i d t h ( e ) ：e 一- r + 时延抖动d e l a y - j i t t e r ( e ) ：e 一- r + 丢包率p a c k e t - l o s s ( e ) ：e 一- r + 不同的度量具有不同的性质，按照这些性质，q o s 度量可以分为可加性度量、可 乘性度量、凸性度量和凹性度量。在网络n 中，设m e t r i c ( u ，v ) 为链路( u ， v ) 的一种q o s 度量，对于网络中的任意一条路径p ( s ，t ) = ( s ，) 【，u ，v ，y ，t ) ，则以上 四类度量的定义为： 定义2 1 2 可加性度量可加性度量即p ( s ，t ) 对于度量m e t r i c 满足 m e t r i c ( p ( s ，t ) ) = m e t r i c ( s ，x ) 十- 竹n e t r i c ( u ，v ) + q - m e t r i c ( y , 0( 4 1 1 ) 例如：可加性度量包括时延、代价、时延抖动以及转发跳数等。 定义2 1 3 可乘性度量可乘性度量即p ( s ，0 对于度量m e t r i c 满足 m e t r i c ( p ( 5 ，t ) ) = m e t r i c ( s ，x ) m e t r i c ( u ，v ) m e t f i c ，0 ( 4 1 2 ) 例如：丢包率为可乘性度量。 定义2 1 4 凹性度量凹性度量f i l p ( s ，t ) 对于度量m e t r i c 满足 m e t r i c ( p ( 5 ，t ) ) = m i n m e t r i c ( s ，x ) ，m e t r i c ( u ，v ) ，m e t r i c ( y ，0 ) ( 4 1 3 ) 例如，带宽为凹性度量。 定义2 1 5 凸性度量凸性度量即p ( s ，0 对于度量m e t r i c 满足 m e t r i c ( p ( 5 ，t ) ) = m a x m e t r i c ( s ，x ) ，m e t r i c ( u ，v ) ，m e t r i c o r ，0 ) ( 4 1 3 ) 例如，带宽为凸性度量。 2 4s t e i n e r 树问题及算法 定义2 1 6s t e i n e r 树问题给定带权简单无向图g = ( v ，e ) ，其中v ，e 分别是 网络节点和链路集合。对每条链路( u ，v ) e e ，定义一个正实数的代价函数c o s t ( e ) ： e - r + ，表示链路上网络资源的利用情况。给定组播源节点s ，一个组播目的节点 集m e v - s ，设集合d m = mu s ) 表示参与组播会话的节点集，即由源节点和目的节 点组成的集合，, 贝u s t e i n e r 树问题就是从图g 中寻找一棵覆盖i ) m 中所有节点的最小生一 成树t , 且i j 使得树的代价c o s t ( t ) = e c o s t ( e ) 最小。该最小生成树也称为s t e i n e r 树，记为 t s ( v t ，e t )