BuNet一种基于Cayley图的覆盖网络.pdf

第27卷第2期
计算机应用研究
Vol 27 No. 2
2010年2月
Application Research of Computers
Feb.2010
Bunet:一种基于 Cayley图的覆盖网络
李德苑,魏文红,王高才3
(1.华南理エ大学计算机科学与エ程学院,广州510640:2.东莞理工学院计算机学院,广东东莞523808
3.广西大学计算机与电子信息学院,南宁530004)
摘要;为了构建一个具有路由表小、查询路径长度短、鲁梓性强且支持文件组浏览服务的P2P覆盖网络,通过
对扩展蝶网理论的分析与设计,提出了一个新的基于 Cayley图的结构化P2P网 Bunet o通过模拟实验,证明
了BuNe相比其他结构化P2P网络在查询路径短和鲁梓性等方面具有更好的性能。
关键词:对等网络;结构化;蝶网;凯勒因;銀浏览服务
中图分类号:TP393.0
文献标志码:A文章编号:1001-3695(2010)02-0638-04
doi:10.3969/j.isan.1001-3695.2010.02.065
Bunet: overlay network based on Cayley grap
LI De-yuan, WEI Wen-hong, WANG Gao-cai
(1. choo f Com e &E S t of l u 51064 hn .chd of mtr
DongguamnUiniaersirygfrechnology,DonggnuanCansdong523808,China;3,.ScehoolorfCompuier&Electonienfomation,euangxiUlniei
ty, Nanning 530004, China)
Abstract: This paper f u a x n t f method o sign and analyzed a novel structured P2P network named
Bunet based Cayley graph. Bunet had many excellent properties such as small routing table, short query path and high robust
mess, and it proposed file group browsing service. Finally, it discussed and evaluated the performance compared to other DHT
based schemes
Key words: P2P; structured; butterfly; Cayley graph; group browsing service
近年来,一些P2P(per-lo-per)系统相继被提出来,如 DHTS最佳网络性能以及更优的容错性。
Chord、CAN2等,它们为大规模P2P应用提供了自组织的基
础设施。这类结构化的P2P系统是以分布式散列表DHT为基
静态蝶网协议
础的。它们使用一致性哈希函数将数据和节点都均匀地映射
Bunet的静态拓扑结构是以蝶网( butterfly)结构为基础
劉一个键值空间。然而,每个节点都被随机映射到一个节点标的,静态蝶网结构具有节点度小
号,这样的映射过程丢失了很多节点和资源的性质,同时网络缺
乏对用户使用PP网络方式的考虑,无法提供文件组湖览1.1 Butterfly I的定义
( group browser)功能,因而无法更加有效地平衡网络负载。
k维有向 butterfly图可以表示为B2,总共有n=x2个节
为了解決上述问题,笔者引人了基于 Cayley图“的P2P点。其定义如下的:是一个有向图,顶点V=W()=x
结构化覆盖网络,而基于 Cayley I网络模型可以有效地解决网2;而从a=(,“",の-1;i)V到b=(no,a,…,の-)
络负载平衡问题l。 Cayley图是使用代数群论建立的一类图,V有边当且仅当ie10,1,…,k-1,=i+1且=。其中:
它的最大优势是其对称性],其顶点具有传递性,即图中的每
1)-。而k维无向 butterfly图可以表示为
个顶点的地位相同。这使得对图中顶点间路由的研究可以转,其定义和类似;不同的是连边方式,即在中两个连着
换为对任意一个顶点到某个特殊顶点路由的研究?。因此可有向边的点,在5中用无向边连接起来。k≥3时,是4正
以使用代数方法来分析和设计基于 Cayley图的P2P网络路由则图。
算法;同时,可以采用统一的方法来分析真实P2P网络中各个
无向图是 Cayley图(,其定义为Cay(G,S)。其中:
对等点的负载情况。在基于 Cayley图的P2P网络中,负载都群G=(2xZ,?),G上的操作?为V(ロ,),(v,)∈V,(,
被均衡地分配到各个对等点中。
i)?《J)=(vea-u,v1B109-Bm0_1_;i⊕j),⊕是
本文设计了一种新颖的基于 Cayley图的P2P结构化覆盖取模加法。显然C的单位元是(0;0),S=1(1,0),(1,(1,0,
网络-BuNe( butterfly network)。该拓扑图的节点度为…,00-0)},其相关数学细节可参见文献[8]。
o(logn),图直径为O(logn/ olog n)。 Bunet可以支持文件1.2 Bunet的静态拓扑定义
浏览以及基于兴趣的分组等模仿人类社会行为,具有更高的可
根据 butterfly无向图的定义,推广其顶点集为V=hxZ2,
用性。模拟仿真实验表明,BuNe还能达到文献[6]所提到的则得到 Bunet的静态拓扑定义为
收稿日期:2009-05-18;修回日期:2009-06-29基金项目:国家自然科学基金资助项目(60763013);广东省科技计划资助项目
(2006B11301001);广东省工业科技攻关计判项目(200B80407001)
作者简介:李他苑(1985-),男,广东汕头人,士研究生,主要研究方向为P2P拓扑结构与并行算法( deyuan,i@mil.scu.edu.,cn);魏文红
(197-),男,讲师,博士,主要研究方向为P2P拓扑结构与并行算法;王高オ(1976-),男,教授,博士,主要研究方向为计算机网络、容错计算等
万方数据