一種新型的常量度結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)

宋靜靜

摘 要： 為了改進結(jié)構(gòu)化P2P網(wǎng)絡(luò)的擴展性，我們設(shè)計了BGKR。它是一個具有常量度的新型P2P網(wǎng)絡(luò)，是以廣義Kautz有向圖和環(huán)作為拓?fù)浣Y(jié)構(gòu)。在BGKR中，具有相同前綴的節(jié)點集上查找每個數(shù)據(jù)項，這樣可維護網(wǎng)絡(luò)的平衡負(fù)載。每個節(jié)點維護的路由表大小不超過2d+1，任意兩節(jié)點間的路由不超過 跳。

關(guān)鍵詞： 對等網(wǎng)絡(luò)；分布式哈希表；覆蓋網(wǎng)絡(luò)；廣義Kautz有向圖

一、引言

最近幾年，Peer-to-Peer（簡稱P2P）迅速成為計算機界關(guān)注的熱門話題之一，美國財富雜志將P2P列為影響Internet未來的四項科技之一。P2P網(wǎng)絡(luò)最大的特點就是用戶之間共享資源，其核心技術(shù)就是分布式對象的定位機制，這也是提高網(wǎng)絡(luò)可擴展性、解決網(wǎng)絡(luò)帶寬被吞噬的關(guān)鍵所在。

DHT是結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，它的特性直接決定著P2P網(wǎng)絡(luò)及應(yīng)用的性能。對基于DHT網(wǎng)絡(luò)的研究是當(dāng)前國際學(xué)術(shù)界的熱點問題，它的性能評價的重要參數(shù)有節(jié)點度數(shù)、網(wǎng)絡(luò)直徑和擁塞等。現(xiàn)有的大多數(shù)網(wǎng)絡(luò)都是基于一些傳統(tǒng)的多機互聯(lián)網(wǎng)拓?fù)鋽U展而來的，如Chord、Tapestry和Pastry是基于hypercube拓?fù)洌珻AN基于d維的torus拓?fù)洌琄oorde和D2B基于de Bruijn圖，KZCAN基于Kautz圖。覆蓋網(wǎng)絡(luò)的特性常受限于所基于的拓?fù)鋱D。與上面使用的拓?fù)鋱D相比較，廣義Kautz圖有著更好的特性，如常量度、最優(yōu)直徑和擴展性。但目前還沒有基于廣義Kautz圖的網(wǎng)絡(luò)，因此本文對廣義Kautz圖進行了研究，設(shè)計了基于廣義Kautz圖和環(huán)的新型覆蓋網(wǎng)絡(luò)BGKR。

二、BGKR網(wǎng)絡(luò)

BGKR是以環(huán)和廣義Kautz有向圖作為拓?fù)浣Y(jié)構(gòu)，同環(huán)節(jié)點使用廣義Kautz有向圖KG（d，m）鏈接，當(dāng)環(huán)上的節(jié)點數(shù)目達到2D+2D-1（D是環(huán)上節(jié)點標(biāo)識符的長度）時形成完全的Kautz有向圖。為清楚起見，我們只描述2-維的BGKR（d=2）。

（一）BGKR的基本結(jié)構(gòu)

2-維BGKR中每個節(jié)點的標(biāo)識都是一個基底為2長度不同的Kautz串，按照標(biāo)識符的長度形成環(huán)型結(jié)構(gòu)，且標(biāo)識符長度相同的節(jié)點按照廣義Kautz有向圖的規(guī)則組成鄰居關(guān)系。我們稱具有相同長度標(biāo)識符的所有節(jié)點形成一個環(huán)，當(dāng)環(huán)上的節(jié)點數(shù)達到2D+2D-1時，它們形成一個完全Kautz有向圖（D是環(huán)上節(jié)點標(biāo)識符的長度）。隨著節(jié)點的不斷加入或退出，BGKR中環(huán)數(shù)不斷的變化，各節(jié)點的標(biāo)識會發(fā)生變化，節(jié)點的鄰居關(guān)系也會進行相應(yīng)的調(diào)整，新節(jié)點的標(biāo)識是在其加入過程中根據(jù)環(huán)的個數(shù)產(chǎn)生的。各節(jié)點標(biāo)識的長度可能是不同的，我們用|U|來表示節(jié)點U的標(biāo)識符長度，則BGKR中節(jié)點的鄰居關(guān)系滿足下面的性質(zhì)1。

