（计算机系统结构专业论文）聚合组播算法研究.pdf

山东大学硕士学位论文 摘要 近年来，随着在i n t e r n e t 上流媒体、视频点播等业务的相继开展，i p 组播 技术得到了快速的发展。组播是一种有效的支持多点通信的机制，它采用树转发 结构，每一个数据包只在节点处被复制，在每一条链路上只发送一次。这种方法 使i p 组播能有效的同时向组成员发送数据，并支持大量的组播组。i p 组播是 i n t e r n e t 上流媒体、视频会议等高带宽、共享型应用的重要基础。 然而，一棵组播分布树要求所有树节点保持每一个组的转发状态，因此，当 多个组播组并存于网络当中的时候，i p 组播遇到一系列问题：随着组播组个数 的增加，组播转发状态增多，组播树上路由器的内存需求随之增大；同时，由于 每个数据包的转发需要进行地址查找，进行组播转发查询的c p u 开销也随之增 大，转发过程也会变慢。当网络中的组播会话数很大时，需要大量的资源和控制 开销来管理组播组。组播转发状态数是制约网络中大规模组播应用可扩展性的瓶 颈。 聚合组播技术就是针对大规模组播可扩展性问题、结合真实网络拓扑结构 特点提出来的。其主要思想是适当放宽对节约带宽的要求，使能够复合的组播组 共享一棵组播分发树。树节点上保持的是这棵树的状态，而不是每一个组播组的 状态，这样大大减少了组播转发的状态数，提高了网络性能。聚合组播问题的关 键在于如何找到数目最小的组播树，使之覆盖所有的组播组。它的数学本质是最 小集合覆盖问题，是一个n p - c 问题。传统的解决聚合组播的方法是贪婪算法。 贪婪算法有一定的局限性，它每一次都选择当前情况下的最优解，很容易陷入局 部最优解，所以得到全局最优解的可能性很小，最终的聚合效果并不理想。 针对于这个问题，本文提出了拉格朗日松弛算法、遗传算法和免疫算法来 选择聚合组播树。 拉格朗日松弛的基本思想是，把造成问题难的约束条件吸收到目标函数中， 并使得目标函数仍保持线性，使得问题容易求解。在传统的拉格朗日松弛算法的 基础上，算法能够动态调整拉格朗日乘子，使找到的解尽量接近于全局最优解。 遗传算法是一类借鉴生物界“自然选择、适者生存”机制的智能搜索算法。 在生物进化过程中，适应性好的个体生存和繁衍的可能性大，适应性差的个体被 山东大学硕+ 学位论文 淘汰，最终生成最优个体。遗传算法是一种有效的全局优化搜索算法。 免疫算法是一类借鉴生物免疫系统提出的智能搜索算法，它利用先验知识来 引导种群的进化，通过生成不同抗原的抗体来达到全局优化的目的，可以在庞大 的搜索空间中寻找接近最优解的准全局最优解。 相同网络拓扑和相同数目组播组条件下的仿真结果表明，这三种算法在提高 聚合度、降低转发状态方面都优于传统的贪婪算法。 关键词：聚合组播：带宽浪费；最小集合覆盖；贪婪算法；拉格朗日松弛算法； 遗传算法；免疫算法 i i 山东大学硕士学位论文 a b s t r a c t r e c e n t l y ，、析t ht h ee x p a n s i o no ft h ei n t e m e ts t r e a mm e d i aa n dv i d e o o n - d e m a n d , t h epm u l t i c a s tt e c h n o l o g yh a sd e v e l o p p e dr a p i d l y i pm u l t i c a s ti sam e c h a n i s m w h i c hc a l ls u p p o r t sm u l t i - p o i n tc o m m u n i c a t i o ne f f i c i e n t l y i tu t i l i z e sat r e ed e l i v e r y s t r u c t u r e ，o nw h i c hd a t ap a c k e t sa r ed u p l i c a t e do n l ya tf o r kn o d e sa n da l ef o r w a r d e d o n l yo n c eo v e re a c hl i n k t h i sa p p r o a c hm a k e s 口m u l t i c a s tr e s o u r c e e f f i c i e n ti n d e l i v e r i n gd a t at oag r o u po fm e m b e r ss i m u l t a n e o u s l ya n ds c a l a b l ei ns u p p o r t i n gv e r y l a r g em u l t i c a s tg r o u p s s oi pm u l t i c a s ti st h ei m p o r t a n tb a s i so fh i g h - b a n d w i d t ha n d s h a r e di n t e m e ta p p l i c a t i o n s ，s u c ha ss t r e a mm e d i aa n dv i d e oc o n f e r e n c e h o w e v e r , am u l t i c a s td i s t r i b u t i o nt r e er e q u i r e sa l lt h et r e en o d e st om a i n t a i n p e r - g r o u pf o r w a r d i n gs t a t e ，s ow h e nt h e r ea r el a r g en u m b e r so fm u l t i c a s tg r o u p si nt h e n e t w o r k ，i pm u l t i c a s ts u f f e r sf r o mm a n yp r o b l e m s ：t h en u m b e ro ff o r w a r d i n gs t a t e s o b v i o u s l yi n c r e a s e sw i t l lt h eg r o w t ho ft h en u m b e ro fg r o u p s t h ei n c r e a s i n gg r o w t h o ft h ef o r w a r d i n gs t a t e sr e q u i r e st h eg r o w t ho fm e m o r yo ft h er o u t e r m e a n w h i l e ， s i n c et h ef o r w a r d i n go f e a c hg r o u pt a k e st i m et os e a r c ha d d r e s s ，t h ec o s to fc p uw i l l a u g m e n ta n dt h ef o r w a r d i n gp r o c e s sw i l ls l o wd o w n t h e r e f o r e ，w h e nt h e r ea r ea l a r g en u m b e ro fs i m u l t a n e o u sm u l t i c a s ts e s s i o n s ，t h es t a t ei n f o r m a t i o na n dc o n t r o l i n f o r m a t i o nw i l lb et o og r e a tt od e a lw i t ho nt i m e t h es t a t es c a l a b i l i t yp r o b l e mh a s r e s t r i c t e dt h ea p p l i c a t i o no fs c a l a b l em u l t i c a s t t os o l v et h ep r o b l e mo fs c a l a b i l i t y ，an o v e la p p r o a c hc a l l e da g g r e g a t e dm u l t i c a s t h a sb e e np r o p o s e d ，w h i c hi sb a s e do nt h ef e a t u r eo fa c t u a ln e t w o r k s i t sm a i ni d e ai st o b r o a d e nt h ed e m a n d so fs a v i n gb a n d w i d t h ，a n dt oe n a b l em a n ym u l t i c a s tg r o u p st o s h a r eam u l t i c a s td i s t r i b u t i n gt r e e t h et r e en o d e sm a i n t a i no n l yt h es t a t eo ft h et r e e ， i n s t e a do fe v e r yg r o u p i nt h i sw a y , t h en u m b e ro ff o r w a r d i n gs t a t e sd e c r e a s e s a c c o r d i n g l ya n dt h ep e r f o r m a n c eo fn e t w o r ki si m p r o v e d t h ek e yo fa g g r e g a t e d m u l t i c a s ti sh o wt of i n dt r e e sw i t hm i n i m a ln u m b e r , e n a b l i n gt h e s et r e e st oc o v e ra l l t h eg r o u p s a g g r e g a t e dm u l t i c a s tc a na c t u a l l yb ea t t r i b u t e dt om i n i m a ls e tc o v e r p r o b l e m , w h i c hi s a nn p - c o m p l e t ep r o b l e m t h ec o n v e n t i o n a lw a yt os o l v e i i i 山东大学硕士学位论文 a g g r e g a t e dm u l t i c a s tp r o b l e mi sg r e e d ya l g o r i t h m g r e e d y a l g o r i t h mi s al o c a l o p t i m a la l g o r i t h mh a v i n gi t sl i m i t a t i o n t h ea g g r e g a t e de f f e c to f t h i sa l g o r i t h mi sn o t i d e a l t os o l v et h ep r o b l e mo fh o wt os e l e c ta g g r e g a t e dm u l t i c a s tt r e e s ，t h i sp a p e r p r e s e n t sl a g r a n g er e l a x a t i o na l g o r i t h m ，g - e n e t i ca l g o r i t h ma n d i m m u n ea l g o r i t h m t h eb a s i ci d e ao fl a g r a n g er e l a x a t i o na l g o r i t h mi st oc o m b i n et h ec o n s t r a i n t c o n d i t i o n st h a tm a k et h ep r o b l e mh a r di n t oo b je c t i v ef u n c t i o n ，w h i c hi sk e p tl i n e a rt o f a c i l i t a t et h es o l u t i o n i tc a l ld y n a m i c a l l ya d j u s tl a g r a n g em u l t i p l i e r , m a k i n gi t p o s s i b l ef o rt h es o l u t i o nt h a ti sf o u n d t ob ec l o s et og l o b a lo p t i m a ls o l u t i o n g e n e t i ca l g o r i t h mi sak i n do fi n t e l l i g e n ts e a r c ha l g o r i t h mw h i c hi sp r e m i s e do n t h ee v o l u t i o n a r yi d e a so fn a t u r a ls e l e c t i o na n d “s u r v i v a lo ft h ef i t n e s s i n d i v i d u a l s w h i c ha l em o r es u c c e s s f u li na d a p t i n gt ot h e i re n v i r o n m e n t w i l lh a v eab e t t e rc h a n c e o fs u r v i v i n ga n dr e p r o d u c i n g ，w h i l s ti n d i v i d u a l sw h i c ha r el e s sf i tw i l lb ee l i m i n a t e d b yt h i sw a y , t h eb e s ti n d i v i d u a lw i l lc o m e i n t ob e i n g g e n e t i ca l g o r i t h mi sa ne f f e c t i v e g l o b a lo p t i m a ls e a r c h i n ga l g o r i t h m i m m u n ea l g o r i t h mi sak i n do fi n t e l l i g e n ts e a r c ha l g o r i t h mt h a tu s e sb i o l o g y i m m u n es y s t e mf o rr e f e r e n c e i tc a ni n d u c tt h ee v o l u t i o no fs p e c yw i t hp r i o r k n o w l e d g e i nt h i sw a y ，i tc a l lg e th y p o g l o b a lo p t i m a ls o l u t i o nf r o mah u g er e s e a r c h s p a c eb yc r e a t i n ga n t i g e no f d i f f e r e n ta n t i g e n t h er e s u l t so fs i m u l 撕o nu n d e rt h es a m en e t w o r kt o p o l o g ya n dm u l t i c a s tg r o u p s i n d i c a t et h a tt h e s e t h r e ea l g o r i t h m sa r eb e t t e rt h a nt h ec o n v e n t i o n a lg r e e d ya l g o r i t h m i ni m p r o v i n ga g g r e g a t i o nd e g r e ea n dr e d u c i n gm u l t i c a s tf o r w a r d s t a t e s k e y w o r d s ：a g g r e g a t e dm u l t i c a s t ；b a n d w i d t hw a s t e ；m i n i m a l s e tc o v e r ； g r e e d ya l g o r i t h m ；l a g r a n g er e l a x a t i o na l g o r i t h m ；g e n e t i c a l g o r i t h m ；i m m u n ea l g o r i t h m i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声 明的法律责任由本人承担。 论文作者签名：塑 日期：墨盟垒至i 幺巫盆 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保 存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蕉垄丝导师签名：三虽益日期：塑噬塑尘盆 l l i 东大学硕士学位论文 1 1 组播转发状态数问题 第一章绪论 自从d e e r i n g 博士口1 1 9 8 8 年建立i p 组播模型以来，由于组播在数据转发上 有明显的优势，因此一直是人们研究的热点。然而经过2 0 年的组播理论研究 和工程实践，i p 组播仍然远未在i n t e r n e t 上普及。 组播转发状态数问题是阻碍组播技术发展的技术难题之一。组播中，一个 组播地址对应着一个组播组，而且不能表示组播组成员的位置信息。组播分布 树要求所有树节点保持每一个组的转发状态，而这些转发状态随着组播组个数 的增加以组播组个数x 源个数的速度增长乜1 。 随着网络上并发进行的组播组数量的增加，路由器上保持的转发状态越来 越多，特别是在并发进行的组播组会话很多的骨干网络。这些不断增长的转发 条目使得路由器的内存需求增大；同时，由于每个分组的转发需要地址查找，转 发过程也会变的很慢。因此当网络中的组播会话数很大时，会消耗大量的资源 ( 如保存组状态信息的内存) 和控制开销( 如建立和维护组播树) 来管理组播 组，这就是组播转发状态数问题。组播转发状态数问题严重的影响了网络性能， 已经成为制约组播技术发展的瓶颈。 1 2 聚合组播的提出 针对组播转发状态数问题，国外的一些研究者提出了许多种方案，大致上可 以分为三类：l - 状态聚合技术，2 状态转移技术，3 聚合组播技术。 状态聚合技术的代表有r a d o s a l v o v 、t h a l e r 等。其中r a d o s a l v o v 嘲等人提出 了一个算法来聚合转发状态并分析研究了内存和带宽的折中问题，t h a l e r 等人 使用输入输出过滤模型来分析转发状态的聚合。这两种状态聚集技术都尝试在 分布树构造好之后，在每一个路由器上把一些组播转发状态聚合成一种状态。这 些聚合算法一般非常复杂，而且需要活动组播组的细节信息( 如文献 3 中对带 宽率的评估等) 。因而对于很多服务提供商来说，这种方案是不能接受的。 山东大学硕士学位论文 状态转移技术的代表有t i a n 、n e u f e l d 、c h u 、f r a n c i s 等。其中t i a n $ 口 n e u f e l d 瞌1 提出了在组播分布树的非分支路径上建立动态单播通道的方案来减少 转发状态。这样，组播转发状态在非分支路由器上被消除。然而，这种方案需要 设计复杂的方法来辨别非分支路由器，更重要的是，这种方案只能应用于稀疏网 络中，因而局限性较大。c h u 畸1 $ 口f r a n c i s n 3 试图在所有路由器上完全消除组播状 态。他们的方案是，在组播组成员中构造一棵自组织树来提供多点通信，这样就 不需要网络层组播的支持，从而将复杂性移到端节点上。这些状态转移技术虽然 不需要路由器维护组播转发状态，但是转移组播状态本身就需要路由器来处理， 增加了额外的开销，因而并没有达到预期效果。 聚合组播技术是由u c l a ( 加利福尼亚大学洛杉矶分校) 网络研究实验室的 j u n - h o n gc u i 睁1 0 1 等人提出的。与前两类方案不同的是，该方案使能够复合的 组播组共享一棵组播分发树( 称为聚合组播树) ，这样明显减少了网络中树的 总数目。核心路由器只需要保持每棵聚合组播树的状态，而不是每个组播组的 状态，从而大大减少了转发状态；同时，有效减少了路由器转发组播包的开销， 提高了网络性能。 1 3 聚合组播的研究现状 由于聚合组播很好的支持了大规模组播，所以该方案一经提出，已经迅速引 起全世界的关注，美国、法国等国家纷纷进行聚合组播的研究。 u c l h 网络研究实验室于2 0 0 2 年深入研究了聚合组播，在文献 11 中他们 举例说明了聚合组播在组一树映射时有四种情形，针对其中的不完全匹配情形， 提出了采用隧道技术在原有树上进行扩展的方法来进行组一树映射，并基于此思 想给出了算法的具体描述：1 为每一个组播组建立一棵原始树；2 对于组播树 集合中的每一棵树，计算它的带宽开销和隧道开销，将满足限度的树选作这个组 的候选树；3 在组的候选树集合中，选出开销最小的树，如果该树不能覆盖这个 组，则在这棵树的基础上建立相应的隧道；4 如果步骤2 中没有得到候选树，则 这个组的原始树被选中并被加入组播树集合。 同年，u c l a 网络研究实验室进行了聚合组播协议的研究，并在网络仿真工 具n s 一2 下成功实现了基于双向树的聚合组播协$ 义b e a m n 引。b e a m 协议的特点是：1 2 山东大学硕士学位论文 使用p i m - s m c b t 协议构建原始树；2 当某个边界路由器接收到某个组的加入消 息时，它会根据组一核哈希函数给该组指派一个默认核，由默认核负责为该组查 找或建立一个合适的聚合组播树；3 每一个核都需要维护三张表：组表、树表和 组树映射表，每一个核接收到来自一个组的加入离开消息时，它所维护的三张 表也随之更新；4 如果某个默认核无法找到一棵现存的能够覆盖某个组的聚合 组播树，而另一个核中恰好存在一棵满足要求的树，此时可以考虑切换核，虽然 切换核可以得到更好的聚合效果，但是要付出更大的开销；5 每个边界路由都需 要维护一张组一树映射表，以便于它能够将数据包发送到对应的聚合组播树。 2 0 0 6 年，u c l a 网络研究实验室进行了满足o o s 约束的聚合组播协议的研究， 并在n s - 2 下成功实现了基于区分服务网络的满足o o s 约束的聚合组播协议 a q o s m n 副。a q o s m 协议的基本内容是：1 该协议应用于支持区分服务的m p l s 域内， 主要特点是一个组可以方便的从一棵组播树切换到另一棵组播树；2 a q o s m 弓i 入 了树管理员的概念。树管理员是一个逻辑实体，在构成上可以是集中的也可以是 分布式的。树管理员划分了几大模块，如准入控制模块、路由模块和组一树映射 模块等，每个模块分别实现各自的功能；3 当需要为一个组新建一棵组播树 时，a q o s m 先采用类似p i m s m c b t 的路由算法构造一棵双向树，然后将双向树转 化为m p l s 树。文献 1 3 中还给出了基于双向树的标签分配解决方案。 雷恩大学网络实验室研究了u c l a 提出的组播聚合算法，在文献 1 4 中指出， u c l a 的聚合组播存在一点不足：没有在大规模的环境下仿真。确切的说，当树的 数目很多时，单纯的聚合组播扩展性很差，主要原因是每当一个新的组加入时， 聚合组播需要分析全部可能的树，即使很多树根本不可能成为候选树；b e a m 也存 在一点不足：当一个新的组加入时，b e a m 根据一个哈希函数将该组指定到某个 核上，然后在该核建立的组播树中寻找候选树，但是这种方法往往找不到满足要 求的候选树，导致切换到其他核构成的组播树上，这样代价比较大。所以，雷恩 大学网络实验室于2 0 0 5 年提出了一种大规模树聚合算法s t a 1 t 1 ，其主要思想 是：1 按照代价将所有组播树划分为一系列树的集合，这里的代价是指每棵组播 树上所有链路的代价和；2 当某个新的组劝口入网络时，其对应的候选树集合为 一个指定代价范围的组播树集合，该代价的范围是 t c o s t ( g ) 丁c o s ，( g ) + r c o s ，国) * b t h ，这里的b t h 为带宽浪费比，t c o s t ( g ) 为每 3 山东大学硕十学位论文 棵组播树上所有链路的代价和。 2 0 0 5 年，雷恩大学网络实验室从流量工程的角度进行了基于q o s 约束的大 规模树聚合算法q s t a 的研究n 朝。q s t a 是在s t a 基础上对带宽约束方面的扩展，它 为每个组设定了响应的带宽要求，为每条链路设定了带宽容量。当有新组加入时， 按照相应的代价范围寻找能够覆盖这个组的、满足带宽要求的费用最小的组播 树；如果找不到，则按照优先利用带宽负载最小的链路的原则，为这个组建立一 棵新的组播树。 同年，雷恩大学网络实验室提出了一种分布式的聚合组播协议d m t a n 们。在 文献 1 6 中，他们首先指出了u c l a 网络研究实验室的a q o s m 协议和b e a m 协议的不 足：对于a q o s m ，所有组成员关系的变化都要通知树管理员，这样既增大了延迟， 又过分依赖树管理员；而对于b e a m ，所有组成员关系的变化也都要通知所有的核 心路由器，这样增大了延迟，而且往往要搜索所有的核心路由器才能找到合适的 组播树。在此基础上，他们提出了d m t a 协议，其主要思想是：1 去掉了树管理员， 而引入拓扑管理员，仅当拓扑变化时，才需要对组成员关系作响应调整；2 对于力 个边界路由器b lb 2 ”b n , 使用妇位二进制编码，每一位代表一个相应的边界路 由，例如共5 个边界路由，0 1 1 0 1 便是覆盖b 2 , 6 墨b 5 的组播树，用该二进制的十 进制值将其标识为旭在必她施处均用该标签存储组播树。通过这种方法， 在每个边界路由处仅需保存一张不同的标签列表，当每次组需要适当的组播树 时，仅从候选树集合的相应子集中寻找，从而提高了执行效率。 雷恩大学网络实验室于2 0 0 6 年提出了大域中的组播聚合算法t a l d n 利，其主 要思想是：预先将边界路由分成不同的组，当有一个组播组会话加入网络中时， 根据预先设计好的方案将这个组的边界路由进行分解，得到若干个子分发树，分 别对这些子分发树进行组一树匹配，获得一组聚集子树，用这组聚集子树完成分 发任务。文献 1 7 提出了一种帮的而且很易理解的划分子域的方法，其主要思 想是：先域玢为2 个子域，寻找域砷距离最大的两个节点x 1 ，z 2 ，x l 子域p ， 也子域肼；然后循环寻找相应的最近的节点加入对应的子域中，直到所有节 点要么划入历，要么划入占统如果将刃j ，彪采用该方法进一步划分，便可得到4 个子域，依此类推。由于t a l d 将一个大规模的域划分为一个个小的子域，只需 为每个子域设置一个管理实体，该实体只需为自己子域内的拓扑作相应的决策 4 山东大学硕士学位论文 葛曼曼曼量曼皇曼量量曼蔓曼曼曼曼曼曼蔓曼曼曼曼罡曼曼曼鼍i 一一 m _ 鼍曼曼曼曼曼曼曼皇曼曼量曼舅曼曼曼曼曼曼曼皇曼皇鼍量皇皇曼 即可。在以欧洲k p n o w e s t 网络为网络拓扑结构下进行的仿真实验表明，t a l d 的 聚合效果非常显著。 c i s c o 公司深入研究了聚合组播的吞吐量和潜能，于2 0 0 7 年6 月推出了基于聚 合组播技术产品一i p t v 引。聚合组播产品的面世，意味着聚合组播已经从理论研 究阶段发展到工程研究阶段。： 尽管目前国际上很多机构从不同的角度对聚合组播进行了研究，不过当网 络中有大规模组播组存在时，如何从候选树集合中选择出数量最小的树，使之 为所有的组播组会话提供支持，这是大规模组播聚合的核心。本文研究的重点 正是聚合组播的选树问题，而不是聚合组播协议的细节。文献 8 ，1 0 ，1 9 指 出，聚合组播选树问题本质上是n p - c n 题乜0 2 1 1 。随着组播组数目的增多，问题 的复杂性大大提高，寻找聚合组播树所需要的时间几乎呈指数级增长。 u c l a 网络实验室采用贪婪算法在候选树集合中进行选树，每一次找到的 解都是当前情况下的最优解。贪婪算法是一种局部优化算法，容易陷入局部最 优解，最终找到的聚合组播树比较多，聚合效果并不理想。如何设计好的启发 式算法，尽可能从候选树集合中找到数目最小的树，直接关系到大规模组播聚 合的效果。 1 4 论文的主要工作概述 首先，本文介绍了聚合组播的概念，在对相关概念深透理解的基础上，深入 探究了聚合组播问题的实质以及带宽浪费这一关键要素，提出了带宽浪费门限阂 值这一重要概念，并总结出了聚合组播的数学模型。为了量化算法对大规模组播 聚合效果的优化程度，提出了聚合度等三个度量。 然后，根据提出的聚合组播模型，改进了传统的拉格朗日松弛算法、遗传算 法和免疫算法，设计了适合大规模组播聚合的优化算法来从候选树集合中选择聚 合组播树。 最后，为了比较各种算法的聚合效果及复杂度，本文采用了u c l a 网络研究 实验室提出的网络拓扑结构和组播组模型进行仿真实验，用仿真实验结果的比较 对本文算法的优劣进行了验证。仿真结果证明，本文提出的三种算法在提高聚合 度、减少转发状态方面大大优于传统的贪婪算法。 山东大学硕士学位论文 1 5 论文的整体结构和章节安排 本文的其余部分共分为五章。 第二章对聚合组播做了详细的介绍，分为四小节。其中，2 1 给出了聚 合组播的相关概念；2 2 分析了聚合组播中的重要要素一带宽浪费；2 3 抽 象出了聚合组播的数学模型：2 4 介绍了国际上求解聚合组播的方法。 第三章介绍了如何设计拉格朗日松弛算法求解聚合组播问题。其中，3 1 描述了传统的拉格朗日松弛算法；3 2 用拉格朗日松弛算法来求解聚合组播 问题；3 3 通过仿真实验，分析了该算法对聚合组播的优化程度。 第四章介绍了如何用遗传算法求解聚合组播问题。其中，4 1 描述了传 统的遗传算法；4 2 给出了用遗传算法求解聚合组播问题的详细步骤；4 3 通过仿真实验，分析了该算法对聚合组播的优化程度。 第五章介绍了如何用免疫算法求解聚合组播问题。其中，5 1 描述了传 统的免疫算法；5 2 给出了用免疫算法求解聚合组播问题的详细步骤：5 3 通过仿真实验，分析了该算法对聚合组播的优化程度。 第六章对所做的工作进行了总结并对下一步的研究工作进行了展望。 山东大学硕士学位论文 第二章聚合组播介绍 2 1 聚合组播的相关概念 g o ( d l 、b l 、c 1 ) g i ( f i 、b i 、c 1 ) 图2 - 1 聚合组播示意图 图2 - 1 是一个分层的域间网络对等结构。假定域a 是一个区域或全国的i s p 骨干网，域及及，都是域彳在某一区域内的用户网络，域及呵以是另外的用 户网络，或者其他与彳对等的i s p 网络。网络中有三个组播组卯泖，曰厶a 人 g l ( f l 、b i 、c i ) 、g 2 ( d 1 b 1 ) o 组g 嫩a 氏钓子椭为t o ( a l ，a a a b a 2 , 彳? 力组6 1 ：芒e 域彳内的子树为乃翻j ，彳a ，月6 ，肥a 3 a 组必在域a 中的子树为刀 翻j ，如，a b ，a 2 ) 。由于三个组在域a 中有相同或相重合的内部域子树，所以这 三个组是能够复合的，此时可以使用同一个组播组地址，建立一棵覆盖a 1 ，a 2 和彳。带点的预定义树翮j ，如，a b ，a 2 , a 3 ) ，这棵树被称为聚合组播树( a g g r e g a t e d m u l t i c a s tt r e e ) ，可以由这三个组播组所共享。 使用聚合组播树时，域a 的边界路由器( 如彳，) 把发送过来的数据进行封装， 然后用聚合组播树地址在树趾发送，并在离开的边界路由器上( 如彳& a 3 ) 解 封，最后进一步转发到用户网络中。在这种情况下，内部路由器月印彳职需要为 这棵聚合组播树维护单独的转发条目，而不必考虑有多少个组播组在使用它。 由于核心路由器a a 、月识需保存聚合组播树的状态，而不必分别保存三棵原 始树的状态，所以转发状态得到了减少；同时，由于树个数的减少，交换的刷新 消息也随之减少，这样树的管理开销也得到了减少。 文献 8 ，1 0 ，1 9 中指出，聚合组播中有三个重要的概念： 覆盖( c o v e r ) ：组播组嘲所有终端节点都是聚合组播树啪成员节点，则称树 7 山东大学硕士学位论文 履盖组播组侥 完全匹配( p e r f e c tm a t c h ) ：t 覆盖e 且丁的所有叶节点都是口的终端节点， 则称该匹配为g 的完全匹配。 漏匹配( 1 e a k ym a t c h ) ：t 的一些叶节点不是口的终端节点，则称该匹配为口 的漏匹配。 根据上述定义，聚合组播树厂翻j ，儿，彳6 ，彳力a 3 ) 对于成员为观观例 的组播组印来说，是完全匹配；而对于成员为阮8 1 ) 的组播组谨来说，则是漏 匹配。 2 2 带宽浪费分析 对于图2 - 1 中的三个组播组g o , 口所口0 2 , 它们共用一棵聚合组播树厂翻j ，儿， 月6 ，月力a 3 ) 。此时如果在域屿域跎间建立一个组播组会话，从域刃向域跋送 数据，那么由于组播组卯佃j ，b 1 ) 使用聚合组播树乃数据包除了在链路a 1 a a , i b a 2 上传输外，还将通过链路彳别。难送到域g 而域纠【身不需要这个数据包，这样就 引起了带宽的浪费。由于聚合组播树的所有叶节点不可能都是正在使用它的组播 组的成员节点，所以聚合组播中漏匹配是必然的，带宽浪费也是必然的。 为了便于对带宽浪费进行定量分析，从简化问题的角度考虑，本文与文献 8 ， 1 0 ，1 9 一样，没考虑复杂的q o s 约束，而仅采用跳数作为衡量树费用的指标。对 于图2 - 1 中域屿域砣间的会话，原始树7 缃费用为3 ，而聚合组播树哟费用是4 ， 浪费的费用为4 3 = 1 ，这样带宽浪费的比值为1 4 = 0 2 5 。从而可以定义带宽浪费 比： m ：坚剑二哑卫 i t “( g ) i 其中广( g ) 为聚合组播树边的条数，i f ( g ) i 为原始组播树边的条数。 带宽浪费必须控制在一定的范围之内，如果带宽浪费太小，那聚合的益处 随之减少；反之如果带宽浪费太大，超过允许的限度，则没有必要使用聚合技术， 而只需采用原始树进行数据传输。带宽浪费门限阂值啪选取是根据具体的网络 拓扑和组播组模型而定的。 带宽浪费在聚合组播中起着非常重要的作用。由于一定的带宽浪费是允许 【i j 东大学硕士学位论文 的，所以可以合理的利用带宽浪费，来扩大聚合组播树的寻找范围。在文献 8 ， 9 ，1 0 中，对每一个组播组，用一定的组播路由算法得到一棵原始组播树( 此 时b t h = o ) 后，可以对该树添加一定数量的边，扩展出更多新树。扩展时添加 的链路数k 由原始组播树上的链路数l f ( g ) j 和带宽浪费比6 坊决定，即 k = l f ( g ) l b t h 。扩展时，递归地对每一个非树上的结点，判断把该节点与它到 树上最近的节点相连后生成的树的带宽浪费比b t h 是否小于阈值历如果是，则 将该节点添加到组播树中，并把扩展后的树作为一棵候选组播树。通过这种方 法，候选树数目增加，这样合理的扩大了选树范围，有利于更好的寻找聚合组 播树。 聚合组播是在牺牲定带宽的基础上，把能够复合的组播组映射到同一棵分 布树上，从而提高了组间树的共享能力，减少了组播转发状态和核心路由器上树 的管理开销。所以聚合组播可以看作是聚合的益处与随之而来的带宽浪费之间的 一种均衡。 2 3 聚合组播的数学模型 有了带宽浪费比这一参数。我们就可以提出聚合组播的模型：给定一个组 播网络c ( g 剀、组播组集合c r o u p s 以及带宽浪费门限阂值历对于组播组集合 中的每一个组播组，找出所有能够覆盖这个组，并且满足带宽浪费门限阈值刃 的所有，纠，组成候选树的集合：然后在候选树的集合中通过某种算法选取一 些树作为聚合组播树。选择聚合组播树时要满足两个条件：一、树的数目最小， 二、所有的组都被覆盖到。 从聚合组播模型上可以看出，聚合组播问题实质上是最小集合覆盖问题啪1 。 最小集合覆盖问题是n p - c 问题，算法的复杂度随着问题规模的增大而指数级增 长，需要设计合理的启发式算法来求解。 为评估各种算法对大规模组播聚合的优化效果，定义了三个度量： 算法执行时间p e t ( p r o g r a me x e c u t i o nt i m e ) 阿磙示算法的执行时间，反映了算法的执行效率。艘殖越大，算法的执 行效率越低。 9 山东大学硕士学位论文 聚合度a d ( a g g r e g a ti o nd e g r e e ) 彳d ：丝 n t 其中n 。表示组播组的数量，m 表示网络中聚合组播树的数量。彻值越大， 算法聚合能力越强，相应的转发状态就越少。图2 - i 中牺牲了链路a a a 3 的带宽， 使用聚合组播树丁来转发数据，把三个组播组g o , 钟、凹聚合到一棵树，上， 聚合度为3 1 = 3 。 转发状态降低率s r r ( s t a t er e d u c t i o nr a t i o ) s r r s 。一堡二s 嘴一1 s 瑶 ：! 竺：塑二! 丝：一= 三塑 s 一璎s 1 0 一璎 其中表示采用聚合组播情况下网络中的转发状态数，瓯一蝣表示没有采 用聚合组播情况下网络中的转发状态数。s r r 值越大，算法效果越好。图2 - 1 中未使用聚合时核心路由器彳a 、彳6 要保存原始树t o , t 1 、刀的状态，聚合后 只保存聚合组播树丁的状态，转发状态降低了( 3 - 1 ) 3 = 0 6 7 。 聚合度月所口转发状态降低率5 宠尼是衡量聚合性能的关键指标，图2 - i 中以浪费 0 2 5 的带宽的代价，获得了值为3 的聚合度和值为0 6 7 的转发状态降低率，所以 聚合组播可以看作是聚合的益处与带宽浪费之间的一种均衡。 2 4 国际上求解聚合组播的方法 2 4 1 选树算法 对于如何从候选树集合中选择出聚合组播树，目前国际上多采用贪婪算法睛 1 0 3 。具体方法是：首先，找到覆盖的组最多的树，放入聚合组播树集合，并把 相应的组标记为已覆盖；然后，在剩下的未被覆盖的组中重复这一过程，直到 所有的组都标记为已覆盖，最终得到所有聚合组播树。 贪婪算法每一次找到的解都是当前情况下的最优解，这是一种局部优化算 法，容易陷入局部最优解，因此找到的聚合组播树个数比较多，聚合效果并不 特别理想。 山东大学硕士学位论文 2 4 2 仿真环境 u c l a 网络研究实验室采用a t & t 胁1 骨干网络作为仿真的模拟网络。该网络共 1 2 3 个节点，包括9 个网关路由器，9 个骨干路由器，9 个远端吉比特路由器， 9 6 个远端接入路由器。为便于实验仿真，对a t ti p 作如下简化：( 1 ) 网关路 由器和骨干路由器( 统称为核心路由器) 保持不变：( 2 ) 将连接到同一核心路 由器的所有远端路由器汇聚成一个节点；( 3 ) 对每一个网关路由器添加一个交 换节点，代表与其相连的对等网络。简化后的网络拓扑中共有5 4 个节点如图 2 2 所示，其中六边形代表核心路由器。 图2 2 简化后的a t ti p 骨干网络示意图 对于组播组成员的分布，采用r a n d o m - n o d e - w e i g h t e d 模型，将核心路由 器节点的权重设为0 ，由远端路由器汇聚而成的节点的权重与它代表的接入路 由器的数量成正比例，考虑到交换节点常常和具有大量组播组成员的对等网络 相连，将其权重设为0 9 。为控制组播组数量，假定组播组按照泊松过程加入 到网络中，组播组在网络中存活时间呈指数分布，平均存活时间为t ，组播组加 入速率为v ，当组播网络状态基本稳定之后组播组的平均数量霄= v t 。固定仿 真时间为6 0 0 s ，组播组的平均寿命为l o o s ，改变组播组加入的速率 ，可以改变 组播组的数量。假设4 0 0 s 以后，组播状态稳定，然后每隔1 0 s 取样一次，这样 当到达6 0 0 s 时，可以得到2 0 个取样值，分别计算2 0 个取样值情况下的参数， 最后取平均值作为最终结果。 仿真实验在a m da t h l o n ( t m ) 6 4p r o c