（计算机系统结构专业论文）多约束的应用层组播算法研究.pdf

山东大学硕十学位论文 摘要 网络层组播可以比单播更高效地实现一对多或多对多的数据分发，能显著提 高网络资源的利用效率。然而，传统的网络层组播技术存在着路由器转发状态数 膨胀、部署成本高等问题，阻碍了组播的普及推广。虽然后来提出的一些网络组 播方案在一定程度上有所改善，但都无法从根本上解决这些问题。在这样的背景 下，应用层组播应运而生，由于其组播转发在应用层实现而无须路由器参与，因 而从根本上避免了网络层组播的转发状态数问题。近几年，应用层组播被广泛地 部署于视频会议、网络电视、视频通话、网络流媒体等网络应用中。然而，随着 用户需求的不断提升，现有的应用层组播技术也逐渐显现出不足，例如端到端延 迟过大、节点负载过高、转发网络不稳定等，这些问题在一定程度上阻碍了应用 层组播的进一步推广部署。 本文论述了目前应用层组播的各种性能指标以及这些指标对组播质量的影 响，在此基础上，对目前已存在的各种应用层组播建模方案做了对比分析，采用 度和延迟约束的最小生成树( d e g r e e a n dd e l a y c o n s t r a i n e dm i n i m u ms p a n n i n g t r e e ，d d c m s t ) 作为应用层组播的算法模型，该模型对应用层组播的两个关键性 能指标：端到端延迟和节点度数进行约束，使组播的端到端延迟始终保持在可接 受的范围内，并有效限制终端节点的负载。该模型以生成树费用作为优化目标， 可以在满足用户需求的前提下，尽量节省网络资源、降低部署成本，有利于应用 层组播的推广。 在对d d c m s t 问题深入分析的基础上，本文给出了该问题为n p c 问题的证 明，并提出用微粒群算法求解该问题。微粒群算法是一种新兴的群智能算法，该 算法的迭代过程体现了群体行为在个体经验的交互过程中不断趋优的过程。该算 法有着良好的收敛性和稳定性，被广泛应用于各个领域。 微粒群算法起初主要应用于求解连续非线性函数的极值问题，并不能直接用 于求解d d c m s t 这样的组合优化问题，本文在微粒群算法基本思想的基础上， 对标准微粒群算法进行了改造，其中包括初始解的生成、速度向量的更新、可行 解的树形变换和消环等算法过程，从而将微粒群算法应用于求解d d c m s t 问题。 山东大学硕士学位论文 通过对d d c m s t 问题的求解，得出了一种全新的应用层组播路由算法。该算法 继承了标准微粒群算法的优点，扩展性好，收敛速度快，十分适合求解大规模的 应用层组播路由问题。 本文提出的基于微粒群的算法方案不仅能够应用于求解d d c m s t 问题，对 于其它各种带约束的最小生成树问题，同样可以求解，只需针对不同的约束条件 调整其适应度计算函数。基于这一思想，本文又提出了两种求解带约束的最小生 成树问题的算法方案，其中一种用于求解度约束的最小生成树问题，另一种用于 求解叶节点约束的最小生成树问题。 本文最后对提出的基于微粒群的应用层组播路由算法进行了仿真实验，将另 外两种分别基于蚁群和遗传的应用层组播方案与本文方案进行了对比，实验结果 表明，本文的应用层组播路由方案在端到端延迟、生成树费用、节点度数、收敛 时间等方面都具备一定的优势，当拓扑规模较大时，优势更加明显，呈现了良好 的稳定性和扩展性。 关键词：组播；应用层组播；微粒群；生成树 山东大学硕+ 学位论文 a b s t r a c t t h en e t w o r kl a y e rm u l t i c a s tc a l li m p l e m e n to n e 4 0 m a n yd a t ad e l i v e r yi nam u c h m o r ee f f i c i e n tw a yt h a nu n i c a s ta n ds i g n i f i c a n t l yi m p r o v e dt h eu s i n ge f f i c i e n c yo f n e t w o r kr e s o u r c e h o w e v e r , t h et r a d i t i o n a ln e t w o r kl a y e rm u l t i c a s tt e c h n o l o g yh a s m a n yp r o b l e m ss u c ha st h ee x p a n s i o no fr o u t i n gf o r w a r ds t a t e sa n dh i g hd e p l o y m e n t c o s t , w h i c hl a r g e l yi n f l u e n c e dt h ea p p l i c a t i o no fm u l t i c a s ta l lk i n d so fs o l u t i o n sh a v e b e e np r o p o s e d , w h i c hh a v ec h a n g e dt h es i t u a t i o ni nab e r e rw a y ，b u tn e v e rs o l v e d t h e s ep r o b l e m su l t i m a t e l y u n d e rt h i ss i t u a t i o n ，t h ea p p l i c a t i o nl a y e rm u l t i c a s ti s p r o p o s e d a p p l i c a t i o nl a y e r m u l t i c a s t i m p l e m e n t e dt h e m u l t i c a s tf o r w a r do n a p p l i c a t i o nl a y e r , u l t i m a t e l y s o l v e dt h ef o r w a r ds t a t ep r o b l e mo fn e t w o r kl a y e r m u l t i c a s t i nr e c e n ty e a r s ，a p p l i c a t i o nl a y e rm u l t i c a s ti sw i d e l yd e p l o y e di n a p p l i c a t i o n ss u c ha sv i d e oc o n f e r e n c e ，n e t w o r kt e l e v i s i o n ，v i d e oc o m m u n i c a t i o n ， n e t w o r kf l o wm e d i ae r e h o w e v e r , a l o n gw i t ht h ei m p r o v e m e n to ft h eu s e r r e q u i r e m e n t , t h ea p p l i c a t i o nl a y e rm u l t i c a s tt e c h n o l o g yh a ss h o w ns o m ew e a kp o i n t s t o o ，s u c ha sl a r g ee n d t o e n dd e l a y , n o d eo v e r l o a d ，t h eu n s t a b l ef o r w a r dn e t w o r k ， w h i c hh a v eb e c o m eo b s t a c l e so ft h ea p p l i c a t i o nl a y e rm u l t i c a s t t h i sp a p e rh a sc o n c l u d e da l lk i n d so fp e r f o r m a n c em e a s u r e m e n t so fa p p l i c a t i o n l a y e rm u l t i c a s ta n dt h ei n f l u e n c et l l e yh a v et ot h em u l t i c a s tq u a l i t y w h a t sm o r e ，w e c o m p a r e da l lk i n d so fa p p l i c a t i o nl a y e rm u l t i c a s ta l g o r i s mm o d e l sa n dd e c i d e dt ou s e d e g r e e - a n dd e l a y - c o n s t r m n e dm i n i m u ms p a n n i n gt r e e ( d d c m s t ) a st h ea l g o r i s m m o d e lo ft h ea p p l i c a t i o nl a y e rm u l t i c a s t t h i sm o d e lc o n s t r a j n e dt w oo ft h em o s t i m p o r t a n tm e a s u r e m e n t s ：e n d - t o e n dd e l a ya n dn o d ed e g r e e i tc a ni m p r o v et h e q u a l i t yo fm u l t i c a s tf o r w a r d ；k e e p st h em u l t i c a s td e l a yi nt h ea c c e p t a b l er a n g e t h e m o d e lr e g a r d st h ec o s to ft h es p a n n i n gt r e ea st h eo p t i m i m n gt a r g e t ，c a ns a t i s f yt h e r e q u i r e m e n to ft h eu s e ra n ds a v en e t w o r kr e s o u r c ea tt h es a m et i m e ，w h i c hi sv e r y h e l p f u lt ot h ed e p l o y m e n to fa p p l i c a t i o nl a y e rm u l t i c a s t ， b a s e do nt h ea n a l y s i so ft h ed d c m s tp r o b l e m ，w ep r o v e di ti san p - c o m p l e t e 【i f 东大学硕士学位论文 p r o b l e m ，a n dp r o p o s e dan e ws o l u t i o nu s i n gp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a l g o r i s m p s oi san e w k i n do fs w a r mi n t e l l i g e n c ea l g o r i s m t h eb a s i ci d e ao fp s oi s f r o mt h ei n f o r m a t i o ns h a r i n ga n di n f l u e n c eb e t w e e ni n d i v i d u a l sd u r i n gt h ef o o d h u n t i n ga c t i v i t i e so ft h eb i r df l o c k t h ei t e r a t i v ep r o c e s so ft h ea l g o r i s md e m o n s t r a t e s t h ec o n n e c t i o nb e t w e e no p t i m i z a t i o np r o c e s so ft h et e a ma n dt h ee x p e r i e n c e e x c h a n g i n gp r o c e s s a tt h eb e g i n n i n g ，p s oa l g o r i s mi sm a i n l yu s e di nt h es o l v i n go ft h en o n l i n e a r f u n c t i o n s t h ep s oa l g o r i s mc a n n o ts o l v ec o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m sl i k e d d c m s t d i r e c t l y b a s e do nt h eb a s i ci d e ao f p s oa l g o r i s m ，w ec h a n g e dt h es t a n d a r d p s oa l g o r i s m , i n c l u d i n gt h eg e n e r a t i o no ft h er a n d o ms o l u t i o n s ，t h er e f r e s ho ft h e s p e e dv e c t o r , t h et r a n s f o r m a t i o no ft h es p a n n i n gt r e ea n dt h ec i r c l et r u n c a t i o na n ds o o n ，s u c c e s s f u l l ys o l v e dd d c m s tp r o b l e mu s i n gp s oa l g o r i s ma n dt h e nc o n c l u d e da n o v e la p p l i c a t i o nl a y e rm u l t i c a s tr o u t i n ga l g o r i s m t h i s a l g o r i s mi n h e r i t e dt h e a d v a n t a g e so fp s oa l g o r i s mw h i c hh a sg o o ds c a l a b i l i t ya n df a s tc o n v e r g e n c e i ti s v e r yg o o da ts o l v i n gl a r g es c a l em u l t i c a s tr o u t i n gp r o b l e m s t h ep s ob a s e da l g o r i s mp r o p o s e di nt h i sp a p e ri sn o to n l yg o o da ts o l v i n g d d c m s t p r o b l e m i tc a nb eu s e di ns o l v i n ga l lk i n d so fc o n s t r a i n e ds p a n n i n gt r e e p r o b l e m s t h eo n l yc h a n g en e e dt om a k ei st oc h a n g et h ef i t n e s sf u n c t i o n sa c c o r d i n g t od i f f e r e n tc o n s t r a i n s b a s e do nt h i si d e a , w ep r o p o s e da n o t h e rt w op s ob a s e d a l g o r i s m sw h i c hr e s p e c t i v e l ys o l v et h ed e g r e e c o n s t r a i n e dm i n i m u ms p a n n i n gt r e e p r o b l e ma n dt h el e a f - c o n s t r a i n e dm i n i m u ms p a n n i n gt r e ep r o b l e m i nt h ee x p e r i m e n t ，w ei m p l e m e n t e dt h es i m u l a t i o np r o g r a mo ft h ea p p l i c a t i o n l a y e rm u l t i c a s ta l g o r i s mp r o p o s e di nt h i sp a p e ra n dt w oo t h e rs t r a t e g i e sb a s e do na n t c o l o n ya n dg e n e r a t i o na l g o r i s ma n dc o m p a r e dt h e m 、i mo u rs t r a t e g y t h ee x p e r i m e n t r e s u l th a ss h o w nt h a t ，t h ea l g o r i s mp r o p o s e di nt h i sp a p e rh a sg o o da d v a n t a g e so n e n d t o e n dd e l a y , s p a n n i n gt r e ec o s t ，n o d ed e g r e ea n dc o n v e r g e n c et i m e e s p e c i a l l y o nl a r g es c a l et o p o l o g y , t h ea d v a n t a g eb e c o m el a r g e r , t h i sh a ss h o w ng o o ds t a b i l i t y a n ds c a l a b i l i t y k e y w o r d s ：m u l t i c a s t ；a l m ；p s o ；s p a n n i n gt r e e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：螂日期：丝! 皇：主：! ? 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：煎导师签名论文作者签名：墅堡竺圣导师签名 日期： 【ii 东大学硕士学位论文 第1 章绪论 1 1 应用层组播的研究意义 自1 9 9 1 年d e e r i n g 博士【1 】提出网络层组播以来，组播技术得到了国内外专家学 者的广泛关注，有关组播的各类研究成果和协议标准层出不穷，组播的性能和稳 定性也得到了相应的提高，技术也日趋完善。然而，十几年过去了，网络层组播 技术并没有像人们预期的那样，在互联网中得到广泛应用，至今仍只是在局部网 络和科研机构中进行小规模的应用或实验。 网络层组播之所以未能大规模普及，根源就在于网络层组播技术仍然存在着 很多问题【2 1 ，使网络服务商们不愿意在网络中部署，这些问题包括： 1 当网络中组播组数据大、分布广时，路由器中组播转发状态数量的膨胀 2 缺乏对组播组创建的统一认证机制、以及对发送者和接收者的认证机制 3 组播成员的加入、退出等管理开销较大 4 缺乏分布式的组播口地址分配机制 5 由于网络层组播具有一对多的数据分发特性，传统的根据流量计费的机 制不再适用，缺乏针对组播的计费模式 6 在网络安全方面，缺乏网络攻击防范、数据完整性支持等 7 针对组播的网络管理技术还有待完善 其中，组播转发状态数膨胀问题，是阻碍网络层组播发展的核心问题。在支 持网络层组播的网络中，路由器要分别为每个组播组维护转发状态，这些转发状 态存储在路由表中。当网络中出现大量的分布范围较广的组播组时，骨干路由器 中的组播转发状态的数量就会急剧膨胀，由于路由器在进行路由分发时需要根据 数据包的目的地址在路由表中搜寻相应的转发状态，因而当转发状态数量过多 时，路由器的转发效率会急剧降低，进而导致路由器负载过重、网络拥塞甚至瘫 痪。针对网络层组播的转发状态数膨胀问题，学者们提出过各种改进的组播方案 【3 1 ，其中有些能够使该问题有所改善，但都不能从根本上解决该问题。 应用层组播正是在这样的背景下诞生的，应用层组播的基本思想是保持互联 网原有的简单、不可靠的单播转发模型，而由网络终端系统实现组播的复制转发 山东大学硕士学位论文 功能。应用层组播与网络层组播一样，在功能上都实现了一对多或多对多的数据 分发，但不同的是应用层组播在应用层实现，组播过程无需路由器参与，在网络 层看来，所有的数据仍然是通过单播传送的。 应用层组播与网络层组播在实现机理上的截然不同决定了应用层组播不存 在网络层组播的转发状态数问题。又由于应用层组播的部署无须改造路由器，成 本较低，因而近几年应用层组播在互联网中的应用越来越广泛。其典型应用包括 网络电视、视频点播、视频会议、批量数据下载等等。 然而，随着互联网的迅速发展，网络用户对组播服务质量的要求也在不断提 高，包括更小的端到端延迟、更高的稳定性、更低的负载等等，而这些要求又恰 恰是目前许多应用层组播方案的软肋所在。因而，实现一种稳定的、可扩展的、 能够满足各种服务质量约束的应用层组播方案，成为近年来组播领域的研究热 点。 1 2 相关工作和发展现状 在应用层组播的协议研究方面，早期的研究成果有y c h u 等人提出的 n a r a d a m l 协议，n a r a d a 是一种基于网状转发网络的应用层组播协议，只能够支持 较小数量的组成员；后来s u m a n 等人提出的n i c e | 5 埽u o m n i t 6 1 都是基于树形覆盖 网的组播方案，能够支持大规模的单源组播应用，但对网络拓扑和组成员变化的 响应较慢。其它例如a l m i 【7 】、y o i d t 引、b a y e u x t 9 1 、a l m a 1 0 1 、b t p 1 、o v e r c a s t 1 2 1 、 t b c p t l 3 】、s c a t t e r c a s t t l 4 1 等也都采用了不同的思想方法实现了应用层组播。 纵观这些经典的应用层组播协议方案，不难看出，早期的应用层组播协议方 案大都采用了相对直观的杂凑启发式策略，构建出的转发网络在性能和稳定性上 还具有一定的提升空间，并且有些方案只能在特定的应用背景下部署，限制了它 们的推广和应用。因而，在应用层组播协议中引入各种优化策略，对转发网络的 构建和维护过程进行抽象的算法研究，成为应用层组播研究的热点问题。 一套完整的应用层组播算法方案主要包含两方面内容：问题模型和求解算 法。 ( 1 ) 问题模型。即用什么样的数学模型来对应用层组播问题进行抽象，该模 型应当能较好地反映应用层组播的各项主要性能指标，便于优化和算法 2 山东大学硕+ 学位论文 改进。科学合理的建模方案是应用层组播算法方案的基础。 ( 2 ) 求解算法。即在问题模型已经确定的基础上，用何种算法对该问题进行 求解。求解算法的优劣直接关乎到应用层组播方案的效率和稳定性，好 的应用层组播路由算法，应当能够构造出充分优化的转发网络，满足端 到端延迟、带宽需求、节点负载等多方面的约束，并且对拓扑的动态变 化具备良好的适应性。 应用层组播的问题模型，比较典型的方案有s h e r l i a t l 5 1 等人提出的度约束的最 小直径生成树l h 题( m d d b s t ) 、直径约束的负载均衡生成树问题( b d r b s t ) 、直 径约束的负载比例均衡生成树问题( b d r f b s t ) ，b a o l i uy e 等人提出的度约束的 最小总延迟生成树问题( d c m o l s t ) 1 6 1 以及s h e n g y u a nt s e n g 等人提出的度和延 迟约束的最小生成树问题( d d c m s t ) 1 1 7 1 等等。 用于求解应用层组播问题的算法，除了各种杂凑启发式算法以外，还有许多 运用各种优化算法进行求解的研究成果，其中比较有代表性的有s h e n g y u a n t s e n g 等人采用的遗传算法和蚁群算法【1 8 】，孔令发等人采用的免疫算法、宁 爱兵等人采用的竞争决策算法【2 0 1 ，王德志、余镇危等人采用的多克隆2 1 1 和免疫 克隆算法【2 2 1 等。 1 3 论文的主要工作 本文首先对比了应用层组播与传统网络层组播的异同点，分析了应用层组播 的性能要求和特点，对已有的应用层组播问题模型进行了深入的分析和总结，在 此基础上，结合应用背景的实际需求，本文最终采用了度和延迟约束的最小生成 树问题作为应用层组播的问题模型。 本文对微粒群算法的起源、产生和发展进行了详细的介绍，给出了标准微粒 群算法的形式化描述和算法步骤，综述了微粒群优化算法在其提出后的发展情 况，以及在各领域的应用成果。 本文通过对标准微粒群算法【2 3 1 ( p s o ，p a r t i c l es w a r mo p t i m i z a t i o n ) 进行改造， 将其应用于求解度和延迟约束的最小生成树问题，最终形成一种新的应用层组播 路由算法。 本文提出的算法方案，不仅能够求解度和延迟约束的最小生成树问题，对于 山东大学硕士学位论文 各种带约束的生成树问题，同样可以求解，只需针对不同的约束条件改造适应度 计算函数。基于这一思想，本文以求解度约束的最小生成树和叶节点约束的最小 生成树问题为例，阐述了两种本文算法的衍生算法，为各种带约束的最小生成树 问题的求解提供了新的思路。 最后，本文实现了微粒群优化的应用层组播路由算法的仿真程序，并实现了 s h e n g y u a nt s e n g 等人的基于遗传和蚁群算法的两种应用层组播方案，基于 w a x m a n 模型生成了各种规模和特性的覆盖网拓扑，在这些拓扑上对三种算法进 行了仿真实验，对三种算法各方面的性能如端到端延迟、生成树费用、节点度数、 收敛时间等进行了全面的对比分析，实验结果表明，本文算法有着良好的寻优性 能和稳定性。 1 4 论文的章节安排 第二章中首先对比了应用层组播与网络层组播的基本原理、异同点和它们通 常所采用的问题模型，阐述了生成树问题与s t e i n e r 树问题的区别与联系。然后， 总结了目前应用层组播的各种问题建模方法，深入分析了度和延迟约束的最小生 成树问题的特性特点，并证明其为n p c 问题，对已有的求解该问题及相关问题的 算法方案做了总结分析。 第三章首先阐述了微粒群优化算法的起源和提出过程，概要介绍了微粒群优 化算法的基本原理，进而给出了标准微粒群算法的形式化描述，然后总结了微粒 群算法在提出以后的发展演化的过程及各种改进方案，最后介绍了微粒群算法在 各个领域中的应用。 第四章首先阐述了微粒群算法求解度和延迟约束的最小生成树问题的主要 障碍和可能的解决办法，进而给出了基于微粒群优化的度和延迟约束的最小生成 树算法的详细步骤和求解过程，对其中的关键步骤，如随机树生成、速度更新、 适应度计算、生成树的变换和消环等过程给出了详细描述及计算公式。最后，通 过对该算法方案的适应度计算函数的改造，提出了两种基于微粒群的分别用于求 解度约束最小生成树问题和叶节点约束最小生成树问题的算法。 第五章对本文提出基于微粒群优化的应用层组播方案做了仿真实验，实现了 另外两种基于遗传和蚁群算法的应用层组播方案的仿真程序，将三种方案在生成 4 山东大学硕士学位论文 树总费用、端到端延迟、节点度数、收敛时间等各方面性能进行了深入的对比分 析。 第六章为总结与展望，对本文的研究内容做出总结，并对微粒群算法和应用 层组播未来的进一步发展应用做出展望。 山东大学硕士学位论文 第2 章应用层组播的问题建模 2 1 应用层和网络层组播的比较 本节将首先介绍应用层组播和网络层组播的基本原理和实现机制，对应用层 组播和网络层组播在各方面的主要区别加以总结。然后对比了网络层组播研究中 常见的s t e i n e r 树模型和应用层组播的生成树模型，分析了它们各自的特点和采用 的依据。 2 1 1 应用层和网络层组播的基本原理 图2 1 中分别显示了应用层组播与网络层组播的实现机制。 a i pm u l t i c a s t b a p p l i c a t i o nl a y e rm u l t i c a s t 图2 1 应用层组播与网络层组播 图2 1 一a 中演示了网络层组播的工作过程，数据包由a 节点发出后，由路由器 进行复制转发，传送至b 、c 、d 节点，数据包在每条链路上只出现一次，目的节 点只负责接收；图2 1 b 中演示了应用层组播的工作过程，节点a 通过单播将数据 包发送给b 、d 两个节点，其中b 节点又将数据通过单播发送给c ，在一条链路上， 同样内容的数据包可能会出现多次，但路由器只负责发送单播数据包，并不参与 组播过程，因而无需维护组播转发状态，从根本上避免了网络层组播的转发状态 数膨胀问题。 6 山东大学硕士学位论文 2 1 2 应用层组播与网络层组播的主要区别 ( 1 ) 网络层组播依靠路由器实现组播转发，而应用层组播则依靠终端节点实 现组播转发，路由器不参与组播过程。 ( 2 ) 应用层组播不存在网络层组播的转发状态数问题，更有利于在规模大、 分布广的应用中部署。 ( 3 ) 应用层组播依靠终端实现转发，会加重终端节点负担，而网络层组播中 终端节点只负责接收数据，负担较小。 ( 4 ) 由于终端节点的转发能力和稳定性通常低于路由器，因而应用层组播转 发网络的稳定性受终端节点的影响较大。 ( 5 ) 应用层组播中，同一数据包可能在同一链路上传送多次，因而网络资源 的利用效率与网络层组播相比较低。 ( 6 ) 应用层组播通过终端转发数据，在很大程度上延长了数据传输路径，与 网络层组播相比，增加了端到端延迟。 ( 7 ) 由于应用层组播的数据转发是经由单播发送的，因而要为每个转发目的 节点单独发送一次数据，所每个转发节点能够支持的下级节点的数量要 受该节点的网络带宽和节点转发能力的限制。 ( 8 ) 应用层组播的部署成本较低，只需终端用户安装应用层组播客户端即可， 而网络层组播协议的部署则需要升级甚至更换路由器，部署周期长，成 本高。 ( 9 ) 应用层组播的流量都是单播流量，不会对原有按流量计费的业务造成影 响。而要在网络层组播中实现按流量计费则较为困难，因为无论最终有 多少组成员接收到源节点发送的数据，在骨干路由器中，同一数据只产 生一次流量。 ( 1 0 ) 应用层组播的网络管理通常具备较高的灵活性，而网络层组播囿于网络 设备的局限性，其地址分配、组成员认证、组播组创建、安全控制等机 制的发展较为缓慢。 ( 1 1 ) 应用层组播的部署应用主要取决于终端用户，而网络层组播的部署则主 要取决于网络运营商。 7 ii i 东大学硕十学位论文 2 1 3 网络层组播的问题模型 在网络层组播的算法研究中，曾出现过多种问题模型，如最短路径树( s h o r t e s t p a t ht r e e ，s p t ) 、有核树( c o r eb a s e dt r e e ，c b t ) 、s t e i n e r 树2 4 】【2 5 1 等，其q bs t e i n e r 树是被广泛承认的网络层组播模型，这里对s t e i n e r 树做简要介绍。 设无向图g = 形习，其中哟节点集，e 为边集，设每条边e e 都有相应的费 用值c o s t ( e ) 与之对应，节点集矿y 为指定连接的节点集，贝j j s t e i n e r 树堤一种连 接矿中所有节点，且总费用最小的树，砷可以包含指定节点集y7 以外的节点， 这些节点称为s t e i n e r 节点。图2 2 显示了一个s t e i n e r 树的例子。 图2 2 同一拓扑环境中的两个s t e i n e r 树 图中灰色中节点l 、6 、7 、8 为指定连接的节点，每条边上标注的数字为该边 的费用。在该拓扑中，粗实线及其连接的节点构成的是一个s t e i n e r 树，它连接了 所有的指定节点，且总费用最小。树中包含了两个s t e i n e r 节r 点：节点3 和节点4 。 网络层组播问题，就是要在网络层拓扑中构造s t e i n e r 树作为转发网络，s t e i n e r 树中的指定节点对应组成员节点所连接的路由器。组成员节点所连接的路由器必 须纳入组播树中，才能与其他组成员通信；而其它路由器可能位于组播树中，充 当s t e i n e r 节点( 如图2 2 中的3 ，4 节点) ，也可能不在组播树中( 如图2 2 中的2 、 5 节点) 。s t e i n e r 树的定义和性质很好地反映了网络层组播的应用背景，在网络 8 山东大学硕士学位论文 层组播研究中，各种带约束的s t e i n e r 树问题模型被广泛采用。 2 1 4 应用层组播的问题模型 应用层拓扑与网络层不同，应用层拓扑由终端节点及它们之间的逻辑连接构 成，即所谓的覆盖网( o v e r l a yn e t w o r k ) 拓扑。 覆盖网拓扑中不包含路由器，在应用层组播的应用背景中，路由器不参与组 播过程，所有的数据都经由单播发送，数据的存储转发都在终端节点中进行。而 终端节点与路由器不同，路由器是互联网中的共享资源，网络中任何用户的数据 都可能经由某个路由器转发；而终端节点则是用户的私有资源，一个应用层组播 组的转发负载只能由组内成员节点负担，非组成员节点不会也没有义务参与该组 的转发过程。 因而，应用层组播的覆盖网中无需考虑也不能包含非组成员节点，即覆盖网 中的所有节点均为组成员节点，所以要在覆盖网中构造转发网络，连接所有组成 员节点，就等同于在覆盖网中构造连接所有节点的生成树。所以，应用层组播问 题通常被抽象为生成树问题。 生成树问题与s t e i n e r 树问题的主要区别在于，生成树必须连接图中所有节点； 而s t e i n e r 树不必连接所有节点，只须连接指定节点，同时树中可以包含非指定节 点。可以说，生成树问题是s t e i n e r 树问题的一种特例，若将图中所有节点都标记 为指定节点，则s t e i n e r 树问题就等同于生成树问题。 2 2 应用层组播的性能指标 一套科学合理的应用层组播的问题建模方案，应当体现出应用层组播的各方 面性能和特点，而评价应用层组播方案的性能通常采用以下这些指标： ( 1 ) 端到端延迟，即数据包由源节点传输到接收节点所经过的路由器的跳 数。端到端延迟直接影响了应用层组播的转发质量，用户所能容忍的端 到端延迟通常是有限的。 ( 2 ) 节点负载，即组播组中每个终端节点所承担的转发任务的多少，通常用 节点所负责转发的下级节点的个数来衡量。应用层覆盖网中的节点都是 用户的网络终端，其转发能力往往有限，其负载如果过重，会导致转发 9 i i f 东大学硕士学位论文 效率低下甚至节点瘫痪。 ( 3 ) 节点带宽要求，即组播组中的每个终端节点要完成其转发任务，所需要 的带宽最小值。在源节点发送数据的速率一定的情况下，节点带宽要求 与该节点负责转发的下级节点个数成正比。 ( 4 ) 链路强度( s t r e s s ) ，即每条链路在传输组播分组时发送相同分组的次数。 链路强度体现了应用层组播对网络资源的利用效率。 ( 5 ) 伸展度( s t r e t c h ) ，即应用层组播转发网络中自源节点到最终接收节点的 转发路径距离与两者之间的直接单播路径距离的比值，这里所指的距离 通常由路由器跳数来衡量。 ( 6 ) 控制信息负载，转发网络中的每个节点都要和其它节点交换控制信息， 这些信息包括节点的加入退出、链路状态的变化等等。控制信息过重会 影响正常数据的转发而降低组播效率。 在以上列出的性能指标中，链路强度、伸展度和控制信息负载这三个指标主 要体现了应用层组播相对于单播和网络层组播对网络造成的额外负担，是网络服 务商们关注的焦点。然而，应用层组播的使用者终端用户对链路强度、伸展 度和控制信息负载可能并不是十分关心。 应用层组播的部署应用与网络层组播不同，网络层组播主要依靠网络服务商 提供支持，如路由器的改造升级、新的计费模式等等，而应用层组播的部署决定 权则掌握在终端用户手中，通常只需终端用户安装相应的组播客户端。因而，在 许多应用层组播方案设计中，链路强度、伸展度和控制信息负载等往往并不是关 键的性能指标。 从终端用户的角度看，他们更多关注的是端到端延迟、节点负载和节点带宽 要求等直接影响用户体验的性能指标。在源节点的数据发送速率固定的前提下， 节点负载和节点带宽要求与节点所负责转发的下级节点个数成正比例，而在树形 转发网络中，某一节点的下级节点数就等于该节点度数减1 。因而，端到端延迟 和节点度数，往往成为终端用户关注的应用层组播的关键性能指标，体现在算法 模型中，就是延迟约束和度约束，这也是本文采用度和延迟约束的最小生成树算 法的主要原因之一。 1 0 l l i 东大学硕士学位论文 2 3 应用层组播的建模方案 将应用层组播抽象为带约束的生成树问题是十分合理的，这种建模方案也得 到了国内外学者的普通认同，其中比较有代表性的方案有： ( 1 ) s s h i 等人1 5 1 提出的度约束的最小直径生成树( m i n i m 哪d i a m e t e r , d e g r e e b o u n d e ds p a n n i n gt r e e ，m d d b s t ) 。 ( 2 ) s s h i 等人1 5 1 提出的直径约束的负载均衡生成树( b o u n d e dd i a m e t e r , r e s i d u a l - b a l a n c e ds p a n n i n gt r e e ，b d r b s t ) 。 ( 3 ) s s h i 等人 1 5 1 提出的直径约束的负载比例均衡生成树( b o u n d e dd i a m e t e r ， r e s i d u a lf r a c t i o n b a l a n c e ds p a n n i n gt r e e ，b d r f b s t ) 。 ( 4 ) b a o l i uy e 等人1 6 1 提出的度约束的最小总延迟生成树( d e g r e e c o n s t r m n e d m i n i m u mo v e r a l ll a t e n c ys p a n n i n gt r e e ，d c m o l s t ) 。 ( 5 ) m o j t a b ah o s s e i n i 等人2 6 1 提出的出度约束的最小直径多源路由问题模型 ( m i n i m u md i a m e t e rm u l t i - s o u r c eo u t d e g r e e - c o n s 仃m n e dr o u t i