（计算机应用技术专业论文）基于均衡策略的二维应用层组播模型研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着数字技术、多媒体技术和网络通信技术的迅速发展，因特网已成为人们获取信息 的重要渠道。而网络应用的巨大需求导致网络系统经常会出现拥塞现象，虽然网络设备的 处理速度不断加快、网络带宽持续增长，但是硬件建设的速度依旧赶不上应用需求的增长。 点对点的单播传输方式已难以满足当前的网络需求，于是组播技术应运而生，同时i p 组播 的服务模型和协议存在着一些不足，使得它至今没有能在因特网上得到广泛的部署，于是 人们开始把目光转向i p 组播的替代方案，应用层组播就是其中重要的一种。 应用层组播将组播功能从路由器转移到端系统，由端系统完成所有组播组通信的功能 如成员管理、数据包复制和分发等。组成员之间建立起一个叠加在i p 网络之上的、实现组 播业务的功能性网络，从而摆脱了传统的i p 组播对路由器的依赖，充分发掘端用户的计算 资源，并且在功能上具有良好的扩展性。 在研究了国内外大量相关资料和分析现有的应用层组播算法和协议的基础上，本文提 出了一个新的应用层组播模型t d b s ( t w o d i m e n s i o n a lm o d e lb a s e do nb a l a n c e ds t r a t e g y ) ， 文中详细论述了模型的结构和协议工作机制，并对其进行仿真和分析，实现了组播组的创 建，成员的加入和退出以及失效的处理。 t d b s 模型具有许多特点如高效、分布式结构等，在组成员的加入过程中首先以综合 参数均衡算法来选取目标域，接着以d c m r 算法二次择优产生域内路径，最终达到a l m 拓扑结构的整体优化。经仿真实验验证，t d b s 模型在带宽资源不足的网络环境中，能有 效缓解网络拥塞，更好的保证端到端的q o s 。 关键词：应用层组播，域饱和度，动态优化，服务质量 a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n ti nd i g i t a l ，m u l t i m e d i aa n dn e t w o r kc o m m u n i c a t i o n t e c h n o l o g y , i n t e r n e th a sb e c o m et h e m o s ti m p o r t a n tw a yt oa c q u i r et h ei n f o r m a t i o nf o rp e o p l e a l t h o u g ht h ec p uo ft h en e t w o r ke q u i p m e n t sb e c o m em o r eq u i c k l ya n dt h eb a n d w i d t ho f n e l ：w o f k sc o n t i r m ei n c r e a s i n g ，t h en e t w o r k sc a nn o ts a t i s f yt h em o r ei n c r e a s eo fa p p l i c a t i o n r e q u i r e m e n t t r a d i t i o n a lu n i c a s tt e c h n o l o g yc a r lh a r d l ym e e tt h i sk i n do fa p p l i c a t i o n sw e l l ，s o p e o p l eb e g i nr e s e a r c ho nm u l t i c a s tt e c h n o l o g y u pt on o w , u n s o l v e di s s u e s i ni pm u l t i c a s t s e 州c cm o d e la n dp r o t o c o lp r e v e n ti tf r o mw i d e l yd e p l o y m e n t t h e np e o p l et u r n t oo t h e r a l t e r n a t i v et e c h n o l o g i e s ，a m o n gw h i c hi sa p p l i c a t i o nl e v e lm u l t i c a s t i na p p l i c a t i o nl a y e rm u l t i c a s t ，m u l t i c a s tf u n c t i o n sa r em o v e df r o mr o u t e r st oe n ds y s t e m s - e n ds y s t e mi st ob eu s e dt or e a l i z ea l lc o m m u n i c a t ef u n c t i o n so f m u l t i c a s tg r o u p ，f o re x a m p l e , 廿l ec o i l s 缸u c t i o no fm u l t i c a s tt r e e ，c o p ya n dd i s t r i b u t eo fd a t ap a c k e ta n ds o o n a l lg r o u p m 锄b e r ss e tu pa no v e r l a yn e t w o r ko nt o po fi pn e t w o r ka n dc o n s t r u c tm u l t i c a s tt r e ei ni t i nt h i s w a y , i td i s p o s e st h eb u n d l eo fd e p e n d i n go nr o u t e r sw h i c ht r a d i t i o n a li pm u l t i c a s tm u s t b e n e e d ， c o m p u r i n g r e s o u r c ea r ef u l l ye x c a v a t e da n da l lk i n d so ff u n c t i o n sc a nb ea d d e df l e x i b l y i nt h i st h e s i s ，w em a i n l yr e s e a r c hi r r e c i p r o e a la p p l i c a t i o nl a y e rm u l t i c a s ts y s t e mf a c i n g s i n g l es o r r t s t r e a m i n g m e d i a a f t e rr e a d i n gp l e n t yo fl i t e r a t u r e a n da n a l y z i n gr e l a t i v e a l g o r i t h m sa n dp r o t o c o l sf o ra p p l i c a t i o nl a y e rm u l t i c a s tw h i c h h a v eb e e np r o p o s e dt h o r o u g h l y , w ep r o p o s e dan e wm u l t i c a s tm o d e ln a m e dt d b s ( t w o - d i m e n s i o n a lm o d e lb a s e do nb a l a n c e d s t r a t e g y ) i nt h i st h e s i s ，w er e a l i z et h ec o n s t r u c t i o no fm u l t i c a s tg r o u p ，j o i na n dl e a v em u l t i c a s t g r o u pa n dt h ed i s p o s eo f n o d ef a i l u r e ，a l s ow ea n a l y z e i tb ys i m u l a t i o n t h et d b sm o d e lh a sm a n ym e r i t s ，s u c ha sh i g he f f i c i e n c y , d i s t r i b u t e ds t r u c t u r ea n ds oo n w bf o c l l s 鼯o nn o d e sj o i n i n ga n dd e p a r t u r ep r o c e d u r e s ，s or e g i o i ls a t u r a t i o ni sd e f m e da st h e 咖d a r df o r t h ee l e m e n t a r ys e l e c t i o n , a n dd c m ra l g o r i t h mf o rf u r t h e rs e l e c t i o n , t h i sa c h i e v e s 锄e n t i r eo p t i m i z a t i o no fa l mt o p o l o g y i ti sp r o v e dt h a tt h i sm o d e lc a ns o l v et h en e t w o r k c o n g e s t i o np r o b l e m e f f e c t i v e l ya n di m p r o v et h ee n d - t o - e n dq o sw h e nb a n d w i d t hi s as c a r c e k e y w o r d s ：a p p l i c a t i o nl a y e rm u l t i e a s t ( a l m ) ，r e g i o ns a t u r a t i o n ，d y n a m i c a lo p t i m i z a t i o n , q u a l i t yo fs e r v i c e l i 南京邮电大学硕上研究生学位论文 缩略语表 缩略语表 a l m a r c t a s i g 咿 c d n d h t d v m 限p i c p i s p o s p f m d c m r c t m s t n r u r p 2 p a p s a l s q o s r c t i 心 r u r s 、胛 h r d c m r a p p l i c a t i o nl a y e rm u l t i c a s t ，应用层多播 a v e r a g er e p l i c a t i o nc o m p l e t i o nt i m e ，平均复制完成时间 a u t o n o m o u ss y s t e m s ，自治系统 i n t e m e tg r o u pm a n a g e m e n tp r o t o c o l ，因特网组管理协议 c o n t e n td i l i v e r y d i s t r i b u t i o nn e t w o r k s ，内容分发网络 d i s t r i b u t e dh a s ht a b l e ，分布式散列表 d i s t a n c e - v e c t o rm u l t i e a s tr o u t i n gp r o t o c o l ，距离向量多播路由协议 i n t e m e tc o n t e n tp r o v i d e r , 互联网内容提供商 i n t e r n e ts e r v i c ep r o v i d e r , 互联网运营商 o p e ns h o r t e s tp a t hf i r s t , 优先开放最短路径协议 m u l t i p l ed e s c r i p t i o nc o d i n g , 多描述编码 m a x i m a lr e p l i c a t i o nc o m p l e t i o nt i m e ，最大复制完成时间 m i n i m u ms p a n n i n gt r e e ，最小生成树 n o r m a l i z e dr e s o u r c eu s a g er a t i o ，归一化资源使用率 p e e r - t o p e e r , 对等网 a v e r a g ep a t hs t r e t c h , 平均路径伸展率 a v e r a g el i n ks t r e s s ，平均链路压力 q u a l i t yo fs e r v i c e ，服务质量 r e p l i c a t i o nc o m p l e t i o nt i m e ，复制完成时间 r e n d e z v o u sp o i n t ，汇聚点 r e s o u r c eu s a g er a t i o ，资源使用率 s h o r t e s tw i d e s tp a t h ，最短最宽的路径 h i e r a r c h i c a l r i n gm u l t i c a s tm o d e l ，分层环状组播模型 d e g r e e - c o n s t r a i n e d ，m i n i m u mr a d i u ss p a n n i n gt r e ea l g o r i t h m ，带度 约束的最小半径支撑树算法 v 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生躲盟隰丝芝：竺 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：二笠二至重一导师签名：k 日期：盘! 乞：笙：! ! 南京邮电大学硕 研究生学位论文第一章绪论 1 1 研究背景及现状 第一章绪论 随着i n t e m e t 网络和宽带接入技术的快速发展，各种信息的共享和访问需求达到了前 所未有的高度。首先，全球个人计算机的数量也在飞速增长，据c n n i c 2 0 0 8 年7 月数据， 全球互联网用户人数超过了1 5 亿，超过现在全球人口总数的2 2 ，中国的互联网普及率 也接近2 0 。其次，i n t e r n e t 中的应用出现了新的特点，具体表现为个人计算机计算能力的 不断增强和与之对应的应用需求的变化。网络用户已经不再仅仅满足于在i n t e r a c t 上浏览 网页，收发邮件等基本功能，而对于多媒体内容如视频点播、网络电视直播的需求日渐增 加。新出现的一类应用需求包括在i n t e r n e t 上进行实时的音视频交流，网络直播和交互式 游戏等。这类应用通常具有一对多，多对多的通信特点，同时要求网络提供服务质量保证。 为保证网络协议设计的通用性和适应性，i n t e m e t 体系建议在网络层仅提供支持报文传 输的基本功能，而将其它功能交由终端系统实现。口多播的核心思想是通过在路由器对数 据进行复制，随后转发给加入多播组的每个接收者。尽管p 多播的研究已经进行了近2 0 年 时间，但是由于技术和商业模式上的难题，p 多播目前并没有在i n t e r a c t 上得到广泛的应用。 在技术上，首先，为了提供多播转发，需要在路由器上添加多播组管理协议，例如i g m p 【l l ( i n t e r n e tg r o u pm a n a g e m e n tp r o t o c 0 1 ) ，来维护多播接收者的状态信息，并且需要运行多 播路由协议，例如d v m r p 2 1 ( 距离向量路由协议) 、m o s p f 3 】( 开放式组播路径优先协议) 、 p i m - - d m 4 1 ( 独立多播路由协议密集模式) 、p 蹦一s m 【5 1 ( 独立多播路由协议稀疏模式) 等来转发数据，在路由器上的开销使得口多播的扩展性差；其次，要提供口多播则需对 i n t e r a c t 上所有不支持i p 多播的路由器进行更换，代价太大；另外，现有的口多播缺乏有效 的安全性、可靠性、以及拥塞控制等机制；最后就是商业的因素，不同的互联网服务提供 商i s p ( i n t e r a c ts e r v i c ep r o v i d e r ) 之间通常有服务级别协议s l a ( s e r v i c el e v e la g r e e m e n t ) ， 不同i s p 通常按照网络间的数据包流量计费结算。从其它i s p 网络传入某个i s p 网络的单个p 多播数据包，可以在该i s p 网络内部复制成多个，然后传到第三方i s p 网络，从而造成计费 的不对称。因此，即使一些路由器具备了口多播功能，i s p 也没有开放路由器对d 多播功能 的支持。 目前存在的多播技术除了i p 多播，还有应用层多播( a p p l i c a t i o nl a y e r m u l t i c a s t ，a l m ) 。 上文描述的m 多播由于其自身的缺陷，至今没能在i n t e r a c t 上进行有效地大规模部署。针对 l 南京邮电大学硕十研究生学位论文第章绪论 i p 多播存在的诸多问题，出现了以底层网络为基础的基于叠加网的应用层多播协议。叠加 网( o v e r l a yn e t w o r k s ) 是位于一个或多个已知网络上的独立虚拟网络。它的主要优点在于 其架构不需要改变原有底层网络的结构，可以快速部署所需要的网络功能。如果在叠加网 的基础上实现多播，即可以把多播实现从网络层提高至应用层，称之为应用层多播。 应用层多播技术近年来吸引了广泛的研列6 】【7 】【8 】【9 】【10 1 ，与i p 多播不同的是，应用层多 播不需要路由器提供多播功能的扩展，端系统之间通过单播的形式连接，在应用层上建立 一个虚拟的o v e r l a y 网络。一些接收者收到数据后，通过单播连接再转发给其它接收者。 a l m 与i p 多播的根本区别在于：a l m 在端系统实现复制和转发，而i p 多播必须要在路 由器上实现同样操作。因此a l m 具有了许多i p 多播所没有的优点。首先，a l m 不需要 对现有的i n t e m e t 底层进行任何修改，只需要通过端系统之间的协作，在应用层就可以实 现多播；其次，a l m 可以直接利用现有传输技术中成熟的拥塞控制、可靠性等机制，因而 可以很方便地得到实用；最后，由于端系统具有比路由器更多的资源( c p u 处理能力、存 储等) ，a l m 可以利用这些资源来优化时延、吞吐率等性能。因此，a l m 并不是多播 的简单替代品，a l m 具有很好的应用前景。 虽然a l m 在m 多播的基础上有了很大的发展，但是作为一门新兴技术仍然不可避免 地存在很多问题和缺陷，比如带宽利用率低、组织混乱等，所以a l m 在被广泛使用的同 时依然需要广大研究者继续对其进行探索并不断地改进。 1 2 主要研究工作 在对现有应用层组播系统和协议进行深入研究的基础上，提出新的应用层组播协议。 该系统具有较高的效率和良好的扩展性，主要面向实时应用，根据节点不同的q o s 需求和 服务能力，提供可靠的组播服务。论文的具体研究和实现工作包括以下几个方面： 1 、阅读了国内外大量的应用层组播相关的文献资料，对现有的应用层组播系统进行 研究、分析，总结其特点、优势和存在的问题，找出论文的研究突破点。 2 、应用层组播协议的研究。仔细分析现有的应用层组播系统的优势和不足，设计新 的组播协议，协议考虑到实时应用对时延和带宽要求较高，可以针对用户对时延和带宽的 不同需求提供区分服务。此外，高效的处理节点的加入和离开，同时具有良好的扩展性。 3 、对所设计的协议进行仿真，进一步分析它的性能。 4 、对新模型的不足进行总结，展望了未来进一步的研究方向。 2 南京邮电大学硕士研究生学位论文 第一章绪论 1 3 论文的创新性 本文的创新之处在于： ( 1 ) 提出了应用层组播的二维模型结构t d b s ，将同属于一个物理平面上的终端节点映 射为网络二维逻辑结构，建立和维护网络的逻辑层和域内树型拓扑结构。 ( 2 ) 提出了域饱和度的概念，通过层来管理区域节点集，以域饱和度为基础的综合参 数平衡选取法确定目标加入域，实现了节点加入的一次快速择优过程。 ( 3 ) 设计了带度约束的最小半径支撑树算法d c m r ，优化了节点在域内的数据路径。 ( 4 ) 采用基于优先级的动态规划法改变拓扑中各域中心节点所在的逻辑层次，以此达 到a l m 拓扑网络传输性能的整体优化。 t d b s 利用节点冗余信息存储、链路数据预留来增强在网络拓扑异动下的自愈能力。 1 4 论文结构安排 论文共分六章，每章的内容承上启下、相互衔接。 第一章为绪论，主要讲述论文的研究背景、研究现状、主要工作、创新性以及内容的 结构安排。 第二章介绍了组播的解决方案，多播最初是建立在p 层上，需要由特殊的设备支持， 而多播对网络的要求较高所以难以部署，由此引出了应用层的多播技术。在这一章节的 内容里，将概括性地描述了群组通信、p 组播的原理、组播地址的分配及i p z u 组播所存在 的问题，由此而引出应用层组播技术。 第三章对应用层组播系统的体系结构进行研究，分析了应用层组播的结构特点，路由 策略，主要算法以及主要性能评价标准。 第四章在第三章的基础上提出一种新的应用层组播模型，并详细介绍组播模型的构 建、系统设计、拓扑维护、传输算法等。 第五章对第四章提出的模型进行仿真，首先介绍模型参数的含义，并详细描述通过仿 真平台建立模型的过程。最后分析结果、得出结论。 第六章为总结及展望，先总结新模型的特点，然后提出还有待解决的问题。 南京邮电大学硕士研究生学位论文第二章组播的解决方案 第二章组播的解决方案 随着电信宽带网络建设的日益完善和宽带接入业务的迅速发展，用户对于以多媒体流 服务为主的v o d 视频点播、视频会议、宽带游戏、p 2 p 文件共享等众多宽带应用服务的 需求越来越迫切。但由此带来的带宽急剧消耗和网络拥塞也成为目前亟待解决的问题。为 了缓解由此带来的网络瓶颈，人们提出各种方案以提高网络可用带宽，主要包括以下四种 方案： ( 1 ) 增加网络带宽； ( 2 ) 服务器的分散与集群，改变网络流量结构，减轻主干网的负载压力； ( 3 ) 应用q o s ( 服务质量保证) 机制，把带宽分配给一部分应用： ( 4 ) 采用组播技术。 相比较而言，组播技术拥有独特的优越性，在下面的章节中将详细论述。 2 1 群组通信 群组通信首先是作为分布式进程之间的一种通信模式出现的，在八十年代的分布式系 统和并行计算机系统中有着非常广泛的应用。其中比较著名的有c o m e l l 大学的i s i s 分布系 统以及a m e i b o 系统。它们都拥有支持群组通信的底层通讯库。组是动态的，可以创建新 的组，也可以注销旧的组。参与者可以动态地加入或者退出一个组，也可以同时成为多个 组的成员。因此，需要一种机制来管理组和组的成员。在分布式系统中，一个组代表了协 同工作的多个进程集合；对于i n t e r a c t ，一个组代表相互通信的多个主机系统的集合。 群组通信与点对点通信有着不同的通信模式，数据往往要同时发送给组内的多个接收 者。按照发送者和接受者之间的对应关系，群组通信的通信模式可以分为一对多、多对一、 多对多三种。一对多是指一个发送者向多个接收者发送数据，属于这一类应用的有音视频 数据广播( 网络电视) ，广播各类信息，如股票价格的广播等等。多对一则表现为多个接 受者向一个数据源返回数据。例如，数据收集类应用，投票类应用等等。这类应用往往先 要求每个节点多播其查询请求( 一对多) ，而后等待其它节点向它返回数据。而在多对多 通信中，每个组成员即可以发送数据，也可以接受数据，发送者和接受者共同构成一个网 状的通信组。多点通信相比其它两种方式更能体现群组通信的特点，被认为是群组通信的 代表。 4 南京邮电大学硕士研究生学位论文第二苹组播的解决万累 目前的群组通信方式主要有以下三种： 单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果一台主 机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望获得数据 包的同一份拷贝时却很难实现。这将导致发送者负担沉重、延迟长、网络拥塞，为保证一 定的服务质量需增加硬件和带宽。 多播( m u l t i c a s t ) 传输：它提高了数据传送效率，减少了主干网出现拥塞的可能性。 多播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络。 广播( b r o a d c a s t ) 传输：是指在口子网内广播数据包，所有在子网内部的主机都将收 到这些数据包。广播意味着网络向子网内主机都投递一份数据包，不论这些主机是否乐于 接收该数据包。然而广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁广 播通信。广播传输增加非接收者的开销。 2 2i p 组播 i p 组播的体系结构如图2 1 所示。图中左边是单播协议，右边是组播协议。组播协议 从下而上，最底层是域间和域内的组播路由，它们之上是主机路由器接口i g m p ，最上层 是如r t p r t c p 等的一些主机服务。 i p 组播将一个p 报文向一个“组播组”传送，组播组可以包含一个或多个主机，由 一个单独的d 类口地址标识。除了目的地址部分，组播报文与普通i p 报文没有区别。i p 组播提供不可靠的、尽力而为的服务。 u n l c a s tm u l t i c a s t o s p f r i p 一p i 一， 口译 日g f 护础 i ；手髓r d c , 船o s p e b g p 霪 ： 瞒b c - m p i i a b g p ( b g p 4 + ) 黔。凯 图2 - 1p 组播体系结构 5 南京邮电大学硕士研究生学位论文第二章组播的解决方案 2 2 1 lp 组播基本原理 传统的i p 组播基于开放的服务模型，对主机和用户创建组播组，发送、接收组播数据 没有限制，不提供任何接入控制。组播组的成员可以动态变化，主机有权选择加入或者退 出某个组播组。主机可以加入多个组播组，也可以向自己没有加入的组发送数据。组播路 由器负责路由、复制和转发组播报文。i p 组播避免了在链路上传输重复报文，从而节省了 网络带宽，可实现高效的组播通讯。 图2 - 2 i p 组播 在p 组播通信中需要完成两个方面的基本工作：组播成员如何加入组播，如何将组 播信息路由到每个接收者那里去。这样就产生了两类基本的协议：组管理协议和组播路由 协议。i g m p t l 】用于主机与边缘组播路由器之间。主机使用i g m p 消息通知本地的边缘组 播路由器它想加入的组，即通知相应组的组播地址。组播路由器通过i g m p 协议来维护一 个组播成员列表，并且定期发送“成员询问”消息来探寻表中的各个成员是否仍然存在。 i g m p 是口v 4 下的组播组成员管理协议( 1 2 v 6 使用m u l t i c a s tl i s t e n e rd i s c o v e r y ：m l d 实现类似功能) ，运行于主机和与主机直接相连的组播路由器之间。主机使用i g m p 通知 子网组播路由器，希望加入组播组；路由器使用i g m p 查询本地子网中是否有属于某个组 播组的主机。 ( 1 ) 加入组播组 当某个主机加入某一个组播组时，它通过“成员资格报告 消息通知它所在的口子网 的组播路由器，同时自己的p 模块做相应的准备，以便开始接收来自该组播组传来的数据。 如果这台主机是它所在的子网中第一台加入该组播组的主机，将通过路由信息的交换， 组播路由器加入组播分布树。 ( 2 ) 退出组播组 在i g m p v l 中，当主机离开某一个组播组时，它将自行退出。组播路由器定时( 如1 2 0 秒) 使用“成员资格查询 消息向口子网中的所有主机的组地址( 2 2 4 0 0 1 ) 查询，如 果某一组播组在p 子网中已经没有任何成员，那么当组播路由器确认该事件后，将不在子 6 南京邮电大学硕士研究生学位论文第二章组播的解决方案 网中转发该组播组的数据。与此同时，通过路由信息交换，从特定的组播组分布树中删除 相应的组播路由器。这种不通知任何节点而悄悄离开的方法，使得组播路由器知道m 子网 中已经没有任何成员的事件延时了一段时间，所以在i g m pv 2 0 中，当每一个主机离开某 一个组播组时，需要通知子网组播路由器，组播路由器立即向i p 子网中的所有组播组询问， 从而减少了系统处理停止组播的延时。在i g m p v 2 中，增加了退出通知这一功能。 在i p 组播技术中，组播转发树有四种基本类型：泛洪法、有源树、有核树和s t e i n e r 树。 ( 1 ) 洪泛法( f l o o d i n g ) 这是最简单的向前传送组播路由算法，并不构造所谓的转发树。其基本原理如下：当 组播路由器收到发往某个组播地址的数据包后，首先判断是否首次收到该数据包，如果是 首次收到，则将其转发到所有接口上，以确保该数据包最终能到达所有接收者；如果不是 首次收到，则抛弃该数据包。 ( 2 ) 有源树 有源树也称为基于信源的树或最短路径树( s h o r t e s tp a t ht r e e ：s p t ) 。它是以组播源 为根构造的从根到所有接收者路径都最短的转发树。如果组中有多个组播源，则必须为每 个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树上， 因此采用s p t 有利于网络中数据流量的均衡。 ( 3 ) 共享树 共享树也称r p 树( 1 冲t ) ，是指为每个组播组选定一个共用根( 汇合点r p 或核心) ， 以r p 为根建立的组播树。同一组播组的组播源将所要组播的数据单播到r p ，再由r p 向 其它成员转发。目前，讨论最多同时也是最具代表性的两种共享树是s t e i n e r 树和有核树 ( c b t ) 。 s t e i n e r 树是总代价最小的转发树，它使连接特定图中的特定组成员所需的链路数最少。 有核树是由根到所有组成员的最短路径合并而成的树。 2 2 2ip 组播地址分配 在多播通信中需要两种地址：一个口多播地址和一个e t h e r n e t 多播地址。其中，d 多播地址标识一个多播组。由于所有d 数据包都封装在e t h e r n e t 帧中，所以还需要一个多 播e t h e r n e t 地址。为使多播正常工作，主机应能同时接收单播和多播数据，这意味着主机 需要多个口和e t h e m e t 地址。 p 地址方案专门为多播划出一个地址范围，在疋v 4 中为d 类地址，范围是2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 ，并将d 类地址划分为局部链接多播地址、预留多播地址、管理权限多 播地址；在p v 6 中为多播地址提供了许多新的标识功能，图2 3 为i p v 4 和口v 6 的多播地 址格式，其中i p v 6 中特殊域的定义见表2 1 。 7 南京邮电大学硕士研究生学位论文 第二章组播的解决方案 包； i p v 4 ： i p v 6 ： 0l23 43 1 lll0 组标示符 ， ， ， 0781 11 21 5 1 6 3 2 1 2 7 1 1l1 1l l1 f l a g ss c o p e 组标示符 图2 3i p v 4 和i p v 6 的多播地址格式 局部链接地址：2 2 4 0 0 0 - 一2 2 4 0 0 2 5 5 ，用于局域网，路由器不转发属于此范围的i p 预留多播地址：2 2 4 0 1 0 - - - 2 3 8 2 5 5 2 5 5 2 5 5 ，用于全球范围或网络协议； 管理权限地址：2 3 9 0 0 0 - 2 3 9 2 5 5 2 5 5 2 5 5 ，组织内部使用，用于限制多播范围： 表2 - 1 口v 6 中特殊域的定义 域值含义 0 0 0 0永久多播地址 f l a g s 0 0 0 1动态多播地址 0 0 0 1本地地址 0 0 1 0本地链路 0 1 0 1 本地网点 s c o p e 1 0 0 0 本地组织 1 1 1 0全局多播地址 其它保留或未指定 p 多播帧都使用以0 x 0 1 0 0 5 e x x x x x x 的2 4 位前缀开始的m a c 层地址，但只有其 中一半的m a c 地址可以被p 多播使用，剩下的m a c 地址空间的2 3 位作为第三层p 多 播地址进入第二层m a c 地址的映射使用。由于第三层p 多播的2 8 位地址不能映射到只 有2 3 位的可用m a c 地址空间，造成有3 2 ：1 的地址不明确，所以主机c p u 必须对收到的 每一个多播数据包做出判断，这增加了主机c p u 的开销。此外，还产生抑制第二层局域网 交换的多播扩散问题。 2 2 3 ip 组播存在的问题 但是目前口组播的服务模型和协议存在着一些问题，使得m 组播至今还没有能在 南京邮电大学硕 研究生学位论文 第l s 荦组播的解决方暴 i n t e m e t 上得到广泛部署。一方面，从因特网服务提供者( i n t e r n e ts e r v i c ep r o v i d e r ，i s p ) 的角度看，目前的母组播不能很好地适应商业应用的需求：组播数据包的复制和转发都由 路由器来完成，这就需要物理网络中所有路由器对i p 组播功能的支持。如果现有设备不支 持m 组播，就需要更换设备，这大大增加了i s p 的商业运营成本；此外一些使用共享树组 播路由协议，如p i m s m 和c b t 的i s p 面临跨域组播管理的问题：如果集中点( r e n d e z v o u s p o i n t ，r p ) 和其它组播源点不在同一个域内，难以进行流量控制和拥塞控制；i s p 对其它域 中的r p 服务没有控制能力；当需要跨域的组播服务时，i s p 必须协调彼此间的跨域组播代 价问题，m 组播的实施与管理和单播相比，要复杂和困难得多。因此只有使用m 组播所 节省的带宽大大超过它实施、管理代价时，p 组播的大规模应用才具有商业价值。 综合起来，目前的口组播存在着以下若干缺陷： ( 1 ) i p 组播还没有成熟稳定的商业计费模型，对于i s p 而言，这一点无疑是一个致命 的缺陷。 ( 2 ) i p 组播服务模型本身还存在一些有待解决的技术问题：要求路由器保存每个组的 状态，这破坏了最初设计i n t e r n e e 时所提出的“无状态”原则。 ( 3 ) i p 组播提出时并没有考虑到组成员是移动用户的情况，缺乏移动环境中可靠的组 播传输协议。因此目前的口组播路由协议无法在移动环境中正常工作，这也带来了巨大的 复杂性，限制了系统的可扩展性。 ( 4 ) d 组播服务模型虽然有i g m p 协议，但是i g m p 缺少组播组管理机制，如缺乏组 创建的管理，没有对接收者和数据传输的授权机制，发送者可以随意传输数据而不需要进 行任何身份验证和注册工作，主机可以动态加入或离开组播组，发送者不能阻止其它发送 者也选用同样的地址。 ( 5 ) 缺少访问控制机制会带来很多问题：比如恶意地泛洪攻击，当大量无用的数据传 输到组播组中会导致拥塞和报文丢失。 ( 6 ) 组播的安全问题：由于很多防火墙不能识别d 类m 地址，目前的解决办法是使 用隧道技术来穿越防火墙，这样在部署组播服务的同时也造成一些安全漏洞。 ( 7 ) 组播服务质量问题：m 组播是基于u d p 协议，而u d p 是一种“尽力而为 ( b e s t - e f f o r t ) 协议。因此，口组播应用必定会遇到数据包丢失和乱序等问题。要想在它之上实现更高质 量的服务，例如可靠性、拥塞控制和流控制【1 2 】等功能，比在m 单播( u n i c a s t ) 上实现要困 难很多。 ( 8 ) 可扩展性差。要求路由器保持每个组播组的状态信息，而这些d 类地址不能很好 地聚合，组播组的数量一旦大量增加，必然增加路由器存储和处理开销。 o 南京邮电大学硕：上研究生学位论文 第二苹组播的解决方案 ( 9 ) 缺乏灵活、可扩展的地址分配机制。节点不能有效地发现一个立即可用的组播地 址，而只是随机地选取一个来使用，这样随着组数目的增加，组播地址冲突的可能性也随 之增加。而且在现有的m v 4 下使用d 类地址作为组播地址，还可能面临着地址空间用尽 的问题。 2 3 应用层组播 面对口组播业务在因特网中的困境，一些研究者开始反思口组播体系结构本身的问 题，提出将复杂的组播功能放在端系统实现的新思想。端系统实现组播业务的思想是将组 播作为一种叠加的业务，实现为应用层的服务，因此，端系统组播又称为应用层组播 ( a p p l i c a t i o nl a y e rm u l t i c a s t ) 。应用层组播是指组播功能是实现在终端主机的应用层而不 是网络层路由器上。这主要体现在以下两个方面： ( 1 ) 对同一个数据包向多个接收者的发送是由应用层根据某种应用层的组播路由协 议，利用网络的u d p 或t c p 协议提供的单播服务分别单播给多个接收者； ， ( 2 ) 在应用层实现组播组的创建、组成员的加入和退出及安全认证等所有关于组播 组的管理与维护功能。 图2 - 4 应用层组播 应用层组播的基本思想是屏蔽底层物理网络的拓扑细节，将组成员节点直接自组织成 一个逻辑叠加网络【1 3 】，在应用层提供组播管理协议来构建和维护该网络，并通过特定的路 由协议为数据传输提供高效、可靠的服务。如图2 - 4 所示，终端节点在p 网的基础上形成 一个叠加网，数据的转发和复制由终端主机完成，它将转发树构建在应用层上。在网络层 层面来讲，应用层组播其实是由单播方式实现的组播。具体来讲：组播源准备数据、查询 组播路由表，获得子节点的单播p 地址，再分别打包、转发。数据包通过相应的单播路 1 0 南京邮电大学硕：研究生学位论文第二荦组播的解决方暴 径传输给子节点，子节点接收数据包后查询路由表，再分别打包、转发。这一过程重复进 行，直到所有节点都收到数据包。查询、打包、接收和转发工作都在网络终端主机的应用 层上完成。通过在主机上安装相应的应用层组播软件就可以实现广域网范围内的组播服 务。应用层组播可看作是传统的c s 模式和i p 组播的一种折中方式，相对于c s 模式，应 用层组播分散了服务器的负载，相对于i p 组播，存在数据在物理链路中重复传输的问题。 应用层组播与p 组播相比较的优点主要是： ( 1 ) 应用层组播不需要改变底层网络，不需要路由器支持组播功能，组播服务的部 署相对容易； ( 2 ) 应用层组播不需要路由器支持，也不需要在路由器上维护组播组的状态，因此 具有良好的扩展性； ( 3 ) 利用t c p 的拥塞控制、错误控制等机制使得应用层组播具有更好的可靠性。由 于单播技术在这方面比较成熟，而应用层组播是通过终端系统之间单播来实现的，所以差 错控制、流控制、拥塞控制容易实现； ( 4 ) 应用层组播可以很好地解决组播地址分配不足的问题。 南京邮电大学硕t 研究生学位论文 第三章应用层组播的体系结构研究 第三章应用层组播的体系结构研究 i n t c m e t 变得日益庞大和复杂的同时，人们对网络服务质量( q o s ) 的要求也在不断提高， 计算机网络的可靠性、稳定性以及高效性等诸多性能方面的表现也被越来越多的网络使用 者和管理开发者所关注。如何在现有网络环境基础上提高网络性能，为下一代互联网设计 出具有更高效率和更高稳定性的网络互联协议，而这些问题的解决都要求对网络性能能够 进行有效地评价与分析。 本章首先分析了应用层组播的结构特点，组播的各种策略，以及组播中的主要算法， 最后同时也分析了应用层组播的性能评价标准，为下一章节问题的解决提供了突破口。 3 1a l m 的结构类型 针对口组播在因特网上不能部署的困境，一些研究者提出了将复杂的组播功能放在 端系统来实现的思想。因为应用层组播是在一个功能性的虚拟叠加网( o v e r l a y n e t w o r k ) 基础上实现的，所以应用层组播协议首先要考虑的是叠加网的构建。 3 1 1 叠加网 叠加网是位于传输层和应用层之间的一个功能性的虚拟网络，利用底层服务，向上层 应用提供a p i 。它们实际上是按协议而构成的一系列叠加网套接字( o v e r l a ys o c k e t s ) 。 图3 1 是一个叠加网的拓扑示意图，基础网络的七个节点中的两个子集通过彼此之间 的单播连接，形成了具有星型拓扑和环形拓扑的两个虚拟叠加网。叠加网的概念提出很早， 因特网也可以认为是一种建立在各类局域网之上的叠加网。不论叠加网具体的拓扑结构和 协议是怎样的，它们都