基于混合結構的Ｃｈｏｒｄ系統研究

摘要：Chord是一種比較有效的P2P路由算法，它能夠快速地查找到該資源的位置，但是當節點能力差異較大時會影響網絡的穩定性；Chord環上的節點ID與實際物理地址不一致會造成信息的延遲現象；混合式的P2P能夠較好的管理能力較差的節點，但是查詢具有盲目性。該文通過分析它們兩者的優缺點提出了基于混合結構的Chord系統，在一定程度上解決了傳統Chord的穩定性、繞路問題和混合P2P結構的查詢效率問題。

關鍵詞：Chord；P2P；混合的P2P結構

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)35-2559-02

Based on the Mixed Structure of the Chord System

ZENG Xiao-yun

(Guangxi University of Finance and Economics，Nanning 530003，China)

Abstract: Chord is an efficient routing algorithm of P2P， and it can locate resources quickly. However， the stability of network will be impacted when the abilities of nodes is different. The disaccord between actually physical address and node ID of Chord ring also leads to information delay. Hybrid P2P could be used to effectively manage the nodes with bad managing abilities， but its query lacks of clear objects. This paper analyses both advantages and disadvantages of them， and suggests a new Chord system based on mixed structure. It will solve the problems which involve the stability of traditional Chord， detour limitations and query efficiency of hybrid P2P.

Key words: chord;P2P;hybrid P2P

1 引言

當今，P2P搜索技術是網絡研究的熱點。集中式、結構化、非結構化和混合式的P2P結構各有各的優缺點。其中Chord網絡模型，以它的無中心控制、可擴展強、負載平衡、高容錯和使查詢具有方向性使得P2P的優勢更為突出，但現實環境中，Chord環上的節點之間存在很大差異性，有很多能力較弱的節點在Chord中作為獨立節點的時候，也要負責系統中大量的查詢和下載工作，由于自身資源的限制，它們必然會引起系統響應時間增加等問題，可能成為系統的瓶頸；而且，這些能力較差的節點可能隨時出現加入或離開系統的情況，這種頻繁的變遷必定增加結構化P2P系統的開銷；同時，搜索網絡與物理網絡不一致產生查詢的繞路問題。而混合結構的P2P系統通過處理能力較強的超級節點管理其他節點，能較好的管理能力弱的節點；但是混合結構的P2P系統在查詢時需要通過泛洪方式來進行，使得查詢盲目沒有方向性，查詢效率較低。如果能夠造一個系統將他們兩者結合起來，取長補短，應該可以克服雙方的缺點。

2 基于混合結構的Chord系統模型

為了實現上述想法，我們讓處理能力強、網絡帶寬大的超級節點作為Chord系統中的獨立節點，負責管理其它的節點，并代替那些節點來負擔的部分工作，就像是很多局域網的服務器作為Chord系統的節點一樣，搜索僅在超級節點中進行。如下圖(矩形表示超級節點，小圓圈表示普通節點)。

我們采用超級節點的IP地址前綴作為Chord模型的節點標識，并按照IP地址前綴將超級節點順序排成Chord環。在一定程度上可以保證標識相近的超級節點在Chord網絡中也是相鄰的。每個超級節點都直接管理若干普通節點，它們具有與超級節點標識相等的IP地址前綴。從而改變了傳統P2P系統中Chord網絡節點由單個節點構成的狀況，增強了網絡節點的健壯性。

3 系統基本操作

每個超級節點維護一張本地客戶索引表，以保存與自己IP地址前綴相同的客戶機信息，還有一張信息索引表，記錄該超級節點所管理的客戶機和發布在它們上的信息資源關鍵字的hash值。

3.1 節點的加入

這一部分主要處理新結點的加入以及由此帶來的網絡自適應問題。

當一個普通節點A加入系統的時候，它首先找到系統中的一個超級節點B，然后比較A和B的IP地址前綴，如果前綴相同，則A作為B的一個客戶機添加到以B為超級節點的域中，B修改本地客戶索引表，將A的信息添加進去。這是超級節點所在域的內部操作，對外是不可見的。如果在Chord環中沒有找到與之前綴相同的超級節點，則網絡不允許A直接加入Chord環，只有等到A有一個自己的超級節點后，才能讓該超級節點加入Chord。而域中超級節點的Chord路由表則不必進行更新，這將使得節點加入頻繁的情況下Chord 系統的路由也不會受到太大影響，從而提高了系統的效率。如果加入系統的節點是超級節點，則它根據自己IP地址前綴在Chord上找到自己的位置，并調用Chord處理節點加入的函數修改其前驅和后繼的指針表完成加入操作。

