（计算机系统结构专业论文）考虑负载均衡的动态聚合组播研究.pdf

爹一 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 盈蒸 日 期： 枷t o 、夕i o 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：主燃导师签名： 埠 日期：丝! ! ：! ：! ! ， ，4 t 、 、i ， 【u 东大学硕+ 学位论文 目录 摘要i a b s t r a c t ： 第一章绪论j l 1 1 组播及组播扩展性问题1 1 2 聚合组播的提出1 1 2 1 削减组播状态的方案1 1 2 2 聚合组播状态的方案2 1 2 3 聚合组播方案2 1 3 聚合组播要面对的负载均衡问题5 1 4 论文主要工作概述7 1 5 本文结构7 第二章聚合组播与负载均衡问题9 2 1 聚合组播介绍9 2 2 聚合组播的数学模型1 0 2 3 负载均衡的需求1 l 2 4 仿真环境- 1 3 2 4 1 仿真工具1 3 2 4 2 仿真拓扑15 2 5 本章小结l8 第三章负载均衡的动态聚合组播算法1 9 3 1 现有算法模式1 9 3 2 算法策略2 0 3 2 1 聚合组播的负载均衡模型2 0 3 2 2 聚合组播的生成树过程2 2 3 2 3 聚合组播的组树匹配过程2 3 3 3 算法运行步骤2 4 3 4 仿真2 7 3 4 1 仿真建模2 7 3 4 2 仿真结果2 9 3 5 本章小结3 2 第四章基于a n t n e t 的动态聚合组播协议3 3 4 1 蚁群算法的发展3 3 4 2a n t n e t 模型简介3 4 4 3a n t n e t 对网络负载均衡的意义3 6 4 4 应用a n t n e t 的聚合组播协议算法思想3 7 4 5 协议模型及数据结构3 8 4 5 1 协议采用的数据结构3 8 4 5 2a n t n e t 的运行方式4 0 4 5 3 组动态：组加入过程4 2 4 5 4 组动态：组离开过程4 5 i i 东大学硕十学位论文 4 5 5 组成员动态：加入和离开过程4 6 4 5 6 协议细节4 8 4 6 实验与仿真4 8 4 6 1 仿真建模4 9 4 6 2 仿真结臬5 3 4 7 本章小结5 6_ 第五章总结与展望5 7 5 1 总结5 7 5 2 展望5 8 j 参考文献5 9 致谢6 4 攻读学位期间发表的主要学术论文6 5 在读期间参与的科研项目情况6 6 ， 奎 一 山东大学硕+ 学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i i a b s t r a c ti ne n g l i s h i i i c h a p t e r1i n t r e d u c t i o n l 1 1m u l t i c a s ta n di t ss c a l a b i l i t yp r o b l e m 1 1 2p r o p o s a lo f a g g r e g a t e dm u l t i c a s t 1 1 2 1s c h e m e so fd e c r e a s i n gm u l t i c a s ts t a t e s l 1 2 2s c h e m e so fa g g r e g a t i n gm u l t i c a s ts t a t e s 2 1 2 3s c h e m e & a g g r e g a t e dm u l t i c a s t 2 1 3l o a db a l a n c i n gp r o b l e mi na g g r e g a t e dm u l f i c a s t 5 1 4m a i nc o n t e n to fs t u d yw r o r k 7 1 5c h a p t e ra r r a n g e m e n t 7 c h a p t e r2a g g r e g a t e dm u l t i c a s ta n dl o a db a l a n c i n gp r o b l e m 9 2 1d e s c r i p t i o no f a g g r e g a t e dm u l t i c a s t 9 2 2f o r m u l a t i o no f a g g r e g a t e dm u l t i c a s t 1 0 2 3d e m a n d so f l o a db a l a n c i n g 1 l 2 4s i m u l a t i o ne n v i r o n m e n t s 1 ：； 2 4 1s i m u l a t i o nt o o l s 1 3 2 4 2s i m u l a t i o nt o p o l o g y 1 5 2 5s u m m a r y 1 8 c h a p t e r3a na g g r e g a t e dm u l t i c a s ta l g o r i t h mw i t hl o a db a l a n c i n g 1 9 3 1c u r r e n ta l g o r i t h mp a t t e r n s 1 9 3 2a l g o r i t h ms t r a t e g y 2 0 3 2 1a g g r e g a t e dm u l t i c a s tl o a db a l a n c i n gm o d e l 2 0 3 2 2a g g r e g a t e dm u l t i c a s tt r e eg e n e r a t i o np r o c e s s 2 2 3 2 3a g g r e g a t e dm u l t i c a s tt r e ea g g r e g a t i o np r o c e s s 2 3 3 3a l g o r i t h me x e c u t i o ns t e p s 2 4 3 4s i m u l a t i o n 2 7 3 4 1s i m u l a t i o nm o d e l s ：2 7 3 4 2s i m u l a t i o nr e s u l t s ：1 9 3 5s u m m a r y 3 2 c h a p t e r4d y n a m i ca g g r e g a t e dm u l t i c a s tp r o t o c o lb a s e do n a n t n e t 3 3 4 1d e v e l o p m e n to f a n tc o l o n ya l g o r i t h m 3 3 4 2i n t r o d u c t i o no f a n t n e t 3 4 4 3a n t n e t ss i g n i f i c a n c et on e t w o r kl o a db a l a n c i n g 3 6 4 4i d e a l o g yo f a g g r e g a t e dm u l t i c a s tp r o t o c o lb a s e do na n t n e t 3 7 4 5p r o t o c o lm o d e l sa n ds t r u c t u r e s 3 8 4 5 1d a t as t r u c t u r e 3 8 4 5 2e x e c u t i o no f m o d i f i e da n t n e t 4 0 4 5 3g r o u pd y n a m i c ：g r o u pj o i n i n g z i ：1 4 5 4g r o u pd y n a m i c ：g r o u pl e a v i n g 4 5 5 1c o n c l u s i o n 5 7 5 2e x p e c t a t i o n ! ；8 ” r e f e r e n c e s 5 9 a c k n o w l e d g e m e n t s 6 4 a c a d e m i cp a p e r sd u r i n gm a s t e rd e g r e es t u d y i n g 6 5 r e s e a r c hp r o j e c t sj o i n e dd u r i n gm a s t e rd e g r e es t u d y i n g 6 6 、 ， ， f i i 东大学硕十学位论文 摘要 随着i n t e r n e t 的发展，出现了许多新兴的大规模多用户网络应用，诸如 音频视频会议、网络游戏、交互式仿真等，这些应用都采用由一个源节点向多 个接收节点发送数据的方式。口组播技术是支持此种通信模式的一种高效机制。 组播技术能够减少冗余数据在网络中的传输，节省网络资源，因而在i n t e r n e t 中得到广泛部署和应用。但是组播技术也有其局限性。当网络中同时存在大量组 播组时，保存组播转发状态信息要消耗路由器的大量存储资源，并且建立和维持 组播树也产生大量控制开销，给路由器造成沉重负担。由大规模组播产生的上述 问题我们称之为组播扩展性问题。 聚合组播技术将多个组播组聚合以共享使用一棵聚合树传输数据，不但减少 了对节点资源的占用，而且同时降低了建立组播树与维持组播会话所需的控制开 销，成为解决组播扩展性问题的一种较好方案。但是，随着聚合在一棵聚合树上 的组播组越来越多，聚合树上的流量变大，导致出现拥塞现象，也使得传输时的 延迟增加，使q o s 需求难以得到满足，严重影响网络服务质量。同时，这种方 式使得网络中不在树上的链路无法得到充分利用，导致网络资源的严重利用不 均。 针对这个问题，本文提出了采用负载均衡策略对聚合组播技术进行改进的思 想，并在算法级别和协议级别分别进行了研究。 本文首先提出了负载均衡度、链路拥塞率等聚合组播负载均衡衡量标准，并 以其为依据设计了一种动态聚合组播算法a m l b 。该算法随着组播组的动态加 入和离开，对组播树进行建立，聚合，扩展，收缩，删除等操作，并且在生成原 始组播树和聚合过程中都采用负载均衡策略，更加适合于真实网络环境下的多用 户网络应用。仿真实验表明基于负载均衡策略的算法在保持聚合效果的同时，使 网络资源得到均衡利用，网络性能得到提高。 然后本文提出了一种基于a n t n e t 模型的动态聚合组播协议a m p m a ，该协 议通过人工蚂蚁的分布式正反馈行为实时反映网络链路负载，并采用合理的评价 机制，实现聚合过程的动态负载均衡。本文使用o p n e t 仿真工具对a m p m a 协 议进行建模和仿真，实验结果表明该协议能够有效平衡网络的流量负载，减少丢 u - 【j i 东大学硕十学位论文 a b s t r a c t a st h er a p i dd e v e l o p m e n to fi n t e r n e t , t h e r ee x i s t sm a n ye m e r g i n gl a r g es c a l e m u l t i u s e ra p p l i c a t i o n s ，s u c h 嬲a u d i o v i d e oc o n f e r e n c e ，n e t w o r kg a m e s ，d i s t r i b u t e d i n t e r a c t i v es i m u l a t i o n ( d i s ) ，e t c a l lt h e s ea p p l i c a t i o n si n v o l v em u l t i - p o i n tg r o u p c o m m u n i c a t i o n s ，t h a ti s ，d e l i v e r i n gd a t af r o mo n es o u r c et om u l t i p l er e c e i v e r s i p m u l t i c a s ti si n t r o d u c e d 嬲锄e f f i c i e n ts c h e m et os u p p o r tt h i ss o r to fc o m m u n i c a t i o n m u l t i c a s tt e c h n o l o g yi sw i d e l yi m p l e m e n t e da n da p p l i e di n1 n t e r n e tb e c a u s ei t r e d u c e sr e d u n d a n td a t ai nt h en e t w o r ka n ds a v e sn e t w o r kr e s o u r c e m u l t i c a s ta l s oh a s d i s a d v a n t a g e s w h e nt h e r ea r el a r g en u m b e r so fc o n c u r r e n tm u l t i c a s tg r o u p si nt h e n e t w o r k ，al o to fr e s o u r c e st ok e e pf o r w a r d i n gs t a t e sa n dm a n a g e m e n to v e r h e a dt o s e t u pa n dm a i n t a i nm u l t i c a s tt r e e sw i l lb er e q u i r e d ，w h i c hb r i n g sh e a v yb u r d e nf o r n e t w o r kr e u t e r s t h i sp r o b l e mb r o u g h tb yl a r g e s c a l em u l t i c a s ti sd e f i n e d 舔m u l t i c a s t s c a l a b i l i t yp r o b l e m a g g r e g a t e dm u l t i c a s tm a k e sm u l t i p l em u l t i c a s tg r o u p st os h a r eas i n g l ed e l i v e r y t r e e ，w h i c hs a v e sn o d em e m o r yr e s o u r c ea n da tt h es a m et i m ed e c r e a s e sc o n t r o l o v e r h e a df r o ms e t u pa n dm a i n t e n a n c eo fm u l t i c a s tt r e e s ，s i n c eb e c o m e sap r e f e r a b l y s o l u t i o nt om u l t i c a s ts c a l a b i l i t yp r o b l e m h o w e v e r , 嬲t h en u m b e ro fg r o u p s a g g r e g a t e dt oo n es i n g l et r e ei n c r e a s e s ，m o r ef l o w sw i l lb ea d d e dt oo n t r e el i n k s ， r e s u l t i n gi nc o n g e s t i o n ，a n db r i n g i n gh i g h e rt r a n s m i s s i o nd e l a y , w h i c hm a k e si th a r d t om e e tq o sr e q u i r e m e n t s i na d d i t i o n ，o f f - t r e el i n k si nt h en e t w o r kc o u l dn o tb eu s e d s u f f i c i e n t l ya n dn e t w o r kl o a di su n b a l a n c e d a c c o r d i n gt ot h i sp r o b l e m ，t h ei d e ao fa p p l y i n gl o a db a l a n c i n gi na g g r e g a t e d m u l t i c a s ti sp r o p o s e da n ds t u d i e dr e s p e c t i v e l yo na l g o r i t h ml e v e la n dp r o t o c o ll e v e l w ef i r s tp r o p o s e dl o a db a l a n c i n gm e t r i c sf o ra g g r e g a t e dm u l t i c a s t ，s u c h 弱 d e g r e eo fl o a d - b a l a n c i n ga n dc o n g e s t i o nr a t e ，a n dd e s i g n e dad y n a m i ca g g r e g a t e d m u l t i c a s tw i t hl o a db a l a n c i n ga l g o r i t h mb a s e do nt h o s em e t r i c s a m l ba l g o r i t h m c o n s t r u c t s ，a g g r e g a t e s ，e x t e n d s ，s h r i n k sa n dd e l e t e sm u l t i c a s tt r e e s 谢t hg r o u p sj o i n 1 1i 东大学硕士学位论文 a n dl e a v i n g ，a n da p p l i e sl o a db a l a n c i n gs t r a t e g yt h r o u g h o u tt h ep r o c e s s e so fn a t i v e t r e e g e n e r a t i o n a n dt r e e a g g r e g a t i o n t h e r e f o r e i ti sm o r es u i t a b l ef o r m u l t i u s e rn e t w o r ka p p l i c a t i o n si n r e a l i s t i cn e t w o r kc o n d i t i o n s i m u l a t i o nr e s u l t s d e m o n s t r a t et h a ta g g r e g a t e dm u l t i c a s tb a s e do nl o a db a l a n c i n gc a na c h i e v em o r e b a l a n c e dn e t w o r kf l o wa n db e t t e rn e t w o r kp e r f o r m a n c ew h i l em a i n t a i n sa g g r e g a t i o n e f f i c i e n c y t h e nw ep r o p o s e dad y n a m i ca g g r e g a t e dm u l t i c a s tp r o t o c o lb a s e do nm o d i f i e d a n t n e t a m p m ab a s e do nm o d i f i e da n t n e tm o d e l t h i sp r o t o c o lr e f l e c t sn e t w o r k l i n kl o a dv i ad i s t r i b u t e dp o s i t i v ef e e d b a c ko fa r t i f i c i a la n t s ，a n du s e sr e a s o n a b l e m e t r i c si no r d e rt oa c h i e v ed y n a m i cl o a db a l a n c i n gi na g g r e g a t i o n a m p m am o d e l e d a n ds i m u l a t e db yo p n e tm o d e l e r s i m u l a t i o nr e s u l t si n d i c a t et h a tt h ep r o t o c o li s e f f e c t i v ei nb a l a n c i n gn e t w o r kl o a da n dr e d u c i n gn e t w o r kf a i l u r es u c ha sp a c k e tl o s s a n dc o n g e s t i o n ，p e r f o r m sp r e f e r a b l yi nl o a db a l a n c i n g k e yw o r d s ：a g g r e g a t e dm u l t i c a s t ；l o a db a l a n c i n g ；a n tc o l o n ya l g o r i t h m ； a n t n e t ；r o u t i n ga l g o r i t h m ； i v 囊 d e e r i n g 博士在1 9 8 8 年建立了口组播模型【l 】，被看作是对基于组通信的多 用户网络应用的合理解决方案，并引发学术界的广泛研究i 2 1 。组播技术对每个组 只发送一份数据，而不是对每个组成员分别发送数据。在p 组播中，为了能有 效的同时向组成员发送数据，每个组播组都有自己的组播转发地址，并使用树形 传输结构，每棵树的组播转发状态信息都保存在这棵树所经过的路由器的路由表 中。因此，当网络中的组播组及其对应的组播分布树的数量增加时，路由器中的 转发地址表项也随之增加。 随着互联网的发展，使用各种应用服务的组播组数量越来越多，带来路由器 上组播地址数量的迅速增长，特别是在存在很多并发进行的组播组会话的骨干网 络上。庞大的路由表使口地址查找和转发的速度变慢，占用了路由器的大量内 存资源。同时，路由器之间为了维持组播树而相互交换控制信息时也会产生大量 开销。这个问题被称为组播扩展性问题【3 】。组播扩展性问题严重影响网络性能， 不解决这个问题，就无法使组播在互联网上进行大规模部署。 1 2 聚合组播的提出 为了解决组播扩展性问题，国际上已经提出了多种方案。这些方案大体可分 为三种：( 1 ) 削减组播状态；( 2 ) 聚合组播状态；( 3 ) 聚合组播。 1 2 1 削减组播状态的方案 削减组播状态的方案希望通过部分或全部的减少组播状态以达到缩小路由 表规模的目的。其中，t i a n 和n e u f e l d l 4 1 提出在组播树的非分支路径上建立一个 动态的单播通道，即在非分支路由器上消除组播转发状态。但这种方法需要设计 复杂的算法来辨别路由器是否是非分支路由器。s t o i c a t 5 1 等人提出了一种组播算 法r e u n i t e ，也是采用一种“递归单播”的方式，只有分支节点保存组播状态， 山东大学硕士学位论文 从根节点开始将组播数据依次传给自己路由表上的分支节点直到最终组成员。它 们的共同特点是只有当网络中的组比较稀疏时才适用，并且没有考虑控制开销问 题。另一些方案则采用完全不同的组播框架，以达到消除组播转发状态的目的， 如应用层组播吲和x c a s t t 7 1 。应用层组播通过在端节点组成的覆盖网络上构造自 组织树来完成组播功能，而当两个节点通信时，在网络层采用的是单播方式。应 用层组播在部署上相对简单，但覆盖网络无法避免物理链路上出现冗余数据，因 此效率不如d 组播，也不适用于大规模应用，比如网络电视这种需要向许多用 户传输高带宽实时数据的服务。x c a s t 则对组播包中的目标文件进行显式编码， 而非使用组播地址。但这种编码会造成路由器的运算开销，因此只适用于视频会 议等小规模多用户应用。y a n g 对x c a s t 进行的改进【8 】虽然改善了扩展性，但没有 解决控制开销问题。 。 1 2 2 聚合组播状态的方案 聚合组播状态的方案如【9 ，1 0 1 等，其主要思想是在分布树构造好以后，在路由 器上使用某些算法将多个组播转发状态聚合成一个。文献 9 1 中研究了内存和带宽 的折中问题，文献【1 0 】中使用输入输出过滤模型来分析转发状态的聚合。这些聚 合算法都是在组播分布树建立之后再聚合转发状态，并且要求改变现有的组播状 态信息格式，所以很难得到服务供应商的支持。文献【1 1 】中，c h e n g 等人提出了树 切换协议来切换提前得到的组播树。使用这个方法，组播树会有更多的重叠，这 样通过使用状态聚合方案，减少了更多的状态。然而，该方案继承了状态聚合方 案的缺点：没有考虑状态扩展问题的控制开销。 1 2 3 聚合组播方案 聚合组播技术是由u c l a ( 加州大学洛杉矶分校) 网络研究实验室的j u n h o n g c u i 等人提出的。该方案的特点是使多个组播组共享一棵组播分发树，称为聚合 树。因此，网络中树的数量大大减少，路由器只需要保存聚合树的组播状态信息， 一 而不是每个组的组播状态信息。同时，由于聚合树的状态减少，也减少了路由器 之间交换的控制信息。因此，聚合组播技术甫一提出，就引起了国际研究者的注 意，成为组播研究的热点问题。 2 i i j 东大学硕+ 学位论文 j u n h o n gc u i 等在2 0 0 2 年提出了聚合组播的第一个基本框架a m ( a g g r e g a t e dm u l t i c a s t ) f 1 2 1 3 】。文献中对可能出现的不同的组树匹配情况进行了 定义和区分，并采用开销较小的隧道模式以覆盖孤立的组成员。a m 的主要算法 思想包括：( 1 ) 采用类似p i m s m c b t l l 4 中所采用的路由算法为每个组播组建 立一棵原始组播树：( 2 ) 计算所有组播树的带宽开销和隧道开销，将满足阈值的 组播树选为这个组的候选树；( 3 ) 在该组的候选树集合中选取开销最小的树加入 聚合组播树集合，如果该树无法覆盖该组，则在该树基础上建立相应的隧道：( 4 ) 如果该组没有候选树，则将其原始组播树加入聚合组播树集合。a m 的仿真采用 集中式策略，设置一个得到全局拓扑信息的组播控制器负责运行算法。作为一种 新的思想，a m 的主要目的是评估状态聚合的效果与带宽和隧道开销之间的代 价，并没有考虑真实条件下链路带宽上限和负载对聚合的影响。 同年，j u n h o n gc u i 等又提出了分布式的双向树聚合组播协议b e a m ( b i d i r e c t i o n a la g g r e g a t e dm u l t i c a s t ) 1 5 1 为了适应单源或多源的组播服务请求， b e a m 采用在网络中设置根节点以完成组树匹配的工作。想加入组播组的成员 首先向边界路由器发出请求，由边界路由器使用哈希函数为这个组找到一个默认 根节点。根节点先利用p i m s m c b t 协议为该组计算一棵原始组播树，再进行 组树匹配的聚合工作。当有组成员加入或离开时，如果不存在满足要求的聚合树， 将根据情况进行树切换或根切换。树根切换可以得到满意的聚合树，但需要付 出开销代价。每一个根节点都需要维护三张表：组表，树表和组树映射表：边界 路由器则需要维护组树映射表。 在研究了u c l a 的相关工作之后，雷恩大学网络实验室的g u i t t o n 等认为 a m 在每个组加入时需要计算全部组播树，因此在大规模组播下的扩展性较差， 而b e a m 则有根切换时开销过大的问题。g u i t t o n 等于2 0 0 5 年提出了大规模聚 合算法s t a ( s c a l a b l et r e ea g g r e g a t i o n ) 【1 6 1 ，s t a 将所有组播树按照树本身的 代价进行排序，当新组加入时按照树的代价在组播树序列的合适范围中寻找聚合 树。 另外，u c l a 网络实验室和雷恩大学网络实验室的研究人员还提出了多个大 规模组通信条件下的聚合组播算法1 1 7 - 2 0 】。其中，u c l a 网络实验室的l il a o 等 在2 0 0 7 年的文献1 2 0 】中对前期研究成果进行了总结，提出了针对静态和动态条件 山东大学硕士学位论文 下的不同算法。对于已知所有组播组的静态模式，提出了找出候选树之后使用贪 婪算法和i l p 算法将组树匹配问题转化为集合覆盖问题，或者使用伪动态算法随 机选择组播组加入网络并聚合。对组播组动态加入的动态模式，则提出动态算法 在组加入，组离开，组成员加入，组成员离开等动态条件下进行树的生成，扩展， 缩小，撤销等一系列操作完成聚合过程。文献主要讨论了组树匹配过程中的算法 效果及其复杂度，对原始树生成阶段没有过多关注。雷恩大学网络实验室的 m o u l i e r a c 等在2 0 0 6 年提出的t a l d ( t r e ea g g r e g a t i o ni nl a r g ed o m a i n s ) 算法【1 9 】 采用按距离划分的思想将大规模域划分为较小的予域，在每个子域内设置一个管 理实体，当有组播组加入网络时，根据预先划分好的子域对边界路由进行分解， 得到若干分发子树，各子域内的管理实体分别对这些子树进行组树匹配，获得一 组聚合子树，用这组聚合子树完成分发任务。 为了推动聚合组播在实际网络中的应用，q o s 约束的聚合组播问题也得到了 重视，并出现了一系列研究成果。u c l a 网络实验室在2 0 0 2 年就开始了对满足 q o s 的聚合组播算法的研究【2 1 1 ，并在2 0 0 6 年实现了相关协议a q o s m ( a g g r e g a t e d q o sm u l t i c a s t ) 。该协议应用于支持区分服务2 2 1 的m p l s l 2 3 1 域内，为了应对负载 均衡的要求及网络环境的变化，组播组可以在聚合树之间快速切换。协议设置了 称为“树管理员”的实体，收集网络拓扑、有效资源、组成员、q o s 约束等信息， 并实现准入控制、路由、组树匹配等功能。树管理员可以是集中式，也可以是分 布式。有新组加入时，边界路由器首先基于区分服务域对其进行行为分类，然后 通知树管理员。树管理员的组树匹配模块首先按照如下原则查看是否有满足条件 的树：( 1 ) 组成员与树叶节点的匹配情况( 2 ) 组播组的q o s 需求( 3 ) 树上的 剩余带宽。如有，则将相应标签分配给该组，否则由路由模块采用类似 p i m s m c b t 的算法计算一棵新树，然后由准入控制模块检查是否有足够资源满 足q o s 需求。如有则匹配成功，将树转化为m p l s 树，否则拒绝该组播组的加 入请求。 2 0 0 5 年，m o u l i e r a c 等人也在s t a 的基础上提出了满足q o s 约束的算法 q s t a ( q o ss c a l a b l et r e ea g g r e g a t i o n ) 1 2 4 1 。q s t a 的设计思想兼顾了q o s 与负 载均衡的需求，针对a q o s m 进行了如下改进：( 1 ) 生成组播树时使用低负载的 链路，以平衡网络负载( 2 ) 将组播组聚合到最小代价树以分摊网络资源( 3 ) 当 4 l if 东大学硕士学位论文 新组加入时计算树的数量较a q o s m 更少。当新组g 加入时，只从代价为( 矧一1 ) 到c ( 岛) 的树集合内寻找合适的聚合树，其中蚓是组g 的成员数，c ( 岛) 是g 的原始 树的代价。有足够剩余带宽以满足q o s 需求的候选树被选为g 的聚合树。如果 找不到满足代价范围或带宽要求的树，则使用负载最小的链路为g 建立一棵树， 并将其加入聚合树集合。实验结果证明，q s t a 能够对网络负载进行一定程度的 平衡，因此在大规模组播环境下空闲资源分布更平均，可以比a q o s m 接受更多 组播组的加入请求。 2 0 0 8 年，a l i 等又提出了多o o s 约束条件下的聚合组播算法m q m a ( m u l t i c o n s t r a i n e dq o sm u l t i c a s ta g g r e g a t i o n ) 1 2 5 】。该算法借鉴了单播q o s 路由 算法的策略。在为新加入的组建立原始树时，首先使用s a m c r a t 2 6 1 或其他类似单 播q o s 路由算法产生从源节点到组成员的一系列满足多q o s 约束的路径，然后 采用基于贪婪思想的策略对这些路径进行合并，产生这个组的原始树集合。如果 有一条路径在合并时会对原始树集合中的所有树产生环，则将该路径单独作为一 棵树。即，一个组播组可能会由多棵树覆盖。合并结束后，对覆盖该组的多棵树 重新执行聚合，直到只剩一棵树覆盖该组。 以上支持q o s 的聚合组播算法与协议可以看作是聚合组播向着实用化迈出 的重要一步，但是在网络资源利用与负载平衡方面，仍然有许多要做的工作。 1 3 聚合组播要面对的负载均衡问题 尽管聚合组播技术已经成为新的研究热点，也出现了一些试验性质的聚合组 播协议，但是通过对现有聚合组播算法和协议进行分析，可以发现聚合组播在实 际应用中所要面对的链路负载均衡问题还没有得到充分研究。 就聚合组播现有的研究成果来看，一般可将聚合组播过程划分为几个步骤。 对于静态条件，即已知所有组播组的聚合问题，可以划分为( 1 ) 候选树生成， 即对每一个组播组生成其候选树( 2 ) 树选择，即对所有的候选树集合，按照特 定算法从中挑选出合适的聚合树( 3 ) 组树匹配，即将合适的组播组聚合到聚合 树上。对于动态条件，即组播组按时间顺序随机加入的动态聚合问题，则是每加 入一个组播组就生成其对应的原始树，在树选择之后将该组聚合到合适的聚合树 上，即将上述三个步骤顺序执行一次。 a m b e a m a q o s m m q m a 类p i m s m c b t p i m s m c b t 类p i m s m c b t s a m c r a 在源节点相同的情况下，某个节点重复加入多个组播组时，其到源节点的路 径有很大几率出现重合。这固然改善了聚合效果，但在实际应用中，随着链路利 用率的上升，路由器的排队延迟将迅速增加，也就失去了最短路径的意义。图 1 1 为一个简单的网络拓扑示意图，由节点间连线的粗细表示链路上流量的多少。 如图可见，随着源节点为s 的组播组g j 嘶的依次加入和聚合，从源节点发出的 部分