（计算机系统结构专业论文）基于蜂窝结构覆盖网络的应用层多播研究.pdf

上海大学硕士学位论文 ! 堕曼旦塾g 坚坚垫丝宝q i ! ! ! ! 哇丝i q 璺2 1 兰垒垒翌g 垒璺i 竺坠坌篮i 盟 摘要 当今世界，互联网在一对一模式的应用上取得了巨大成功，点对点的可靠 文件传输和即时消息服务大量涌现并为广大用户所青睐。近些年来，人们对流 媒体数据的共享需求日益增加，这些需求迫切需要本质上属于一对多模式的应 用来满足，而多播技术目前正是在多用户间共享数据的最好方法。另一方面， 一些缺点和不足导致i p 多播不能被广泛地部署，因而不能作为一种便捷的服务 被用户使用。这个矛盾导致研究人员转向另一种多播机制：应用层多播。由于 树结构和基于树结构的数据转发网络具有易实现、网络资源利用率高等优点， 因而在应用层多播协议中被广泛使用。但是，这些数据转发网络具有健壮性较 差、节点失效恢复代价较高和存在影响吞吐率的瓶颈节点等问题。 为了在应用层上建立一个健壮的、可快速失效恢复的、充分利用节点带宽 的数据转发网络，本文给出了一种基于蜂窝结构覆盖网络的应用层多播协议， 该协议针对互联网上中小规模的单源视频或音频多播服务。在该协议中，所有 的网络节点通过本文给给出节点加入算法映射到应用层上一个基于蜂窝结构的 数据转发网络中，利用蜂窝结构的自然稳定性可以使得节点失效只影响局部少 量节点，受影响的节点在不需要多播服务器干预的情况下可以从失效状态快速 恢复。在此基础上，本文还给出了一种数据转发网络吞吐率的改善算法，该算 法通过根据指定的规则调换节点在蜂窝结构网络中的位置，让节点更加有效地 利用上行和下行带宽，从而增强整个应用层多播系统的数据转发能力。 此外，本文还给出了一种基于n s 2 和b r i t e 的应用层多播协议仿真方法， 在该仿真方法的基础上，为了评价数据转发网络的健壮性，在仿真实验中将本 文给出的协议和另外一种稳定的应用层多播协议k 树进行了比较；为了评价失 效恢复代价，将基于蜂窝结构的数据转发网络和度受限的最短路径树、度受限 的最小生成树这两种普遍使用的数据转发网络进行了比较。为了证实本文给出 的改善数据转发网络带宽利用率算法的有效性，在另外一项仿真实验中评价了 该算法对于整个应用层多播系统数据转发能力的改善情况。 最后，本文给出了一个基于蜂窝结构覆盖网络应用层多播平台的设计和实 现，利用这个平台提供的应用编程接口可以实现多种单源多播应用。作为研究 项目的一部分，该多播平台被应用到了n t t 未来网络研究所的i - v i s t o 项目中， 为该项目实现了一个单源多播系统的原型，在应用中证实了该应用层多播协议 的可靠性和有效性。 关键词：蜂窝结构，覆盖网络，p 多播，应用层多播，网络模拟 上海大学硕士学位论文 二! 垒曼2 型丝墨! 堂型宝殳i ! ! ! ! 塑! i q 翌殳! 墨垒璺翌吐垒i 型望叠堡塑韭z a bs t r a c t t o d a y , i n t e r n e th a sg a i n e db i gs u c c e s si no n e t o o n ea p p l i c a t i o ns u c ha sr e l i a b l ef i l e t r a n s f e ra n di n s t a n tm e s s a g es e r v i c e r e c e n ty e a r s ，t h er e q u i r e m e n t so ns h a r i n go f s t r e a m i n gd a t a a r ei n c r e a s e d s h a r p l y t h e s er e q u i r e m e n t sh a v ef o s t e r e dt h e e m e r g e n c eo fn e wa p p l i c a t i o n st h a ta r ei n h e r e n t l yo n e t o m a n y t h em u l t i c a s ti st h e b e s tw a yt os h a r et h ed a t aa m o n gu s e r s o nt h eo t h e rs i d e ，s e v e r a ld r a w b a c k sc a u s e i pm u l t i c a s ti s n tw i d e l yd e p l o y e da n d g 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 e a v e r a g ee n du s e r s t l l i sc o n t r a d i c t i o nd r i v e sr e s e a r c h e r st ot u r nt oa l la l t e r n a t i v e m u l t i c a s tm e c h a n i s m ：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 ) b u ti na l m ，t h et r e ea n d t r e e - b a s e ds t r u c t u r ew h i c ha r eu s u a l l yu s e df o rc o n t e n td e l i v e r yh a v ei s s u e s i n r o b u s t n e s s ，t i m ea n dc o n t r o lo v e r h e a df o rr e c o v e r yf r o mf a i l u r e ，a n db o t t l e n e c ko f b a n d w i d t hu t i l i z i n g i nt h i st h e s i s ，an o v e la p p r o a c hf o rc o n s t r u c t i o no fr o b u s t d e l i v e r ys t r u c t u r ef o r a p p l i c a t i o nl a y e rm u l t i c a s tu s i n gh o n e y c o m bs t r u c t u r eh a sb e e np r o p o s e d t h i s a p p r o a c hf o c u s e so ns i n g l es o u r c ea u d i o v i d e os t r e a m i n go ni n t e m e t i no u r h o n e y c o m ba p p r o a c h ，a l la l g o r i t h mi su s e df o rc l u s t e r i n gp a r t i c i p a n tn o d e si n t oa s t a b l eh o n e y c o m b - b a s e dd e l i v e r ys t r u c t u r e ，a n du t i l i z i n gt h en a t u r e s t a b i l i t yo f h o n e y c o m bs t r u c t u r et ol e tf a i l u r er e c o v e r yt ob ed o n el o c a l l ya n dq u i c k l yw i t h i m p a c to n l yo nas m a l ln u m b e ro fn o d e sw i t hn ob u r d e no nt h es o u r c es e r v e r b a s e d o nt h eh o n e y c o m ba p p r o a c h ，a n o t h e r a l g o r i t h mi sp r o p o s e df o re f f i c i e n t l yu s i n gt h e s e n d i n gc a p a b i l i t ya n dd o w n l o a d i n gc a p a b i l i t yo fe a c hn o d eb ye x c h a n g i n gs u i t a b l e n o d e s p o s i t i o ni nd e l i v e r ys t r u c t u r e f u r t h e r m o r e ，an e ww a yt os i m u l a t et h ea u p r o t o c o l sb a s e do nn s 2a n db r i t e h a sb e e nr e v e a l e d f o re v a l u a t i n gt h ep e r f o r m a n c eo fh o n e y c o m ba p p r o a c ho n s t a b i l i t ya n df a i l u r er e c o v e r y , ac o m p a r i s o nh a sb e e nm a d eb e t w e e nt h eh o n e y c o m b a p p r o a c h a n dt w oo n s h e l fa l mp r o t o c o l s ：d e g r e e c o n s t r a i n e d s p ta n d d e g r e e c o n s t r a i n tm s t w i t hap o p u l a ra p p r o a c hf o rf a i l u r er e c o v e r yi na l m a p p l i c a t i o n ：s p t - g r a n d f a t h e ra p p r o a c h ，a n dw i t ha ni n h e r e n ta p p r o a c hf o rt a c k l i n g t h ep r o b l e mo fs t a b i l i t yi na l m ：k t r e e a n o t h e rs i m u l a t i o nh a sb e e nm a d ef o r e v a l u a t i n gt h ei m p r o v e m e n to nb a n d w i d t hu t i l i z a t i o nb yu s i n gt h ea l g o r i t h mw h i c h i i 上海大学硕士学位论文 ! 坠宝q ! ! 唑墅兰q i ! ! 型i 2 望垡墨皇磐吐墅型璺i 竖i 盟 i sp r o p o s e di nt h i st h e s i s f i n a l l y , as t a b l ea l mp l a t f o r mb a s e do nh o n e y c o m ba p p r o a c hh a sb e e nd e s i g n e d ； m a n yk i n d so fa l ma p p l i c a t i o n sc a nb ei m p l e m e n t e db a s e do na p i ss u p p o r t e db y t h i sp l a t f o r m f o re v a l u a t i n gt h ef u n c t i o n a l i t yo fs t a b l ea l m p l a t f o r m ，ap r o t o t y p e o fa l m a p p l i c a t i o nf o rn t tf u t u r ei n n o v a t i o nl a b s i - v i s t op r o j e c th a sb e e n i m p l e m e n t e d t h ep e r f o r m a n c eo fp r o t o t y p es y s t e ms h o w st h a tt h ea p p r o a c hw e p r o p o s e di sr e l i a b l ea n de f f i c i e n t k e y w o r d s ：h o n e y c o m b ，o v e r l a yn e t w o r k ，i pm u l t i c a s t ，a p p l i c a t i o nl a y e rm u l t i c a s t ， n e t w o r ks i m u l a t i o n i i i 上海大学硕士学位论文 ! 垒曼q ! ! g 翌坚坚型宝旦i ! ! ! 旦堕坐i 2 翌2 1 苎堕垒璺g 垒璺i 竺望i ! 翌韭y 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 8 图3 9 图3 1 0 图3 1 l 图3 1 2 图3 1 3 图3 1 4 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图索引 组通信的基本方法 7 i e e e8 0 2 3 物理地址结构( a ) 和p 多播地址( b ) 9 p 多播地址向物理地址的映射( a ) 和物理地址的不唯一性( b ) 9 口多播( a ) 和应用层多播( b ) 1 1 应用层多播的性能评价标准：链路压力和展度 1 3 应用层多播协议的分类 1 5 a l m i 的体系结构1 5 n a r a d a 拓扑结构和协议中的基本功能 1 6 n i c e 应用层多播协议 1 8 节点失效导致的多播树分割 2 0 基于蜂窝结构的覆盖网络和其中的数据转发路径 2 2 六边形网络中的不同数据转发方式2 3 基于蜂窝结构覆盖网络的生长方式 2 4 加入过程中的节点状态变化 2 5 节点加入算法l ：n e w n o d ej o n 例流程图 2 6 节点加入算法2 ：s o u r c e n o d e 流程图 2 8 _ d e t e r m i n e ( s ) 节点加入算法3 ：o v e r l a y n o d e ) 流程图 31_determine(n 节点失效恢复算法流程图：失效恢复请求的发起 3 3 节点失效恢复算法流程图：失效恢复请求的响应 3 4 基于蜂窝结构覆盖网络中节点位置的交换 3 8 数据转发网络吞吐率改善算法流程图 3 9 数据转发网络吞吐率改进算法的应用4 0 i n t e m e t 的拓扑结构( a ) 和t r a n s i t s t u b 模型( b ) 4 3 n s 2 中两个应用层代理之间的数据传递过程 4 4 n s 2 修改部分的类图 4 5 蜂窝结构数据转发网络和m s t 以及s p t 在健壮性上的对比，节点数量为1 0 0 05 0 蜂窝结构数据转发网络和k 树在健壮性上的对比，k 值为2 ，3 和4 ，节点数量为 5 0 05 2 蜂窝结构数据转发网络和k 树在健壮性上的对比，k 值为2 ，3 和4 ，节点数量为 1 0 0 05 2 蜂窝结构数据转发网络和k 树在健壮性上的对比，k 值为2 ，3 和4 ，节点数量为 1 5 0 05 3 蜂窝结构数据转发网络和k 树在健壮性上的对比，k 值为2 ，节点数量分别取5 0 0 ， 1 0 0 0 和1 5 0 05 4 蜂窝结构数据转发网络和使用祖父节点备份算法的s p t 在健壮性上的对比，s p t 中节点度取值为 2 ，4 】，节点数量为1 0 0 0 5 5 基于蜂窝结构覆盖网络的应用层多播协议与结合祖父节点备份算法的s p t 应用层 多播协议在失效恢复时间上的比较，节点数量为 1 0 0 ，5 0 0 ，失效概率为1 0 5 7 当节点数量为 1 0 0 ，1 0 0 0 ，失效概率分别为1 0 和2 0 的时候，基于蜂窝结构覆 v i 上海大学硕士学位论文 ! 堕曼里q ! 堡匹! 堕竖! 丝旦i ! ! ! ! 哇型i 旦翌旦! 照竺g 垒垒i 堕旦i ! ! 塑丛! 盖网络的应用层多播协议在节点失效恢复时间上的比较 5 8 图4 1 2 基于蜂窝结构覆盖网络的应用层多播协议与结合祖父节点备份算法的s p t 应用层 多播协议在失效恢复控制开销上的比较，节点总数为5 0 0 ，失效概率为1 0 6 0 图4 1 3 对数据转发网络吞吐率的改进算法 6 2 图5 1 应用层多播平台的系统层次结构 6 4 图5 2基于蜂窝结构覆盖网络的应用层多播服务模块类图 6 5 图5 - 3覆盖网络模块的两个组成部分 6 6 图5 4覆盖网络模块类图 6 7 图5 5覆盖网络中p 2 p 应用层路由协议c h o r d 的实现类图 6 7 图5 6通信服务模块类图 6 8 图5 7通信服务模块中t c p 通信实现类图 6 9 图5 8系统原型服务器端类图 7 0 图5 9 视频采集工作流程 7 1 图5 1 0 系统的原型在服务器端的运行情况 7 4 图5 1 1 系统的原型在客户端的运行情况 7 4 v i i 上海大学硕士学位论文 ! 坠壁旦q ! ! 翌曼垒丛璺蝗旦i ! ! 曼型i 旦翌q ! 墨垒璺坠g ! 逝竺翌堑箜韭y 表3 1 表3 2 表3 3 表3 4 表3 5 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表4 9 表索引 加入算法1 ：n e w n o d ej o i n ( s 3 2 6 节点加入算法2 ：s o u r c e n o d ed e t e r m i n e ( s ) 2 9 节点加入算法3 ：o v e r l a y n o d ed e t e r m i n e ( n ) 3l 节点失效恢复算法：失效恢复请求的发起 3 5 节点失效恢复算法：失效恢复请求的响应 3 6 用于仿真的硬件平台 4 2 b r i t e 中的主要参数配置 4 3 最小生成树、最短路径树、蜂窝结构健壮性比较仿真结果数据 4 9 k 树与蜂窝结构健壮性比较仿真结果数据 5 1 最短路径树、采e h 祖父节点备份算法的最短路径树、蜂窝结构健壮性对比仿真结 果数据 5 5 采用祖父节点备份算法的最短路径树和蜂窝结构平均失效恢复时间对比仿真结果 数据 5 6 节点失效概率1 0 及2 0 情况下蜂窝结构平均失效恢复时间对比仿真结果数据5 8 采用祖父节点备份算法的最短路径树与蜂窝结构平均失效恢复控制开销仿真结果 数据 5 9 数据转发网路吞吐率改善算法仿真结果数据 6 l v i i i 上海大学硕士学位论文 ! 坠曼里q ! 堡匹! 堕竖! 丝旦i ! ! ! ! 哇型i 旦翌旦! 堕竺g 垒垒i 型旦i ! ! 塑巫! 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 签名： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 畔蛐飙删 上海大学硕士学位论文 ! 垒曼旦墅兰受墅叁望蝗旦i ! ! ! ! 塑垒2 翌q ! 兰塾璺望吐璺i 竺翌叠堡变丛z 第一章绪论 今天，互联网在一对一模式的应用方面已经取得了巨大的成功，点对点的 可靠文件传输和即时消息服务大量涌现并被广大用户所青睐。相比过去，由于 硬件设备价格的不断下降和网络带宽的不断增加，越来越多的视频和音频等个 人多媒体数据在互联网上被广泛传播，人们希望可以在任何时候都可以通过互 联网选择和观看他们喜爱的流媒体内容，这些趋势加速了本质上一对多模式的 互联网应用的产生。对于这类应用最简单的解决方案是客户端n 务器模型。但 是，由于服务器端的有限出口带宽，瓶颈问题是不可避免的，大量的客户端会 给服务器带来巨大的负担，导致服务质量下降。m 多播是一种将i p 数据包发送 给一组接收者的有效方式，这是因为在m 多播中，一个d 数据包将在多播路 由器中被复制并转发，这种途径可以大大减少在服务器端和传输链路上的带宽 使用。但是由于i p 多播自身的一些限制和不足，导致了口多播不能在互联网 上大规模部署，具体主要有以下几个原因： 首先，口多播需要支持i p 多播功能的路由器被部署在各个层次的网络 上，对于互联网服务提供商( i s p ) 来说是一笔巨大的开销；另外，单 个口多播路由器需要保存多播组的所有成员信息和多播组的状态信 息，当多播组成员数量快速增长时，口多播路由器将限制i p 多播的可 扩展性；以上两点原因都阻碍了m 多播在互联网上的大范围部署。 其次，一些管理和安全问题仍然困扰着i p 多播的大范围部署，例如多 播组的分布式管理，多播地址的分配问题，多播网络的管理问题，多播 网络中黑客洪泛攻击的防止和多播服务收费等等。 最后，在口多播中提供可靠的服务和服务质量的保证是非常困难的。 尽管很多协议被提出用于解决这些问题，但是异构的网络环境和异质的 用户需求阻碍了可扩展的反馈机制的实现，进而阻碍了p 多播的大范 围部署。 另外一方面，应用层多播自从被提出以来就得到了大量研究者和商业机构 的重视。在应用层多播中，多播功能从网络层被转移到了应用层【2 8 1 ，数据转发 网络中的节点从它的父节点得到数据并使用，同时将数据转发给它的所有子节 点。因为多播功能是在应用层上被实现的，多播服务、数据复制和转发作为一 个应用在终端计算机上运行，避免了多播路由器的使用，所以它比口多播的扩 展性更强。这个明显的优势可以让应用层多播比较容易地支持大量的数据接收 者；另外，如前所述，应用层多播不需要使用特殊的多播路由器，从而不需要 上海大学硕士学位论文 ! 塾宝q ! 垒翌翌型竺型宝旦i ! ! ! ! 哇型i 2 翌2 1 苎垒璺璺g 丛墅堕坠i ! ! ! 堕重! y 对物理网络进行任何改变，所以它可以很容易和迅速地被部署在互联网上。但 是，应用层多播会导致同一个数据包及其副本在一条通信链路上被多次传递， 消耗了比m 多播更多的带宽；相比口多播，由于应用层多播建立的数据转发 树不是最优的，容易带来较高的服务器端到终端用户的端到端延时。 近些年来，许多基于对等网络的应用层多播协议和多播系统被提出和实现， 在互联网上取得了巨大的成功。在这些协议和系统里面，参与多播的节点从网 络层被映射到应用层上，自发组织成一个覆盖网络，进而在这个覆盖网络上形 成一个或若干个大规模的数据转发树用来转发数据。 1 1 研究目的及意义 现如今，通信领域的快速发展伴随着硬件价格的不断下降和网络通信带宽 的不断增加，越来越多的人们通过互联网连接到了一起，并享受由i s p 提供的 各项服务。快速更新的硬件设备使得开发者可以为终端用户设计和实现更激动 人心的互联网应用，例如在线摄像头，视频会议，网络游戏和网络电台等等。 一些基本的，但却至关重要的需求往往与这些应用联系在一起：一到多的数据 分发能力，较高的带宽需求，低延时和偏差，以及应用的可靠性。 尽管d 多播已经被提出了很多年，并被证实是一种非常有效的数据分发方 法，但是截止到目前，i p 多播由于技术上、管理上和商业上等很多原因的阻碍， 迟迟不能被大范围地部署到全球的计算机网络上。 应用层多播是另外一种可行的数据分发方法，它将多播功能从网络层转移 到了应用层，通过在属于一个多播组的节点间建立应用层上的数据转发网络来 达到多播的目的。最近，针对应用层多播的研究主要集中在多播协议的设计上， 许许多多的应用层多播协议被研究者们提出用来满足可扩展性，资源利用率和 低延时等需求。 可靠性是绝大多数实时性应用需要关心的主要需求之一，应用层多播也不 例外。而且在某种程度上，这个需求在应用层多播的应用中是一个非常重要的 问题，因为数据转发网络中的节点可以自由的加入和离开，给多播系统带来不 稳定性。现有的应用层多播协议可以根据数据转发网络的类型被粗略地分为基 于树结构的多播协议和基于网状结构的多播协议两种。基于树结构的多播协议 由于具有实现简单、带宽利用效率较高等特点被广泛应用在现有的应用层多播 系统中。如果任何一个数据转发树中的非叶子节点主动或者被动离开，数据转 发树将被一分为二，处于断点下面的节点将无法从数据转发树中得到数据。尽 管对于网状结构来说，所有节点被一分为二的可能性很小，但也不是不可能的。 2 上海大学硕士学位论文 ! b 兰2 1 生l 墅坚垫堂宝旦i ! ! ! i ! 堕i q 望2 1 兰垒垒翌g 皇堑型巫! 登堑y 通常，基于网状结构的多播协议会在加入多播组的所有节点之上建立一个生成 树，利用这个生成树进行数据转发。如果生成树中的节点主动或者被动离开， 该多播协议就需要利用很多的时间来重建这个生成树。在现有的应用层多播协 议中，这个重要的问题一直没有被很好地解决。 综上所述，在应用层多播这个研究领域，多播应用的稳定性，即数据转发 网络的可靠性以及如何适应节点的动态行为是非常有价值和有必要的研究内 容。 1 2 国内外研究现状 在对应用层多播的研究中，国内外大量学者做出了很多非常有意义和建设 性的工作。大多数研究者都把精力集中在应用层上数据转发网络的建立。近几 年，许多关于如何建立数据转发网络去更有效地分发流媒体数据的应用层多播 协议【2 6 】被提出。 a l m i 9 】是一种集中式的应用层多播协议，a l m i 需要部署一个中央控制节 点用来接收来自终端的请求，并负责根据终端的一些性能参数建立数据转发树。 很明显，中央控制节点的负载会因为终端用户的增加而加重，所以该协议仅适 用于小型的、少量终端客户的多播应用。 e s m 2 4 类似于a l m i ，也是适用于小型多播组的一种应用层多播协议。在 e s m 中，多播组内的终端之间定期交换成员和路由信息，在所有的终端间根据 某些测量值在应用层上建立一个网状结构，然后通过运行分布式距离向量协议 建立一个数据转发树。 在加入多播组的终端数量较多的情况下，分布式应用层多播协议相比集中 式应用层多播协议具有更好的可扩展性。一般来说，分布式应用层多播协议可 以根据数据转发网络的特点被分为网状结构优先协议【8 1 【1 0 】【13 1 ，树结构优先协议 和一些基于特殊结构的协议 5 】【2 5 】。 n a r a d a 【4 】是一种网状结构优先协议。该协议使用一个自组织的覆盖网络来进 行数据转发。n a r a d a 通过两个步骤来建立数据转发树：首先，在每个多播组的 所有成员间建立一个网状结构覆盖网络，然后，n a r a d a 在此基础上建立一个生 成树用来从多播源向其他节点转发数据。该协议的网状结构覆盖网络建立和维 护算法假定多播组内的所有成员都必须知道每个节点的信息，所以该协议不能 支持中到大规模的多播组。 o v e r c a s t i t 4 提出了一种简单的数据转发树生成算法用来适应多变的网络状 态。像口多播一样，o v e r c a s t 允许数据一次性被转发到所有的终端。数据包会 3 一| ：海大学硕士学位论文 ! b 曼q ! ! i 翟翌竖! 坠璺苎曼旦i ! ! ! 兰塑垡q 望q ! 墨垒璺望g 垒垒i 型璺坌! ! 翌i 丝 在数据转发网络中合适的节点被复制，来减少同时转发到多个终端所需要的带 宽。该协议还引入了缓存和服务器复制机制，通过在网络中建立多个缓存和服 务器来更好的转发数据。与n a r a d a 类似，o v e r c a s t 建立一个以多播源为根节点 的树状数据转发网络，在建立时，通过对一些端到端参数的测量来在多播源和 多播组成员之间优化带宽的利用。 n i c e 6 】和z i g z a g 7 】试图通过建立一个层次化的数据转发网络来减少控制 开销，这两个协议都是为了适用于大规模的应用层多播而设计，在获得支持大 用户量的同时，尽量使用较少的带宽。在n i c e 中，所有的多播组成员递归性 地加入一个位于应用层上的、层次化的覆盖网络，该覆盖网络在结构上隐含了 一个数据转发树，n i c e 可以同时支持多个多播源，而z i g z a g 仅支持一个多 播源。z i g z a g 同样将多播组中的所欲成员映射到一个层次化的覆盖网络中， 在z i g z a g 中，区域的控制头节点和多播头节点是两个不同的节点，这种设计 可以避免n i c e 协议中容易在靠近多播源的位置产生瓶颈的问题，也可以容易 地从头节点失效中恢复。 在y o i d 1 1 】中，每个参与多播的节点都负责为自己查找和选择父节点。所以， y o i d 建立数据转发树不需要事先建立一个网状结构的覆盖网络。y o i d 协议向 成为一种通用的数据分发工具包发展。 s c r i b e ( 1 2 】是一个可扩展的应用层多播架构，该协议是基于特殊结构数据转发 网络的应用层多播协议，可以同时支持大量多播组，每个多播组又可以支持大 量用户。s c r i b e 建立在p a s t r y 之上，后者是一个部署在互联网上的、通用的、 基于p 2 p 的对象查找和数据路由覆盖网络。利用p a s t r y 的可靠性，自组织性和 对象查找能力，s c r i b e 通过对成员间关系的管理在p a s t r y 上建立一个数据转发 树来在多播组内转发消息。 最近，由于节点被动或主动离开而引发的数据转发网络可靠性问题逐渐被 研究者们关注【1 4 】 1 6 】【1 9 】【2 1 】【2 7 】。当数据转发树由于节点失效而被分割后，多数应用 层多播协议的做法是立即重建该数据转发树。 p r m 1 6 】使用一种前摄的方式重建被分割的数据转发树。该协议引入了随机 游走的方法来选择备份节点，该方法会持续产生冗余的数据包，并在随机选择 的备份路径上传送，以备在节点失效恢复时使用。 h b m 1 8 】通过在数据转发树上显式地增加冗余连接来解决数据转发网络的 可靠性问题。在h b m 中，一个集合节点( r e n d e z v o u sp o i n t ) 得到所有终端节 点的信息，然后根据这些信息建立一个优化过的数据转发树。h b m 通过增加冗 余连接来避免数据转发树的单点失效问题。然而，这个方法对于没有增加冗余 连接的部分仍然没有改善。 4 上海大学硕士学位论文 ! 堕曼旦竺望皇匿! 虫堕曼旦i ! ! 旦哇型i 垒翌2 1 兰丛璺翌趾垒i 望璺坠堡壁韭z k 树【2 0 】提出了一种新的数据转发树构建方法，用来建立一个本质上健壮的 数据转发网络来减少节点失效带来的影响。k 树创建了一个度平衡的数据转发 树，该树中的每个非叶节点都有相同的度，这样可以减少由于某个节点失效而 导致与树干脱离的节点数量。 s p l i ts t r e a m 1 5 】利用一种叫做m u l t i p l ed e s c r i p t i o nc o d i n g 的编码技术将流媒 体数据流分割成若干条，对每一条建立一个数据转发树，即使受其他节点失效 影响的节点不能从某一个数据转发树得到数据，它可以从其他数据转发树得到 所缺少的数据。 1 3 主要研究内容 本文主要讨论了以下研究内容： 第一，总结了应用层多播的发展过程；分别讨论了i p 多播、应用层多播的 优点和缺点，并在两者之间进行了详细的比较；指出了存在于目前广泛使用的 应用层多播协议中数据转发网络存在的健壮性差和节点失效代价较高的问题。 第二，应用蜂窝结构网络到应用层多播中，利用蜂窝结构网络作为应用层 多播中的数据转发网络来替代树或基于树的数据转发网络。对蜂窝结构网络的 特点从图论的角度给予了详细的分析。给出了在应用层上建立蜂窝结构数据转 发网络的具体算法，以及节点失效恢复的具体算法。使用大量的仿真实验评估 了该协议在数据转发网络健壮性和节点失效恢复代价两个方面的性能，通过对 仿真结果数据的分析，验证了基于蜂窝网络结构的应用层多播协议在这两个方 面是有效的，可靠的。 第三，给出了一种数据转发网络吞吐率改善算法。利用该算法可以有效地 提高节点的带宽利用率，从而改善整个数据转发网络的吞吐能力。 第四，基于该协议，设计和实现了一个应用层多播服务平台。该平台提供 了应用编程接口，利用这些接口可以快速地、容易地在互联网上实现单源的多 播应用。由于采用了层次化和模块化设计，该平台具有很强的兼容性和扩展性。 第五，基于应用层多播服务平台，为n t t 未来网络研究所i - v i s t o 项目设计 和实现了一个视频应用层多播系统的原型。 第六，给出了一种新的、基于n s 2 和b r i t e 的应用层多播仿真方法和平台。 1 4 论文的组织 本论文包括以下六个部分： 5 上海大学硕十学位论文 ! 塾里呈q ! 生翌璺堕竺型曼旦i ! ! 呈! ! 型i 2 翌q ! 墨垒垒坠g 垒垒i 望璺坌，旦韭y 第一章是整篇论文的简介，在一个较高的层次总结了本文的研究，指出了 研究的动机；总结和分析了国内外学者在应用层多播领域的研究现状和存在的 问题，以及一些针对本文指出的问题的一些解决办法。在第一章的最后，总结 了本文的贡献。 第二章主要讨论了应用层多播的发展过程，基本概念，并对一些典型的应 用层多播协议进行了分析。首先，对应用层多播的起源做了一些介绍，然后讨 论了应用层多播的一些基本概念和性能评价的方法，最后，讨论了三个典型的 应用层多播协议，分析了在这些协议中数据转发网络和节点失效恢复这两方面 存在的问题。 第三章主要详细讨论了存在于应用层多播协议中数据转发网络的可靠性问 题和节点失效恢复代价的问题并给出了基于蜂窝结构覆盖网络的应用层多播协 议用来作为解决这两个问题的方法。首先，分析了由于节点主动或被动离开而 给数据转发网络带来的可靠性问题以及受影响节点的失效恢复问题，然后给出 了基于蜂窝网络结构的应用层多播协议。最后，针对蜂窝结构网络给出了一种 改善数据转发网络吞吐率的算法，详细讨论了该算法的应用过程。 在第四章，大量仿真实验被用来评价本文给出的应用层多播协议在数据转 发网络健壮性和节点失效恢复代价这两个方面的表现。这章详细介绍了仿真平 台，仿真评价标准和仿真结果的分析。 在第五章，讨论了基于本文给出的应用层多播协议设计和实现的应用层多 播服务平台。利用这个平台，可以快速、容易地在互联网上实现和部署健壮的、 较少节点失效恢复代价的单源多播应用。作为研究的一部分，也为了在实际使 用中验证该协议的表现，基于这个平台实现了一个应用层多播系统的原型，在 第五章的最后作了详细的介绍。 在文章的最后是论文的工作总结和未来的研究方向。 1 5 小结 本章主要对本文的研究做了一个概述，指出了研究的动机。在本章中还总 结了许多应用层多播方面国内外学者的相关工作，分析了其他学者在应用层多 播这个研究领域中，针对如何建立健壮的数据分发网络和降低节点失效恢复代 价这两个主要问题的解决方法。 6 上海大学硕士学位论文 ! 鲢q ! 奠塑堂堂皇望i ! ! 塑堕i 2 翌2 1 塾垫吐垒i 竺翌i ! 旦垡盟 第二章应用层的多播 互联网的快速发展催生了大量一对多模式的应用，这些应用一般对带宽有 较高的要求，传统的服务端客户端模式不再适用于这种需求。为了有效地满足 这类需求，研究者们提出了i p 多播技术。 由于种种原因，p 多播还没有被部署在互联网上。随着p 2 p 文件共享应用 的大规模流行，研究者们尝试着在应用层上实现多播功能，这就是应用层多播。 在这一部分中，首先，将总结用于数据分发的一般方式；然后，将讨论口 多播的基本概念和缺点；随后会介绍应用层多播的基本概念，并将应用层多播 和p 多播进行对比；最后，会对三个典型的应用层多播协议进行讨论，包括具 体的性质，基本的运行机制和缺点。 2 1 数据分发的基本方法 目前在互联网上应用的数据分发方法与组通信方法是一致的。通常，数据 分发可以被分成两种类型：一对多型和多对多型。在组通信中，一个组是零个 或多个拥有唯一地址的终端的集合。组通信方法主要有四种，适用于从仅包含 两个终端节点的组( 单播和泛播) 到包含多个终端节点的组( 多播和广播) 。 o oo o o o ( d ) 广播 ( c ) 一对多型多播( d ) 多对多垄多播 图2 1 组通信的基本方法 单播( u n i c a s t ) 单播是互联网上两个主机间传递数据最基本的方法，用于一台主机仅向另 外一台主机发送数据。数据的接收端通过p 头中的目的地址来唯一区分，在单 播中没有组的概念。因此单播是一对一型通信模式，如图2 1 ( a ) 所示。 7 上海大学硕士学位论文 ! 坠曼q 墅墨羔! 鱼! 坠! 旦i ! ! ! ! 塑! i q 翌垒! 墨塾璺翌g 照垒i 望璺i 坚韭y 泛播( a n y c a s t ) 泛播是一种向一组主机发送数据时所采用的网络寻址和路由机制，但是只 有一台组中的主机可以接收到数据。在泛播系统中，一个目的地址代表了一组 主机，数据将会被转发到路由拓扑中被认为最近的或者最好的目的主机，距离 的远近或者主机的性能将被用来参与评价。泛播一般用于向无状态的数据服务 提供高可靠性和负载平衡，例如对一份数据的多个复制源进行访问。 广播( b r o a d c a s t ) 广播是一种向网络中所有设备发送数据的方法，在实际应用中，广播的作 用域被限定在了广播域中。一个广播地址代表了一个跟定网络或子网中的所有 主机。广播是一种一对多模式的通信方式，如图2 1 ( b ) 所示。广播通信典型 的应用是服务发现。 多播( m u l t i c a s t ) 多播用于同时向一组终端发送数据，使用最有效的策略使得数据包在一条 转发路径上仅经过一次。仅在通往终端节点的转发路径发生分叉的时候才对数 据包进行复制。在多播中，一个目的地址代表了一组终端节点，多播源和多播 组内节点的关系可以被分为以下两类： 一对多型( 1 t o m ) ：一个节点作为源节点，向多播组内的m 个接收节点发送 数据。源节点可以属于或不属于该多播组，如图2 1 ( c ) 所示。 多对多型( m t o n ) ：多个源节点向多播组中的多个接收节点发送数据。同样， 源节点可以属于或不属于该多播组。 2 2 i p 多播 多播是数据分发领域中的研究热点，研究者们认为在物理层的路由器上实 现多播功能是一个比较合适的选择，p 多播就是在这个背景下被提出的。 在p 多播中，多播源仅需要将数据包发送到多播的目的地址，该地址对应 了一组想要接收该数据包的主机。数据包在传播链路中合适的路由器上被复制、 转发，直到多播组中的所有成员主机收到该数据包为止。所有的数据转发路径 构成了一个多播树，对于多播树中的任一条转发路径，一个数据包仅通过一次。 因此，i p 多播具有较高的带宽利用率。 8 上海大学硕士学位论文 ! 垒皇q ! ! g ! 里曼竺垒堕旦i ! ! ! 型i 2 翌旦! 兰垒垒望g 垒垒i 堕翌叠堕韭z 2 2 1 i p 多播的相关定义 i p 多播由s t e v ed e e r i n g 在1 9 9 8 年被提出，在1 9 9 2 年，m b o n e 被建立并用 于m 多播的研究。一个口多播系统主要包括三个部分：多播组的表示，多播 组内成员的管理和多播路由协议。 多播组的表示：在口多播中，一个目的地址对应了一组想要参与多播的主机， 地址2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 被指定用于多播地址，该地址范围被定义为“d 类地址”。当路由器收到带有此类地址的数据包时，路由器将负责复制和转发该 数据包到所有加入到该多播组的主机。多播地址的格式如图2 2 ( a ) 和( b ) 所 示。 图2 2i e e e8 0 2 3 物理地址结构( a ) 和i p 多播地址( b ) 由于大量的以太网物理地址被保留，所以地址中只有2 3 位用于口多播组地址。实际 使用中将i p 多播组地址的低2 3 位置接映射到物理地址中预留的2 3 位，如图2 3 ( a ) 所示。 由于i p 多播组地址的高5 位在映射中被丢弃，导致了映射后得到的物理地址不唯一。事实 上，3 2 个不同的多播组地址全部被映射到了同一个物理地址上，如图2 3 ( b ) 所示。 网。暨懋0 睁m a - d m o m ： s o l 嚣一r t - - 蕊4 = _ 奄 _ 一 淼嬲 三燕量夏 + 1 ；i 一+ 1 i j i + h m + i 葫r ” ( a ) 图2 3i p 多播地址向物理地址的映射( a ) 和物理地址的不唯一性( b ) 多播组中成员的管理：每个想参与多播的主机必须使用互联网组管理协议 ( i g m p ) 加入多播组，邻接的路由器也需要使用该协议相互通信。i g m p 协议 中没有寻找多播组地址的机制，所以在一个主机加入多播组之前，在该主机上 运行的多播应用必须知道该多播组的地址。 多播路由协议：p 多播中使用的路由协议在工作中主要有以下两个过程：一个 9 上海大学硕士学位论文 ! 坠旦! ! 逊虫坐堕! 塑生q 翌垡堕塑吐堑堕匹兰墅盟 过程发生在路由域内，另外一个过程发生在路由域间。在一个路由域内，p i m 或m o s p f 协议被用于路由；在路由域