试析P2P网络应用层多播树的建立及维护

　　试析P2P网络应用层多播树的建立及维护

　　关键词:P2P　应用层多播　多播树

　　摘要:本文主要研究了P2P网络应用层多播方案中建立和维护多播树的问题。采用单树结构的ALM建立方案，按照网络地址邻近的原则，并综合考虑节限制和服务能力的问题来获取父节点，构建一探低延迟、低连接压力的单源多播树，实现应用层多播。

　　0、引言

　　应用层多播树的建立和维护是P2P网络拓扑结构建立的关键。在PZP流媒体中，首要问题是将服务器和参与服务的节点组织成应用层多播(Application-Layer Multicast,ALM)树。多播树的建立算法将直接决定流媒体直播系统的连接效率。因此，有必要深人研究应用层多播树的建立和维护算法。

　　对面向Internet流媒体技术，最简单的解决办法是为每个申请者建立一条发送视频流的链接。但太耗费带宽，又不能支持大量观众实时收看，申请者接收到的将是低质量视频组播相对而言是一种好的解决方法，但Internet中多数ISP不支持IP组播，造成其发展受限。应用层组播克服了IP组播的缺陷:无需更改网络协议和网络设备的配置，在客户机间复制和转发数据，数据报沿逻辑链路转发，数据路由、复制、转发功能均由客户机完成，客户机间建立一个叠加在IP网络上、实现组播业务逻辑功能性网络，要实现这样的功能，就必须建立对应的应用层多播树。现阶段，已经有一些学者开始进行应用层多播树的建立的研究，并取得了一定的成果。

　　本文首先介绍P2F网络中应用层多播技术研究的相关工作，然后在比较现有多播树建立方案的基础上，设计出适用于P2P流媒体直播系统的应用层多播树建立和维护方案，并分析了其性能。

　　1、相关工作

　　应用层多播的研究，作为覆盖网络研究的一个方向，是国际上刚刚兴起的研究热点。很多大学和研究院都在进行这方面的研究。从2000年6月，卡耐基梅隆大学的Y.H Chu在ACMSIGMETRICS上发表了一篇端系统多播的论文开始，标志着应用层多播开始进人了热点研究。2001年Ratnasamy在ACMSIGCOMM上发表了基于Peer-to-Peer网络的应用层多播论文CAN Multicaste S.Q.Zhang也在NOSSDAV上发表了基于Peer-to-Peer网络的应用层多播的论文Bayeuxo 2002年，SumanBanerjee在ACM SIGCOMM上发表了基于 NICE应用层多播的论文。在这些论文中，研究学者都提出了自己的应用层多播实现思路，对应用层多播路由协议中多播树计算算法进行了研究。这些应用层多播方案具有不同的特点，适用的范围也不相同。其中对于Peer-to-Peer覆盖网络上的应用层多播研究还处于探索阶段。

　　目前在Peer-to-Peer网络上实现的应用层多播方案主要有三种;CAN Multicast,Scribe}Bayeux。它们都是在基于动态哈希路由的Peer-to-Pee:网络上实现的，其中CAN Multicast是在CAN之上实现的，Scribe是在Pastry上实现的，Bayeux是在Tapestry上实现的。这几种方案都充分利用了Peer-to-Pee:网络的路由机制，因此只需增加少量的模块就可以实现多播功能。与原先的Peer-to-Peer网络相比，只增加少量的开销就实现了多播功能，同时继承了Peer-to-Peer网络的支持大规模、支持成员动态变化的特性。可用于分布式仿真、多方实时游戏、大规模协作应用等，但这三种方案对于应用层多播的模型、性能分析、性能优化都没有进行研究。

　　2、应用层多播树方案分析

　　2.1单树结构的ALM方案

　　单树结构的ALM方案包含小规模的多源ALM方案和大规模的单源组ALM方案。小规模的多源ALM方案多应用于视频会议。将用户节点组成一个应用层mesh，周期性检查mesh中的连接质量，mesh上以数据源为根，根据带宽、时延各自构造生成树。可以针对每个源单独优化，每个成员维护一个组成员列表，可靠性高，但开销大，扩展性差。

　　大规模的单源组ALM方案中，最具代表性的就是NICE,Zigzag BALM树构建方案。两者的思路都是”分层”(Hierarchi-cal),”分群”(Cluster)，成员只和少量固定数目的节点联系。NICE(如图1)的维护管理具有分布性和自治性，节点的维护负载较轻，且节点的退出只影响局部节点，不影响根节点。缺点是层次越高的节点负载越重，如最高层的节点的度数达到(logN)，当系统规模很大时，这会成为系统的瓶颈。

