BuNet:一種基于Cayley圖的覆蓋網(wǎng)絡(luò)

摘 要:為了構(gòu)建一個具有路由表小、查詢路徑長度短、魯棒性強(qiáng)且支持文件組瀏覽服務(wù)的P2P覆蓋網(wǎng)絡(luò)，通過對擴(kuò)展蝶網(wǎng)理論的分析與設(shè)計，提出了一個新的基于Cayley圖的結(jié)構(gòu)化P2P網(wǎng)絡(luò)BuNet。通過模擬實驗，證明了BuNet相比其他結(jié)構(gòu)化P2P網(wǎng)絡(luò)在查詢路徑短和魯棒性等方面具有更好的性能。

關(guān)鍵詞:對等網(wǎng)絡(luò); 結(jié)構(gòu)化; 蝶網(wǎng); 凱勒圖; 組瀏覽服務(wù)

中圖分類號:TP393.02

文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)02-0638-04

doi:10.3969/j.issn.1001-3695.2010.02.065

BuNet: overlay network based on Cayley graph

LI De-yuan1， WEI Wen-hong2， WANG Gao-cai3

(1.School of Computer Science Engineering， South China University of Technology， Guangzhou 510640， China; 2. School of Computer， Dongguan University of Technology， Dongguan Guangdong 523808， China; 3. School of Computer Electronic Information， Guangxi University， Nanning 530004， China)

Abstract:This paper first introduced a extend butterfly method to design 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 robustness， 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(peer-to-peer)系統(tǒng)相繼被提出來，如Chord[1]、CAN[2]等，它們?yōu)榇笠?guī)模P2P應(yīng)用提供了自組織的基礎(chǔ)設(shè)施。這類結(jié)構(gòu)化的P2P系統(tǒng)是以分布式散列表DHT為基礎(chǔ)的。它們使用一致性哈希函數(shù)將數(shù)據(jù)和節(jié)點都均勻地映射到一個鍵值空間。然而，每個節(jié)點都被隨機(jī)映射到一個節(jié)點標(biāo)號，這樣的映射過程丟失了很多節(jié)點和資源的性質(zhì)，同時網(wǎng)絡(luò)缺乏對用戶使用P2P網(wǎng)絡(luò)方式的考慮，無法提供文件組瀏覽(group browser)功能，因而無法更加有效地平衡網(wǎng)絡(luò)負(fù)載。

為了解決上述問題，筆者引入了基于Cayley圖[3，4]的P2P結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)，而基于Cayley網(wǎng)絡(luò)模型可以有效地解決網(wǎng)絡(luò)負(fù)載平衡問題[5]。Cayley圖是使用代數(shù)群論建立的一類圖，它的最大優(yōu)勢是其對稱性[5]，其頂點具有傳遞性，即圖中的每個頂點的地位相同。這使得對圖中頂點間路由的研究可以轉(zhuǎn)換為對任意一個頂點到某個特殊頂點路由的研究[5]。因此可以使用代數(shù)方法來分析和設(shè)計基于Cayley圖的P2P網(wǎng)絡(luò)路由算法;同時，可以采用統(tǒng)一的方法來分析真實P2P網(wǎng)絡(luò)中各個對等點的負(fù)載情況。在基于Cayley圖的P2P網(wǎng)絡(luò)中，負(fù)載都被均衡地分配到各個對等點中。

本文設(shè)計了一種新穎的基于Cayley圖的P2P結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)——BuNet(butterfly network)。該拓?fù)鋱D的節(jié)點度為O(log n)，圖直徑為O(log n/loglog n)。BuNet可以支持文件瀏覽以及基于興趣的分組等模仿人類社會行為，具有更高的可用性。模擬仿真實驗表明，BuNet還能達(dá)到文獻(xiàn)[6]所提到的DHTs最佳網(wǎng)絡(luò)性能以及更優(yōu)的容錯性。

1 靜態(tài)蝶網(wǎng)協(xié)議

