（计算机应用技术专业论文）一种负载均衡的优化应用层组播模型.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着i n t e m e t 的高速发展和终端机器的性能提高，网络信息已经由传统的以文字图片 为主的静态信息发展为以音视频为代表的多媒体动态信息。对于网络视频直播、文件下载 等大规模数据传输，组播是种理想的解决方案。但是由于技术和管理方面的原因，传统 i p 组播未能在i n t e m e t 上得到大规模部署。因此，近年来研究人员提出了将组播功能放在 端系统中实现的新思想，即应用层组播。 。 应用层组播逐渐成为i n t e m e t 中提供组播服务的主要方案，基于a l m 的应用技术也越 来越多，特别是应用层上的p 2 p 技术和应用越来越多。如何快速有效地分发资源，如何使 得各个节点负载均衡，如何在p 2 p 覆盖网上构建合理的a l m 模型成为目前研究的重点之 一。 本文提出了一种负载均衡的应用层组播模型，这是一种优化的树结构。文中主要阐述 了基于d h t 算法的组播节点标识符的分配，组播树的构建，节点的指针表构建，组播节 点加入与退出过程，对传输低效率的节点采用不影响网络拓扑的“节点交换”机制，最终 达到a l m 拓扑结构的整体优化。 本文的具体实现是从经典的p 2 p 搜索协议c h o r d 入手，构建了基于p 2 p 覆盖网的不定 叉树，支持任意源组播，将节点的加入和根的发现结合起来，并对其网络动荡( 节点加入 与退出) 实行制约限制，使网络环境保持基本稳定，达到负载平衡，并预测了本模型发展 的方向。 南京邮电大学硕士研究生学位论文a b s t r a c t a b s t r a c t a l o n gw i t ht h ec o n t i n u o u sd e v e l o p m e n to ft h ei n t e m e t ，t h ei n f o r m a t i o no i lt h en e t w o r kh a s g r o w nu pf r o mt h et r a d i t i o n a lt e x t sa n dp i c t u r e st om u l t i - m e d i ar e p r e s e n t e db ya u d i oa n dv i d e o a sf o rt h ed a t at r a n s p o r t a t i o ni nal a r g es c a l es u c ha st h ev i d e ol i v i n gb r o a d c a s ta n dd o c u m e n t s d o w n l o a de t c ，t h em u l t i c a s ti sak i n do fi d e a ls o l u t i o n h o w e v e r , f o rs o m ec a u s a t i o nr e s u l t e d f r o mt h ea b s e n c eo ft e c h n o l o g ya n dm a n a g e m e n t ，t h et r a d i t i o n a li pm u l t i c a s tc a nn o tb e d e p l o y e di nal a r g e s c a l et os a t i s f yt h en e e do fm u l t i m e d i ad a t as e r v i c e s o ，n o w a d a y s ，s o m e r e s e a r c h e r sp u tf o r w a r dan e w t h i n k i n gt oa c h i e v et h ec o m p l i c a t e df u n c t i o no fm u l t i c a s ta tt h e e n dh o s t s t h a ti st h ea p p l i c a t i o nl a y e rm u l t i c a s t a sa p p l i c a t i o nl a y e rm u l t i c a s th a sg r a d u a l l yb e c o m et h em a i ns c h e m et op r o v i d em u l t i c a s t s e r v i c e so ni n t e r a c t ，a l m b a s e da p p l i c a t i o nt e c h n o l o g yi sa l s om o r ea n dm o r e ，e s p e c i a l l yp 2 p t e c h n o l o g ya n da p p l i c a t i o n so na p p l i c a t i o nl a y e ra r em o r ea n dm o r e h o wt oq u i c k l ya n d e f f i c i e n t l yd i s t r i b u t er e s o u r c e s ，a n dm a k ee a c hn o d el o a d b a l a n c e ，h o wt ob u i l dr e a s o n a b l ea l m m o d e lo i lp 2 p o v e r l a yn e t w o r kb e c o m eo n ef o c u so ft h ec u r r e n tr e s e a r c h t h i st h e s i sp r o p o s e sal o a d b a l a n c i n ga p p l i c a t i o nl a y e rm u l t i c a s tm o d e l ，w h i c hi sat r e e s t r u c t u r eo p t i m i z a t i o n t h ea r t i c l ef o c u s e do nt h ea s s i g n m e n to fm u l t i c a s tn o d ei d e n t i f i e r sw h i c h b a s e do nd h ta l g o r i t h m ，t h ec o n s t r u c t i o no fm u l t i c a s tt r e e ，r o u t i n gt a b l e s ，t h ej o i na n de x i t p r o c e s so ft h en o d e s ，a n da d o p t e d ”n o d e se x c h a n g e ”m e c h a n i s mt ot h et r a n s m i s s i o nn o d eo fl o w e f f i c i e n c yw h i c hd o e s n ta f f e c tn e t w o r kt o p o l o g y , e v e n t u a l l yr e a c h i n gt h eo v e r a l la l mt o p o l o g y o p t i m i z a t i o n s p e c i f i ci m p l e m e n t a t i o no ft h i st h e s i ss t a r t e df r o mt h ec l a s s i cp 2 ps e a r c hp r o t o c o lc h o r dt o b u i l da l lu n d e f i n e d d e g r e et r e eb a s e do np 2 po v e r l a yn e t w o r kw h i c hs u p p o r t sa n y - s o u r c e m u l t i c a s t t h i ss c h e m ec o m b i n e dn o d ej o i n e do p e r a t i o nw i t hr o o td i s c o v e r ya n dc o n s t r a i n e di t s n e t w o r ki n s t a b i l i t y ( n o d et oj o i na n de x i o ，s ot h a tt om a i n t a i nt h eb a s i cs t a b i l i t yo ft h en e t w o r k e n v i r o n m e n ta n da c h i e v el o a d b a l a n c e a tt h ee n d ，w ef o r e c a s t e dt h em o d e l d e v e l o p m e n t u 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：埤日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名： ，、 导师签名：企兰 日期： 南京邮电大学硕士研究生学位论文第1 章绪论 第1 章绪论 因特网的迅速发展使得新的网络服务应用大量涌现，大量服务往往需要组通讯模式。 针对组通讯模式中的数据传输，如果采用单播( u n i c a s t ) 方式，所需的多条单播信道会占用 较多的网络传输资源，如果采用广播( b r o a d c a s t ) 方式，又会耗费不必要的网络资源并给接 收端带来不必要的麻烦。针对这种应用需求，产生了一种有效的传输模式一一组播 ( m u l t i c a s t ) 。为了解决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 ) 。 。 本章着重介绍应用层组播的相关概念，首先介绍了应用层组播的产生背景，随后介绍 了组播传输模式在网路通讯中的重要性，随后介绍了i p 组播与应用层组播在传输中的一些 差别，最后给出本论文的研究内容和研究思路，以及本文的组织结构。 1 1研究背景 随着现今网络的高速发展以及终端机器的性能提高，用户的应用需求不断地充实，互 联网相应出现了新的服务内容；如视频点播、电视会议、远程学习、计算机协同工作、分 布式计算等新业务。这类应用通常具有一对多、多对多的组通信特点，能够进行快速地分 发，减轻服务器的负担，同时又需要保证服务的质量。在传统的单播和广播传输方式之后， 一种能最大限度地利用带宽的组播技术也随之产生。组播作为多点传输的组通信模型，能 够节省网络资源，提高数据传输效率，是下一代i n t e r n e t 应用系统的关键支撑技术。 为保证网络协议设计的通用性和适应性，i n t e m e t 体系建议在网络层仅提供支持报文传 输的基本功能，而将其他功能交由终端系统实现。文献【l 】从端到端的角度给出了新增功能 的部署原则：“除非在低层实现所能获得的性能收益可超过其所需额外开销的复杂性，新 增功能应尽可能放在上层实现。 1 9 8 8 年d e e r i n g 提出在i p 层实现组播功能的框架【2 j ，并 在其1 9 9 0 年的论文【3 j 中得到详细的阐述。i p 组播的核心思想是通过在路由器对数据复制， 从而转发给加入组播组的每个接收者。 尽管i p 组播的研究已经进行了1 0 多年，但是由于技术和商业模式上的难题【4 1 ，i p 组 播目前还没有在i n t e m e t 上得到广泛的应用。 在技术上，首先，为了提供组播转发，需要在路由器上添加组播组管理协议，例如 i n t e m e t 组管理协议( 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 ，i g m p l 5 1 ) ，来维护组播接收者的 南京邮电大学硕上研究生学位论文第1 章绪论 状态信息，而且需要运行组播路由协议，例如距离向量路由协议( d i s t a n c ev e c t o rm u l t i c a s t r o u t i n gp r o t o c o l ，d v m r p l 6 1 ) 、开放式组播路径优先协议( m u l t i c a s to p e ns h o r t e s tp a t h f i r s t ，m o s p f t 7 】) 、协议无关组播密集模式( p r o t o c o li n d e p e n d e n tm u l t i c a s td e n s em o d e ， p i m d m f 8 1 ) 、协议无关组播稀疏模式( p r o t o c o li n d e p e n d e n tm u l t i c a s ts p a r s em o d e ， p i m s m 9 1 ) 等来转发数据，这样提供i p 组播就需要对i n t e m e t 上的所有不支持i p 组播的 路由器进行更换，代价太大；其次，路由器不具有高速处理器，在路由器上的复制开销以 及管理开销使得i p 组播的扩展性差，甚至难以胜任；另外，现有的i p 组播缺乏有效的安 全性、可靠性以及拥塞控制等机制，甚至难以部署。 从商业角度上说，不同互联网运营商( i n t e m e ts e r v i c ep r o v i d e r ，i s p ) 之间通常有服务 级别协议( s e r v i c el e v e la g r e e m e n t ，s l a ) ，不同的i s p 通常按照网络间的数据包流量计 费结算。从其他i s p 网络传入某个i s p 网络的单个i p 组播数据包，可以在该i s p 网络内部 复制成多个，然后传到第三方i s p 网络，从而造成计费的不对称。因此，即使有的路由器 支持m 组播功能，i s p 也没有开放路由器对i p 组播功能的支持。 上文描述的i p 组播由于其自身的缺陷，至今没能在i n t e r a c t 上进行有效的大规模部署， 于是人们开始寻找其他的替代方案，出现了以底层网络为基础的基于覆盖网的应用层组播 协议。覆盖网( o v e r l a yn e t w o r k s ) 是一个位于一个或多个已知网络上的独立虚拟网络。它 的主要优点在于它的架构，它不需要改变底层网络的结构，可以快速部署所需要的网络功 能。如果在叠加网的基础上实现组播，即可以把组播实现提高到应用层，称之为应用层组 播。 针对p 组播的缺陷，应用层组播有着诸多优势，它不需要底层网络的改变，在端系统 实现复制转发。相对于i p 组播，从技术上说，首先，应用层组播不需要在路由器上实现协 议，需要的是在端系统上实现协议，同i p 组播一样，它同样需要实现组播组管理协议和组 播路由协议，硬件上没有任何改动而只需要软件实现的协议，代价很小；其次，由于端系 统具有比路由器更多的资源( c p u 处理能力，存储) ，应用层组播可以利用这些资源来优 化时延、吞吐率等性能；最后，应用层组播可以直接利用现有单播传输成熟的技术，例如 拥塞控制、可靠性等机制，因而可以很方便地得到应用。应用层组播架构在覆盖网之上， 不受i s p 的制约，从商业角度上讲，也是可以实现的。因此，应用层组播并不是i p 组播的 简单替代品，而是具有很好的应用前景。 虽然a l m 在i p 组播的基础上有了很大的发展，但是作为一门新兴技术仍然不可避免 地存在很多问题和缺陷，比如带宽利用率低、组织混乱、无法感知底层物理网络等，所以 a l m 在被广泛使用的同时依然需要广大研究者继续对其进行探索并不断地改进。 2 南京邮电大学硕士研究生学位论文 第l 章绪论 1 2 单播、广播与组播 按照d 组播的构想，群组的通信方式主要有以下三种： 1 单播传输：如图1 1 所示，在发送者和每一接收者之间需要单独的数据信道。如果 一台主机同时给少量的接收者传输数据，对发送者的影响并不大。但如果有大量主机希望 获得数据包的同一份拷贝时，将导致发送者负担重、延迟长、高传输率，导致网络拥塞。 而且，发送者还必须维持每个连接，保存接收者信息，所以，为保证一定的服务质量，就 需要增加硬件和带宽。 接收者1接收者2接收者3接收者4接收者5 图1 1 单播方式实现群组通信 2 组播传输：如图1 2 所示，路由器不仅具有转发功能，还将具有复制的处理功能。 它提高了数据传送效率，减少了主干网中出现拥塞的可能性，减少了网络中的冗余传输和 侵占。组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络。 接收者1接收者2接收者3接收者4接收者5 图1 2 组播方式实现群组通信 南京邮电人学硕e 研究生学位论文 第1 章绪论 3 广播传输：是指在i p 子网内广播数据包，所有在子网内部的主机都将收到这些数 据包，如图1 3 所示。广播意味着网络向子网主机都投递一份数据包，不论这些主机是否 乐于接收该数据包。然而广播的使用范围非常小，只在本地子网内有效，因为路由器会封 锁广播通信。广播传输增加非接收者的开销，而且广播传输会对带宽进行不合理的侵占。 一 ii ji 7 八 i l i l i i 1 息血杰。愈匙 接收者接收者数据源接收者接收者 图1 3 广播实现群组通信 从上面的图示可以看出，组播是三种群组通信中最为高效和可行的，它适用于将大量 相同的数据传输到不同终端的场合。以下总结组播传输在群组通信的优势： 1 能节省源主机的系统资源和带宽； 2 组播是有选择地复制给有要求的主机： 3 组播可以穿越公网广泛传播，而广播则只能在局域网或专门的广播网内部传播； 4 组播能节省网络主干的带宽。 1 3 i p 组播与应用层组播 在图1 2 中，给出了i p 组播的传输方式，使用同一个p 组播地址接收组播数据包的 所有主机构成了一个主机组，也称为组播组。一个组播组的成员是随时变动的，一台主机 可以随时加入或离开组播组，组播组成员的数目和所在的地理位置也不受限制，一台主机 也可以属于几个组播组。此外，不属于某一个组播组的主机也可以向该组播组发送数据包。 i p 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者( 一 次或同时) 的网络技术。p 组播的核心思想是通过路由器对数据复制，再转发给加入组播 组的每个接收者来达到节约网络带宽和减小服务器负载的目的。组播能使一个或多个组播 源只把数据包发送给特定的组播组，而只有加入该组播组的主机才能接收到数据包。在组 播网络中，无论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。 因此，组播可以大大的节省网络带宽，组播作为一点对多点的通信，是节省网络带宽的有 效方法之一。 图1 4 给出了应用层组播的方式，与单播方式相比，直观上看，链路压力有所减轻， 4 南京邮电人学硕上研究生学位论文 第1 章绪论 例如数据源到r l 之间的链路，单播方式为7 ，而应用层组播方式为4 。但相比于i p 组播 方式，应用层组播在链路上的消耗有着一定的冗余。 接收者1接收者2接收者3接收者4接收者5 7 6 图1 4 应用层组播方式买现群组通信 a l m 是在端系统实现组播转发的，端系统之间通过单播连接，在应用层建立一个虚拟 的覆盖网，部分接收者收到数据后，再通过单播连接转发给其它接收者。a l m 与i p 组播 的根本区别在于，a l m 在端系统实现组播数据的复制转发，且不需要路由器提供i p 层组 播功能，而口组播必须在路由器上实现组播数据的复制转发。a l m 组播功能是在终端主 机的应用层而不是网络层路由器上，这主要体现在以下两方面： 1 对同一个数据包向多个接收者的发送是由应用层根据某种应用层的组播路由协议， 利用网络的u d p 或t c p 协议提供的单播服务分别单播给多个接收者。 2 在应用层实现组播组的创建、组成员的加入和退出以及安全认证等所有关于组播 组的管理与维护功能。 a l m 与i p 组播的主要区别： 1 。报文转发位置：a l m 数据转发节点是覆盖式网络中的终端主机，而疋组播的报文 转发必须由核心路由器来处理。 2 网络拓扑的创建方法ia l m 的覆盖式网络是由节点间直连而成的一个虚拟图( 有 向图或无向图) ，完全隐藏了底层的物理网络拓扑。这种覆盖式网络拓扑是完全可控的， 且可以利用一些额外的知识或特定的度量对网络拓扑进行优化。而在i p 组播中，路由器 是预先部署的，因此网络拓扑难以控制和改变。 3 组成员关系维护：i p 组播的组成员关系信息分布于组播路由器，而a l m 的成员 关系由系统中的会聚点集中控制或完全分散于各个节点。 s 南京邮电大学硕f ：研究生学位论文第l 章绪论 1 4 本文的研究思路及研究内容 应用层组播在o v e r l a y 上实现组播功能时，主要采用三种不同的拓扑结构：( 1 ) 网状拓 扑优先结构；( 2 ) 树拓扑优先结构；( 3 ) 基于隐式方法的特殊结构。在众多学者提出多种应 用层组播协议的同时，缺乏同p 2 p 搜索协议相结合，考虑物理拓扑的高效的应用层组播协 议。单中心的网络无法负担多远程终端的接入，应用层组播伴随着网络的发展，迫切需要 一种大规模的、分布式的、多中心的远程信息交换手段。为了实现大规模的网络，需要分 布式散列表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 和分层组织的思想，也就是基于隐式方法的特 殊结构，本文试图结合现有的经典p 2 p 搜索协议，利用现有的网络协议实现组播协议。 在选取父节点时，现有路由协议采用的选路算法总是计算节点对之间的最优路径，这 导致了单下一跳路由【1 0 1 ，从而导致信息分组沿最优路径传输，网络流量于是总是倾向占用 处理能力强的节点和链路。网络中不同节点对的最优路径趋向重叠，而且这种最优路径的 重叠在时间上保持相对稳定，这使得某些节点和链路被长时间过多地占用，传输负荷过大， 时常导致局部网络拥塞。从总体上看，当前的“单下一跳路由”机制虽然发现并建立了分 组传送的“最优路径 ，但却使得网络中各节点和链路对于传输信息分组的作用极其不均 衡，在某些节点、链路持续拥塞的同时，其他的几乎持续闲置。本文正着眼于此，试图构 建负载均衡的网络。 本文构建了一个三层的模型结构，并利用c h o r d 】协议建立起组播转发树，管理组播 节点。而对于利用d h t 构建网络的缺点【1 2 】，也就是d h t 算法的逻辑拓扑并不一定与物理 网络拓扑适配，这会导致转发时延增加，效率不高。本文借鉴了文献【1 3 】里所提出的“交换 策略，优化所提出的应用层组播模型，在保证系统负载均衡的前提下，实现组播数据的高 效传输。基于此，本文的主要研究内容如下： 1 应用层组播叠加网结构的构建 目前应用层组播方案主要采用的三种类型的叠加网：树状结构，网状结构以及层次状 混合结构。分析这三种结构的优缺点。叠加网是应用层组播技术实现的基础，因此设计一 个分布易维护的叠加网对提高整个组播协议的性能有着重大的意义。本课题将采用层次型 的d h t 叠加网络结构。 2 传输路径的建立 叠加网构建的最终目的是在此基础上构建传输拓扑，传输拓扑的性能也是衡量组播方 案性能的一个重要指标。本课题将根据叠加网络机构建立反向路径传输算法，建立传输路 径。 6 再京邮电入学坝土研j z 生学位论义第l 章绪论 3 节点动态进出机制 应用层组播中的节点都是独立自治的节点，它们会自由进出组播组，如何使得控制简 单，节点维护有效，是一个值得研究的方面。本课题将根据节点性能及传输带宽决定节点 在组播组中的位置，并在节点失效时维护组播组的性能。 4 优化转发树的算法 由d h t 建立的传输路径不一定是优化的，本课题采用“交换策略来优化转发树。 5 应用层组播协议模型的测试分析 根据提出模型，进行测试分析，论证提出方案的合理性和有效性。 1 5 本文的组织结构 论文共分为六章，本章主要介绍论文的研究背景、组播相关概念以及论文的研究思路、 研究内容、组织结构。接下来几章的内容安排如下： 第二章首先介绍了i p 组播协议，包括组管理协议i g m p 、密集模式组播路由协议和稀 疏模式组播路由协议，然后介绍了应用层组播的相关协议，包括网状拓扑优先结构、树拓 扑优先结构和基于隐式方法的特殊结构，其中对于本文所采用的基于隐式方法的特殊结构 着重介绍，包括p 2 p 的相关概念。 第三章在第二章的基础上提出一种新的应用层组播模型c a l m ( c h o r d b a s e d a p p l i c a t i o nl a y e rm u l t i c a s 0 ，并详细介绍组播模型的理论基础和组播模型的构建、组播成 员的加入退出方式等。 第四章对第三章提出的模型进行优化，首先介绍优化的理论基础，然后应用理论基础 对模型实现具体优化。 第五章对模型进行性能分析，首先介绍了应用层组播的评价标准，然后选取其中几个 有意义可行的参数进行测试，并介绍一些实验工具，并给出实验结果。 第六章对全文总结，梳理本文的创新点，总结在整个研究与设计的过程中不足之处， 归纳c - a l m 模型中仍然可以继续改进的地方，为下一步的研究与改善工作做好准备与铺 垫。 7 南京邮电大学硕士研究生学位论文第2 章组播协议 第2 章组播协议 第一章介绍了文章的研究背景及相关概念，本章将具体介绍组播的相关协议。由于应 用层组播协议与i p 组播协议有相似之处，它们都包括组播组管理协议和组播的路由协议， 本章将对典型的组播协议举例。 本章着重介绍具体的组播协议，首先介绍了i p 组播协议，包括组管理协议i o m p 和组 播路由协议密集模式( d v m r p 、p i m d m ) 及稀疏模式( c b t 、p i m s m ) ，其次介绍了三 种类型的应用层组播协议，包括网状拓扑优先结构、树拓扑优先结构及基于隐式方法的特 殊结构。最后点出了p 2 p 与a l m 的关系。 2 1i p 组播协议 i p 组播协议运行于网络层上，它既包括组成员管理协议又包括组播路由协议，以下介 绍具体的协议内容。 2 1 1 组管理协议i g m p i g m p 是i p v 4 下的组播组成员管理协议( i p 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 加入组播组 当某个主机加入某一个组播组时，它通过“成员资格报告 消息通知它所在的i p 子网 的组播路由器，同时将自己的d 模块做相应的准备，以便开始接收来自该组播组传来的数 据。如果这台主机是它所在的子网中第一台加入该组播组的主机，通过路由信息的交换， 组播路由器加入组播分布树。 2 退出组播组 在i g m p v l 中，当主机离开某一个组播组时，它将自行退出。组播路由器定时( 如1 2 0 秒) 使用“成员资格查询 消息向口子网中的所有主机的组地址( 2 2 4 0 0 1 ) 查询，如果 某一组播组在疋子网中已经没有任何成员，那么组播路由器在确认这一事件后，将不再在 子网中转发该组播组的数据。与此同时，通过路由信息交换，从特定的组播组分布树中删 g 查室坚皇查兰堡主竺壅竺堂篁堡兰星! 兰丝堡塑堡 除相应的组播路由器。这种不通知任何人而悄悄离开的方法，使得组播路由器知道i p 子网 中已经没有任何成员的事件延时了一段时间，所以在i g m pv 2 中，当每个主机离开某一 个组播组时，需要通知子网组播路由器，组播路由器立即向i p 子网中的所有组播组询问， 从而减少了系统处理停止组播的延时。在i g m p v 2 中，增加了退出通知这一功能。 2 1 2 密集模式组播路由协议 1 距离向量组播路由协议d v m r p 第一个支持组播功能的路由协议就是距离向量组播路由协议，它已经被广泛地应用在 组播骨干网m b o n e 上。d v m r p 为每个发送源和目的主机组构建不同的分布树，每个分 布树都以一个组播数据源作为根，以组播接受目的主机作为叶的最小扩展分布树。这个分 布树为发送源和组中每个组播接受者之间提供了一个最短路径，这个以“跳数”为单位的 最短路径就是d v m r p 的量度。当一个发送源要向组播组中发送消息时，一个扩展分布树 就根据这个请求而建立，并且使用“广播和修剪”的技术来维持这个扩展分布树。 扩展分布树构建过程中的选择性发送组播包的具体运作是：当一个路由器接收到一个 组播包，它先检查它的单播路由表来查找到组播组发送源的最短路径的接口，如果这个接 口就是这个组播包到达的接口，则路由器就将这个组播组的信息记录到它的内部路由表 ( 指明该组数据包应该发送的接口) ，并且将这个组播包向除接受到该数据包的路由器以 外的其它l f 6 5 近路由器继续发送。如果这个组播包的到达接口不是该路由器到发送源的最短 路径的接1 2 ，则这个包就被丢弃。这种机制被称为“反向路径广播 ( r e v e r s e p a t h b r o a d c a s t i n g ，r p b ) 机制，保证了构建的树中不会出现环，而且从发送源到所有接受者都 是最短路径。 对子网中密集分布的组播组来说d v m r p 能够很好的运作，但是对于在范围比较大的 区域上分散分布的组播组来说，周期性的广播行为会导致严重的性能问题，因此，d v m r p 不能支持大型网络中稀疏分散的组播组。 2 协议无关组播密集模式p i m d m 独立组播协议p i m 是一种标准的组播路由协议，并能够在因特网上提供可扩展的域间 组播路由而不依赖于任何单播协议。p i m 有两种运行模式，一种是密集分布组播组模式， 称为协议无关组播密集模式p i m d m ；另一个是稀疏分布组播组模式，称为协议无关组播 稀疏模式p i m s m 。 p i m d m 类似于d v m r p ，都使用了反向路径组播机制来构建分布树，但它们的主要 9 南京邮电人学硕上研究生学位论文 第2 章组播协议 差别在于p i m 完全不依赖于网络中的单播路由协议而d v m r p 依赖于某个相关的单播路由 协议机制，并且p i m d m 比d v m r p 简单。既然p i m d m 不依赖于任何单播路由协议， 路由器某个接收端口( 就是返回到数据源的最短路径的端口) 接收到的组播数据包被发送 到所有下行接口直到不需要的分枝从树中被修剪掉。p i m d m 则更加倾向于简单性和独立 性，甚至不惜增加数据包复制引起的额外开销。 2 1 3 稀疏模式组播路由协议 当组播组在网络中集中分布或者网络提供足够大带宽的情况下，密集模式组播路由协 议是一个有效的方法，当组播组成员在广泛区域内稀疏分布时，就需要另一种方法即稀疏 模式组播路由协议将组播流量控制在连接到组播组成员的链路路径上，而不会“泄漏”到不 相关的链路路径上，这样既保证了数据传输的安全，又能够有效的控制网络中的总流量和 路由器的负载。 1 基于核心树的组播协议( c o r e b a s e dt r e e s ，c b t ) c b t 协议构建一个树给组中所有成员共享，这个树被称为共享树。整个组播组的组播 通信量都在这个共享树上进行收发而不论发送源有多少或者在什么位置，这种共享树的使 用能够极大的减少路由器中的组播状态信息。 c b t 共享树有一个核心路由器用来构建这个树，要加入的路由器发送加入请求给这个 核心路由器。核心路由器接收到加入请求后，沿反向路径返回一个确认，这样就构成了树 的一个分枝。加入请求数据包在被确认之前不需要一直被传送到核心路由器你，如果加入 请求包在到达核心路由器之前先到达树上的某个路由器，该路由器就接收下这个请求包而 不继续向前发送并确认这个请求包，发送请求的路由器就连接到共享树上了。c b t 将组播 流量集中在最少数量的链路而不是在一个基于发送源的共享树上，集中在核心路由器上的 流量可能会引起组播路由的某些问题。某些版本的c b t 支持多个组播核心的使用，和单个 组播核心相比多核心更能达到负载平衡。 2 协议无关组播稀疏模式p i m s m p i m s m 将组播限制在需要收发的路由器上，其围绕一个被称为集中点( r e n d e z v o u s p o i n t ，r p ) 的路由器构建组播分布树，这个集中点扮演着和c b t 核心路由器相同的角色， 接收者在集中点能查找到新的发送源。但是p i m s m 比c b t 更灵活，c b t 的树通常是组 播组共享树，p i m s m 中的独立的接收者可以构建组播共享树或最短路径树。 1 0 南京邮电人学硕十研究生学位论文第2 章组播协议 2 2应用层组播相关协议 组播协议的复杂性和处理负载转移到了应用层，不可避免地造成数据包的传输效率要 低于基于网络层的组播。为了提高组播数据包的高效率的传输以及组播组成员的管理，研 究人员设计提出多种应用层组播协议。 2 2 1 网状拓扑优先结构 网状拓扑优先结构首先将组播组的成员组织成一个“网”( m e s h ) ，在网上以每个数据 源为根各构造一个生成树，每个成员节点都维护所有组成员的列表，这样可针对每个数据 源进行性能优化，如此则可提高组播组的可靠性。其缺点在于对网络带宽的浪费较大、系 统的管理开销过高、生成树的维护开销限制了组播组的规模，降低了系统的可扩展性。因 此m e s h 只适合小规模组播组的情况。常见的这类应用层组播协议有e s m b 4 1 、n a r a d a 1 4 1 、 s c a t t e r c a s t l l 5 】等。 e s m 是卡耐基梅隆大学开展的一个端系统组播研究项目，是迄今为止最成功的一个 项目。2 0 0 0 年e s m 的研究表明，在端系统中实现组播功能的体系结构是可行的，可以支 持组成员节点在几百个节点范围内、分布稀疏的、较小规模的多方通信。2 0 0 1 年通过在 i n t e m e t 中实际运行基于e s m 的视频会议，验证了e s m 采用的自组织协议可以在动态的、 异构的因特网中支持较小规模的视频应用。 n a r a d a 是最早提出的应用层组播策略之一，是e s m 的组网协议。n a r a d a 首先在组成 员之间建立一个具有网状连接的o v e r l a y 网络拓扑，随后建立基于该拓扑的组播转发树， 每个转发树的根都对应着一个数据源，通过动态探测网络状态，n a r a d a 动态地对叠加网进 行维护和优化。 在n a r a d a 网状拓扑构建的过程中，首先定义了一个特定的主机，即为汇聚点，被用来 启动新成员节点的加入过程。该r p 保存着所有加入组播组中成员节点的状态信息。新成 员节点从列表中随机选择一些组成员节点并向它们发送加入组播组的请求消息，当其中有 一个组成员节点接受了新成员节点的加入请求消息时，则该新节点成功加入组播组。当组 播组中有任意节点加入、退出时，所有的组播成员节点信息都会被m e s h 中所有的成员节 点共享。 但是这样的措施在使得n a r a d a 组播组的健壮性得到增强的同时，又引入了巨大的控制 管理开销，尤其需要将任意节点的变化通知到m e s h 中的全部节点，这使得n a r a d a 的扩展 南京邮电大学硕士研究生学位论文 第2 章组播协议 性受n t 极大的限制。因此n a r a d a 只适合小规模的o v e r l a y 网络，并不适合在网络上的大 规模部署。 2 0 0 0 年，b e r k e l e y 大学的y c h a w a c h e 在其博士论文中提出了s c a t t e r c a s t 的体系结构。 这是种基于应用层组播实现因特网大规模组播业务的体系结构。其思想是在i n t e m e t 中 部署支持组播业务的服务器，称为s c a t t e r c a s tp r o x y 节点，应用层组播将这些服务器组织成 一个i n t e m e t 组播业务的支撑网，支持用户规模巨大的i n t e m e t 组播和软件分发应用。 s c a t t e r c a s t 体系结构包括应用层组播机制、应用层组播之上的传输层机制以及内容请求的 实现机制。 2 2 2 树拓扑优先结构 直接采用分布式算法构造一棵单源数据转发树，每个接收成员主动发现组播树中的其 它非邻居节点并和这些节点保持连接，与它们建立数据、控制拓扑关系。这类应用层组播 协议的代表有h m t p 1 6 1 、n i c e 1 7 1 、z i g z a 9 1 1 引、a l m i l l 9 1 、y o i d t 2 0 1 ，所有的网络应用都使用 这棵组播树来传播数据。 这几种协议之间的区别在于：n i c e 将接收者分成群( c l u s t e r ) ，每个群中设置一个控制 节点，负责转发数据和维护本群内其它接收者，所有节点的数据拓扑结构构成一棵树； z i g z a g 与n i c e 类似，也是建立层次的树。不同的是，z i g z a g 把对群的控制功能和数据转 发功能分离，群的控制节点和数据转发节点不是同一个节点；a l m i 、h m t p 的树结构可 以动态适应网络状况的变化；y 0 i d 组播树构建好后是静态的。 n i c e p l l 协议是基于树优先，但同时又利用簇聚合组织共享树。这种组织方式的优点 是共享树层次清晰；但同时如果簇中的r p 状态变化，会引起节点状态的不稳定，影响整 个树的数据转发效率。分层拓扑的构建对于数据传输路径的质量至关重要，n i c e 把成员 主机安排成一个分层结构。当新节点加入和离开时，n i c e 负责创建和维护该分层结构。 该分层结构把节点安排到不同的层次，分层从最低层开始编号，每层中的成员被分成一系 列的集群或者称为簇( c l u s t e r ) ，每个集群中的成员数量较为接近，且都有自己的中心节点， 中心节点到集群中其它节点的距离之和是最小的，以此来保证新加入节点能够迅速地在组 播系统中定位。 n i c e 协议中有两种路径：一种是控制路径，一种是数据传输路径。为了使得控制信息 更快更好的在控制路径上汇聚且不产生比较高的开销，n i c e 协议采用了一种连通性比较 高的控制路径结构，选用树作为数据传输路径。n i c e 协议中的数据路径是由控制路径隐 1 2 南京邮电大学硕士研究生学位论文 第2 章组播协议 性决定的，一个源节点就唯一性地决定了一组组播路径。也就是说， 一个分发数据的源点，也就决定了一棵作为组播树的源树。 但是n i c e 容易引发链路瓶颈，特别是上层集群中的中心节点， 数据的分发。 2 2 3 基于隐式方法的特殊结构 在控制路径上决定了 因此只适合窄带低速 在p 2 p 网络中如果一个节点维护其他所有节点的信息，所带来的开销太大，为了提高 可扩展性，结构化p 2 p 网络的工作提出了利用分布式散列表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 来构建一个逻辑的空间，每个节点只需要维护逻辑空间中相邻或相关的部分其他节点的信 息。由于基于d h t 的结构化p 2 p 网络提供路由协议，通过简单修改路由规则就可以实现 在p 2 p 网络中实现应用层组播。 例如b a y e u x 2 2 1 是一种基于t a p e s t r y 2 3 1 的a l m ，s c r i b e l 2 4 1 是一种基于p 删【一2 5 1 的 a l m ，c a n m u l t i c a s t ( c o n t e n t a d d r e s s a b l en e t w o r km u l t i c a s t ) t z 6 是对c a n 2 7 】的扩展。它 们使用特殊的逻辑结构对组播节点映射或编址：组播转发可使用简单的规则实现，从而减 少状态维护开销和转发开销，避免路由协议的使用。 b a y e u x 基于t a p e s t r y 。每个节点拥有全局唯一的d ，并维护一个邻居表，这些邻居节 点的i d 和本节点的i d 在一定数量的位上相同。转发中第n 跳节点i d 和目的节点i d 至少 有n 位相同。b a y e u x 在t a p e s t r y 的基础上将组播树的状态信息保存在“中间节点”上。其 主要问题是这种维护状态的方式会限制算法的可扩展性。 c a n 组播是对c a n 的扩展。c a n 将一个d 维坐标空间划分成若干部分，每个节点 都拥有其中的某一部分。两个直接相邻部分的坐标在d 1 维上相同，而在另一维上不同。 转发报文时把报文发给邻居中和目标坐标最接近的节点。c a n 组播将组播组构造为c a n ， 使用“洪泛”方法在c a n 内转发报文。这样可减少节点上维护的状态