（计算机系统结构专业论文）基于组播转发状态的聚合模型研究与算法分析.pdf

【li 东大学硕士学位论文 摘要 p 组播在口网络中实现了多点通信模型，促进了视频点播、音视频会议和 数据分发等多点通信业务在互联网上的发展。同时，新兴的i p v 6 技术更增强了 对组播的支持；再加上组播技术相对于单播与广播技术的巨大优势，组播技术的 应用越来越广泛，网络应用的要求也越来越强烈，人们日益认识到组播技术所带 来的优点与好处，其研究价值也越来越凸现出来。 组播采用树型转发结构实现单点对多点通信的支持，每一个数据包只在分叉 节点处被复制，每一条链路只转发一次。这种方法使得i p 组播能有效的同时向 多个组成员发送数据，并且能够同时支持多个组播组。i p 组播这种多点通信机 制使之成为互联网中视频会议等高带宽、共享性应用的重要基础。 然而，组播共享树要求所有树上节点处的路由器均保持每一个组的转发状 态。因此，当多个组播组并存时，i p 组播遇到一系列问题：路由器的转发状态 数会随网络中的组播组数量线性增长，不但增加了路由器额外的存储和c p u 处理 开销，而且导致了更加缓慢的转发过程，当组播会话数很多时，会耗费大量的资 源和控制开销来管理组播组，制约了组播会话的可扩展性。也就是说，组播转发 状态问题成为影响i p 组播大规模扩展应用的一个瓶颈。 组播聚合模型是针对大规模组播扩展性问题，结合当前网络拓扑特点提出来 的新思想，最早由u c l a 网络实验室提出，并给出了基于该种模型的贪婪算法。 其主要思想是：适当牺牲带宽，使能够复合的组播组共享一棵组播分发树，通过 这种方式，网络中组播树的数目会大大减少，组播转发状态也随之减少，最终提 高了网络性能。 本文在对传统组播聚合模型深入研究的基础上，提出了优化组播转发状态问 题的两个方案：基于叠加树算法的优化方案和基于遗传模拟退火算法的优化方 案。 1 基于叠加树的聚合算法借鉴了图论中“相似”的概念，将符合特定q o s 要 求的原始组播树进行叠加合并，然后按照树的定义对叠加树进行剪枝，去环等操 作以获取聚合树集合。 山东大学硕士学位论文 仿真实验表明，叠加树算法在时间、聚合度及转发状态降低率方面均优于传 统的贪婪聚合算法。 2 基于遗传模拟算法的优化方案中，模拟退火算法在理论上，经过足够长 的时间会收敛到全局最优解；而遗传思想强调的是两代之间的进化关系，但其 交配有可能使最优解遗失而陷入局部最优解；由此，本文给出了遗传模拟退火 算法的设计方案。 组播聚合问题的数学本质是最小集合覆盖问题( m s c p ) ，这是一个n p c 问题。本 文将遗传模拟退火算法应用到求解m s c p ，进而对组播聚合问题寻优，最终获得近 似于全局最优的准最优解。 仿真实验通过与贪婪算法、拉格朗日松弛算法进行比较来表明该算法在优化 聚合度、转发状态降低率两个方面的优势。 关键词：转发状态；组播聚合；聚合度；叠加；最小集合覆盖；遗传： 模拟退火 i i 山东大学硕十学位论文 a b s t r a c t i pm u l t i c a s ti sa l le f f i c i e n tm u l f i p o i n t t o m u l t i p o i n td e l i v e r ym e c h a n i s mi ni p n e t w o r k ，a n da c c e l e r a t e st h ed e v e l o p m e n to fm u l t i p o i n tc o m m u n i c a t i o n ss e r v i c e s s u c ha sv i d e eo nd e m a n d v i d e e a u d i oc o n f e r e n c e sa n dd a t ad i s t r i b u t i o n 、枷l i e 6s t r e n g t h e ni t ss u p p o r to nm u l t i c a s ta n dm u l t i c a s tt e c h g e t sal a r g ea d v a n t a g e o v e ru n i c a s ta n db r o a d c a s t r e c e n t l y ,m u l t i c a s ti su s e dm o r ea n dm o r ew i d e l y , t h ed e m a n do fn e t w o r ki sm o r ea n dm o r ei n t e n s e ，a n dt h eh u g es u p e r i o r i t yo f m u l t i c a s tc o m p a r e 、析mu n i c a s to rb r o a d c a s t , p e o p l eb e g i nr e a l i z et h ea d v a n t a g e a n db e n e f i to fm u l t i c a s t h o w e v e rl,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 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 h i c a s tg r o u p si n t h en 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 g s t a t e so b v i o u s l yi n c r e a s e sw i t ht 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 g g r o w t ho 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 ya n dc p up r o c e s so f t h er o u t e r ，a 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 i t w i l lc o s tm u c hr e s o u r c ea n d c o n t r o ls p e n d i n go nt h eg r o u p s m a n a g e m e n to fm u l t i c a s t , i no t h e rw o r d s ，t h es t a t e s c a l a b i l l t yp r o b l e mh a sr 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 li 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 d m u l t i c a s th 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 s f i r s tp r o p o s e db yt h eu c l an e t w o r kl a b o r a t o r y , a n di t sf o l l o w e dw i t ht h eg r e e d y a l g o r i t h m i t sm a i ni d e ai st ob 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 hp r o p e r l y , 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 os 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 i nt h i s w a y , t h en u m b e ro fm u l t i c a s tt r e e si sd e c r e a s e dd e e p l y , a n da c c o r d i n g l yt h e f o r w a r d i n gs t a t e so fm u l t i c a s ti sd e c r e a s e d , a n df i n a l l yt h ep e r f o r m a n c eo f n e t w o r ki s i m p r o v e d i nt h i sp a p e r , t w od i f f e r e n ta l g o r i t h m sa r ep r o p o s e dt os o l v et h ef o r w a r d i n g s t a t e sp r o b l e mo fm u l t i c a s ta f t e ra c h i e v i n ge x t e n s i v ea n di n t e n s i v er e s e a r c ho nt h e a r e ao ft r a d i t i o n a la g g r e g a t e dm o d e lo fm u l t i c a s t ：as c h e m eb a s e d - o nt r e e s u p e r p o s e da l g o r i t h ma n das c h e m eb a s e d o ng e n e t i ca l g o r i t h m 1 t h et r e es u p e r p o s e da l g o r i t h mb o r r o w si d e af r o mt h ec o n e 印to f ”s i m i l a r ”o fg r a p ht h e o r y m a k i n go r i g i n a lm u l t i c a s tt r e e ss u p e r p o s e da c c o r d i n g g i v e ns p e c i a ld e m a n d so fq o s ，a n dt h e np r u n i n ga n dc u t t i n gr i n g sa n d t h el i k eb yt h e d e f i n i t i o no ft r e e ，a n df i n a l l yg e tt h es e to fa g g r e g a t e dm u l t i c a s t t h er e s u l t so fs i m u l a t i o ni n d i c a t et h a tt h es u p e r p o s e dt r e ea l g o r i t h m sa r e s u p e r i o rt ot 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 mo nt h et i m ep e r f o r m a n c e ，a g g r e g a t e d d e g r e ea n df o r w a r d i n gs t a t er e d u c i n g 2 i ns c h e m e sb a s e do ng e n e t i ca l g o r i t h ma n ds i m u la t e da n n e a l i n g a l g o r i t h m 。s i m u l a t i n ga n n e a l i n g a l g o r i t h mc a ng e tt h eh y p o - g l o b a lo p t i m a ls o l u t i o n b ye n o u g ht i m e ，w h i l eg e n e r i ci d e ae m p h a s i z e so nt h ee v o l u t i o nr e l a t i o n sb e t w e e n t w op o p u l a t i o n s ，b u tt h em a t i n go p e r a t i o nm a yl o s tt h eb e s ts o l u t i o n t h e r e f o r e ，i n i i i 山东大学硕十学位论文 t h i sp a p e r , w ep r o v i d ea na p p r o a c hb a s e do ng e n e t i ca n ds i m u l a t e da n n e a l i n g a l g o r i t h m t h er e s u l t so fs i m u l a t i o ni n d i c a t et h a tt h es u p e r i o rp e r f o r m a n c eo fg e n e t i c a l g o r i t h m b yc o m p a r i n gt ot h eg r e e d ya l g o r i t h ma n dl a g r a n g ea l g o r i t h m , t h e g e n e t i ca l g o r i t h mg e tb e t t e rr e s u l t so nt h ea s p e c to fb o t ha g g r e g a t e dd e g r e ea n d f o r w a r d i n gs t a t e sr e d u c i n g k e y w o r d ：f o r w a r d i n gs t a t e ；a g g r e g a t e dm u l t i c a s t ；a g g r e g a t e d d e g r e e ； s u p e r p o s e ；m s c p ；g e n e t i c ；s i m u l a t e da n n e a l i n g i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：垂鱼塑 日期：! ! 皇：! 兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：龟垒至錾 导师签名：日期：7 上也 山东大学硕士学位论文 1 1 引言 第一章绪论 自2 0 世纪8 0 年代末期d e e r i n g 博士建立i p 组播模型1 以来，研究人员对 i p 组播路由协议进行了广泛的研究，提出来多种i p 组播路由协议。这些组播路 由协议尽管在设计原理和实现机制方面有所不同，但都能有效支持点到多点或多 点之间的通信业务。 然而，尽管如此，经过2 0 年的组播理论研究和工程实践，i p 组播仍然没有 在i n t e r n e t 中广泛使用，其中一个重要原因是组播转发状态的可伸缩性比较差， 网络节点必须为经过它的每个组播组存储转发状态，才能将组播组的数据有效地 传送到组播接收者。由于i p 组播在设计时，考虑了对接收者动态加入和离开组 播组的支持，因此组播地址不像单播地址那样与网络拓扑位置紧密相关，这导致 在单播路由中可以有效减少路由表项的基于网络前缀的聚集方法无法应用到组 播转发表中。 组播转发状态问题在一定程度上阻碍了组播应用的扩展。在组播转发过程 中，一个组播地址对应着一个组播组，当同时存在多个组播组时，组播树便需要 所有转发的树节点记录并保持每一个组播组的转发状态，而这些转发状态会随着 组播组个数的增加而线性增加。网络上并发执行的组播组数量越多，转发节点( 即 路由器) 上保持的转发状态也会越来越多，而骨干网络中由于并发执行的组播会 话通常很多，尤为突出。这些不断增加的转发条目使得路由器的内存需求增大； 同时，由于每个分组的转发查询操作，转发效率也会有所降低。因此，当网络中 的组播会话数数以万计时，便需要耗费大量的存储和控制开销来管理组播组；而 当前路由器的存储器与c p u 资源却很难以满足这个要求。这便形成了目前组播 技术面i 临的转发状态问题。组播的转发状态问题降低了组播的网络性能，解决组 播转发状态问题能够对组播技术的大规模扩展部署起到重要的积极作用。 1 2 国内外的研究现状 近年来，国内外有关组播转发状态扩展性方面的研究取得了一定的成果，并 【ii 东大学硕士学位论文 且已经提出了一些有效的减少组播转发状态的方案。主要有两种方案2 1 可以降低 网络中组播的转发状态：组内压缩方案和组间聚集方案。 1 2 1 组内压缩方案 组内压缩的主要思想是根据稀疏模式下组播的特点，消除组播树上非分枝路 由器上存储的组播转发表项【3 】。已有的组内压缩方案多是基于稀疏模式组播。当 组播业务在i n t e m e t 上广泛应用时，路由器所维护的转发状态将成为制约组播应 用的重要因素。但是尽管组播组的数量很大，大多数组播组是稀疏模式的组播。 当组成员稀疏地分布在网络中时，组播树将包含一些较长的非分枝路径。组内压 缩方案基木思想是只有充当组播树上分枝节点的路由器才维护组播转发状态。其 主要优点是非分枝路由器无须维护和存储组播转发状态，这样便可以大大减少网 络中总的组播转发状态。 以t i a n 和n e u f e l f 4 】为代表提出了在组播分布树的非分枝路径上建立动态单 播通道的方案来减少转发状态，从而使得组播转发状态在非分叉路由器上被消 除。然而，这种方案需要设计复杂的方法来辨别非分叉路由器，更重要的是，这 种方案只能应用于稀疏网络中，因而局限性较大。虽然不需要路由器维护组播转 发状态，但是转移组播状态本身就需要路由器来处理，增加了额外的开销，因而 并没有达到预期效果。 1 2 2 组间聚合方案 组间聚集方案决定着组播转发状态聚集的最终部署，目前的组播组间的聚合 主要有两种：基于路由器的组间聚集和基于共享树的组间聚合方案。 基于路由器的组间聚集方案的基本思想是，在处理组播请求时，路由器对具 有相同的网络前缀或者具有相同的端口列表的转发表项进行聚集整合，如文献【5 】 提出的一种方案，在遵循一定带宽浪费约束的前提下，对具有相同的部分网络前 缀，同时允许端口列表不完全相同的组播请求进行基于地址的聚合。然而，在组 播转发过程中，仅考虑路由器本身的组播转发表项往往具有局限性，因为具有相 同的网络地址前缀或者出口列表的表项个数一般很少；并且，组播地址往往并没 有是与网络拓扑中的实际点的位置相对应，因而这种基于路由器的的组间聚集方 2 f ii 东大学硕十学位论文 案优化效果并不显著，有一定的局限性。 基于共享树的聚集思想最早由u c l a ( 加利福尼亚大学洛杉矶分校) 网络研 究实验室的j u n h o n gc u i t 6 8 】等人提出的，并给出了基于贪婪机制的组树匹配算 法。它的基本思想是使多个具有相似结构的组播转发树聚合成一棵组播聚合树， 让实现多个组在满足带宽浪费约束的前提下，对同一棵组播转发树的共享。基于 贪婪机制的组树匹配算法是一种局部优化算法，较容易实现，但容易陷入局部 最优解，最终导致聚集的效果并不理想，如何设计好的启发式算法来优化组树 匹配问题便成了组间聚集技术的关键。 基于共享树的组间聚集方案的核心部分是组树匹配算法，即如何将多个组 映射到一个树上，同时组与树之间建立良好的对应关系，其实现过程大致如下： ( 1 ) 根据聚集方案中的算法为网络中当前的组播组及动态加入、离开的组播组 计算他们的组播树； ( 2 ) 如果新加入的组播组所在的树结构包含于已有的组播树中，则在带宽浪费 允许的范围内，可以直接采用已有的树结构进行转发：否则，如果网络中 当前的组播树集中没有适合新组播组转发的树结构，则利用扩展树模型寻 找新的组播树结构，使其覆盖新的组播组。 ( 3 ) 在存在多个能够覆盖当前组播组的情形下，要选择带宽浪费最小的组播候 选树，也即代价最低的组播树；如果在经过原始树扩展的候选树集合中仍 没有找到适合的候选树，则将该组播组的原始树加入最终树集合中即可。 1 3 主要研究内容与目标 使新一代i n t e r n e t 网络能够提供高效的组播服务是目前计算机网络组播研 究的主要课题，也是正在过渡中的i p v 6 网络对组播提出的要求。研究基于组播转 发状态的聚合模型及路由算法，对实时多媒体组播应用的发展具有重要的意义。 本课题的主要研究目标是通过组播状态聚集相关技术提高组播转发状态的效率， 以此来提高网络性能。本文的主要研究内容包括： ( 1 ) 对基于贪婪思想的组播聚合模型做作深入分析，主要包括聚合的建树模型 与选树模型两部分； ( 2 ) 提出了基于叠加树的组播聚合优化方案。该方案以原始组播树间的相似程 山东大学硕士学1 奇：论文 度为基准，进行两树的合并叠加操作，然后通过一系列的剪枝、去环路等 操作完善聚合树集； ( 3 ) 提出了基于遗传模拟退火算法的组播聚合优化方案。该方案将遗传模拟退 火算法综合应用到求解集合覆盖问题，通过种群与退火温度初始化、编码 与解码、设计适应函数与邻域解、退火、交配与变异、补偿等一系列优化 操作，最终完成寻求近似全局最优解的目的。 1 4 论文的组织结构 论文的后续部分共分为五章： 第二章对组播技术的相关概念作了介绍，包括组播功能的实现方式、组播的 分类，以及目前比较常见的组播路由算法与路由协议。 第三章对组播聚合的模型及相关概念进行了介绍；同时，对聚合模型做了简 要的q o s 参数分析，重点分析了基本的贪婪聚合算法，为后面新算法及仿真实验 的论述做好铺垫。 第四章首先对叠加思想进行了简单描述，分析了已有的聚合算法的不足之 处；然后详细描述了基于叠加树算法求解聚合问题的一般步骤，通过仿真试验与 贪婪算法进行，并进行了结果分析。 第五章介绍了遗传模拟退火算法的特点，提出了组树匹配算法的本质一 m s c p ( m i n i m a ls e tc o v e rp r o b l e m ) ，描述了综合应用两种算法的优势求解最小集 合覆盖问题，并应用到求解组播聚合的一般步骤，最后将遗传模拟退火算法与贪 婪算法进行仿真试验比较，并给出结果分析。 最后一章对全文的工作进行总结并对下一步研究工作做了展望 4 山东大学硕士学位论文 第二章组播 随着网络技术的飞速发展，在i n t e r n e t 上产生了许多需要单点到多点和多 点到多点的应用，例如，网络视频会议、网络音频视频广播、多媒体远程教育、 远程会诊业务。这些业务的出现带来了带宽的急剧消耗和网络拥塞等问题。采用 单播技术构建的传统网络已经无法满足新兴网络应用在q o s ( 服务质量) 方面的 要求。为了缓解网络瓶颈，人们提出了多种解决方案：增加网络带宽、运用q o s 机制、控制特定业务的带宽使用、服务器的分散与集群、减轻主干网的瓶颈、采 用i p 组播技术等。在所有这些方案中，i p 组播以其“一点传送多点接收， 即使用户数成倍增加，主干网络带宽也不需要随之增加这特性成为一枝独秀。 2 1 组播概述 所谓组播，一般指的是一个源节点向多个目的节点发送信息的通信方式。目 前，实现组播功能主要有下述三种方式西3 ： ( 1 )由源节点向各用户单独发送同样的消息，这种方式以单播为基础，因此每 次会话需要产生与用户数量相等的分组，当用户数量较少时，基本可以满 足要求； ( 2 ) 每个分组含有一个目的节点列表，当分组到达路由器时，路由器检查所有 的目的节点，以确定将要用到的输出链路集合；路由器为所使用的每条输 出线路复制一个新分组，每个分组中仅含有使用此线路的那些目的节点。 这种路由方式使得若干分组必须经过同一路由，其中一个分组负担全部费 用，而其它的分组不必承担费用； ( 3 ) 建立组播树，由源节点向树中的邻居节点发送消息，然后，这些相邻节点 继续向树中下一级节点转发这些消息。这样便大大减少了源节点发送的消 息量，防止了网络和链路的阻塞。 山东大学硕士学位论文 2 2 组播分类 e n dh o s t ( 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 r m u l f i c a s t 图2 - 2i p 组播和应用层组播示意图 根据组播方案具体实施的网络层次，组播可分为网络层邛组播和应用层组 播两种方式。( 如图2 2 ) 2 2 1lp 组播概述 i p 组播体系结构由d e e r i n g n 们首先提出的，i p 组播中的组播功能在网络层 实现的。在i p 组播中网络中的路由器采用分布式算法构造一棵分组转发树，当 组播分组沿着转发树进行转发时，分组会在树的分支节点处，由路由器进行相应 的分组复制。i p 组播在实现组播分组转发方面效率较高，因为它可以使得全网 范围的分组复制数量最少。 在p 组播中，分组由网络中的路由器进行复制，如图2 3 ( 左) 所示，假设 主机a 要往主机b 、c 和d 发送分组，则分组在路由器r 1 处复制一次，然后在 路由器r 2 处再进行一次复制。 i p 组播模型自提出到现在已有十几年的时间，但i p 组播仍然没有得到广泛 应用，发展仍然比较缓慢，主要存在以下几个原因： ( 1 )i p 组播需要每个路由器维护每个组播组的状态，当组播组数量很大时， 6 山东大学硕士学位论文 每个组播组的状态需要占用路由器大量的内存与c p u 开销，特别是对于流 量很大的核心路由器，大量的转发表和路由表会很大程度上降低路由器的 效率； ( 2 ) 在i p 组播中实现可靠性与拥塞控制比较困难，这些因素都会使服务供应 商i s p 对于在网络中提供组播服务产生疑虑； ( 3 ) 目前尚缺乏针对组播流量的计费模型，由于组播分组在i s p 网络内部需要 进行复制，这就和i s p 现行的根据流量对分组进行计费的模型相矛盾。 p 终端 图路由器分组 图2 - 3i p 组播与应用层组播分组路由方式 2 2 2 应用层组播概述 应用层组播是在i n t c m e t 上提供组播服务的一种新策略。在网络层组播遇 到重重障碍，发展缓慢的时候，研究人员开始重新考虑实现组播功能的最佳层次， 并开始研究应用层组播方案。也就是说在应用层上实现组播功能，即分组复制操 作发生在端系统中，而不是在路由器中实现。在应用层组播中，组成员自组织成 应用层的覆盖网络，并自行建立组播转发拓扑结构，而不需要网络层提供组播支 持；大多数应用层组播协议都可以利用网络层提供的组播支持来获得更好的性 能。 而在应用层组播中，分组在端系统处进行复制。例如图2 3 ( 右) 所示，假 设主机a 要往主机b 、c 和d 发送分组，则分组在端系统即主机a 处复制一次， 分别发送给主机b 、c ，而后在端系统b 处完成一次复制转发给主机d 。 7 山东大学硕士学位论文 由于应用层组播完全在端系统上运行而不需要路由器支持，因此它较容易部 署；但是，由于分组转发规则脱离了网络层，并不考虑网络本身的拓扑结构，因 此，相比p 组播，应用层组播在延迟方面的性能较差；而且，由于分组重复传 送的因素，应用层组播会给网络层增加额外的负担。在应用层组播过程中，端系 统构成了逻辑上的覆盖网络( o v e r l a yn e t w o r k ) ，应用层组播的目标就是为了便 于进行数据传输，构造并维护高效率的覆盖网络。由于应用层组播可能会在同一 条链路上多次发送相同的分组，因此它的效率要低于口组播。 2 3 组播路由算法 组播路由的基本问题是找到一棵代价较低的组播树，在传送组播报文时，按 照需要构造一个连接所有组播组成员的树，根据这棵树，路由器得出转发分组的 一条唯一路径。根据构建组播树方式的不同，可将组播路由算法分为有源树和共 享树两类1 1 1 。 2 3 1 有源树算法 有源树是以组播源为根节点构造到所有组播组成员的生成树，有源树的分支 形成通过网络到达接收主机的分布树。有源树对于每个源都会有一棵组播树，即 如果网络中有n 个可以产生报文的源主机，那么就会有1 1 棵组播树：同时，在组 播表里，会有( 组数x 每组成员数) 个项目条数，这种拓扑较适用于密集模式。 在组播研究的初期，面向的应用主要是单源应用；并且实际中，有源树算法 完全可以用于解决共享树问题，因此形成较多的有源树算法。有源树较多的被用 于解决树约束和树优化问题。 ( 1 ) 树约束是指沿着组播树从源到接收者的路径限制条件，例如端到端的延迟 上界； ( 2 ) 树优化问题是指用树优化函数构造最优组播树。例如，最小化整个组播树 的代价的s t e i n e r 树问题便属于树优化问题，s t e i n e r 树问题是组播路由 中的经典问题，一般情况下s t e i n e r 树问题是n p c n 2 ，1 3 3 ，其本质是求出连 接网络中部分节点( 即组成员) 的最小代价组播树。本文在表2 - 1 中对几 种主要的有源树算法进行举例分析。 l ii 东大学硕+ 学位论文 表2 - 1 有源树算法比较 算法类型算法举例树类型问题类型发起方分布方式 最短路径树d i j k s t r a有源树树约束源节点集中式 算法 最小生成树 p r i m 有源树树优化源节点集中式 算法 s t e i n e r 树 k 船 有源树树优化源节点集中式 算法 2 3 2 共享树算法 有源树虽然能提供从源到每一个组播组成员之间的最短路径，但是如果一个 组播组的成员很多时，路由器需要维护每一个参与组播转发的组成员的状态，转 发条目也将相应变得非常大。并且，为每一个组的每一个源都计算其有源树也将 给路由器带来巨大的开销。 共享树，也称为核心树，最早出现在文献n 4 3 中，共享树是以组播网络中某些 可选择的一个组播路由器作为公共根的组播树，该路由器被称为汇聚点即r p ( r e n d e z v o u sp o i n t ) 。由此节点生成包含所有组成员的树，所有组播报文都需 要从这个点来进行传送，所以它没有( s ，g ) 项，只有( 木，g ) 项。所有要发送 的组播报文的源主机在发送报文之前，都需要到r p 上进行注册，然后通过直连 的路由器来确定到r p 的最短路径，通过r p 路由器来确定到目的地的最短路径， 即r p 成了组播树的根节点。 共享树的优点是不需要为每个发送方分别建立有源树，而只需建立一次组播 共享树，不论什么时候组成员加入或离开，只需要在现有的共享树上增加或删除 分枝，因此，有很好的灵活性和可扩展性，并且只有树上的路由器才需要维持组 成员信息，在路由器所需存储的状态信息的数量和路由树的总代价两个方面都具 有较好的性能n 引。 共享树的缺点也很明显，它将流量集中到核心路由器上，可能造成共享树上 的网络拥塞，核心路由器处就可能成为瓶颈。另外，共享树算法的转发路由不是 9 山东大学硕十学位论文 最优路由。 2 4 组播路由协议 组播技术要想真正地投入使用，设计出可扩展的、可部署的并且高效的组播 路由协议是问题的关键。可扩展性指的是路由器所需的开销只同组播组的规模和 网络规模成线性关系；可部署是指在现有网络中部署组播功能而不需要升级所有 的主机和路由器；最后，高效性是指路由器维护组播组状态及控制方面的开销等 必须在合理的范围内。 根据协议在域内或域间的适用情况，组播路由协议可分为域内组播路由协 议和域间组播路由协议两类。 m q s 、 、r i m o 源节点( 组成员 汇聚点 q 源节点o 自i 成! | j e 核心路由 a ) p i m s m ( b ) c b t 图2 4p i m - s m 与c b t 示意图 2 4 1 域内组播路由协议 国际上较常见的域内组播路由协议有d v m r p 1 6 】( 距离向量组播路由协议) 、 m o s p f t l 7 】( 基于组播的开放式最短路径优先) 、c b t ( 核心树) 、p i m d m ( 密集 模式洗衣无关组播协议) p i m s m ( 稀疏模式协议无关组播协议) 以及m i p ( 因 特网组播树协议) 。在众多的域内组播路由协议中，目前应用最多的是p i m s m ( p r o t o c o li n d e p e n d e n tm u t i c a s t d e n s em o d e ) 【1 8 】和c b t ( c o r eb a s e t dt r e e ) 【1 9 】。 下面，我们对p i m s m 与c b t 进行简单的对比介绍： 1 0 r 、 、 一 、 s、 q 山东大学硕十学位论文 ( 1 ) p i m s m 如图2 4 ( a ) 所示，所有组成员节点通过向汇聚点r p 发送j o i l l 消息申请加入组播组；源节点s 无须知道各个组成员的地址，s 只需将分 组单播发送至r p ，然后由r p 将分组通过组播树转发给各个组成员。同 时p i m s m 具有一个比较独特的特性，即当源节点的发送速率超过某个特 定的阈值时，可以使用源根树来代替r p 共享树。 ( 2 ) c b t 如图2 4 ( b ) 所示，与p i m s m 相比，源节点无须将分组发送到指 定的r p ，s 只需将分组发送至由c o r e 构建的组播共享树的分支即可：而 且在c b t 中，组播树是双向的，因此所有分组并不是都要通过c o r e 转发， 这一特性可以降低核心节点对数据转发的影响，c o r e 只在新成员加入时 发挥作用，大大减轻了核心路由的负担。 2 4 2 域间组播路由协议 ( 1 ) 初期的组合协议方案 域间组播路由相对域问路由更为复杂，域间组播路由协议是组播最终得到广 泛部署之前需要解决的必要问题。目前域间路由协议的部署的首选方案是 m s d p 2 0 i ( m u l t i c a s ts o u r c ed i s c o v c r yp r o t o c 0 1 ) m b g p 2 1 】( m u l t i p r o t o c o l e x t e n s i o n st ob g p 4 ) p i m s m 三个协议的组合。 1 m s d p ( 组播源探索协议) ：使用t c p 协议，采用f l o o d ( 洪泛) 进行域间对 等体间的通信，其作用是让p i s s m 域中的r p 了解其他域中活动的所有的 组播源： 2 m b g p ( 基于b g p 4 的多协议扩展) 是b g p 4 的扩展，其作用是提供p i m s m 的下一跳信息，并且传送组播路由选择信息。这些选择信息会被用来在a s ( 自治域) 间的逆向路径转发计算，但是并不传送组播组的信息。 3 p i m s m 负责域间组播路由的构建。 ( 2 ) 长期研究的目标 之所以采用上述三种协议的组合，是因为这三种协议是目前正在使用的组播 协议，这种组合在建立有源树的同时，也继承了共享树的缺点，并且他们都有存 在扩展性方面的问题。为此研究人员仍在不断探索更为有效的解决方案。m a s c ( m u l t i c a s ta d d r e s s s e tc l a i m ) b g m p ( b o r d e rg a t e w a ym u l t i c a s tp r o t o c 0 1 ) 被 l i f 东大学硕士学位论文 认为是一个长期的研究目标2 2 1 。 1 b g m p t 2 3 1 ( 组播边界网关协议) ：是一种可以和任何一种域内组播路由协议 协同工作的域间组播路由协议，在域间组播过程中，b g m p 为每一个组播组 建立一个单独的根节点，这个根节点是某个域而不是某个路由器；b g m p 通 过b g p 的路由来为每个组播组构建组播树，并构造连接各个域的组播双向 树。 2 m a s c t 2 4 1 ( 组播地址设定声明协议) ：采用冲突检测的监听和声明机制为域 分配组播地址。在m a s c 中，子域负责监听它们上一级域选择的地址范围， 并从中选择一个子集向自己的邻居域声明，m a s c 使用一种层次地址分配方 式，从而保证单个域可以通过网络加入消息转发到根域。 2 5 本章小结 本章对组播的概念做了较为详细的介绍。首先在第一节，对组播技术做了概 述，并且从功能上来介绍了组播功能目前的实现方式；在第二节，本文从组播实 现的层次的角度介绍目前的组播分类，口组播和应用层组播；最后在第三、四 节从组播路由算法与路由协议的角度介绍了组播技术的现状，主要包括常见组播 路由算法与路由协议。 1 2 山东大学硕士学位论文 第三章组播聚合 3 1 组播转发状态及聚合模型概述 组播转发不但要求路由器对当前的组播分组提供下一跳的路由的功能，而 且，需要路由器维护每个组播组的状态以及组内每个组成员的状态，这些构成了 所谓的组播转发状态的扩展性问题。也就是说组播转发状态的扩展性在一定程度 上制约着组播技术的大规模部署应用。 组i d 与组成员的 刘廊关系： g o ( d 、b 、c ) g i ( f 、b 、c ) g 2 ( d 、b ) 图3 - 1 组播聚合模型示意图 组播聚合模型的提出是为了应对组播过程中膨胀的转发状态，它提供了一 种域内的组播方案。其关键的思想：在骨干网络拓扑中，采用一定的策略强制多 个组播组共享一棵组播聚合树，而不是为每一个组播组分别构建一棵组播原始 树。如图3 一l 所示，域a 是一个i s p 骨干网，其中，a b ，a a 为两个核心路由节点。 域b 、c 、d 、e 、f 是域a 的用户网络。当前网络中的组播会话形成了三个组播 组分别为：g o ( d 、b 、c ) 、g 1 ( f 、b 、c ) 、g 2 ( d 、b ) ，它们各自构建的原始 组播树结构分别为：t o ( a 1 ，a a ，a b ，a 2 ，a 3 ) 、t 1 ( a 1 ，a a ，a b ，a 2 ，a 3 ) 和 t 2 ( a 1 ，a a ，a b ，a 2 ) 。不难发现，该三个组播组的树结构在域a 内均有重叠的 分支；因此，基于相似的骨干分支结构，我们可以考虑让该三个组在域a 内共享 同一树结构，从而减轻核心路由的负担。即建立一棵同时覆节点盖a 1 、a 2 和a 3 l i i 东大学硕士学位论文 的聚合树t a g ( a 1 ，a a ，a b ，a 2 ，a 3 ) ，这棵树称为聚合组播树，可以为三个组 播组所共享。这样，核心路由器a a 、a b 只需保存聚合组播树t 的状态，而不必 分别保存原始树t o 、t l 、t 2 的状态，从而高效地降低了转发状态。 簟，s u r c eq 僦，q 懈? i ( a ) p e r f e c tm a t c h( b ) p u r e l e a k ym a t c h ( c ) p u r e - i n c o m p l e t em a t c h( d ) i n c o m p l e t el e a k ym a t c h 图3 - 2 组树匹配四种模型 组播聚合通过组间树共享机制多个组共享一棵组播树，获得了较优的转 发状态性能。当一个组播组加入时，聚合树的分配理应遵循一定的规则。对于比 较简单的情况，我们可以直接采用代价最小的能够并且能够覆盖组播组的树即 可；而当存在一定的约束时( 如带宽约束) ，或者组播组动态是变化时，则有必 要指定较为复杂的算法来实现聚合机制。当我们要将一个组播组g 与某个聚合树t 进行匹配时，一般会存在下述四种情况瞳踟如图3 2 所示： ( 1 ) w p - 够覆盖组g ，并且t 的所有叶节点都是组g 的成员，我们称这样的匹配关 系为相对组g 的完美匹配( p e r f e c tm a t c h ) ( 2 ) t 能够覆盖组g ，但是t 的某些叶节点不是组g 的成员，我们称这种匹配为相 1 4 山东大学硕士学位论文 对组g 的漏匹配( p u r e l e a k ym a t c h ) ( 3 ) t 不能覆盖组g ，但是t 的所有叶节点均是组g 的成员，我们称这种匹配为相 对组g 的