BuNet的靜態(tài)拓?fù)浣Y(jié)構(gòu)是以蝶網(wǎng)(butterfly)結(jié)構(gòu)[7]為基礎(chǔ)的，靜態(tài)蝶網(wǎng)結(jié)構(gòu)具有節(jié)點度小、直徑小的性質(zhì)。

1.1 Butterfly的定義

k維有向butterfly圖可以表示為Bk2，總共有n=k×2k個節(jié)點。其定義如下[5]:Bk2是一個有向圖，頂點V=V(Bk2)=Zk2×Zk;而從a=(v0，v1，…，vk-1;i) ∈V到b=(w0，w1，…，wk-1;j)∈V有邊當(dāng)且僅當(dāng)i∈{0，1，…，k-1}，j=i+1且vl=wl。其中:l∈{0，1，…，k-1}-{i}。而k維無向butterfly圖可以表示為Bk2，其定義和Bk2類似;不同的是連邊方式，即在Bk2中兩個連著有向邊的點，在Bk2中用無向邊連接起來。k≥3時，Bk2是4正則圖。

無向圖Bk2是Cayley圖[3，4]，其定義為Cay(G，S)。其中:群G=(Zk2×Zk，#8226;)，G上的操作#8226;為(v，i)，(w，j)∈V，(v，i)#8226;(w，j)=(v0w-1，v1w-l+i，…，vd-1w-l+d-1;ij)，是取模加法。顯然G的單位元是(0k;0) ，S={(1，0)，(1，(1，0，…，00…0))} ，其相關(guān)數(shù)學(xué)細(xì)節(jié)可參見文獻(xiàn)[8]。

1.2 BuNet的靜態(tài)拓?fù)涠x

根據(jù)butterfly無向圖的定義，推廣其頂點集為V=Zkr×Zk，則得到BuNet的靜態(tài)拓?fù)涠x為

V={(v;i)|(v;i)∈Zkr×Zk，where v=(v0，v1，…，vk-1)，

vi∈Zr，i∈Zk};

E={〈(v;i)，(v;ir)〉|r∈{1，…，k-1}}∪

{〈(v;i)，(w;i1)〉，〈(v;i)，(w;i(r-1))〉

|w=(v0，v1，…，wi，…，vk-1)，wi∈{0，1，…，r-1}}

BuNet的靜態(tài)拓?fù)渚褪窃赽utterfly的基礎(chǔ)上增加進(jìn)制的同時，增加了不同層間的完全圖連邊。可以證明BuNet(k， r)是Cayley圖[3，4]，其定義為Cay(G，S)。其中:群G=(Zkr×Zk，#8226;)，G上的操作#8226;為(v;i)，(w;j)∈V，(v;i)#8226;(w;j)=(vσi(w);i+j)。其中:σ是循環(huán)右移操作，是模r加法，+是模k加法。顯然群G的單位元是(0k;0) ，S=Sk∪Sr，where Sk={(0k，i)|i∈Zk\\0}，Sr={(c0k-1，1)|c∈Zk}。因為BuNet有兩種生成集Sr和Sk，因此邊集可以分成兩種類型，即由生成集Sk構(gòu)成的層與層之間的連接k-link和由生成集Sr構(gòu)成的不同組之間的連接r-link。

1.3 BuNet靜態(tài)拓?fù)鋱D的相關(guān)性質(zhì)

性質(zhì)1 BuNet靜態(tài)拓?fù)鋱D的度為(k-2+2r)。

Cayley圖的度等于S集合的勢，所以BuNet靜態(tài)拓?fù)鋱D節(jié)點的度為|S|=|Sk|+|Sr|=k-2+2r，而該靜態(tài)圖為(k-2+2r)正則圖。

性質(zhì)2 BuNet靜態(tài)拓?fù)鋱D的度可以達(dá)到O(log n)，直徑可以達(dá)到O(log n/loglog n)。

BuNet靜態(tài)拓?fù)鋱D的節(jié)點個數(shù)為n=krk，假設(shè)k=log n/loglog n，那么r=(n/(log n/loglog n))1/(log n/loglog n)

2 BuNet協(xié)議設(shè)計

