基于改進(jìn)的混合P2P的Chord算法

吳惠芳，吳園萍

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

0 引言

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

針對該問題，文獻(xiàn)［5－7］指出，在結(jié)構(gòu)化 P2P網(wǎng)絡(luò)中有3類解決方案:臨近路由選擇、臨近鄰居選擇和拓?fù)涓兄腄分配。這3種方案都需要考慮如何在區(qū)間內(nèi)所有存活節(jié)點中選擇最近節(jié)點。目前研究比較多的是基于網(wǎng)絡(luò)地標(biāo)的實現(xiàn)方法，但這種方法在實現(xiàn)過程中需要預(yù)設(shè)LandMark服務(wù)器，在廣域范圍內(nèi)存在服務(wù)器的提供與選擇等問題。

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

1 Chord路由算法

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

圖1 Chord路由算法

2 CBEH算法

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

2．1 改進(jìn)的混合P2P

混合 P2P［8］吸取了中心化結(jié)構(gòu)［9，10］和完全分布式拓?fù)洌?1，12］的優(yōu)點，選擇性能較高(處理、存儲和帶寬等方面性能)的結(jié)點作為超級結(jié)點，每個超級結(jié)點存儲部分葉子結(jié)點信息，路由算法僅在超級結(jié)點之間轉(zhuǎn)發(fā)，超級結(jié)點再將查詢請求轉(zhuǎn)發(fā)給適當(dāng)?shù)娜~子結(jié)點。

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

為了獲得更多的網(wǎng)絡(luò)局部信息，改進(jìn)的混合P2P采用不同的策略，具體實現(xiàn)如下:

①根據(jù)自己的網(wǎng)絡(luò)地址和子網(wǎng)掩碼計算出自己的網(wǎng)絡(luò)號;

②從超節(jié)點列表緩存中選擇和自己網(wǎng)絡(luò)號相同的候選超節(jié)點，給其中的每一個發(fā)送一個UDP數(shù)據(jù)包來探測;

③用戶將選擇候選節(jié)點中UDP回復(fù)快且子結(jié)點數(shù)沒有達(dá)到最大值的超節(jié)點建立連接;

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

2．2 CBEH算法的設(shè)計與實現(xiàn)

2．2．1 CBEH 的設(shè)計

CBEH將EHP2P中所有結(jié)點組織在Chord環(huán)上，其中的超結(jié)點已經(jīng)不具備超結(jié)點間的路由功能，只在查詢過程向正在查詢的結(jié)點提供向?qū)Чδ?局部結(jié)點的感知能力)。系統(tǒng)結(jié)構(gòu)圖如圖2所示。

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

圖2 CBEH系統(tǒng)結(jié)構(gòu)

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

在結(jié)點k查找關(guān)鍵值Key過程描述如下:

2．2．3 結(jié)點的管理

當(dāng)一個普通的結(jié)點加入系統(tǒng)時，它首先利用Chord算法加入到網(wǎng)絡(luò)中，并更新其他結(jié)點的路由表。之后該結(jié)點向向?qū)ЬW(wǎng)絡(luò)注冊以獲取超結(jié)點信息。當(dāng)一個普通結(jié)點退出系統(tǒng)的時候，首先它請求該結(jié)點的超結(jié)點刪除該結(jié)點的信息，然后按照Chord算法將該結(jié)點負(fù)責(zé)的信息轉(zhuǎn)移到該結(jié)點的后繼結(jié)點，并更新其他結(jié)點的路由表項以反映結(jié)點的退出。

按照改進(jìn)的混合P2P算法，如果在向?qū)ЬW(wǎng)絡(luò)中沒有找到符合條件的超結(jié)點且該結(jié)點符合要求，那么它就會成為新的超結(jié)點。該結(jié)點采用洪泛的方式通過向?qū)ЬW(wǎng)絡(luò)通知網(wǎng)絡(luò)中的其他超節(jié)點更新超結(jié)點列表。當(dāng)一個超結(jié)點退出系統(tǒng)時，它也會以洪泛的方式通過向?qū)ЬW(wǎng)絡(luò)更新超結(jié)點列表，然后按照普通結(jié)點退出系統(tǒng)。該超結(jié)點的子結(jié)點如果在有限的時間內(nèi)沒有收到任何信息，就會向系統(tǒng)申請重新指定其他超結(jié)點。

2．2．4 CBEH 算法分析

基于Chord，增加了向?qū)ЬW(wǎng)絡(luò)，使得CBEH算法具有更多的優(yōu)勢:

①將物理網(wǎng)絡(luò)鄰居信息引入Chord算法。在路由查找過程中，優(yōu)先選取物理距離較近的鄰居結(jié)點來替代指向表中的后繼結(jié)點。

②整體路由過程以Chord路由為主，從超結(jié)點得到的網(wǎng)絡(luò)信息在路由過程起到向?qū)Чδ埽圆檎业臅r間復(fù)雜度仍為O(logN)。

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

3 仿真實驗結(jié)果及分析

3．1 實驗環(huán)境

PeerSim［13］是 BISON項目的一部分，它可以模擬大規(guī)模動態(tài)P2P協(xié)議網(wǎng)絡(luò)的通用P2P網(wǎng)絡(luò)模擬器，支持結(jié)構(gòu)化和非結(jié)構(gòu)化P2P網(wǎng)絡(luò)模擬，采用Java開發(fā)。

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

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

3．2 實驗結(jié)果

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

圖3 平均查找時延對比

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

圖4 平均查找跳數(shù)對比

4 結(jié)束語

提出了CBEH算法，它首先對混合P2P進(jìn)行了改進(jìn)，基于Chord的資源查找路由過程中，利用向?qū)ЬW(wǎng)絡(luò)提供的信息，優(yōu)先選取鄰居節(jié)點作為路由節(jié)點。經(jīng)過實驗證明了該算法可以有效縮短查找時延，并在一定程度上優(yōu)化了路由查找過程，縮短查找路徑。但是Chord網(wǎng)絡(luò)仍存在拓?fù)渚S護(hù)代價大，負(fù)載均衡不易等問題。下一步的工作將在CBEH系統(tǒng)中研究如何減少網(wǎng)絡(luò)維護(hù)的代價。

［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］ 龐慶元，林亞平．在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的搜索算法研究［J］．計算機工程與設(shè)計，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］陳貴海，李振華．對等網(wǎng)絡(luò):結(jié)構(gòu)、應(yīng)用與設(shè)計［M］．北京:清華大學(xué)出版社，2007:83－93，207－238．

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

［12］魏恒舟，宋志群，邵國媛，等．基于NC-MCDS算法的拓?fù)渖杉夹g(shù)研究［J］．無線電工程，2014，44(1):10－12，45．

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