（计算机系统结构专业论文）基于p2p的混合型应用层多播的研究.pdf

j ：海大学硕士学位论文 摘要 i p 多播已经在流媒体传递技术，比如在高速网络数据流和视频会议等方面 取得了一定的成功。但是某些缺点导致了i p 多播尚未被大范围部署，并且也不 能作为一项基本的网络服务提供给终端用户使用。由于i p 多播不能被广泛接 受，研究人员把目标转向了其他可选择的多播机制，应用层多播就是其中的一 项。应用层多播在最近一段时期颇受青睐，主要原因在于它把对于多播的支持 从网络层转移到终端系统，也就是应用层。 在本论文中，作者提出了一种基于p 2 p 技术的混合型应用层多播模型。该 模型结合了两种常用的应用层多播的网络结构( 即本地传递树和结构化中枢网 络) 。首先，每一个本地p e e r 分组通过使用一种被称为适应性协调者选择算法 ( a d a p t i v ec o o r d i n a t o re l e c t i o n ，a c e ) 1 】的方式选出一个协调者节点 ( c o o r d i n a t o r ) ；其次，网络中所有被选出的协调者节点再一起构建出一个结构 化的中枢网络。这种双层的结构为应用层多播服务提供了很好的可扩展性。 在本文提出的混合型应用层多播模型中，协调者节点是下层本地传递树和 上层结构化中枢的边界。在本地一侧，协调者节点负责管理本地p e e r 并且构造 传递树。构造传递树的整个过程会根据不同的应用需求进行动态调整。在结构 化中枢一侧，协调者节点通过彼此之间的相瓦协作实现“尽最大努力的传输”。 这种相互协作包括了两个丰要功能：一个是通过合并路由路径减少结构化中枢 网络中的路由跳数和内容副本，并且保持负载平衡；另一个是通过交换协调者 节点相互之间的位置最小化结构化中枢网络中的总的传输延迟。 可扩展性、协作性和按需是本文所提出的混合型应用层多播模型区别与其 他应用层多播的三个主要特点。 关键词：p 2 p 、应用层多播、协调者、传递树、结构化网络 v 上海大学硕一i ：学位论文 a b s t i 认c t i pm u l t i c a s th a ss o m es u c c e s sf o rd e l i v e r i n gs t r e a m i n gm e d i as u c ha sh i g h - s p e e d n e t w o r ks t r e a m i n ga n dv i d e oc o n f e r e n c e b u ts e v e r a ld r a w b a c k sc a u s ei pm u l t i c a s t n o tw i d e l yd e p l o y e da n dg e n e r a l l yn o ta v a i l a b l ea sas e r v i c ef o rt h ea v e r a g ee n d u s e r s w i t hi pm u l t i c a s tn o tg a i n i n gw i d ea c e e p t a n c e ，r e s e a r c h e r st u m e dt o a l t e r n a t i v em u l t i c a s tm e c h a n i s m sl i k ea p p l i c a t i o n l e v e lm u l t i c a s t ( a l m ) a l mh a s r e c e n t l yb e e np r o p o s e da n dg a i n e di np o p u l a r i t yw h i c hs h i f t sm u l t i c a s ts u p p o r tf r o m t h en e t w o r k i n gl a y e rt oe n ds y s t e m s i i lt h i st h e s i s w ep r o p o s eap 2 p b a s e dh y b r i da p p l i c a t i o n l e v e lm u l t i c a s tm o d e l ， w h i c hc o m b i n e sl o c a ld e l i v e r yt r e ea n ds t r u c t u r e db a c k b o n en e t w o r k e a c hl o c a l p e e rg r o u pe l e c t so n ec o o r d i n a t o ra c c o r d i n g t oa c e ( a d a p t i v ec o o r d i n a t o re l e c t i o n ) l1m e t h o da n da l lc o o r d i n a t o r sf r o ml o c a lp e e rg r o u p sb u i l du pt h es t r u c t u r e d b a c k b o n e t h i st w o t i e rs t r u c t u r ep r o v i d e sg o o ds c a l a b i l i t yf o rm u l t i c a s ts e r v i c e i n o u rh y b r i da p p l i c a t i o n 1 e v e lm u l t i c a s t e o o r d i n a t o r sa r et h eb o r d e ro fl o c a ld e l i v e r y t r e e sa n ds t r u c t u r e db a c k b o n e i nl o c a ls i d e e o o r d i n a t o r sm a n a g el o c a lp e e r sa n d c o n s t r u c td e l i v e r y 仃e e s w bc o n s t r u c td e l i v e r yt r e e so nd e m a n da c c o r d i n gt o d i f f e r e n tr e q u i r e m e n to fa p p l i c a t i o na n dt a r g e t s i nb a c k b o n e ss i d e ，c o o r d i n a t o r s c o l l a b o r a t ew i t he a c ho t h e r st oi m p l e m e n tt h eb e s t e f f o r td e l i v e r y t h i si n c l u d e st w o f u n c t i o n s ，o n ei sm e r g i n gr o u t i n gp a t h st or e d u c et o t a lh o p sa n dc o n t e n tr e p l i c aa n d k e e pl o a db a l a n c eo v e rt h eb a c k b o n e a n dt h eo t h e l i se x c h a n g i n gt h ep o s i t i o n so f e o o r d i n a t o r st om i n i m i z et h et o t a ld e l a yi nt h eb a c k b o n e t h e r ea r es e v e r a lf e a t u r e sd i s t i n g u i s ho u rh y b r i da l mm o d e lf r o mt h ec u r r e n t e x i s t i n go n e s ：s e a l a b l e ，c o l l a b o r a t i v ea n do nd e m a n d k e y w o r d s ：p e e r - t o p e e r a l m ，c o o r d i n a t o r , d e l i v e r yt r e e ，s t r u c t u r e dn e t w o r k s v l 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名么蜀斟醯日期：碰乡硇 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名师签名： i i 上海大学硕士学位论文 1 1 单播与多播 第一章背景介绍 单播与多播是数据传输的两种基本模式。当一台主机向另一台单一接收主 机发送数据时称作单播。当一台主机向网络中多个f - 日不一定是全部接收主机传 送数据时称作多播。当向所有连接的丰机发送数据时称作广播。广播是多播的 一个特例，单播是主机之间通信的最常使用的一种传统模式，而多播则在许多 新型应用，如多媒体和远程会议中被使用。至于广播，由于它的可扩展性问题 导致了在较大的网络中很少被使用，仅仅被用在一些共享介质的局域网中的地 址解析等通信任务中。 1 2i p 多播 i p 多播 2 是一种向一组接收者发送i p 数据包的方法。它通过向一组口地 址发送包的方式把数据包的副本传送给组中的每一个成员。如今，i p 多播在传 送流媒体方面，比如高速网络数据流和视频会议，得到了成功的应用。在一些 金融领域，比如股票交易系统中，也可以看到i p 多播的部署。i p 多播还被广泛 应用在校园和金融网络中的文件分布存储，尤其是向远程主机传送操作系统镜 像和升级【3 。 但是一些劣势造成了i p 多播至今没有在互联网上得到大范围广泛部署，也 还不能作为一项普通的网络服务提供给用户。主要原因有以下三点：首先，部 署i p 多播需要在网络的基础结构层做一定的改动，这种改动需要在路由器上进 行设置用来保存多播过程中的状态信息。但是那些控制着大量网络基础设施的 互联网服务提供商出于某些商业目的并不热衷于推动i p 多播，比如应该向谁收 取i p 多播过程中所产生的流量费用，是口数据包的发送者还是接收者? 其次， i p 多播是为分层次结构的路由基础设施而设计的，比如说树型结构。这些分层 次结构在支持大量并行分组方面的可扩展性并不是很好。最后，i p 多播是一种 尽最大努力的传送方式而不是一种可靠传送方式，这就导致了它并不能保证数 据包的发送成功或者用户的接收成功，而需要其他的更高层次的应用程序来提 供这些功能 4 】。 1 3 应用层多播 由于p 多播没有得到广泛的应用，研究人员转而投向了其他的多播机制， 其中的一种就是应用层多播 5 。所谓应用层多播就是把对于多播功能的支持从 网络层转移到应用层，也就是客户程序端。由于不需要网络层的直接支持，应 用层多播显得非常有吸引力。因为应用层多播具有可扩展性的自我管理协议， 有效的网络带宽监控和适应，很多人认为它是一种可以代替i p 多播的很好的网 坶大学硕学位论文 络服务模式。最近的一些研究也表明了应用层多播服务模式可以为相当数量的 用户集群提供可靠的服务质量。在应用层多播中，所有的应用客户端构建出一 个覆盖网络( o v e r l a y n e t w o r k ) ，覆盖网络中的内容分布则是通过网络中成员之 问单播转发数据包来实现的【6 】。由于在应用层多播中，路由信息保存在应用层， 所以它比口多播具有更好的可扩展性可以用来支持大量的并行分组。 但是，应用层多播还存在一些其他问题。第一为了成功部署应用层多播 应用程序必须把自己和特定的应用层多播模式集成在一起。这意味着应用层多 播和它相应的实现成了应用程序整体的一部分。但是理想的模式是把应用程序 和相关的多播机制分离开，从而可以可以实现简单部属。第二，应用层多播在 一些带宽受限制的网络链路上经常会遭遇带宽瓶颈。为了避免这一瓶颈，可阻 把访问链路转移至企业级网络，因为局域网中的带宽是相对宽裕和便宜的；或 者把访问链路向网络核心部位转移，那里的带宽会更加的稳定。第三，用来支 持应用层多播机制的终端节点需要相当规模的处理能力。 图1 1 表明了口多播和应用层多播的主要区别【7 】o 在口多播中，源数据 包首先被发送到路由器，然后由路由器负责将这些数据的复制和转发。但是在 应用层多播中，多播是独立与物理链路的，路由功能的实现以及对数据包的复 制和转发从路由器转移到了终端= e 机。这也是为什么应用层多播比多播需要 更多的带宽和产生延时的原因。但这样做的好处是可雌支持更多的用户和具有 更好的可扩展性 8 。 挚 i 二二i ：掣 p 号 = 二二二0 “ 泸 9 m a p p l i c a t i o n l e v e lm u l t i c a s t p h s t a i l 岫 t r a i tr 砒嘲 1 4p 2 p 网络 圈l 1 ：i p 多播与应用层多播 最近几年，p 2 p 技术成了商业和学术领域中的一个热点。因为它具有可扩 展性、灵活性、容错性与自我管理等特点【9 。 p 2 p 系统是一个分布式系统，在这个系统中所有的成员节点相互平等，起 着相似的作用。p 2 p 可以被看作是分散型的网络体系结构。相比之下，客户端 上海大学硕上学位论文 服务器体系结构则把客户端和服务器明确的区分开来，客户端请求和使用服务， 服务器端负责提供服务。 尽管在p 2 p 网络中，节点之间相互平等，但整个p 2 p 系统还是具有一定的 结构状态。根据自制等级的不同，每一个节点联系与它同等的相邻节点，并一 起来维护整个系统的结构状态。这一特性使得p 2 p 网络中的节点比客户端服务 器系统中的客户端更加复杂。由此可见，p 2 p 系统的最大优点就是它的可扩展 性，容错性和避免在服务期端出现资源瓶颈。 p 2 p 网络的一个重要目标就是所有的节点一起提供资源，包括网络带宽， 存储空间和计算能力。因此，随着p 2 p 网络中的节点数量的增加，整个系统的 总负载能力也在同时增加。而在客户端服务器体系结构中恰恰相反，由于服务 器数量的固定，增加更多的客户端会减慢所有用户的数据传输。p 2 p 网络分布 式的属性也增加了系统的强壮性，当错误发生时可以通过多个节点上的数据副 本进行容错处理。另外，在纯p 2 p 系统中，节点之间的查找数据将不依赖于集 中式的索引服务器。 在p 2 p 网络中，终端用户可以通过计算机之间的直接交互进行资源共享。 信息分布在各个成员节点上而不是单一的服务器。一个纯p 2 p 系统是没有集中 式控制的分布式系统，并且运行在每一个节点上的应用程序在功能上是平等的。 因此，一个p 2 p 系统应该是高度可扩展、可利用与分布式；并且具有一定的对 称性。 1 5 基于p 2 p 的协作式应用层多播 在本文中，作者提出了一种基于p 2 p 技术的混合型应用层多播模型。这一 混合型模型结合了两种不同的常用的应用层多播结构( 即传递树和结构化网络) 分别用来构建本地p e e r 组和结构化中枢网络。图1 2 说明了作者所提出的应用 层多播模型的双层结构。每一个本地p e e r 组使用一种被称为适应性协调者选择 算法( a d a p t i v ec o o r d i n a t o re l e c t i o n ，a c e ) 的方式选出一个协调者节点 ( e o o r d i n a t o r ) 。首先，a c e 算法根据从本地p e e r 获取来的环境度量参数来选 择和重定位协调者节点。根据不同应用程序的不同目的，每一个度量参数在选 择协调者节点的过程中具有相应的优先级和权重值。其次，网络中所有被选出 协调者节点再一起构建出一个结构化的中枢网络。这一双层结构的模型可以提 供具有良好扩展性的应用层多播服务。 在本文作者提出的混合型应用层多播模型中，协调者节点作为下层本地传 递树和上层结构化中枢网络的边界。在本地一侧，协调者节点负责管理本地p e e r 并且构建传递树。根据本文作者提出的设想，传递树的构建应根据应用目的不 同进行动态调整。在中枢网络一侧，协调者节点之间相互协作以实现“尽最大 努力的传输”。这种相互协作包括了两个主要功能：首先，合并路由路径以减少 整个中枢网络中的路由跳数、内容副本并且保持负载平衡。本文对d i j k s t r a 最 短路径算法进行了改进用来实现路由路径的合并。其次，交换中枢网络中协调 者节点之间的相互位置，达到最小化网络总体延时的目的。本文假设每一条从 节点f 到节点，的路由路径具有一个延时值w ，l ，这一延时值是根据目标节点 上海大学硕士学位论文 _ ，的权重值m 和从节点f 到节点，的路由路径的物理链路延时厶，计算得到的。 = c 1 0 0 r d i n a 士 0 l a lb 撼r d i s t r i b u t e d s t o r e d 8 0 u r c e 图1 2 ：基于p 2 p 的协作式应用层多播模型 1 6 本文的组织结构 t r e a m i n g 本文其余部分的章节安排如下：下一章讨论应用层多播的相关研究。第三 章阐述了混合型应用层多播的基木设计以及协调者节点之间相互协作所能提供 的功能的实现。在第四章中，作者模拟并评估了所提出的算法的实际性能。最 后，对本文进行总结以及对将来工作的展望。 4 上海大学硕士学位论文 2 1 相关工作 第二章研究背景 大部分的应用层多播系统通过两种不同的方式，传递树或结构化模型，来 实现应用层的多播。采用传递树的诸如o v e r c a s t 1 0 、n a r a d a 【1 1 和y o i d 1 2 等；使用结构化模型的则有s c r i b e 1 3 、b a y e u x 1 4 1 和c a n e l 5 等。 结构化的覆盖网络比如c h o r d 1 6 和p a s t r y 1 7 考虑到了多播应用的可扩展 性需求，但是它们在结构上的同构的设计方式在遇到异构网络的时候会导致分 组之间通信的低效率。主要原因包括节点计算能力过载或资源的未充分利用。 这样的影响在对带宽要求很高的多播服务中显得尤为明显。 相反，非结构化的覆盖网络结构比如传递树结构具有灵活传递的能力，并 且能够适应p 2 p 的网络环境。尤其是对异构网络的适应性提高了覆盖网络的性 能。但是，非结构化的覆盖网络往往使用基于泛洪机制的多播路由，这就限制 了它的可扩展性和效率。 2 1 1n a r a d a n a r a d a 使用一种具有自我管理属性的覆盖网络来实现多播，并且假设底层 的网络层只支持单播【1 l 】。n a r a d a 把构建多播树的过程分为两个步骤。首先， 在每个一分组中建立一个包含所有组成员的n a r a d a 网格。然后，根据这些网格 生成一颗生成树用来多播内容。 采用基于n a r a d a 网格的方式是为了支持多数据源应用，比如视频会议。单 一共享树并没有对每一个独立数据源进行优化并且对于网络中心点的失效非常 敏感。另一种替代方法就是为每一个数据源都明确地建立一个覆盖树。但这一 方法在维护和优化多个覆盖树的开销上存在劣势。( 这里的论述如何又突然的与 网格联系在一起了，比较突然，请给出过渡句) 一个良好的n a r a d a 网格应该具有以下两点属性：1 ) 任意一对成员之间的 路径质量至少相当于这一对成员之间的单播路径的质量；2 ) 网格中每一个成员 的相邻节点的数量是有限的。对于路径质量，采用与应用相关的参数作为度量， 比如延时和带宽。对网格中相邻节点的数量做出限制可以有效地控制网格中的 路由算法的运行开销。 在n a r a d a 中，网格的优化是通过测量端到端的延时、增加和删除链路来达 到减少延时的目的。这里的网格建立和维护算法假设所有的分组成员都彼此联 系，因此不需要扩展到更大的分组。 n a r a d a 的分组管理的方法如下：每一个分组成员维护一张列表，这张列表 记录着同一分组中其他成员的信息。当有新的成员加入或者已经存在的成员离 开，每个成员所维护的表需要被更新。同样，网格中的成员需要定期地与相邻 成员交换本分组中的成员信息。 上海大学硕t = 学位论文 此外，每一个分组成员不仅仅维护通向其他所有节点的路由开销，而且维 护着这些路由所需要的路径。为每一个数据源所建立的用来传递数据的传递树， 是根据每一个接收者和数据源之间的相反最短路径构建起来的。这种构造树的 方法是一种d v m r p 方式 18 】。 2 1 2o v e r c a s t o v e r c a s t 提供了一种可扩展和可靠的单数据源的多播，它使用了一种简单 协议来建立适应于多变网络环境条件下的有效的数据分布树。为了支持节点的 快速加入，o v e r c a s t 实现了一种能够有效追踪变化中分布树的全局状态的新协 议【1 0 】。 与i p 多播一样，o v e r c a s t 允许数据同时被发送到多个目的地。当存在多个 目的地的时候，数据将在网络中的合适的节点上被复制，以此达到最小化带宽 需求的目的。它同时也具备c a c h e 和服务器冗余的功能。它的多播能力往往被 用来填充c a c h e 和在网络中对服务器进行复制。另外，o v e r c a s t 被设计成一种覆 盖网络结构，使得它可以被增量部署。当o v e r c a s t 系统中的节点数量增加时， 系统的收益也同时增加，但它并不需要通过完全部署的方式来实现有效性。 与n a r a d a 类似，o v e r c a s t 构建以数据源作为根节点的多播树，并且通过端 到端的测量来优化数据源与目标组成员之间的带宽。它实现了一种简单的建树 协议用来建立适合于单一数据源多播的、带宽有效的数据分布树；并且这种协 议以一种可扩展的方式向数据分布树的根节点适时提供状态更新信息。o v e r c a s t 在覆盖网络中实现了这几种协议，这一覆盖网络是位于i n t e r n e t 之上的。这些协 议支持大规模、可靠的单数据源的多播分组；并且允许o v e r c a s t 网络可以动态 适应下层网络基础结构中的变化，比如网络堵塞和节点失效等。一些在地理位 置上分散的公司已经构建了一个小规模的o v e r c a s t 网络，并在一般的桌面电脑 上部署o v e r c a s t 节点，用来分布按需求的、高质量的视频。 基于模拟的结果显示，o v e r c a s t 可以在性能不输给i p 多播的情况下，提供 更多的功能。模拟同时显示，与口多播相比，o v e r c a s t 可以快速建立带宽有效 的数据分布树，用接近于2 倍的网络负载提供7 0 到1 0 0 的网络带宽。 2 1 3s c r i b e s c r i b e 是一种可扩展的应用层多播的基础结构。它同时支持大量分组，并 且每个分组中可以有大量的分组成员。s c r i b e 是建立在p a s t r y ( 图2 1 和图2 2 ) 之上的，它是一种支持p 2 p 对象定位和路由的、建立在i n t e r n e t 之上的低层覆 盖网络；并且继承了p a s t r y 的可靠性、自制性和局部性【7 】。 6 上海大学硕士学位论文 9打西fdp1口j2?5j8 - 、xx， 、 xxx、x，、 ，x工、- 666666 666666 666 口j77467占9口西fdp 1 、xxx、- 、x工x- 、xx x工工 _ - 一 6666666 66 666 _666 55555，j 55 555555 口j27彳56 ，占 9 西fdp f ，、xx xx xxx、- x 一 摹 ，x xx - 。- 、 66666666666 6666 ，5555js5 5 555555 打口盯口盯a口打疗仃打口口仃盯 口2?456 _ 艿9盯6cde f xx工 x xxx xxxx，x x工 图2 1 ：i d 为6 5 a h 的p a s t r y 节点上的路由表， x 代表一个任意的前缀 图2 2 ：从节点6 5 a l f c 上发送关键字为d 4 6 a l c 的消息， 圆点表示了p a s t r y 环形名字空间中的活动节点 一个s c r i b e 系统由一个p a s t r y 节点网络组成，每一个节点上运行着s c r i b e 应用程序。根据它的分组管理机制，每个分组具有一个唯一的分组i d 。在每 一个分组中，节点i d 在数学上最接近分组i d 的一个节点，负责与其他分组联 系。这个对外联系的节点也是在分组中构建多播树时候的根节点。 7 一i - 海大学硕士学位论文 作为一种选择，经常会把某个分组的建立者作为本组的对外联系节点。在 成员管理功能方面，s c r i b e 会建立一棵以对外联系节点作为根节点的多播树， 用来在本组所传播多播消息。那些用来构建每一个分组中的多播树的s c r i b e 节 点被称作本组中的转发者。在s c r i b e 中是不会出现环路的，因为在p a s t r y 路由 路径上，每一个后继节点的节点i d 与前一个节点的节点i d 相比，与本组的分 组i d 有着更长的共同前缀，或者共同前缀的长度相等但数学上更接近，或者该 后继节点就是根节点。 为了保证其可靠性，s c r i b e 使用t c p 协议传播多播树中从父节点到子节点 的消息和进行流控制。当一个转发者失效时，它使用p a s t r y 网络来修复多播树， 每一个非叶子节点定期地向它的子节点发送确认消息。这种多播树的修复机制 具有很好的可扩展性，依靠向少数节点发送小心来检测错误，在本地进行修复， 这样使得很少数量的节点涉及其中。 2 1 4c a nm u l t i c a s t c a n 网络是最早提出的四个分布式哈希表( d h t ) 设想中的一个，其余三 个是c h o r d 、p a s t r y 和t a p e s t r y 。与其他的d h t 相同，c a n 是一种分布的、非 集中式的p 2 p 基础结构，它在接近于i n t e r n e t 的规模下提供哈希表功能。c a n 的设计思想就是可扩展性、容错性和自我管理。它在一个多环面的结构上建立 了一个虚拟的多维的笛卡尔协作空间。这个多维的笛卡尔协作空间完全是逻辑 概念上的。整个协作空间在所有系统节点中动态划分，比如每一个节点都拥有 自己独立、独特的空间。每一个c a n 节点都维护着一张路由表，这张路由表记 录着该节点所有相邻节点的i p 地址和虚拟协作空间。c a n 网络中的节点使用 一种贪婪算法向目标地址发送消息。在路由过程中，消息将会被节点转发到离 目标地址最近的那个相邻节点上。在c a n 系统中，信息的关键字是被映射到某 个值上的【9 】。 c a n 多播模型使用由c a n 网络维护的路由表向覆盖网络中的所有节点散 播消息，而不是通过建立多播传送树。c a n 通过在每个分组中建立独立的c a n 覆盖网络来支持多分组模式当一个新节点加入时，它首先在全局c a n 覆盖网络 中找到该分组的联络节点，然后通过该节点加入到该分组的覆盖网络中。每一 个分组中的叶子节点由c a n 的常规维护算法来处理。 c a n 多播模型的一些特点使得它在某些特定场景下具有优势：分组中的网 络流量并不受限制于单一多播树中的数据流，并且只有分组中的成员节点转发 本组中的多播数据流。但是很明显，和s c r i b e 的多播树相比，建立和维护独立 的c a n 覆盖网络需要更大的开销。根据网络的拓扑结构来构造c a n 覆盖网络 似乎可以减少网络中的延时和链路上的流量压力，但这会增加构建和维护覆盖 网络的开销。另外，c a n 多播中的分组加入机制缺少可扩展性。c a n 覆盖网 络中的每个分组的联络节点承担并处理着所有与新节点加入有关的数据流量。 c a n 的设计者也建议，为这些对外联络节点增加冗余以避免出现可扩展性方面 的问题。 匕海大学硕士学位论文 2 2 研究目的 在n a r a d a 和o v e r c a s t 等通过构建多播树来实现应用层多播的系统中，都对 多播树进行了一定的优化。但是这些多播树都是事先构建好的，并且在实现多 播的过程中，它的主要结构也是保持不变的。对于应用层多播而言，不同的应 用和目的具有不同的需求。比如说，在流媒体多播中，控制同步延时是非常重 要的；而在数据文件多播系统中，如何保持负载平衡是关键。 另外，与前文所述的结构化的应用层多播系统，比如s c r i b e 和c a n 相比， 本文对所提出的上层中枢网络中的路由机制进行优化。作者通过改进d i j k s t r a 最短路径算法，对路由路径进行合并，以减少网络中的总的路由跳数和链路上 的流量压力。另外，通过协调者节点之间的相互协作，交换中枢网络中节点的 位置，达到减少整个结构化中枢网络中总的延时的目的。 在本文中，作者探索了一种混合型的应用层多播的新模型，该模型把结构 化网络和传递树结合在一起。在设计过程中，有以下三点目标： 可扩展：单一传递树并不具备很好的可扩展性。在本文中，作者通过构建 双层结构模型为应用层多播服务提供了良好的可扩展性。 相互协作：在本文作者提出的混合型应用层多播模型中，协调者节点是结 构化中枢网络和本地传递树的边界。通过协调者节点之间的相互协作，可 以合并路由路径来减少网络中的内容副本和保持中枢网络的负载平衡；也 可以通过交换中枢网络中节点的位置来减少传输延迟时间。 按需：因为不同的应用和目的具有不同的需求，比如说，流媒体要求同步 和低延迟，而数据文件多播需要保持负载平衡。所以多播传递树应该按照 不同的需求按需动态构造。 9 上海大学硕十学位论文 第三章混合型应用层多播 如图1 2 所示，本文所提出的混合型应用层多播模型把两种不同的应用层 多播网络结构结合在一起：下层本地p e e r 分组采用传递树结构，上层中枢网络 采用结构化网络。在这一模型中，协调者节点是本地传递树与结构化中枢网络 之间的边界。在本地分组一侧，协调者节点管理本地节点并且负责构建传递树。 本文根据不同应用和目的的不同需求动态构建传递树；在结构化中枢网络一侧， 通过协调者节点之间的相互协作实现尽最大努力的数据传输。这里包括了两方 面的功能：首先是路由路径的合并，用来减少结构化中枢网络中的传输总跳数 和内容副本的数量，并保持负载平衡。本文通过改进d i j k s t r a 最短路径算法来 实现路由路径的合并；其次，通过交换协调者节点之间的相互位置，最小化中 枢网络中的总的延时。 3 1 双层结构的构建 3 1 1 协调者节点的选择 在本文所提出的应用层多播的模型中，每一个本地分组使用“适应性协调 者选择算法( a c e ) ”的方法选择本组中唯一的协调者节点。在a c e 平台中， 每一个p e e r 分组根据从本组中的p e e r 那里获取来的环境度量参数，动态地选择 和重新分配协调者节点。每一个度量参数都有各自权重值和优先级，这样可以 根据不同的应用目的选择协调者节点。 当一个新的节点加入或一个已知节点离开时，a c e 算法按照以下的步骤来 执行协调者节点选择： ( 1 ) 每一个节点通过应用层多播搜索现任的协调者节点； ( 2 ) 如果现任协调者节点存在的话，它将对搜索请求做出响应； ( 3 ) 每一个节点每隔固定的时间间隔，获取一次自己的环境信息，并发送给现 任协调者节点； ( 4 ) 现任协调者节点收到其他节点发送过来的环境信息后，返回一个a c k 消 息给每一个节点； ( 5 ) 现任协调者节点根据收到的、每一个节点的环境信息，在它们之中选出新 的协调者节点和候选节点各一个； ( 6 ) 现任协调者节点把重新分配的信息传送到新的协调者节点上； ( 7 ) 新的协调者节点把这一改变通知所有其他的节点。 在步骤( 1 ) 中，本地分组中第一个发送请求消息的节点往往会被初始化为 协调者节点。否则当第一个节点加入到本地分组中时，可能会没有其他的节点 来响应它的请求。这时，就需要事先设置一个响应等待时间，以避免一个节点 无休止地等待请求响应。 l o j ：海大学硕士学位论文 在步骤( 4 ) 中，现任的协调者节点将等待其余所有的节点把环境信息发送 过来。在这时，如果某个特定的节点在事先规定的响应等待时间过后，还未把 环境信息发送过来的话，则该节点将被认为是非活动状态的节点。响应等待时 间是根据参与节点的i 盯t 值动态设定的。 在步骤( 5 ) 中，现任的协调者节点首先根据其他节点发送过来的环境信息， 也就是每一个度量参数的值，对所有节点进行排序。下面的步骤说明了如何根 据网络拓扑结构决定节点的顺序： ( i ) 协调者节点根据所有节点发送过来的路由信息，建立一个连接图；当中继 节点不是已知的参与节点时，这些中继节点的数量将被设置成连接图中每一条 边的值； ( i i ) 协调者节点使用广度优先搜索为这一连接图建立最小生成树，最小生成树 的起始节点就是协调者节点本身，并且排除闭合回路； ( i i i ) 把所有的叶子节点从这棵最小生成树上依次删除，直到剩下最后一个节 点。 接着，根据下面的步骤从已经有序的节点队列中选出新的协调者节点和候 选节点： ( i ) 为每一个度量参数设置一个决定节点顺序的权重值脓； w k ：半( 后：。砘，：咒。比删肌b 们 n 、 ( i i ) 为每一个度量参数设置一个权重系数，并且计算每个节点的度量值 s i , ； s f ，= 岷c ， ( f ：n o d e ，：m e t r i c ) ( i i i ) 计算出每个节点所有度量值的总和s u m ，； s u m ，= 一， ( i v ) 度量值总和最高的那个节点将被选举为新的协调者节点n e w ，下一个 成为候选节点。 n e w = m a x s u m ) 如果新当选的协调者节点不是现任的协调者节点，那么这一改变将会被 通知给其余所有节点。当新的协调者节点失效时，候选节点将会被启用。 3 1 2 结构化中枢 本文使用路由表来构建结构化中枢网络，这一中枢网络包含了每一个本地 二海大学硕士学位论文 p e e r 组中的协调者节点。这种路由表与c h o r d 协议中的“指针表”类似。为了 实现前面提出的设计思想，本文同时对d i j k s t r a 最短路径算法做了改进，用来 优化基本的路由路径( 这部分内容将在章节3 2 中讨论) 。 首先，我们假设2 ”等于或仅次于结构化中枢网络中的节点数量。每一个节 点m 维护着一张路由表，这张路由表中最多包含n 项条目。节点m 所维护的路 由表中的第f 项条目包含了指向节点s 的标识，该节点s 是在中枢环路中，与节 点m 相距至少为2 h 的后继节点，表示为s = s u c c e s s o r ( m + 2 h ) ，其中l f ，l ， 并且所有的算术计算结果都以2 ”取模。在c h o r d 中，节点s 被称作节点m 的第f 个指针，并且用m t i n g e r 川来表示。每一项路由表条目包含了相关节点的节点 i d 和i p 地址( 及端口) 。 这种设计方法的优点是每一个节点只需要保存一小部分其他节点的信息， 并且其中大部分是离自己距离较近的节点的信息，而不是距离较远的节点。 图3 1 给出的例子显示了在一个共有8 个节点的中枢环路中，节点1 所维 护的路由表。节点l 的第一个后继节点指向节点2 ，因为( 1 + 2 0 ) m o d 2 3 = 2 。类 似的，节点1 的最后一个后继节点是节点5 ，因为( 1 + 2 2 ) m o d 2 3 = 5 。 在图3 2 中，假设希望在该中枢环路中建立一条从节点1 到节点8 的路由 路径，因为在节点1 的所有后继节点之中，在节点8 之前且距离节点8 最近的 节点是节点5 ，所以节点1 会首先建立一条通往节点5 的路由路径，然后要求 节点5 负责建立通往节点8 的剩余路径。接着，节点5 同样会在其后继节点中 寻找在节点8 之前且距离节点8 最近的节点。在本例中，该节点是节点7 。最 后，节点7 发现节点8 就是自己的后继节点，这样就完成了一条从节点l 到节 点8 的完整的路由路径。 1 2 上海大学硕+ 学位论文 7 3 1 3 可扩展性 7 5 图3 1 ：节点1 所维护的路由表 1 5 图3 2 ：节点1 至节点8 的路由路径 3 部分应用层多播系统，比如o v e r c a s t 和n a r a d a ，通过传递树结构来实现多 播功能。但它们在可扩展性方面的性能有限。当新的节点加入到本地p e e r 分组 上海大学硕：i = 学位论文 中的时候，传递树会向两个方向增长：宽度和高度。无论是宽度增长，还是高 度增长都会影响到整棵传递树的可扩展性。比如说，如果新节点采用图3 3 a 中 的广度优先的方式加入到本地传递树中，父节点a 就会有越来越多的子节点。 当子节点的数量超过父节点a 的容量时候，就会造成节点a 的负载过度甚至节 点失效。又比如说，如果新节点采用图3 3 b 中的深度优先的方式加入到本地传 递树中，该传递树的层数会逐渐增加。这时，传递树的叶子节点，比如节点b ， 离根节点越远，延时越大。由此可见，新节点广度优先加入传递树会破坏整棵 树的负载平衡；深度优先加入传递树则会造成叶子节点更大的传输延时。 ( a )( b ) 图3 3 ：新节点加入传递树( a ) 广度优先( b ) 深度优先 在本文所提出的混合型应用层多播模型中，使用双层结构( 即结构化中枢 网络和木地传递树) 来解决可扩展性问题。首先，给每一个本地p e e r 分组定义 两个限制参数：出度边界m 和传递树层数边界，。出度边界m 限制了传递树中 的每个父节点最多可以拥有m 个子节点；层数边界，规定了传递树最多可以达 到，层这两个限制参数的值是根据本地p e e r 分组的环境信息和应用需求来决定 的。 出度边界m 控制着父节点的负载平衡。如果本地p e e r 分组的平均性能，如 c p u 、内存、存储空间和网络条件足够强大，那么出度边界聊可以适当地增大。 相反，如果本地p e e r 分组中的大部分节点的c p u 、内存、存储空间和网络性能 较差，那么出度边界m 的值应该被保持在一个较小的范围里，避免造成传递树 的负载过度及失效。 层数边界，控制着传递树的平均延时。比如说，流媒体数据多播对数据同步 的要求较高，应该降低该多播过程中的延时。因此，在流媒体数据多播中，层 1 4 上海大学硕l 学位论文 数边界，应该适当的减小；相反，对于数据文件多播来说，延时对其的影响并不 是很大，那么这里的层数边界，就可以适当的增加一点，从而更有效地控制多播 过程中的负载平衡。 图3 4 ：双层结构中的可扩展性 接下来，我们将给出一个例子，具体说明如何使用双层结构来改进节点加 入和离开过程中的可扩展性。在图3 4 中，本地p e e r 分组a 的出度边界和传递 树层数边界分别被设置成聊= 2 和，= 3 。当新节点出现的时候，根据m = 2 和 z2 3 ，如果现有的传递树的容量还没有满，那么它可以被允许加入进来。如果 该传递树的容量已经满了，那么它将不再接收新成员的加入。这时候，新节点 将创建一个新的本地p e e r 分组b ，并且自己作为该分组的协调者节点，然后加 入到上层的结构化中枢网络中去。当然，在新的本地p e e r 分组创建的过程中， 它的出度边界和传递树层数边界也会根据该分组的环境信息和应用需求被分别 设定。在这之后，新的本地p e e r 分组就可以开始接收新成员加入，除非它的容 量达到限制条件。 上海大学硕士学位论文 3 2 协作性 在本文提出的混合型应用层多播模型中，协调者节点扮演着最重要的角色。 协调者节点是结构化中枢网络和本地传递树的边界。在本地p e e r 分组一侧，协 调者节点管理本地p e e r 并且负责构建传递树。在中枢网络一侧，协调者节点通 过之间的相瓦协作，对网络中的路由性能进行优化。我们给出一个例子，用来 说明如何利用结构化中枢网络把数据源的数据传送到目标p e e r 分组中。在图 3 5 a 中，单一数据源中的数据流通过节点1 进入到结构化中枢网络中。在图中 的应用层多播系统中，总共有三个本地p e e r 分组想要接收该数据流，它们的协 调者节点分别是节点2 、节点3 和节点8 。接着，节点1 负责建立三条路由路径 分别通往节点2 、节点3 和节点8 。在这种传递模式中，存在以下三点隐患： 所有的路由路径都是以节点1 作为起点，这使得节点1 承受了大量的转发 处理负载，降低了节点1 的效率； 每一条路由路径中至少存在一份数据副本，过多的路由路径带来大量的数 据副本会给网络中的流量造成很大的压力； 每一条路由路径从起点到终点都需要若干路由跳数，如果整个中枢网络中 总的路由跳数很高，将会大大地增加网络传输延时。 为此，本文通过协调者节点之间的相互协作来优化结构化中枢网络中的路 由路径，希望可以解决上述问题。本文提出的优化方法可以被分为两个步骤： ( 1 ) 对符合条件的路由路径进行合并，减少中枢网络中的路由跳数和数据副本， 并且保持中枢网络的负载平衡：( 2 ) 交换中枢网络中协调者节点之间的相互位 置，最小化总的网络延时。 3 2 1 合并路由路径 如图3 5 b 所示，原来图3 5 a 中的两条从节点1 分别通向节点3 和节点8 的 路由路径被合并在了一起。合并以后，从节点l 通向节点8 的新路径覆盖了