Chord和CAN等的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并不是Cayley圖，它們不具備很強(qiáng)的對稱性。本章將介紹把P2P對等點嵌入到其對應(yīng)的基于Cayley圖的靜態(tài)拓?fù)鋱D中，并形成BuNet的P2P DHT覆蓋網(wǎng)絡(luò)拓?fù)渌惴ā?/p>

2.1 BuNet的標(biāo)志符空間

在BuNet中，每個對等點的標(biāo)志符是由一個二元組(p，l)惟一確定。其中，p∈{(c0，c1，…，cs)|s=binarylen(r)×k，ci∈Z2∪{}}，l∈Zk(binarylen是將十進(jìn)制轉(zhuǎn)換為二進(jìn)制，去掉前導(dǎo)0后的長度)。從定義可以看出，對等點標(biāo)志符和靜態(tài)拓?fù)鋱D的頂點標(biāo)志符明顯的區(qū)別在于p是二進(jìn)制的字符串，由“0”“1”和“”組成。其中，“”代表可以匹配“0”或“1”。因為p是定長的，所以在實際應(yīng)用中，為了使標(biāo)志符空間足夠大，p采用160 bit的大二進(jìn)制數(shù)，可以取k=8，r=219。而對等點標(biāo)志符(p;l)和靜態(tài)拓?fù)鋱D頂點標(biāo)志符(v0，v1，…，vk-1;i)可以互相轉(zhuǎn)換:l= i，而p中的i，i+k，i+2k …位就是vi的二進(jìn)制表示。將vi稱為v的第i維;p中各i，i+k，i+2k … 位稱為p的第i維。例如對等點標(biāo)志符為(1011， 0)，則其等價的靜態(tài)拓?fù)鋱D頂點標(biāo)志符為(31， 0)。每個對等點根據(jù)“”匹配負(fù)責(zé)一小片區(qū)域，例如對等點標(biāo)志符(01， 1)負(fù)責(zé)的頂點區(qū)域為(0010， 1)、(0011， 1)、(0110， 1)和(0111， 1)。

2.2 BuNet的分布式散列表

在BuNet的DHT中的數(shù)據(jù)文件名和對象索引都會被映射到一個二元組(α，β)。其中，α是定長的二進(jìn)制字符串(|α|≥|p|，β∈Zk)。標(biāo)志符為(p， l)的對等點負(fù)責(zé)所有滿足p是α的前綴，并且l=β的散列表表項。例如對等點(0111， 2)負(fù)責(zé)鍵值(011100， 2)、(011101， 2)等表項。把α稱為組標(biāo)志符，β稱為層標(biāo)志符，把所有滿足p是α前綴的α組成的標(biāo)志符空間稱為對等點p負(fù)責(zé)的組區(qū)域。

2.3 BuNet的拓?fù)?/p>

BuNet拓?fù)涫荁uNet靜態(tài)拓?fù)鋱D在動態(tài)網(wǎng)絡(luò)的映射。在BuNet的拓?fù)渲校琹層中的對等點(p， l)將連向l+1層和l-1層的節(jié)點(p′， l+1)、(p′， l-1)。其中，p和p′在除第i維外，其他維上都匹配，第i維可匹配可不匹配;同時(p， l)還連向(p，l+1)，(p，l+2)，… ，(p，l+k-1)。也可以說兩個對等點(p， l)，(p′， l′)相鄰，當(dāng)且僅當(dāng)它們滿足下面兩個條件之一:l′=l±1且p和p′在zk-{l}維上相匹配，它們之間的連接對應(yīng)于r-link;l′≠L，但p和p′在所有維上都匹配，它們之間的連接對應(yīng)于k-link。

