基于改進的混合P2P的Chord算法

吳惠芳，吳園萍

(1.諾基亞通信系統技術(北京)有限公司，浙江杭州310053;2.杭州縱橫通信股份有限公司，浙江杭州310012)

0 引言

在P2P網絡中，研究人員對資源定位算法進行了大量研究，提出了多種可擴展性的算法，如Chord［1］、Pastry［2］、CAN［3］和 Tapestry［4］等結構化算法。P2P網絡是在IP網絡上建立一個重疊網絡，有關查找和路由的操作都是基于重疊網絡進行的。因此Chord中存在邏輯路徑和物理路徑不一致的問題，即邏輯上相鄰結點，物理距離可能很遠。

針對該問題，文獻［5－7］指出，在結構化 P2P網絡中有3類解決方案:臨近路由選擇、臨近鄰居選擇和拓撲感知的D分配。這3種方案都需要考慮如何在區間內所有存活節點中選擇最近節點。目前研究比較多的是基于網絡地標的實現方法，但這種方法在實現過程中需要預設LandMark服務器，在廣域范圍內存在服務器的提供與選擇等問題。

由此提出一種基于改進的混合P2P的Chord算法——CBEH，該算法首先對混合P2P進行改進，使超結點能夠獲得局部網絡信息，所有的結點組織在Chord環上。在路由過程中，利用超級節點提供的信息優先選取物理距離較近的結點，以減少網絡延遲，提高路由效率。

1 Chord路由算法

Chord是MIT提出的P2P網絡資源定位算法。在Chord中，每個節點標識一般通過對節點IP地址進行哈希運算獲得。所有節點標識從小到大按順時針方向排列在一個邏輯標識圓環上，節點中的資源通過對資源關鍵字進行哈希運算，獲得m位的關鍵字標識。在該空間中，節點的散列值被稱為節點ID，資源的散列值被稱為鍵值。在Chord中，每個節點需要維護一個路由表。這個路由表中的第K條記錄為在地址空間中和該節點距離≥2k(0≤k≤m，地址空間為0～2m－1)的最近節點。在查找時，節點首先判斷自己是否負責該鍵值，如果沒有負責該鍵值，則節點根據路由表中的記錄，將這個查詢請求轉發給和該鍵值最接近的節點，如此下去直到最終找到負責該鍵值的節點，如圖1所示，節點N1查詢負責鍵值為16的節點，根據路由表，通過冪相鄰關系逐步逼近的路由過程，其路由序列為N1－＞N12－＞N15－＞N20。Chord可以保證在O(logN)跳數內完成資源定位。

圖1 Chord路由算法

2 CBEH算法

CBEH利用超結點提供的網絡局部信息，在路由過程中優先選取物理距離較近的結點作為下一跳，以便減少查詢的網絡延遲，提高路由效率。

2．1 改進的混合P2P

混合 P2P［8］吸取了中心化結構［9，10］和完全分布式拓撲［11，12］的優點，選擇性能較高(處理、存儲和帶寬等方面性能)的結點作為超級結點，每個超級結點存儲部分葉子結點信息，路由算法僅在超級結點之間轉發，超級結點再將查詢請求轉發給適當的葉子結點。

當用戶加入混合P2P網絡時，它通常是一個普通結點，并且會得到一個原先保存的超結點列表緩存。它從緩存中選擇p個候選超結點，給其中的每一個發送一個UDP數據包來探測，用戶將收到這些候選結點中的某一些發來的UDP回復。普通結點會選擇它認為最好的那個超結點建立連接，而不再和其他結點連接，被選擇的超結點就是它的“父超結點”。

為了獲得更多的網絡局部信息，改進的混合P2P采用不同的策略，具體實現如下:

①根據自己的網絡地址和子網掩碼計算出自己的網絡號;

②從超節點列表緩存中選擇和自己網絡號相同的候選超節點，給其中的每一個發送一個UDP數據包來探測;

③用戶將選擇候選節點中UDP回復快且子結點數沒有達到最大值的超節點建立連接;

④若沒有相同網絡號的超節點，則用戶節點首先判斷自己是否滿足超節點要求的條件，如果滿足，則設該節點即是新的超級節點，那么將加入超級節點列表，并請求其他節點更新超級節點集;否則該結點采用混合P2P中的方法來選取超級結點。

2．2 CBEH算法的設計與實現

2．2．1 CBEH 的設計

CBEH將EHP2P中所有結點組織在Chord環上，其中的超結點已經不具備超結點間的路由功能，只在查詢過程向正在查詢的結點提供向導功能(局部結點的感知能力)。系統結構圖如圖2所示。

在CBEH中，每個普通結點維護一個m項的路由表和一個指向本地超結點的路由表項，共m+1個表項。每一個超結點在原有t項結點的基礎上，增加m項路由表，共m+t。

圖2 CBEH系統結構

2．2．2 CBEH 算法查找過程

在結點k查找關鍵值Key過程描述如下:

2．2．3 結點的管理

當一個普通的結點加入系統時，它首先利用Chord算法加入到網絡中，并更新其他結點的路由表。之后該結點向向導網絡注冊以獲取超結點信息。當一個普通結點退出系統的時候，首先它請求該結點的超結點刪除該結點的信息，然后按照Chord算法將該結點負責的信息轉移到該結點的后繼結點，并更新其他結點的路由表項以反映結點的退出。

按照改進的混合P2P算法，如果在向導網絡中沒有找到符合條件的超結點且該結點符合要求，那么它就會成為新的超結點。該結點采用洪泛的方式通過向導網絡通知網絡中的其他超節點更新超結點列表。當一個超結點退出系統時，它也會以洪泛的方式通過向導網絡更新超結點列表，然后按照普通結點退出系統。該超結點的子結點如果在有限的時間內沒有收到任何信息，就會向系統申請重新指定其他超結點。