　　Zigzag(如图2所示)与NICE相似，两者在每个节点的平均维护负载都为。闪，树的高度都为0(logN)。但Zigzag解决了NICE存在的瓶颈问题。其改进点为:Zigzag中Clusfe:的管理和数据分发由不同节点完成，而NICE将两功能统一在一个节点上。改进后，多播树中节点所带子节点数目最多为0(k2)，与参与多播树的节点数目无关。、

　　3.2节点离开和失效恢复算法

　　由于网络的动态特性，每个节点都处在不稳定的状态，随时有可能退出P2P网络。在节点的退出方式上，可以分为正常退出和非正常退出。无论节点是哪种方式退出，都会影响到P2P网络直播。因此，我们需要在节点退出后进行节点失效恢复。在本系统中，每个节点除了保存父节点和子节点的信息，同时还保存自己的备用父节点的信息，当父节点离开时可以便捷的用备用父节点代替父节点。对于正常的退出，节点离开恢复算法如下:

　　1)节点向服务器发送退出消息，同时，节点还向所有的直接子节点发送退出消息。

　　2)子节点在接收到该退出消息后，立刻搜索其资源信息表，获取备用父节点的IP地址及端口号，尝试与其建立连接。

　　3)若备用父节点仍然存在于网络中，并可提供服务，则用备用父节点替代父节点继续提供媒体数据服务，并向服务器发送消息，申请新的备用父节点。

　　4)若备用父节点已经离开网络或由于直接子节点数达到上限等原因不可提供服务，则向服务器发送重新连接请求，由服务器按照新节点加人算法提供新的父节点和备用父节点信息，重新加人到P2P网络中。

　　由于每个节点都有缓存，提前缓存了一部分流媒体数据，因此断开的短时间内，播放器可以继续播放。如果能快速恢复连接，继续接收流媒体数据，则不会影响到播放质量和效果。如果在短时间不能恢复连接，则需要等到恢复连接后才能继续播放。

　　对于非正常的退出，不妨假设节点C非正常退出。在正常情况下，节点C和节点B,I),E每隔两秒发送消息以确定对方是否还在网络中存活。当节点C在某个时刻非正常退出，节点B,D;E最迟在两秒之后就会发现节点C已经死亡。由于在本系统中，每个节点都保存着自己的父节点、备用父节点和儿子节点的信息，不妨假定节点B为节点D和E的备用父节点，所以节点D和E也保存着节点B的信息。于是节点D和E在发现C已经死亡后，就会向节点B发送连接请求，由B代替C继续提供服务。同时，节点B代替节点C;向服务器发送节点C退出的信息。

　　4、系统性能分析

　　在网络流媒体播放系统中，对于整个系统具有重要影响的因素主要是时间延迟、网络带宽、服务器处理能力、部署难易度和扩展能力等。我们就此分析一下基于P2P的流媒体直播系统。

　　1)对于服务器的处理能力和带宽的要求。由于本系统中，服务器只是对外提供两路单播流媒体，对于300kbp/s的流媒体来说，服务器只需要具有大于600kbp/s的带宽即可以满足需求。对于服务器的处理能力，当前的机器一般都具有足够的内存和处理器能力满足提供两路流媒体单播的能力。

　　2)对于部署的情沉。由于在本系统中，各个Pee:都具有TCP / IP网络通信的能力，因此只要节点能与互联网进行连接，就可以很方便地加人该系统，不存在部署的问题。

　　3)对于扩展的情况。，由于本系统采用的是P2P模式，流媒体主要是在Pee:之间进行通信和传输，对于服务器端几乎没有什么影响。因此，本系统具有很高的扩展能力。

　　4)关于时间延迟。由于在本系统中，每个Peer在播放之前需要缓存一段时间的流媒体数据，这就会导致用户看到的流媒体不是实时的数据，因此实时性稍差。对于大规模的网络流媒体播放系统，我们比较ClS模式、IP组播和P2F’模式这三种模式下各种因素的影响情况。

　　从上表1可知，P2F’网络流媒体播放系统对网络带宽和服务器处理能力的要求都比较低，同时还具有容易部署和扩展能力高的特点，但是同时也具有时间长的缺点。对于实时性要求不高的流媒体直播，在综合考虑各种因素的情况下，该系统是一个具有较高性价比的大规模流媒体直播解决方案，可以在将来提供更好的网络流媒体播放服务。

　　5、小结

　　本文主要研究了P2P网络上的应用层多播方案中建立和维护多播树节点的问题。建立一棵多播的共享树，主要问题是节点如何加人到树的操作和父节点的选取。本系统采用单树结构的ALM建立方案，按照网络地址邻近的原则，并综合考虑节点限制和服务能力的问题来获取父节点，构建了一棵低延迟、低连接压力的单源多播树，实现了应用层组播。