圖1是BuNet靜態(tài)拓?fù)鋱D與動態(tài)拓?fù)鋱D的映射關(guān)系。其中靜態(tài)拓?fù)鋱D中灰色區(qū)域?qū)?yīng)由一個動態(tài)對等點負(fù)責(zé)，如P0(00，0)負(fù)責(zé)(000，0)和(001，0)的區(qū)域，而P6(10，2)負(fù)責(zé)(100，2)和(110，2)的區(qū)域等。為了計算對等點所負(fù)責(zé)的區(qū)域，只需要將對等點標(biāo)志符中“”替換成“0”或“1”。若標(biāo)志符中“”的個數(shù)為m，則對等點負(fù)責(zé)區(qū)域頂點個數(shù)為2m個。而對等點的鄰居連接關(guān)系和靜態(tài)拓?fù)涠x一樣，只是在標(biāo)志符匹配上面要多考慮一個“”，而“”可以匹配“0”“1”和“”。如P4(1，1)在第零維和第二維上都與P6(10，2)匹配，因而P4和P5是鄰居;但是P4在第二維上與P5(0，2)不匹配，因而P4和P5沒有鄰居關(guān)系。對等點鄰居關(guān)系也可以從另外一個方面來得到，即如果對等點負(fù)責(zé)區(qū)域中有頂點和另一個對等點負(fù)責(zé)區(qū)域的頂點有邊連，則這兩個對等點有邊連。

2.4 BuNet的路由

BuNet中路由包括查找對等節(jié)點和數(shù)據(jù)對象索引，對象索引由包含其前綴的對等點負(fù)責(zé)，所以數(shù)據(jù)對象索引的查找可歸結(jié)于目標(biāo)節(jié)點的查找。BuNet的路由算法框架是通過每一跳來糾正當(dāng)前標(biāo)志符與目標(biāo)標(biāo)志符的差別，同時由于網(wǎng)絡(luò)動態(tài)性，算法引入了容錯性。算法1給出了在BuNet中路由的方法。例如，對于圖1的BuNet拓?fù)浣Y(jié)構(gòu)，假設(shè)當(dāng)前路由算法的初始入口節(jié)點為P1，目標(biāo)節(jié)點為P7。則基于每一跳匹配一位的原則，路徑為P1(01，0)、P3(01)、P5(0，2)、P2(1，0)和P7(101，2)。但是對等點可能因為各種原因而失效，那么可通過13~15行的容錯算法，選擇下一跳以避免查詢失敗。比如之前查詢中如果P3失敗，將在其他鄰居中任選一個作為下一跳。

算法1 BuNet路由算法

請求節(jié)點(P，i)查找目標(biāo)節(jié)點(α，j)

輸入:目標(biāo)節(jié)點(α，j)

輸出:下一跳

begin

if(P和α在所有維度上都匹配)

if(i == j)則到達(dá)目標(biāo)節(jié)點;

else通過k-link可以到達(dá)目標(biāo)，即j層;

else

if(P和α在第i維上匹配)

for(c=1， k-1)

if(P和α在第i+c維上不匹配)通過k-link到達(dá)下一跳(P′，i+c);

else 通過r-link修正，使得P′和α在第i維上匹配，下一跳為(P′，i+1);

if(下一跳為失效節(jié)點)

if(P和α在所有維度上都匹配)目標(biāo)節(jié)點失效，失敗退出

else 在r-link和k-link中隨機(jī)選擇一個鄰居作為下一跳;

end

2.5 加入BuNet

