結(jié)構(gòu)化P2P系統(tǒng)路由機(jī)制的研究

摘要:基于分布式哈希表的結(jié)構(gòu)化P2P系統(tǒng)得到了廣泛的研究，這些系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)一般都以圖論中的一些廣為研究的圖作基礎(chǔ)，而且大量借鑒了并行系統(tǒng)的研究成果。介紹了幾個常見的結(jié)構(gòu)化P2P系統(tǒng)，對其拓?fù)浣Y(jié)構(gòu)和路由算法作了分析對比。

關(guān)鍵詞:對等網(wǎng)絡(luò);結(jié)構(gòu)化P2P;路由;拓?fù)浣Y(jié)構(gòu)

中圖分類號:TP393文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)14-3688-03

Study on Routing of Structured P2P Systems

XU Li-xin， YANG Wen-yin

(1.Department of Computer Information， Guangdong Polytechnic College， Guangzhou 510520， China; 2. Department of Computer，F(xiàn)oshan University， Foshan 528000， China)

Abstract: Nowadays the structured P2P systems are studied comprehensively. The topologies of these systems are usually based on some famous graphs and use many research findings of parallel system for reference. Several popular structured P2P systems are introduced and their topologies and routing algorithms are analyzed.

Key words: peer-to-peer; structured P2P; routing; topology

最近幾年，基于分布式哈希表(DHT)的結(jié)構(gòu)化P2P系統(tǒng)得到了廣泛的研究，一些系統(tǒng)模型被相繼提出來。這個過程主要可以分為兩個階段，早期的系統(tǒng)如Chord[7]、Pastry[5]、Tapestry[9]具有O(logN) 的路由表大小和O(logN)的網(wǎng)絡(luò)直徑，CAN[4]分別是O(d)和O(d*N1/d)。隨著研究的深入，人們逐漸認(rèn)識到結(jié)構(gòu)化的P2P系統(tǒng)的主要弱點(diǎn)在于要維護(hù)嚴(yán)格的拓?fù)浣Y(jié)構(gòu)，尤其是在網(wǎng)絡(luò)攪動劇烈時大量節(jié)點(diǎn)的加入和離開會產(chǎn)生巨大的開銷。節(jié)點(diǎn)維護(hù)的鄰居的數(shù)量即路由表的大小是影響網(wǎng)絡(luò)拓?fù)渚S護(hù)開銷的主要因素，因此一些具有常數(shù)度(即節(jié)點(diǎn)只維護(hù)常數(shù)個鄰居)的P2P系統(tǒng)被提出來，如Viceroy[3]、Koorde[2]和Cycloid[1，6]等。這些系統(tǒng)只維護(hù)較少的常數(shù)個鄰居，而具有O(logN)的網(wǎng)絡(luò)直徑。如Viceroy和Cycloid鄰居數(shù)為7、Koorde鄰居數(shù)最小為2。

這些結(jié)構(gòu)化P2P系統(tǒng)的拓?fù)浣Y(jié)構(gòu)都可以追述到圖論中的一些著名的圖，如Chord來自于環(huán)(ring)，CAN來自于網(wǎng)格(mesh)，Pastry和Tapestry近似于超立方體(hypercube)。而具有常數(shù)度的結(jié)構(gòu)更是直接取自于一些規(guī)范的圖，Viceroy使用butterfly，Koorde使用de bruijn，Cycloid使用CCC。該文對結(jié)構(gòu)化P2P系統(tǒng)的拓?fù)浣Y(jié)構(gòu)和路由算法作了分析對比。

1 路由表大小為O(logN)的系統(tǒng)

1.1 Chord

Chord[7]地址空間組織成一個一維的環(huán)(ring)，每個節(jié)點(diǎn)通過指取表與系統(tǒng)的其余部分連接起來。在地址空間大小為N的Chord系統(tǒng)中，路由表共有l(wèi)ogN 項(xiàng)。ID為n的節(jié)點(diǎn)的指取表按如下方式構(gòu)成，第i行的start=(n+2i-1) mod N，succ=Successor((n+2i-1) mod N)。start表示與當(dāng)前節(jié)點(diǎn)距離為2i-1的鄰居，Successor函數(shù)返回從start開始的第一個存在的結(jié)點(diǎn)，即start的后繼節(jié)點(diǎn)。

Chord在路由一個查詢時，將查詢傳發(fā)到指取表中比關(guān)鍵字小的最大的start所對應(yīng)的succ節(jié)點(diǎn)，逐步逼近目標(biāo)節(jié)點(diǎn)，類似于二分查找算法。Chord的查詢距離為O(logN)。

1.2 Pastry