2．2．4 CBEH 算法分析

基于Chord，增加了向導網絡，使得CBEH算法具有更多的優勢:

①將物理網絡鄰居信息引入Chord算法。在路由查找過程中，優先選取物理距離較近的鄰居結點來替代指向表中的后繼結點。

②整體路由過程以Chord路由為主，從超結點得到的網絡信息在路由過程起到向導功能，所以查找的時間復雜度仍為O(logN)。

③由于混合P2P的結點管理的時間復雜度為O(1)，所以 CBEH的結點管理的時間復雜度為O(log2N)+O(1)。

3 仿真實驗結果及分析

3．1 實驗環境

PeerSim［13］是 BISON項目的一部分，它可以模擬大規模動態P2P協議網絡的通用P2P網絡模擬器，支持結構化和非結構化P2P網絡模擬，采用Java開發。

它支持2種模擬方式:離散事件模擬和輪轉模擬，其中離散事件模擬可模擬底層傳輸層，模擬精度高;輪轉模擬不考慮覆蓋層之下，模擬效率高并且模擬規模大。

實驗采用離散事件模擬方式，網絡結點數取N=2k(k∈［7，14］)，每次獨立地測量定位路徑長度。為了模擬真實網絡之間延遲，采用King數據集作為網絡之間的延遲。King數據集是通過對1 740個實際的DNS服務器之間進行延遲測量而得到的，能夠較為真實地反映Internet的延遲情況。

3．2 實驗結果

利用超級結點提供的網絡局部信息，將請求信息優先導向結點的本地范圍，降低查找時延。CBEH算法與Chord在不同網絡規模(網絡節點個數)下平均查詢時間的對比情況如圖3所示。從模擬實驗結果可以看出，CBEH算法能夠有效降低路由查找時間。

圖3 平均查找時延對比

CBEH算法與Chord在不同網絡規模下平均查找跳數的對比情況如圖4所示。從圖中可以看出，CBEH算法的平均查找跳數比Chord有所改進，其原因在于:①由于導向結點的存在，使得結點路由具備了局部感知能力，有利于首先發現局部結點或直接從本地跳出，從而在局部范圍內解決繞環問題;②在路由查找過程中，如果發現符合條件的本地結點，則把查找請求轉發給該結點請求完成搜索任務。該策略使得被轉發的結點ID比路由表中要轉發的結點ID更接近于Key，加速了路由查找過程。

圖4 平均查找跳數對比

4 結束語

提出了CBEH算法，它首先對混合P2P進行了改進，基于Chord的資源查找路由過程中，利用向導網絡提供的信息，優先選取鄰居節點作為路由節點。經過實驗證明了該算法可以有效縮短查找時延，并在一定程度上優化了路由查找過程，縮短查找路徑。但是Chord網絡仍存在拓撲維護代價大，負載均衡不易等問題。下一步的工作將在CBEH系統中研究如何減少網絡維護的代價。

［1］ STOICA Ion，MORRIS Robert，KARGER David，et al．Chord:A Scalable Peer-to-peer Lookup Service for Internet Applications［C］∥In Proceedings of the SIGCOMM 2001，San Deigo，CA，USA，2001:149 －160．

［2］ DRUSCHEL P，ROWSTRO A．Pastry:Scalable，Distributed Object Location and Routing for Large-scale Peer-topeer Systems［C］∥In IFIP/ACM International Conference on Distributed Systems Platforms(Middleware)，Heidelberg，Germany，2001:329 －350．

［3］ SYLVIA Ratnassamy，PAUL Francis，MARK Handley，et al．A Scalable Content-addressable Network［C］∥In Proceedings of the SIG-COMM 2001，San Diego，CA，USG，2001:161－172．

［4］ ZHAO B，KUBIATOWICK J，JOSEPH A．Tapestry:An Infrastructure for Fault-tolerant Wide-area Location and Routing［R］．Technical Report，U．C．Berkeley，2001．

［5］ CASIRO M，DRU SCHEL P，HU Y C，et al．Proximity Neighbor Selection in Tree-based Structured Peer-to-peer Overlays［OL］．http:∥research．microsoft．com/users/Cambridge/Mcastro/publications/location-mscn－2003－52．pdf．

［6］ KARGER D R，RUHL Matthias．Finding Nearest Neighbors in Growth-restricted Metrics［R］．IN STOC 02，2002:22－24．

［7］ RANTNASSAMY Sylvia，HANDLEY Mark，KARP Richard，et al．Topologically-aware Overlay Construction and Server Selection［C］∥in Proc．21st IEEE INFOCOM，New York，NY，2002:56 －57．

［8］ 龐慶元，林亞平．在非結構化P2P網絡的搜索算法研究［J］．計算機工程與設計，2006，27(21):4049 －4051．

［9］ SAROIU S，GUMMADI K P，GRIBBLE S D．Measuring and Analyzing the Characteristics of Napster and Gnutella Hosts［J］．Multimedia Systems，2003，9(2):170 －184．

［10］陳貴海，李振華．對等網絡:結構、應用與設計［M］．北京:清華大學出版社，2007:83－93，207－238．

［11］高軼，王瑩，馮微．Ad Hoc網絡可靠性評估［J］．無線電通信技術，2011，37(2):7 －9，18．

［12］魏恒舟，宋志群，邵國媛，等．基于NC-MCDS算法的拓撲生成技術研究［J］．無線電工程，2014，44(1):10－12，45．

［13］ BISON，PeerSim［OL］，http://peersim．sourceforge．net，2005．