一個新的對等點P1的加入包括尋找網(wǎng)絡(luò)位置、更新標(biāo)志符、更新路由表以及更新分布式散列表四個步驟。尋找網(wǎng)絡(luò)位置是為了確定新的對等點在現(xiàn)有BuNet中的位置，它首先使用既定的規(guī)則生成一個先驗標(biāo)志符(PriP， i)，但此標(biāo)志符并不是它最后所使用的標(biāo)志符;然后在BuNet中隨機(jī)選一個初始節(jié)點P2作為入口節(jié)點，通過路由算法查找到負(fù)責(zé)(PriP， i)標(biāo)志符的對等點P3，把P1和P3稱為伙伴對等點。更新標(biāo)志符最終生成P1和P3的更新標(biāo)志符。標(biāo)志符的更新方法為:從右到左查找P3標(biāo)志符中第一個為“”的位置，P1標(biāo)志符保持該位置的字符不變，將其他位上的字符從P3上拷貝;P3將該位置的“”改為不同于P1該位置字符的“0”或“1”，即P1和P3標(biāo)志符只有一位不相同。這樣原來由P1負(fù)責(zé)區(qū)域分裂成兩半，一半留給自己繼續(xù)負(fù)責(zé)，另一半分配給P3負(fù)責(zé)。例如在BuNet(4， 2)中，分裂前P1=(01， 0)，它負(fù)責(zé)的區(qū)域為(0001， 0)、(0011， 0)、(0101， 0)和(0111， 0)四個點。分裂后，P1=(011， 0)，負(fù)責(zé)的區(qū)域變?yōu)?0011， 0)和(0111， 0);而剩下兩個點由P3=(001， 0)負(fù)責(zé)。加入BuNet的最后兩步是更新路由表和分布式散列表。更新路由表是為了維持BuNet拓?fù)洌ＷC路由正確;而更新分布式散列表是將那些適合P3標(biāo)志符的散列表項從P1遷移到P3。由于P1和P3所負(fù)責(zé)的區(qū)域都分別是P1所負(fù)責(zé)區(qū)域的子集，P1和P3的鄰居集以及散列表都分別是原來P1的鄰居集和散列表的子集。于是，循環(huán)檢查P1原來的路由表和散列表即可構(gòu)造P1和P3的新路由和散列表。最后由于P1和P3有可能相鄰，如果相鄰則將對方標(biāo)志符加入到自身路由表中。算法2為BuNet的節(jié)點加入算法，圖2為BuNet對等點逐步加入的構(gòu)建過程。其中網(wǎng)絡(luò)的初始狀態(tài)要求每一層至少部署一個對等點，它們層標(biāo)志符各不相同。

算法2 BuNet的節(jié)點加入算法

輸入:隨機(jī)選取的入口節(jié)點P2的標(biāo)志符(p2，i2);

輸出:待加入BuNet的對等點P1的標(biāo)志符(p1，i1)、路由表和分布式散列表

更新后的P3標(biāo)志符、路由表和分布式散列表。

begin

PriP:= 長度為s，通過既定規(guī)則生成的組標(biāo)志符;i1:=Zk中隨機(jī)選取的整數(shù);

(p3，i3)為以(p2，i2)為入口節(jié)點，(PriP，i1)為查詢目標(biāo)節(jié)點，調(diào)用路由算法所返回的目標(biāo)對等點P3;

Diff為p3和PriP從右到左第一個不同位的下標(biāo);

p3[Diff] =!PriP[Diff]，p1=p3，p1[Diff] = PriP[Diff];

for((pn，in) in P3的路由表)

if((pn，in)是(p1，i1)的鄰居)

把(pn，in)添加到P1的路由表，把P1添加到(pn，in)的路由表;

if((pn，in)不再是(p3，i3)的鄰居)

把(pn，in)從P1的路由表中刪除，把P1從(pn，in)的路由表中刪除;

if((p1，i1)是(p3，i3)的鄰居)

把(p1，i1)添加到(p3，i3)的路由表，把(p3，i3)添加到(p1，i1)的路由表;

for(hashItem in P3的分布式散列表)

if(hashItem不再匹配P3的新標(biāo)志符)

將hashItem從P3的分布式散列表中刪除;

把hashItem添加到P1的分布式散列表中;

end

2.6 退出BuNet