Pastry[5]采用一維的地址空間，組織成一個近似的超立方體結(jié)構(gòu)。節(jié)點(diǎn)的ID由m位基數(shù)為2b的數(shù)字組成，b的典型取值為2或4。路由表由m行、2b列組成，其中第i行第j列的路由表項(xiàng)隨機(jī)取自前i-1位數(shù)字與當(dāng)前節(jié)點(diǎn)相同、第i位為j-1的存在的節(jié)點(diǎn)集合中。傳統(tǒng)的n超立方體(在此n=2b)要求節(jié)點(diǎn)與鄰居之間只有一位數(shù)字不同，Pastry的鄰居選擇方法適合P2P系統(tǒng)高動態(tài)性、節(jié)點(diǎn)稀疏的特點(diǎn)，具有更好的容錯性。

Pastry的路由算法采用Plaxton模型的一個變體，通過從左到右一次校正一位數(shù)字，在大小為O(logN) 路由表上達(dá)到O(logN)的查詢距離。另一個經(jīng)典的結(jié)構(gòu)化P2P系統(tǒng)Tapestry[9]與Pastry相似，但I(xiàn)D的基數(shù)不必限定是2b。

1.3 路由表的計(jì)算

基于DHT的結(jié)構(gòu)化P2P系統(tǒng)的路由表結(jié)構(gòu)和內(nèi)容各不相同，在不同的系統(tǒng)中，路由表布署在每個節(jié)點(diǎn)上，支持系統(tǒng)特定的路由算法。路由表中項(xiàng)目的內(nèi)容根據(jù)系統(tǒng)采用的不同的結(jié)構(gòu)，有不同的計(jì)算方法。為了使系統(tǒng)有好的容錯性，路由表的項(xiàng)目一般都代表了一組候選的節(jié)點(diǎn)，其中任何一個都可以作為鄰居。系統(tǒng)中所有節(jié)點(diǎn)的路由表計(jì)算方法是一致的，都是采用到當(dāng)前節(jié)點(diǎn)的相對距離來描述。因此節(jié)點(diǎn)在計(jì)算路由表項(xiàng)目時，首先根據(jù)到當(dāng)前節(jié)點(diǎn)的相對距離確定一組節(jié)點(diǎn)，然后用某種方法(一般是向其他節(jié)點(diǎn)咨詢)從中選擇一個存在的節(jié)點(diǎn)ID填入該項(xiàng)。我們可以用下面的方法[8]抽象描述。

假設(shè)名字空間和關(guān)鍵字空間由0，1，2，…，n-1共n個連續(xù)的ID組成，路由表的大小為k。節(jié)點(diǎn)id(id∈ID)的路由表R的內(nèi)容是由一組鄰居節(jié)點(diǎn)入口組成的:R={|1≤i≤k， Si是id路由表第i項(xiàng)的候選節(jié)點(diǎn)的集合，Di是所選節(jié)點(diǎn)到id的距離}。當(dāng)i≠j時，有Di≠Dj，Si∩Sj=Φ，∪Si={0，1，2，…，n-1}。對路由表的第i項(xiàng)有，Di∈Si，Di=select(Si)，select函數(shù)表示從集合Si中選出Di，第i項(xiàng)內(nèi)容為Ri=id+Di。路由算法就可以簡單的描述為:如果A-id∈Si，那么就把對關(guān)鍵字A的查詢轉(zhuǎn)發(fā)到路由表R的第i項(xiàng)，即節(jié)點(diǎn)Ri。

在Chord系統(tǒng)中，名字空間大小為n=2k，對節(jié)點(diǎn)id指取表的第i行(i=1，2，…，k)，Si=[2i-1，2i)，Di=select(Si)=successor(2i-1)，successor函數(shù)返回節(jié)點(diǎn)id+2i-1活動的后繼節(jié)點(diǎn)的相對距離，則第i行內(nèi)容為Ri=id+Di=id+successor(2i-1)。在Tapestry系統(tǒng)中，名字空間大小為n=dx，設(shè)i=0，1，…，x-1，且j=1，2，…，d-1，則對路由表的第i行第j列，Si*d+j=[j*di，(j+1)*di)，Di*d+j=select(Si*d+j)，此時select向其他節(jié)點(diǎn)咨詢返回集合Si*d+j中的一個活動節(jié)點(diǎn)，路由表項(xiàng)內(nèi)容為Ri*d+j=id+Di*d+j。Pastry系統(tǒng)中限定d是2的冪，其他與Tapestry系統(tǒng)相似。

2 路由表大小為常數(shù)的系統(tǒng)

2.1 CAN

