一种基于CPN的应用层组播模型
魏文红1，胡选子2，王文丰3
(1．华南理工大学电子与信息学院，广东 广州，510640；
2．东莞职业技术学院计算机系，广东 东莞，523808；
3．南昌工程学院计算机科学与技术系，江西 南昌，330099)
摘要：对于一个高性能应用层组播系统的构建，关键部分是如何建立稳定的组播数据分发树和实现能够适应网络的动态变化。CPN是一种具有小世界特征的P2P覆盖网络，本文充分利用CPN分组的特点，提出多根组播源、多会话的应用层组播模型CPN-Multicast，该模型利用分组间相互提供冗余服务，具有良好的容错性能。实验结果表明：CPN-Multicast模型具有较高的性能和可扩展性、较好的健壮性，满足大规模网络中大内容传播的需要。
关键词：对等网络；覆盖网络；应用层组播；小世界
中图分类号：TP393.02 文献标志码：A 文章编号：1672-7207(2011)S1-1084-06
Application-layer multicast model based on CPN
WEI Wen-hong1, HU Xuan-zi2, WANG Wen-feng3
(1. School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510640, China; 2. Department of Computer, Dongguan Polytechnic, Dongguan 523808, China;
3. Department of Computer Science, Nanchang Institute of Technology, Nanchang 330099, China)
Abstract: For building a high-performance application-level multicast system, the key part is how to construct a stable distribution tree and adapt to network dynamics. CPN is a Peer-to-Peer overlay network with small world characteristic, the features of CPN grouping were utilized to propose an application-layer multicast model of multiple multicast source and multi-session, which uses each group to provide redundant services and perform good fault tolerance. The results show that CPN-Multicast has high performance, expansibility and good robustness to meet the demands of transmitting of large files on large scale networks.
Key words: Peer-to-Peer; overlay network; application-layer multicast; small-world
近年来，随着P2P Network和Overlay Network 等技术的提出，出现了“应用层组播”(ALM，即Application-layer multicast)这样一个研究方向[1]。它的主要思想是保持Internet原有的“单播、尽力发送”模型，尽量不改变原来网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。由于对网络本身的改变很少，应用层组播具有很好的灵活性。当前应用层组播中的系统框架和很多细节技术还在研究当中，还有很多问题如带宽利用率、扩展性和可靠性等未得到很好的解决，这些问题的存在为应用层组播 的研究提供了广阔的空间。媒体编码技术、P2P和Overlay Network等技术的发展对应用层组播的研究也有很大的促进作用。
基于P2P覆盖网络的应用层组播方案在覆盖网络的构造方面较其他的应用层组播方案有优势[2]。首先，P2P的DHT协议本身可以使参与节点自组织成一个大规模的、支持成员动态变化的、鲁棒性好的覆盖网络，P2P网络还对上层的应用屏蔽了下层物理网络的各种特性；其次，P2P网络协议具有通用性，因此，可在P2P网络上实现具有不同特性的应用层组播方案。当前为了支持大规模的组播应用，减小建立和维护开销以及增加鲁棒性，研究人员早已提出建立在特定逻辑结构上的(DHT-based)应用层组播。代表是CAN-Multicast[3]，Scribe[4]和Bayeux[5]，其中CAN- Multicast是在CAN上实现的，Scribe是基于pastry实现的，Bayeux是在Tapestry上实现的。通过基于DHT的覆盖网络，可以将大规模的节点按照特定的逻辑关系有效的组织起来，在其上建立源驱动或接收端驱动的组播树。组播协议不需要进行复杂的成员管理和维护，而由底层维护P2P的覆盖网络完成。
为了向结构化的P2P DHT引入小世界特征，魏文红等[6]提出一种基于小世界网络的对等网络模型CPN (Cayley P2P Network)，并设计了适应于动态变化的P2P网络DHT协议。CPN具有较高的聚集系数与较短的路由长度，符合小世界网络的定义，并且支持显式分组功能，能够实现高效的资源搜索服务，可以很方便地提供浏览服务。本文作者以CPN为基础，结合P2P覆盖网络应用层组播技术，提出一种基于CPN的应用层组播模型。
1 组播模型CPN-Multicast
对于一个高性能应用层组播模型的构建，关键部分是如何建立稳定的组播数据分发树和实现能够适 应网络的动态变化。魏文红等[6]提出的CPN覆盖网络符合小世界网络的定义，具有较短的路由长度、较高的聚集系数、鲁棒性和冗余性，并支持显式分组，很适合应用于构建适应网络动态变化的大规模组播模型。本文作者利用CPN覆盖网络作为底层，构建一个多根组播源、多会话的高效应用层组播模型CPN- Multicast。
1.1 基于多根源组播的方式
CPN-Multicast组播模型利用CPN覆盖网的分组功能，在CPN覆盖网络的DHT协议中定义：每一个对等点标识符由一对唯一的二元组(c, r)组成，c和r满足：
CPN DHT中对等点标识符共2d+r位，采取后序匹配的方式。其中cd-1cd-2…c1c0为顶点标识符，d位*取值为0或1，作为资源标识的一部分。整个2d位表示为资源键值，r为分组标识符，通过二元组(c, r)就可以在CPN DHT中定位到所需的资源，而且可以通过设定资源的r域，显式将资源分组。
在CPN-Multicast中，将r域标识为一个组播分组。在每一个组播分组中，设置
为根节点，并将其作为组播源，为组内节点提供组播服务。这样，r个组播分组可以对应r个组播根源，并且每一个组播根源提供一致的组播服务。多根源的好处有：(1)可以为所在组内节点提供服务，也可以为其他分组提供冗余服务，对维护组播系统的鲁棒性具有很大的作用；(2)当多个分组间出现负载不均时，可以动态地调整新加入节点到其他负载较低的组播组，实现负载均衡；(3)将分组根源精心放置可以为大规模组播服务提供地域性的就近接入，有效提高服务质量；(4)基于根源的系统服务是可扩展的，而且非常容易。
1.2 多会话组播的方式
除提供多根组播源外，CPN-Multicast组播系统分组内还提供了基于多会话(SESSION)的组播方式，组内节点用户通过加入到指定的会话，就可以接收由该会话发出的组播信息。每个会话由一个会话标识SESSION_ID唯一确定。由于根节点是组播源，所以设置会话标识的前d位为0，后d位用于选择会话标识。会话消息由一个四元组组成：。其中REQ_TYPE为ADD或LEAVE，表示加入或退出会话。
2 组播会话树构建
CPN-Multicast组播系统的组播会话树构建算法通过利用CPN覆盖网络的底层路由算法完成，查找指定会话标识的多个相关节点，并完成加入组播树。 其中，组播信息转送和接收关系保存在组播信息转发节点列表和组播信息接收节点列表中。
2.1 组播信息转发节点列表
组播信息转发节点列表(MMTL, Multicast message transmit list)是当前节点负责转发的所有节点集合，以双向链表的方式连接成一个队列。当有新的组播节点加入到组播会话树时，需要请求加入其中一个节点的组播信息转发列表，由该节点负责组播信息转发到新加入节点，新加入节点从该节点接收组播信息。一个节点需要负责的转发节点个数由CPN覆盖网络配置参数α决定。
2.2 组播信息接收节点列表
与组播信息转发节点列表相似，MMRL是由当前节点可以接收组播信息的上一层节点的所有节点集合，同样以双向链表的方式连接成一个队表。当有新的组播节点加入到组播会话树时，路由过程中将所有可以接收组播信息的节点加入到自身组播信息接收节点列表中，一个节点可以保存的接收节点个数由CPN覆盖网络配置参数β决定。
2.3 多会话组播树的构建算法
多会话组播树的构建主要是新组播节点的加入，需要利用组播信息转发节点列表和组播信息接收节点列表这两种数据结构，具体算法实现的过程如下：
(1) 首先加入到CPN-Multicast组播网络，过程与加入CPN相同，同时获取目前正在直行组播的会话列表。
(2) 根据在会话列表选择的一个SESSION_ID发出查询组播源根节点的请求，直到返回会话所在组播源的根节点标识ROOT_ID。
(3) 在查找的过程中，如果返回的节点也在同一个会话里，则将该节点加入组播信息接收节点列表中。每一次查找到的组播信息转发节点如果属于同一组播会话，则将其插入到组播信息接收节点列表首部。这样，组播接收信息列表中越靠前的节点离根源越近，第一个节点即为组播源根节点。
(4) 查找结束后，可以得到一个组播信息接收节点链表，并可向链表的每个节点请求加入到该节点的组播转发列表。首先从第一个节点(根节点)开始发送加入请求。如果该节点已达到转发上限α，则该节点返回拒绝加入消息，同时返回其自身的组播信息转发节点链表的所有节点。节点将收到的组播信息转发节点链表合并加入到自身的组播接收信息列表内，并继续顺着组播接收信息列表内的节点逐一请求，直到加入到一个节点的组播转发列表中。为了加快加入组播会话的速度，可以同时向多个组播接收信息列表中的节点请求，只要成功加入，就立即取消其他请求。算法的实现过程如图1所示。
图1 新加入组播节点
Fig.1 New node joining in multicast
(5) 如果组播接收信息列表内的节点请求都不成功，表明在本分组内暂时无法为本节点服务。这可能是由于网络错误，也可能是由于当前分组负载过高，无法完成加入请求。这时，可以改变会话标识中的r域，使得该节点可以转到其他组播分组上查找同一会话标识的相关组播节点，重复整个加入步骤(3)~(5)。这也是充分利用了CPN覆盖网络的分组特性，各分组提供一致的组播服务，除了可以为所在分组提供组播服务外，还可以为其他分组提供冗余组播服务。
如果仍无法加入到组播会话，只能重新HASH自身ID并重新加入CPN覆盖网络后再请求加入会话。
通过上面介绍的加入算法，新的组播接收节点加入到组播会话树后，便可开始接收组播信息。随着多个到不同会话的组播接收节点的加入，形成多会话树结构，并且分组间可以提供冗余组播服务。算法的伪代码实现如表1所示。
2.4 加入组播树的算法改进
由于CPN覆盖网络的高效性，虽然在不考虑失效节点时可以在至多(d+1)步内就路由到指定节点，但为了每次加入过程中防止返回的组播转发节点过少，可以向已找到的组播转发节点，请求其组播接收信息列表。这样，接收到请求的组播转发节点就在其组播接收信息列表中随机选择γ个节点返回。根据返回的组播接收信息节点列表进行快速请求，这样就可以有效地提高新节点加入组播会话的效率。
2.5 组播会话树的维护
CPN-Multicast组播系统需要对组播系统内节点的正常与非正常退出分别进行处理。当接收组播信息的组播节点接收到父组播节点退出，或检测到其失效时，需要更新组播信息接收节点，以继续接收组播信息。对于处于组播会话转发树最底端的叶子节点，也需要做出相同的处理。组播树内节点关系如图2所示在组播树维护的过程中，部分组播接收节点接收到不完整的组播信息，但由于组播的特点，可以容忍部分信息的丢失。
表1 加入算法
Table 1 Algorithm for joining
另外，在传输链路质量下降的情况下，组播接收节点也可以主动进行网络切换，重新加入组播会话组播树，以获取更佳的网络质量。这适用于同一组播组中的多个用户可能存在接收能力不同的情况。
2.5.1 组播节点的正常退出
每一个中会话树中的组播节点在退出前，会通知组播转发列表里的所有下级组播接收节点，重新查找新的组播接收父节点源，这得益于组播系统内每个节点在加入时就已将多个相同会话的组播节点作为冗余资源存放在组播信息接收节点列表中。因此，一旦父节点源失效，可以立即从组播信息接收节点列表中选择新的节点，并请求加入其组播转发列表。
图2 组播树内节点关系
Fig.2 Relation between nodes in multicast
如果当前列表内的所有节点都无法完成请求，那么只能够重新加入组播会话树，查找同一会话树内的其它节点，并请求其组播信息接收节点列表。利用相关算法，进行重新连接，可以有效降低由于父组播节点退出而给组播系统带来的影响。
2.5.2 组播节点的非正常退出
为了防止组播节点的突然失效，每个组播节点与组播接收父节点之间会定时发送心跳包，以确保节点之间有效。当下级的组播接收节点检测到父接收源节点失效时，需要立即按照正常退出时的处理方法，启动重新选择接收源节点并加入，更新组播信息接收节点，以继续接收组播信息。
4 CPN-Multicast模型性能评估分析
从2个方面评估CPN-Multicast组播模型：(1)相对延时比值(RDP, Relative delay penalty)。标识CPN- Multicast模型内的2个组播节点之间的延迟比值(提供组播相信节点与接收组播信息节点)相对于使用物理网络基础上的IP组播延迟。(2)加入开销。节点在加入CPN覆盖网络后，加入CPN-Multicast多会话组播树的时间开销值对比。
3.1 不同参数下的RDP分布
通过配置不同的组播信息转发列表参数α，对比CPN-Multicast组播模型的组播树的相对延时。从图3可以看出，在不同的组播节点规模下，随着参数α的提高，相对延时比值RDP降低。表明新加入的组播节点能更快地接收到组播信息。当然，参数α越大，表明每个组播节点的负载就越大，需要向越多的组播节点转发组播信息。
图3 参数2对RDP的影响
Fig.3 Effect of 2 on RDP
从图4所示的相对延时分布比例实验结果可以看出：90%的情况下，相对延时比值在5以下，对于IP组播来说，其相对延时比值保持在一个较低的水平，比CAN-Multicast更优。
3.2 加入开销
对于IP multicast来说开销是1，因为组播树由路由器生成，所以，加入开销不会随组规模的变化而变 化。而CPN-Multicast组播模型中，在由节点使用CPN构成的覆盖网络中，生成的是一棵覆盖网络中的多会话组播树，所以，在有新节点加入组播会话时，开销高于IP multicast。
图5所示为在不同分组配置参数下，实施优化加入前后的加入开销对比。可以看出：在没有优化加入算法时，开销比较大，而在实施优化加入算法后，加入开销维持在一个较低的水平。
图4 不同比例下的RDP比较
Fig.4 Comparison between RDP in different scale
图5 实施优化前后的组播树加入开销比
Fig.5 Comparison of joining cost before and later optimizing multicast tree
3.3 仿真结论
通过对CPN-Multicast组播系统在相对延迟、链路压力条件下与IP multicast的模拟实验对比，可以看出：在节点规模迅速增加的情况下，CPN-Multicast组播模型在建立组播树所耗费的链接数方面增长幅度较慢，链路压力也较低，这与IP multicast类似；端到端的延时方面比较稳定，随组成员的增长而发生的变化不大。所以，基于P2P的应用层组播系统具有一定的扩展性和健壮性，可满足大规模组播应用的要求。通过仿真评测基于P2P覆盖网络的应用层组播模型的可行性、可扩展性和健壮性，结果表明：基于CPN覆盖网络构建的应用层组播模型CPN-Multicast具有较高的性能和可扩展性、较好的健壮性，可以满足大规模组播应用的需求。
4 结论
在CPN覆盖网络基础上构建CPN-Multicast组播模型，利用组播信息转发节点列表和组播信息接收节点列表，建立多根、多会话树的构建算法，并对构建过程提出可行的改进建议，分析组播节点在正常、非正常情况下退出的处理。将来的工作是如何使用一系列算法来优化组播节点动态加入、退出时对组播会话树的维护。
参考文献：
[1] Kim G, Han D, Son Y, et al. Application-level multicast using P2P protocol[C]// Proceedings of the International Conference on Internet Computing, Piscataway, US: IEEE Bogart, 2005: 354-360.
[2] Ragab K, Yonezawa A. A self-organized clustering-based overlay network for application level multicast[J]. Journal of Networks, 2009, 4(2): 85-91.
[3] Ratnasamy S, Handley M, Karp R, et al. Application level multicast using content-addressable networks[J]. Lecture Notes in Computer Science, 2001, 2233: 14-29.
[4] Castro M, Druschel P, Kermarrec A M, Rowstron A. Scribe: Alarge-scale and decentralized application-level multicast infrastructure[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1489-1499.
[5] Zhuang S Q, Zhao B Y, Joseph A D, et al. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination[C]// Proceedings of the IEEE International Workshop on Network and Operating System Support for Digital Audio and Video. Piscataway, US, 2001: 11-20.
[6] 魏文红, 梁可结, 王高才, 等. CPN: 一种基于小世界网络的P2P模型[J]. 计算机工程, 2010, 36(13): 15-17.
WEI Wen-hong, LIANG Ke-jie, WANG Gao-cai, et al. CPN: A P2P model based on small-world network[J]. Computer Engineering, 2010, 36(13): 15-17.
(编辑 方京华)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目(60973150)
通信作者：魏文红(1977-)，男，江西南昌人，讲师，博士后，从事网络与并行分布式计算研究；电话：13622672620; E-mail: hquwwh@tom.com.