BuNet網(wǎng)絡(luò)中的節(jié)點可以在任何時刻退出。在理想情況下，節(jié)點在退出網(wǎng)絡(luò)之前通知其鄰居，并更新路由表、分布式散列表等，稱此次退出為正常退出，否則稱為非正常退出。若一個節(jié)點P1要退出網(wǎng)絡(luò)時，它首先需要查詢它的伙伴對等點是否還沒有分裂，即兩個對等點負(fù)責(zé)的區(qū)域是一樣大的。如果還沒有分裂，則P1將自己負(fù)責(zé)的區(qū)域交給其伙伴對等點負(fù)責(zé)，而伙伴對等點將標(biāo)志符中和P1標(biāo)志符惟一不同的那一位修改為“”，然后伙伴對等點執(zhí)行加入算法的逆操作，對路由表和分布式散列表進(jìn)行更新，同時通知鄰居對等點更新路由表和分布式散列表。而如果P1的伙伴對等點所在的區(qū)域已經(jīng)進(jìn)行了多次分裂，則P1將在伙伴對等區(qū)域中用深度優(yōu)先搜索算法(DFS)搜索一個負(fù)責(zé)區(qū)域最小的對等點Pi，讓Pi負(fù)責(zé)P1的區(qū)域;而Pi將其原來負(fù)責(zé)區(qū)域交給其伙伴對等點(一定是未分裂對等點)負(fù)責(zé)。最后各個對等點執(zhí)行路由表、分布式散列表更新操作。假如圖2(d)中P1(0，1)節(jié)點要退出網(wǎng)絡(luò)，而它的伙伴對等點已經(jīng)分裂;則算法將選擇一個最小對等點P3(11，1)來負(fù)責(zé)P1的區(qū)域，而P3的標(biāo)志符修改為(0，1);P4將接管P3原來的區(qū)域，同時P4的標(biāo)志符修改為(1，1)。最后P3和P4更新路由表和分布式散列表。雖然此操作比較繁瑣，但是這種情況出現(xiàn)的概率比較低。

節(jié)點非正常退出需要多一個失敗檢測節(jié)點:失敗檢測策略包括向鄰居定期發(fā)送Keep-alive包以及異步檢測機(jī)制。檢測到錯誤后，該節(jié)點幫助非正常退出節(jié)點完成清理更新工作。而注意到非正常退出節(jié)點的分布式散列表無法通過其鄰居節(jié)點進(jìn)行恢復(fù)，因此需要采取其他措施如鄰居節(jié)點定期備份或資源擁有者定期發(fā)送對象索引等保證健壯性。

3 性能評估

通過模擬仿真實驗來評估BuNet的各項性能指標(biāo)。本文選擇Chord[1]作為比較對象，是因為Chord代表了基于DHT協(xié)議的覆蓋網(wǎng)絡(luò)算法，它們的網(wǎng)絡(luò)直徑為O(log n)，路由表大小為O(log n)，而且BuNet也是基于DHT協(xié)議的。所有的實驗都是用C/C++編寫的，評估測試都在單進(jìn)程內(nèi)完成，不涉及任何真正意義上的網(wǎng)絡(luò)通信。網(wǎng)絡(luò)中節(jié)點的個數(shù)為256~4M。Chord協(xié)議是參照文獻(xiàn)[1]中算法實現(xiàn)的。最后所有模擬實驗都是多次實驗結(jié)果的平均值。

3.1 路由長度

圖3顯示了不同網(wǎng)絡(luò)規(guī)模下，BuNet、Chord和CAN的最大路由長度和平均路由長度。其中路由的源對等點和目標(biāo)對等點都是在標(biāo)志符范圍內(nèi)隨機(jī)選取的。實驗評估了各種網(wǎng)絡(luò)規(guī)模的路由路徑特性。從中可以看出，BuNet、Chord和CAN的平均路由長度增長緩慢，且始終沒有超過它們各自的網(wǎng)絡(luò)直徑。而BuNet的最大路由長度約等于log n/loglog n，Chord和CAN的最大路由長度則約等于log n(其中，n為網(wǎng)絡(luò)節(jié)點個數(shù))。在相同的網(wǎng)絡(luò)規(guī)模下，BuNet的路由長度都比Chord和CAN要小，這就縮短了路由查找的時間。圖4給出了由4M個對等點組成的網(wǎng)絡(luò)的路由長度分布圖，由圖中可以看出路由長度都集中分布在一定的范圍內(nèi)(BuNet路由長度主要集中在5~6，Chord的路由長度集中在9~15，CAN的路由長度集中在15~23)。路由長度的方差與基于P2P覆蓋網(wǎng)絡(luò)的網(wǎng)絡(luò)抖動有很大的關(guān)聯(lián):小的方差可能得到低的網(wǎng)絡(luò)抖動，而低的網(wǎng)絡(luò)抖動對實時應(yīng)用具有決定性的意義。在網(wǎng)絡(luò)抖動方面:BuNet

