摘 要：P2P网络广播使用广度优先的泛洪方式，导致对等点的处理负荷过大，网络流量激增，容易造成网络阻塞。在分析ComNET及组播的基础上，提出设计一个分布式算法，使一对多的消息传递变得高效而不含冗余，以此来解决ComNET中的组播问题。
关键词： P2P；组播；ComNET；分布式算法
P2P[1]网络广播使用广度优先的泛洪方式，根据对等点网络拓扑的不同，可能有大部分节点会被广播消息重复到达。重复到达的消息不仅增加了对等点的处理负荷，而且大大地增加了网络流量，容易造成网络阻塞。
通过实验可以简单地模拟广度优先的泛洪算法[2]在ComNET中进行组播消息的传递情况，模拟结果如图1所示。
数据统计过程如下。首先使用简单的广度优先算法在指定的组内传播消息，当一个对等点收到一个组播消息后，记住它曾经收到此消息，然后直接把消息发送到它所有邻居。重复访问次数是统计所有对等点收到的重复消息的总数（一个对等点可能收到多个重复消息，统计时算实际重复的次数，而不是一次），图1（a）所示为重复的次数随着网络规模的增大的情况，而图1（b）则给出了重复消息个数占发送消息总数的比例。从图1中可以看到，无论在比率还是绝对数量上，重复消息的量都是很惊人的。比如当对等点数目为2 M时，有131 917个消息是无用、重复接收的，占发送出去的消息总数140 119的94.14%。这些重复的消息严重祸害着互联网络。
本文主要研究讨论如何在ComNET指定的对等点组中广播消息。方法是首先研究简单的情况，即Cayley图Γ上的组播情况。然后再推广到动态网络ComNET上。
1 ComNET及组播分析
现实中一般很少需要在整个网络中转发消息，因而暂不考虑在整个ComNET上广播消息的情况，而把问题集中在如何在某个指定的对等点组中广播消息，称之为组播。问题的更形式化的定义[3]如下。
1.1 Γ中的组播
给定Cayley图Γ以及起始顶点P0=（c，p，r），给出以P0为根的一颗转发树T，满足：
（cn，pn，rn）（（cn，pn，rn）Tcn=c）
（cn，pn，rn）（（（cn，pn，rn）cn=c）（cn，pn，rn）T）
1.2 ComNET中的组播：
给定一个动态覆盖网络ComNET以及起始对等点P0=（c，p，r），给出以P0为根的一颗转发树T，且满足：
（cn，pn，rn）（（cn，pn，rn）TAPlockall（c，cn，k））
（cn，pn，rn）（（（cn，pn，rn）APlockall（c，cn，k））（cn，pn，rn）T）
1.3 Γ中的组播的缺点
图Γ的一级聚集系数该值较大。较大的聚集系数在直观上来看是指“一个顶点的邻居很可能也相互是邻居”，虽然增大CC1不仅可以增加“浏览功能”的可用性以及增强鲁棒性，但较大的CC1对组播是一场噩梦。可以通过图2来说明情况。
假设组播的起始顶点是P0，并且组播使用广度优先的方式进行扩散。第一步P0会把消息扩散到它的所有4个邻居中，其中包括P1、P2、P3；接着在第二步，由于P3同时又是P1和P2的邻居，所以P3（逻辑上）同时收到它们发出的组播消息。同理P1会同时收到P2和P3的组播消息；P2会收到P1和P3的组播消息。因此仅在两个时间步内，P1，P2和P3就总共收到了3个相同的消息，而且这些都只是所有消息副本中的很少的一部分，随着扩散规模的扩大，被重复到达的顶点以及重复到达的次数将会大大增加，因而在Γ中使用简单的广度优先策略来实现组播并不是一种明智的选择。
2 ComNET组播树实现
2.1 算法思路
在Γ上组播消息的关键是生成组播树，也就是说转发关系图不能含有环，因此只要找出一个分布式算法来确定一条从组播树根P0到其他组播树顶点P的唯一路径就能解决组播问题。事实上，可以把要求再降低一点，只需找出一个算法routeLastHop[4]用于计算从P0到P的路径中顶点P的上一跳，然后执行以下算法框架groupCast[5]即可。
输入：当前顶点P的标识符（c，p，r）以及组播树根标识符（c0，p0，r0）。
输出：无。
forall（（cn，pn，rn）in P的邻居集合）
if（c0=cn）
（cl，pl，rl）：=routeLastHop（（cn，pn，rn），（c0，p0，r0））
if（（c，p，r）=（cl，pl，rl））
把组播消息转发到（cn，pn，rn）
end
end
end
输入：顶点Pn的标识符（cn，pn，rn）以及组播树根标识符（c0，p0，r0）。
输出：唯一地确定从（c0，p0，r0）到（cn，pn，rn）的路由路径中，（cn，pn，rn）的上一跳顶点的标识符（cl，pl，rl）。
lastDiffPos为p0与pn的除第r0位的最后一个（从左到右）不同位的下标，如果找不到则为-1。
if（r0=rn）
if（lastDiffPos=-1）
（cl，pl，rl）：=（c0，p0，r0）
else
（cl，pl，rl）：=（cn，pn，lastDiffPos）
end
else
if（pn[rn]=p0[rn]）/*上一跳是沿着Linkr的*/
if（lastDiffPos=-1）
（cl，pl，rl）：=（cn，pn，r0）
else
（cl，pl，rl）：=（cn，pn，lastDiffPos）
end
else/*上一跳是沿着Linkp的*/
（cl，pl，rl）：=（cn，m（pn，p0，rn），rn）
end
end
问题的复杂度集中在算法routeLastHop。Γ上路由的算法如下所示，而算法routeLastHop实际上是该路由算法的逆过程。
输入：当前顶点的标识符（c1，p1，r1）以及目标顶点的标识符（c3，p3，r3）。
输出：下一跳顶点的标识符（c2，p2，r2）。
if（c1=c3（p1=p3（r1=r3）then
目标顶点已经到达
else
if（c1=c3（p1=p3）then
（c2，p2，r2）：=（c3，p3，r3）/*第二阶段*/
else/*下面属于第一阶段*/
if（lock（c1，c3，r1）（lock（p1，p3，r1））then
/*跳离当前地区，使得可以修正标识符的其他维*/
r2是不满足lock（c1，c3，r2）或不满足lock（p1，p3，r2）的整数，且优先选择非r3的整数。
c2：=c1
p2：=p1
else
if（┐lock（p1，p3，r1））then/*修正组内标识符的当前维*/
p2：=m（p1，p3，r1）
c2：=c1
r2：=r1
else/*修正组标识符的当前维*/
c2：=m（c1，c3，r1）
p2：=p1
r2：=r1
end
end
end
end
输入：当前对等点P的标识符（c，p，r）以及组播树根标识符（c0，p0，r0）。
输出：无。
forall（（cn，pn，rn）in P的邻居集合）
if（APlockall（c0，cn，k））
（cl，pl，rl）：=routeLastHopDHT（（cn，pn，rn），（c0，p0，r0））
if（r=rl（isClosetLock（p，pl，p0））
把组播消息转发到（cn，pn，rn）
end
end
end
输入：对等点Pn的标识符（cn，pn，rn）以及组播树根标识符（c0，p0，r0）。
输出：唯一地确定从（c0，p0，r0）到（cn，pn，rn）的路由路径中，（cn，pn，rn）的上一跳对等点的标识符（cl，pl，rl）。
lastDiffPos是除r0外最大的不满足谓词APlock（p0，pn，i，k）的i，如果找不到则为-1。
if（r0=rn）
if（lastDiffPos=-1）
（cl，pl，rl）：=（c0，p0，r0）
else
（cl，pl，rl）：=（cn，pn，lastDiffPos）
end
else
if（APlock（pn，p0，rn，k））/*上一跳是沿着Linkr的*/
if（lastDiffPos=-1）
（cl，pl，rl）：=（cn，pn，r0）
else
（cl，pl，rl）：=（cn，pn，lastDiffPos）
end
else/*上一跳是沿着Linkp的*/
（cl，pl，rl）：=（cn，APm（pn，p0，rn，k），rn）
end
end
2.2 ComNET中的组播算法
在第2节中本文给出了Γ中的组播算法，事实上只需要在适当的地方使用谓词“APlock”代替谓词“=”就可以得到在ComNET中组播的算法雏形。但是，另一方面，ComNET的动态性导致对等点与Γ上的顶点并不是一一对应的，这又需要对ComNET中的具体组播算法作出相应的修改。
先给出组播算法，然后再分析ComNET和Γ上的这些算法有何不同。
输入：两个对等点标识符P1=（c1，p1，r1）、P2=（c2，p2，r2）以及组播树根对等点标识符P0=（c0，p0，r0）。
输出：若（c1，p1，r1）相对于（c0，p0，r0）最亲密锁定（c2，p2，r2），则true，否则false。
for（i：=0…|p1|-1）
if（i（|p2|（p2[i]=（*（）
if（i<|p0|）
if（p1[i]（p0[i]）
返回false
end
else
if（p1[i]（（0（）
返回false
end
end
else
if（p1[i]（p2[i]）
返回false
end
end
end
返回true
以上算法只用了谓词APlock代替谓词“=”，以及使用操作APm代替操作m。?祝上的谓词“=”并没有改成ComNET中的APlockall，而是改成了isClosetLock。用图3来说明其中的原因。
假设组播的根对等点P0=（01，10111，1），则使用算法routeLastHopDHT计算Pn=（01，1111，2）的上一跳对等点的标识符得到的结果是Pl=（cl，pl，rl）=（01，1111，1）。从图3中可以看到，区域Pl一共由3个顶点组成，分别是P1=（c1，p1，r1）=（01，111100，1），P2=（c2，p2，r2）=（01，11111，1）以及P3=（c3，p3，r3）=（01，111101，1），因而必定有APlockall（p1，pl，k）、APlockall（p2，pl，k）以及APlockall（p3，pl，k）。所以，即使使用APlockall（p，pl，k）代替图53第四行中的p=pl，也无法得到ComNET下正确的组播算法，因为此时对等点P1，P2和P3都会在第二步同时发送组播消息给Pn。
为了消除图3中遇到的情况的方法是在多个组成这个区域的对等点中（如上述的P1、P2和P3），唯一地选择一个（如P2）作为代表来发送组播消息，而这个代表的选择标准则表示在2.2节的算法中。当一个对等点被该算法判定为相对于组播树根对等点P0的组内标识符最亲密地锁定pl，则该对等点就被选为代表。如对于图3，容易得到┐isClosetLock（P1，Pl），isClosetLock（P2，Pl）以及┐isClosetLock（P3，Pl），因而P2被选为区域Pl的代表，负责发送组播消息给Pn。
组播的提出实际上是为了克服基于泛洪的广播算法的种种缺陷，使一对多的消息传递变得高效而不含冗余，以此来解决ComNET中的组播问题。
参考文献
[1] 张联峰，刘乃安，钱秀槟，等.综述：对等网（P2P）技术[J].2003（12）：142-145.
[2] 石锋，吴建平.组播拥塞控制综述[J].软件学报，2002，13（8）：253-260.
[3] ABERER K， ALIMA L O， GHODSI A， et al. The essence of P2P： a reference architecture for overlay networks[C]. Fifth IEEE International Conference on Peer-to-Peer Computing， 2009：11-20.
[4] 宋建涛，沙朝锋，杨智应，等.语义对等网构造及搜索机制研究[J].计算机研究与发展，2010，41（4）：645-652.
[5] FAST A， JENSEN D， LEVINE B N. Creating social networks to improve peer-to-peer networking[R]. KDD′05 Proceedings of the eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data， 2005：568-573.