3.2 信息發布

當一個結點加入了Chord網絡后，它就可以把它本身的資源發布出去了。在發布它的資源之前，它首先會hash它所要發布的資源，由此得到一個資源的hash值，發送給自己的超級節點，超級節點調用find successor函數，查找此hash值的所對應的超級節點，找到后資源的hash值送到這個超級結點上，保存在信息索引表中；然后超級節點在自己的本地客戶索引表中隨機找出一個客戶機，將該客戶機的信息添加到信息索引表相應的資源記錄上，這樣就能實現資源的發布了。

3.3 信息查詢

當超級節點A所管理的客戶機C想查詢某個信息時，C首先把要查找的資源的關鍵字進行一個hash操作，得到一個hash值，發送給A，A調用find successor函數，找到此hash值的對應超級節點B，B在接收到此請求后，在自己的信息索引表中搜索存放有該信息hash值的記錄，找到相應的客戶機，如果未找到，發送找不到，如果找到，把找到的記錄發送給結點C，此記錄信息包含存儲所要查找的資源，最后，結點C與這個結點建立連接通信，使資源的傳送在兩個結點之間進行，而不經過任何服務器。這樣的查找方法使得查找具有方向性，不需要再像混合結構的系統那樣進行泛洪搜索。

3.4 節點的退出

在傳統的Chord 系統中， 如果節點A是Chord環上的某個節點（即超級節點），則它退出的時候，路由表中包含A的節點都將把A替換成A的后繼。如果使用基于混合結構的Chord系統，Chord環上的節點是超級節點，該超級節點所管理的域中某一客戶機退出不會影響Chord環中超級節點的路由表中的信息，只需超級節點的本地客戶索引表中將該客戶機的信息刪除并將發布在它上面的信息轉移到別的節點上即可。這就可以保證Chord系統在有節點頻繁退出時的穩定性。當然，超級節點也有退出Chord環的可能，無論是超級節點B正常或異常退出，根據Chord的自適應能力，能將原先發布在B上的信息轉移到后繼節點C上。 但是，因為超級節點是某個局域網的服務器，具有較強的性能，所以一般情況下不會出現失效退出的情況。

3.5 負載均衡

如果由于發布在某個節點上的信息很熱門引發了高訪問量，則有可能會造成網絡擁塞。為了解決這個問題，超級節點需要定期檢查各個客戶機的文件訪問情況，挑選出一段時間內訪問頻率較高的文件，將他們冗余復制到自己的鄰居超級節點上。

4 系統評估

由于根據IP地址對節點進行了分組，可以保證物理位置相鄰的節點屬于同一區域內，普通節點加入或者退出系統所引發的不穩定性遠少于傳統的Chord；并且信息的轉儲只發生在物理位置相鄰的超級節點間，提高了網絡的穩定性；信息的路由按照從近到遠的順序進行，減少了信息在網絡上的傳輸距離、及傳輸時延，因而減少了信息在網絡中傳輸的代價；而且因為引入了Chord環，克服了混合P2P模型泛洪的致使查詢效率低下的問題。

5 下一步的工作

該論文將Chord系統和混合結構的P2P系統結合起來，在一定程度上優化了P2P系統的結構，使得系統的穩定性和可靠性及效率有了提高。但是對于安全問題和并行查找沒有進行研究，這將是下一步努力的方向。

參考文獻：

[1] 任小金，古志民，高志偉，段趙磊. RR-Chord:一個基于Chord 的低開銷快速查詢P2P系統[J].北京理工大學學報，2008，28(2):134-138.

[2] 楊明華，曹元大，張常有，于炯，譚勵.Fast-chord:快速部署的P2P覆蓋網絡[J].計算機應用研究，2007，24(10):305-307.

[3] 祝銘，李佳，陸際光.G-Chord:具有本地性和可靠性的改進型Chord模型[J].計算機應用與軟件，2008，25(5):203-204.

[4] 董曉剛.Chord網絡的搜索方法研究[D].山東師范大學碩士學位論文，2007，4.

[5] 姜守旭.韓希先，李建中.基于超節點的Chord系統[J].小型微型計算機系統，2007，28(2):266-270.

[6] 呂二濤.混合多層P2P網絡中群的深入研究[D].西安電子科技大學碩士學位論文，2007，1.