3.2 魯棒性

魯棒性是測試當(dāng)網(wǎng)絡(luò)中對等點以不同的概率失效時，路由失敗的比率(包括入口節(jié)點失效、目標(biāo)節(jié)點失效和查找過程的失敗等)與相應(yīng)情況下成功路由的長度。實驗中測試的網(wǎng)絡(luò)規(guī)模均為4M個對等點。路由測試開始前，先按照一定的比例隨機(jī)生成失效節(jié)點，然后在該含有失效節(jié)點的覆蓋網(wǎng)絡(luò)上運(yùn)行路由算法，計算路由失敗率以及路由成功情況下的平均路由長度。對等點的失敗率為0~20%，對于每一次路由測試都隨機(jī)選取源和目標(biāo)，每個失敗率下都運(yùn)行40M次路由查找。圖5給出BuNet、Chord和CAN在不同對等點失效概率下路由查詢最終失敗的概率。在相同的對等點失效概率下，BuNet的路由失敗率比Chord和CAN要低。路由過程中發(fā)生錯誤時會增加該路由的長度，圖6顯示出路由容錯對平均路由長度的影響。BuNet、Chord和CAN的平均路由長度增幅類似，但是BuNet的路由長度總要比Chord和CAN的要小。

4 結(jié)束語

針對傳統(tǒng)P2P覆蓋網(wǎng)絡(luò)缺乏分組瀏覽功能的問題，本文提出了一種新的基于Cayley圖的擴(kuò)展butterfly結(jié)構(gòu)拓?fù)銪uNet，并在上面設(shè)計了P2P拓?fù)洳樵兟酚伤惴ê图尤胪顺鏊惴ǖ取７抡鎸嶒灲Y(jié)果表明，與Chord相比，BuNet能在同等路由表大小前提下可獲得更短查詢路徑，而且它的路由容錯性和魯棒性也更加優(yōu)秀。下一步，筆者將在大規(guī)模網(wǎng)絡(luò)下模擬測試BuNet的動態(tài)路由算法，并進(jìn)一步分析網(wǎng)絡(luò)拓?fù)湓诖笠?guī)模網(wǎng)絡(luò)環(huán)境下的特性;同時研究BuNet在組播、負(fù)載均衡方面的性能。

參考文獻(xiàn):

[1]STOICA I， MORRIS R， LIBEN-NOWELLL， et al. Chord: a scalable peer-to-peer lookup protocol for Internet applications[J]. IEEE/ACM Trans on Networking，2003，11(1):17-32.

[2]RATNASAMY S， FRANCIS P， HANDLEY M， et al. A scalable content addressable network[C]//Proc of Annual ConferenceACM Special Interest Group on Data Communications (ACM SIGCOMM 2001).2001.

[3]AKERS S B， KRISHNAMURTHY B. A group-theoretic model for symmetric interconnection networks[J]. IEEE Trans on Computes， 1989，38(4):555-566.

[4]BIGGS N. Algebraic graph theory[M]. Cambridge: Cambridge Uni-versity Press， 1993.

[5]QU C， NEJDL W， KRIESELL M. Cayley DHTs: a group-theoretic framework for analyzing DHTS based on Cayley graphs[C]//Proc of the 2nd ISPA.2004:914-925.

[6]XU J. On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks[C]//Proc of IEEE Infocom.2003:2177-2187.

[7]SIEGEL H J. Interconnection networks for SIMD machines[J]. IEEE Computer，1979，12(6):57-64.

[8]HEYDEMANN M C， DUCOURTHIAL B. Cayley graphs and interconnection networks[M]//Graph Symmetry， Algebraic Methods and Applications.[S.l.]:Kluwer Academic Publishers，1997:167-224.

[9]ABERER K， ALIMA L O， GHODSI A， et al. The essence of P2P: a reference architecture for overlay networks[C]//Proc of the 5th IEEE International Conference on Peer-to-Peer Computing.2005.