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

吳惠芳，吳園萍

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

0 引言

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

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

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

1 Chord路由算法

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

圖1 Chord路由算法

2 CBEH算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2．2．4 CBEH 算法分析

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

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

②整體路由過程以Chord路由為主，從超結(jié)點(diǎn)得到的網(wǎng)絡(luò)信息在路由過程起到向?qū)Чδ?，所以查找的時(shí)間復(fù)雜度仍為O(logN)。

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

3 仿真實(shí)驗(yàn)結(jié)果及分析

3．1 實(shí)驗(yàn)環(huán)境

PeerSim［13］是 BISON項(xiàng)目的一部分，它可以模擬大規(guī)模動(dòng)態(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ī)模大。

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

3．2 實(shí)驗(yàn)結(jié)果

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

圖3 平均查找時(shí)延對(duì)比

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

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

4 結(jié)束語

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

［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］．計(jì)算機(jī)工程與設(shè)計(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］陳貴海，李振華．對(duì)等網(wǎng)絡(luò):結(jié)構(gòu)、應(yīng)用與設(shè)計(jì)［M］．北京:清華大學(xué)出版社，2007:83－93，207－238．

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

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

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