性質(zhì)1（鄰居關(guān)系特性）對BGKR中不同環(huán)的任意節(jié)點U和V，若節(jié)點U和V是鄰居，則||U|-|V||=1。如圖所示是一個D=3的滿環(huán)BGKR結(jié)構(gòu)。

從圖中可以看出，BGKR中節(jié)點的度最大為2d+1，d是Kautz有向圖的度。因為，在同環(huán)上節(jié)點的最大度是d，相鄰的外環(huán)上最多有d個鄰節(jié)點且內(nèi)環(huán)上最多有1個鄰節(jié)點。

一個節(jié)點x1…xD有三種不同的鄰居：（1）具有相同長度標(biāo)識符的同環(huán)鄰節(jié)點，即廣義Kautz有向圖的鄰節(jié)點；（2）外環(huán)鄰節(jié)點，標(biāo)識為x1…xDα，α屬于{0，1，2}/{xD}；（3）內(nèi)環(huán)鄰節(jié)點，標(biāo)識為x1…xD-1。

D=3的BGKR結(jié)構(gòu)

（二）BGKR路由機制

BGKR中路由操作是利用三種不同的鄰節(jié)點實現(xiàn)的。令節(jié)點x的標(biāo)識符長度為i，節(jié)點y的標(biāo)識符長度為j，節(jié)點x路由消息到目的節(jié)點y。

1）當(dāng)i=j，用同環(huán)路由，即on-ring-forwarding。on-ring-forwarding操作是利用廣義Kautz路由機制從節(jié)點x=x1…xi路由到節(jié)點y=y1…yj。因此，根據(jù)Kautz有向圖的性質(zhì)，同環(huán)上的任意兩個節(jié)點x和y間的最路由長度是Kautz有向圖的直徑。

2）當(dāng)i

3）當(dāng)i>j時，如果y=y1…yj是x=x1…xi的前綴，則向內(nèi)環(huán)鄰節(jié)點路由，即inwards-forwarding。否則，先利用inwards-forwarding操作，節(jié)點x沿著內(nèi)環(huán)鄰節(jié)點到達標(biāo)識為x1…xj的節(jié)點x，再利用on-ring-forwarding操作，沿著廣義Kautz有向圖路由到達目的節(jié)點y。

下面給出了在BGKR覆蓋網(wǎng)中從節(jié)點x到節(jié)點y的路由算法。

輸入：初始節(jié)點x和目的節(jié)點y。

Procedure route （x， y）

If i== j then /*判斷x和y的長度是否相等

return on-ring-forwarding （x， y）

else if i

if x是y的前綴then

return outwards-forwarding （x， y）

else

return on-ring-forwarding （x1…xi， y1…yi）

return outwards-forwarding（y1…yi，y1…yj）

else

if y是x的前綴 then

return inwards-forwarding （x， y）

else

return inwards-forwarding （x1…xi， x1…xj）

return on-ring-forwardsing （x1…xj， y1…yj）

三、結(jié)論

P2P系統(tǒng)中資源處理是當(dāng)前面臨的重要問題，而覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)是解決這一問題的重要途徑。在傳統(tǒng)的互連網(wǎng)絡(luò)拓?fù)渲校琄autz圖具有最優(yōu)網(wǎng)絡(luò)直徑等良好的特性，本文基于環(huán)和廣義Kautz有向圖提出了一種新的P2P網(wǎng)絡(luò)（BGKR）。BGKR是一個常量度數(shù)、O（logN）網(wǎng)絡(luò)直徑且為常量擁塞的系統(tǒng)。在結(jié)點規(guī)模較大時，性能優(yōu)于現(xiàn)有的常量度數(shù)的CAN和Koorde。