CAN[4]采用d維的迪卡爾坐標(biāo)空間，組成一個d維的網(wǎng)格結(jié)構(gòu)。每個節(jié)點(diǎn)占有一個區(qū)域，路由表包含2d項(xiàng)，代表在不同的d維上的2d個鄰居。相鄰的兩個節(jié)點(diǎn)在d-1維上相同，在另一維上鄰接。路由的每一步都選擇在某一維上更靠近目標(biāo)節(jié)點(diǎn)。CAN的路由表大小為O(d)，查詢距離為O(dN1/d)。需要指出的是當(dāng)設(shè)置d=logN時， CAN 也能達(dá)到O(logN)的路由表大小和O(logN)的查詢距離。

2.2 Cycloid

Cycloid[1，6]使用的是d維的cube-connected cycles(CCC)，容納的節(jié)點(diǎn)數(shù)n=d*d2。Cycloid的id采用二維結(jié)構(gòu)(k，ad-1ad-2...a0)，其中k(0≤k≤d-1)代表環(huán)索引，二進(jìn)制數(shù)ad-1ad-2...a0代表立方體索引，介于0到d2-1之間。有相同立方體索引值的節(jié)點(diǎn)根據(jù)k值排序成為一個循環(huán)，稱為局部環(huán)(local cycle)，局部環(huán)中環(huán)索引最大的節(jié)點(diǎn)稱為主節(jié)點(diǎn)，具有不同立方體索引值的局部環(huán)互為遠(yuǎn)環(huán)(remote cycle)。所有的局部環(huán)按立方體索引組成大環(huán)(large cycle)。數(shù)據(jù)會選擇與其關(guān)鍵字先是立方體索引最接近，然后環(huán)索引值最接近的節(jié)點(diǎn)存放。

通常節(jié)點(diǎn)(k，ad-1ad-2...a0)(k≠0)有七個鄰居節(jié)點(diǎn)。其中一個立方體鄰居(k-1，ad-1ad-2...akxx...x)(x任取0和1)，兩個循環(huán)鄰居(k-1，bd-1bd-2...b0)和(k-1，cd-1cd-2...c0)是環(huán)索引為k-1 mod d、立方體索引為第一個大于和小于ad-1ad-2...a0且最大不相同位的下標(biāo)值小于k的節(jié)點(diǎn)。兩個內(nèi)葉子節(jié)點(diǎn)是局部環(huán)中的前導(dǎo)和后繼節(jié)點(diǎn)，兩個外葉子節(jié)點(diǎn)是大環(huán)中前導(dǎo)遠(yuǎn)環(huán)和后繼遠(yuǎn)環(huán)中的主節(jié)點(diǎn)。

Cycloid的路由表大小為O(1)，查詢距離為O(d)。其路由過程分為三個階段(設(shè)M表示最大不同位的下標(biāo)值):1)上升階段:如果關(guān)鍵字的k值小于M，則將該請求沿外葉子節(jié)點(diǎn)轉(zhuǎn)發(fā)直到k≥M。2)下降階段:如果k=M，將請求轉(zhuǎn)發(fā)到立方體鄰居;否則，將請求轉(zhuǎn)發(fā)到環(huán)鄰居和內(nèi)葉子節(jié)點(diǎn)中最接近目標(biāo)的節(jié)點(diǎn)，以靠近目標(biāo)立方體索引。3)橫向階段:如果目標(biāo)id在葉子集中，則將請求轉(zhuǎn)發(fā)到最接近的葉子節(jié)點(diǎn)，直到最接近的節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)本身。

2.3 Koorde

Koorde[2]使用de Bruijn圖作為拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)。容納的節(jié)點(diǎn)數(shù)為2b，節(jié)點(diǎn)的度數(shù)為2。在de Bruijn圖中，節(jié)點(diǎn)用二進(jìn)制數(shù)表示，節(jié)點(diǎn)m有兩個鄰居:2m mod 2b 和 2m+1 mod 2b，也就是m指向?qū)左移一位后去掉最高位并用0和1分別填充最低位得到的兩個節(jié)點(diǎn)，如圖圖5。

因?yàn)樵诃h(huán)狀地址空間中，節(jié)點(diǎn)2m mod 2b 和 2m+1 mod 2b是相鄰的，所以Koorde改變兩個鄰居為m的后繼節(jié)點(diǎn)和2m mod 2b節(jié)點(diǎn)(仍然可以保持de Bruijn圖性質(zhì))。實(shí)際的P2P系統(tǒng)的節(jié)點(diǎn)在地址空間中是非常稀疏的，這樣de Bruijn圖上就有許多“想象中的節(jié)點(diǎn)”，Koorde的路由算法是在這個稀疏的圖上模擬de Bruijn圖路由過程，可用下列偽碼描述:

procedure m.LOOKUP(k; kshift; i)

if k∈(m; successor] then

return (successor)

