結構化P2P系統路由機制的研究

摘要:基于分布式哈希表的結構化P2P系統得到了廣泛的研究，這些系統的網絡拓撲結構一般都以圖論中的一些廣為研究的圖作基礎，而且大量借鑒了并行系統的研究成果。介紹了幾個常見的結構化P2P系統，對其拓撲結構和路由算法作了分析對比。

關鍵詞:對等網絡;結構化P2P;路由;拓撲結構

中圖分類號:TP393文獻標識碼: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，Foshan 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)的結構化P2P系統得到了廣泛的研究，一些系統模型被相繼提出來。這個過程主要可以分為兩個階段，早期的系統如Chord[7]、Pastry[5]、Tapestry[9]具有O(logN) 的路由表大小和O(logN)的網絡直徑，CAN[4]分別是O(d)和O(d*N1/d)。隨著研究的深入，人們逐漸認識到結構化的P2P系統的主要弱點在于要維護嚴格的拓撲結構，尤其是在網絡攪動劇烈時大量節點的加入和離開會產生巨大的開銷。節點維護的鄰居的數量即路由表的大小是影響網絡拓撲維護開銷的主要因素，因此一些具有常數度(即節點只維護常數個鄰居)的P2P系統被提出來，如Viceroy[3]、Koorde[2]和Cycloid[1，6]等。這些系統只維護較少的常數個鄰居，而具有O(logN)的網絡直徑。如Viceroy和Cycloid鄰居數為7、Koorde鄰居數最小為2。

這些結構化P2P系統的拓撲結構都可以追述到圖論中的一些著名的圖，如Chord來自于環(ring)，CAN來自于網格(mesh)，Pastry和Tapestry近似于超立方體(hypercube)。而具有常數度的結構更是直接取自于一些規范的圖，Viceroy使用butterfly，Koorde使用de bruijn，Cycloid使用CCC。該文對結構化P2P系統的拓撲結構和路由算法作了分析對比。

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

1.1 Chord

Chord[7]地址空間組織成一個一維的環(ring)，每個節點通過指取表與系統的其余部分連接起來。在地址空間大小為N的Chord系統中，路由表共有logN 項。ID為n的節點的指取表按如下方式構成，第i行的start=(n+2i-1) mod N，succ=Successor((n+2i-1) mod N)。start表示與當前節點距離為2i-1的鄰居，Successor函數返回從start開始的第一個存在的結點，即start的后繼節點。

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

1.2 Pastry

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

Pastry的路由算法采用Plaxton模型的一個變體，通過從左到右一次校正一位數字，在大小為O(logN) 路由表上達到O(logN)的查詢距離。另一個經典的結構化P2P系統Tapestry[9]與Pastry相似，但ID的基數不必限定是2b。

1.3 路由表的計算

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

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

在Chord系統中，名字空間大小為n=2k，對節點id指取表的第i行(i=1，2，…，k)，Si=[2i-1，2i)，Di=select(Si)=successor(2i-1)，successor函數返回節點id+2i-1活動的后繼節點的相對距離，則第i行內容為Ri=id+Di=id+successor(2i-1)。在Tapestry系統中，名字空間大小為n=dx，設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向其他節點咨詢返回集合Si*d+j中的一個活動節點，路由表項內容為Ri*d+j=id+Di*d+j。Pastry系統中限定d是2的冪，其他與Tapestry系統相似。

2 路由表大小為常數的系統

2.1 CAN

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

2.2 Cycloid

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

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

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

2.3 Koorde

Koorde[2]使用de Bruijn圖作為拓撲結構的基礎。容納的節點數為2b，節點的度數為2。在de Bruijn圖中，節點用二進制數表示，節點m有兩個鄰居:2m mod 2b 和 2m+1 mod 2b，也就是m指向將m左移一位后去掉最高位并用0和1分別填充最低位得到的兩個節點，如圖圖5。

因為在環狀地址空間中，節點2m mod 2b 和 2m+1 mod 2b是相鄰的，所以Koorde改變兩個鄰居為m的后繼節點和2m mod 2b節點(仍然可以保持de Bruijn圖性質)。實際的P2P系統的節點在地址空間中是非常稀疏的，這樣de Bruijn圖上就有許多“想象中的節點”，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))

上述代碼表示節點m對關鍵字k的路由，topBit函數返回kshift的最高位數字，i °0和i °1表示2i mod 2b 和 2i+1 mod 2b。

Koorde每個節點維護兩個鄰居時可以高概率的達到O(logN)的查找距離，通過將鄰居數量增加到logN個，Koorde的查找距離可以達到O(logN/loglogN)。

2.4 Viceroy

Viceroy[3]的拓撲結構采用近似的蝴蝶網絡(butterfly network)。Viceroy是分層結構的，處在butterfly的第l層的節點有七個鄰居，包括環狀地址空間中的前導和后繼節點，同一層的前后節點，第l+1層的左右節點和l-1層的上節點。在Viceroy系統中，每個節點擁有兩個值:ID和butterfly層號。節點的ID獨立一致的從[0，1)上產生，而層號是從[1，logN]中隨機選擇(N為網絡大小的估計值)。一個節點的ID是固定不變的，而層號會隨著節點在系統中的存活時間被校正。

Viceroy的路由過程包括三步:首先是上升階段，沿著向上的連接上升到第一層;然后是下降階段，沿著向下的連接直到沒有向下連接的節點;最后是橫向階段，通過同層連接到達目標節點。Viceroy的查詢距離為O(logN)。

3 總結

以上是對各個系統的逐個分析介紹，下面將上述系統的一些屬性進行匯總。

結構化P2P系統的研究很大程度上借鑒了并行結構和圖論的研究成果，通過對已有的互連網絡結構進行修改以適應P2P系統的特點，上述許多結構被成功的引入到P2P領域。有文章提出判斷哪些拓撲結構可以用于P2P系統[1]的問題值得關注，同時我們也希望有更好的滿足P2P特點的互連網絡結構被提出來。

參考文獻:

[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.