else if i∈(m; successor] then

return (d:lookup(k;kshift << 1; i °topBit(kshift)))

else return (successor:lookup(k; kshift; i))

上述代碼表示節(jié)點(diǎn)m對關(guān)鍵字k的路由，topBit函數(shù)返回kshift的最高位數(shù)字，i °0和i °1表示2i mod 2b 和 2i+1 mod 2b。

Koorde每個節(jié)點(diǎn)維護(hù)兩個鄰居時可以高概率的達(dá)到O(logN)的查找距離，通過將鄰居數(shù)量增加到logN個，Koorde的查找距離可以達(dá)到O(logN/loglogN)。

2.4 Viceroy

Viceroy[3]的拓?fù)浣Y(jié)構(gòu)采用近似的蝴蝶網(wǎng)絡(luò)(butterfly network)。Viceroy是分層結(jié)構(gòu)的，處在butterfly的第l層的節(jié)點(diǎn)有七個鄰居，包括環(huán)狀地址空間中的前導(dǎo)和后繼節(jié)點(diǎn)，同一層的前后節(jié)點(diǎn)，第l+1層的左右節(jié)點(diǎn)和l-1層的上節(jié)點(diǎn)。在Viceroy系統(tǒng)中，每個節(jié)點(diǎn)擁有兩個值:ID和butterfly層號。節(jié)點(diǎn)的ID獨(dú)立一致的從[0，1)上產(chǎn)生，而層號是從[1，logN]中隨機(jī)選擇(N為網(wǎng)絡(luò)大小的估計(jì)值)。一個節(jié)點(diǎn)的ID是固定不變的，而層號會隨著節(jié)點(diǎn)在系統(tǒng)中的存活時間被校正。

Viceroy的路由過程包括三步:首先是上升階段，沿著向上的連接上升到第一層;然后是下降階段，沿著向下的連接直到?jīng)]有向下連接的節(jié)點(diǎn);最后是橫向階段，通過同層連接到達(dá)目標(biāo)節(jié)點(diǎn)。Viceroy的查詢距離為O(logN)。

3 總結(jié)

以上是對各個系統(tǒng)的逐個分析介紹，下面將上述系統(tǒng)的一些屬性進(jìn)行匯總。

結(jié)構(gòu)化P2P系統(tǒng)的研究很大程度上借鑒了并行結(jié)構(gòu)和圖論的研究成果，通過對已有的互連網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修改以適應(yīng)P2P系統(tǒng)的特點(diǎn)，上述許多結(jié)構(gòu)被成功的引入到P2P領(lǐng)域。有文章提出判斷哪些拓?fù)浣Y(jié)構(gòu)可以用于P2P系統(tǒng)[1]的問題值得關(guān)注，同時我們也希望有更好的滿足P2P特點(diǎn)的互連網(wǎng)絡(luò)結(jié)構(gòu)被提出來。

參考文獻(xiàn):

[1] G. Chen， C. Xu， H. Shen， P2P overlay networks of constant degree[R]， in: Proceedings of the International Workshop on Grid and Cooperative Computing， Lecture Notes in Computer Science， vol. 2975， 2003.

[2] M.F. Kaashoek， R. Karger， Koorde: a simple degree-optimal distributed hash table[Z]， in: Proceedings of the Second International Workshop on P2P Systems (IPIPS)， 2003.

[3] D. Malkhi， M. Naor， D. Ratajczak，Viceroy: a Scalable and Dynamic Emulation of the Butterfly[Z]， in: Proceedings of Principles of Distributed Computing (PODC’02)， 2002.

[4] S. Ratnasamy， P. Francis， M. Handley，et al. Shenker， A scalable content-addressable network[Z]， in: Proceedings of ACM SIGCOMM， 2001， pp. 329–350.

[5] A. Rowstron， P. Druschel， Pastry: scalable， decentralized object location and routing for large-scale peer-to-peer systems[Z]，in: Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware)， 2001.

[6] H.Y. Shen， C.Z. Xu and G. Chen， Cycloid: A consistent-degree and Location efficient P2P overlay network[J]， in: Performance Evaluation， Elsevier， 2005.

[7] I. Stoica， R. Morris， D. Liben-Nowell， et al，Chord: a scalable peer-topeer lookup protocol for Internet applications[M]， IEEE/ACM Trans. Networking (2003).

[8] J. Xu， A. Kumar， X. Yu， On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks[J]， IEEE J. Sel. Area Commun. (2003).

[9] B. Zhao， J. Kubiatowicz， A. Joseph， Tapestry: an infrastructure for fault-tolerant wide-area location and routing[R]， Technical Report UCB/CSD-01-1141， Computer Science Division， UC Berkeley， 2001.