Ｆａｓｔ－ｃｈｏｒｄ：快速部署的Ｐ２Ｐ覆蓋網絡

摘要:在與結構化覆蓋網絡Chord進行對比分析的基礎上提出了一種快速部署的P2P網絡模型Fast-chord#65377;該網絡充分利用了節點自身的管理能力，有效分解各節點間協同處理的工作量，能夠以較小的代價迅速創建#65380;部署#65377;實驗表明，該網絡具有良好的自激勵機制和優良的查詢效率，在要求快速組網的應用中具有很強的實用性#65377;

關鍵詞:Fast-chord; 分布式哈希表; 計算機對等網; 路由表

中圖分類號:TP393.02文獻標志碼:A

文章編號:1001-3695(2007)10-0305-03



計算機對等網技術是目前流行于國際計算機網絡技術研究領域的一個熱點#65377;隨著因特網的發展，越來越多的信息可以被分布在世界各地的計算機所共享，人們可以更為方便地在網上獲取所需信息，極大地方便了人們的生活#65377;P2P是一種分布式網絡，網絡的參與者共享他們所擁有的一部分資源(包括計算能力#65380;存儲能力#65380;打印等)，而這些資源能被其他對等節點(peer)直接訪問而無須經過中間媒介#65377;在此網絡中各臺計算機擔當相同的功能，無主從之分，網絡上任一臺計算機既可以作為網絡服務器，即資源(服務和內容)提供者(server)，其資源為其他計算機共享，也可以作為工作站，即資源(服務和內容)獲取者(client)，以分享其他服務器的資源#65377;任一臺計算機均可同時兼做服務器和工作站，也可只做其中之一#65377;

與傳統的分布式系統相比，P2P技術由于采用了非中心化，在可擴展性#65380;隱私保護#65380;負載均衡#65380;健壯性等方面具有無可比擬的優勢#65377;同時，P2P技術具有廣闊的應用前景#65377;目前給Internet帶寬帶來巨大沖擊的PPLive#65380;eMule#65380;BT#65380;Skype等各種P2P應用軟件層出不窮，用戶數量也急劇增加#65377;P2P計算技術正不斷應用到軍事#65380;商業#65380;政府辦公#65380;通信等諸多領域#65377;

1相關工作 

從P2P概念的出現至今出現了多種已被使用和正被研究的P2P網絡#65377;目前主流的P2P網絡模型主要分為集中目錄式對等網絡模型#65380;非結構化對等網絡模型和結構化網絡模型#65377;

Napster[1]是最早出現的P2P系統之一，也是最為典型的集中目錄式對等網絡模型#65377;Napster通過一個中央服務器保存所有Napster用戶共享的文件索引和存放位置的信息#65377;當某個用戶需要某個文件時，首先連接到Napster服務器，服務器進行相應的檢索和查詢后，會返回符合查詢要求的主機地址信息列表#65377;查詢發起主機接收到應答后，會根據網絡流量和延遲等信息進行選擇，并與合適的對應主機建立連接#65377;

在非結構化對等網絡中，不存在專門的目錄服務器，每臺主機在功能上均是對等的#65377;主機必須依靠它們所在的網絡來查找文件和定位其他對等機#65377;Freenet[2]是一個非結構化P2P文件共享系統，它與Napster最大的區別在于Freenet是純粹的P2P系統，沒有索引服務器，它采用了基于完全隨機洪泛(flooding)發現和隨機漫步(random walker)機制[3]#65377;

結構化網絡模型對拓撲結構有很嚴格的控制，數據存放的位置和查詢算法均有很精確的定義或描述，如Chord[4]#65380;Tapestry[5]#65380;Kademlia[6]#65380;SmartBoa[7]#65380;Cycloid[8]等#65377;

Chord是結構化網絡模型中很具有代表性的一種#65377;通過分布式散列表(DHT) [9，10]構成一個邏輯環結構并將關鍵值存儲在Chord中的相應節點上#65377;由于Chord中的路由表是分散的，每個節點通過與其他的少數節點交流來獲取路徑信息，Chord系統具有更好的負載平衡效果，在容錯性#65380;可擴展性#65380;資源定位和魯棒性等方面也具有優勢#65377;

Chord網絡模型為了達到資源的快速定位需要在整個環上重新部署資源定位信息#65380;環的創建#65380;節點的加入和離開均需要環上各節點做大量的協同處理工作，增加了管理及通信的代價，不能很好地適應要求快速組網的環境#65377;

2Fast-chord網絡模型設計

傳統的Chord系統由于設計的需要，一臺主機只能構成Chord環上的一個節點，而任一主機發布的資源定位信息(關鍵值)需要按算法結果在整個Chord環上重新部署，這樣就造成了某一主機節點管理的資源定位信息大部分并不屬于該主機節點#65377;理想的狀態應該是本地主機只管理本地資源信息#65377; 

2.1設計思想與目的

Fast-chord主要設計思想是構建一種快速啟動的P2P網絡#65377;該網絡允許節點的自由加入和離開，避免資源信息的重新部署#65377;Fast-chord環只通過發布的資源進行散列創建節點，不依據物理主機創建節點#65377;資源或資源定位信息不在各節點間遷移，只保留在本地，各節點只對自己節點的資源進行管理#65377;同時在資源定位上采用改進的Chord方法，在原方法基礎上充分利用了DHT均衡分布的特性，能夠更加快速#65380;準確地定位到資源#65377;

資源定位信息仍保留在本地，不涉及資源的遠程調度和訪問控制，權限管理更簡潔，更符合當前網絡安全的要求，降低了管理成本，同時也可有效減少由于資源信息調度而引起的網絡流量#65377;由于任一想加入Fast-chord環的主機必須對環有一定貢獻(至少發布一個資源)，對各個主機節點也具有一定的激勵作用#65377;

這種方法的不足之處在于喪失了對資源定位信息分布的負載平衡處理，單一某節點可能會有訪問量突增問題，但現實應用卻繞過了資源調度，訪問控制等一系列復雜#65380;不確定因素所引起的繁雜問題，能夠在極短時間內部署完畢，很適合即時#65380;高效#65380;安全網絡建設的需要#65377;

2.2Fast-chord工作原理

Fast-chord環是一種雙標簽雙系統體系結構#65377;內標簽由資源的載體(物理主機)組成，標志資源載體的分布;外標簽由所發布的資源定位信息組成，標志資源的分布#65377;每一資源載體(每一臺物理主機)構成一個局部系統，該系統主要由本地發布的資源所創建的路由表組成，并按key值建立順序鏈表#65377;所有主機的所有資源在Fast-chord外環上進行標注，構成一個全局系統，資源的查找#65380;加入#65380;刪除等操作主要依靠此外環完成#65377;

假設某一主機上有K(K≥1)個資源，對每一個待發布的資源通過hash均可算得一個惟一的key值，主機會根據該key值創建相應的節點并在環上找到合適的位置加入Fast-chord環，同時生成路由表，存儲在本地#65377;由于主機待發布的資源K可能大于0，而每一個資源均對應一個路由表，當主機有K個資源需要發布就需要維護K個路由表#65377;

一臺主機由于發布多個資源而可以在Fast-chord環上擔當多個節點的角色，這些資源邏輯上分布在Fast-chord環上的多個節點上，但物理上這些資源位于同一臺主機，資源并沒有遷移#65377;例如主機A有待發布資源ra1#65380;ra2，經hash算得key值為5#65380;9，可表示為A(5)，A(9)#65377;主機B有待發布資源rb1#65380;rb2#65380;rb3，經hash算得key值為16#65380;35#65380;60，可表示為B(16)，B(35)，B(60)#65377;設Fast-chord環規模為26，路由穩定后可得結構如圖1所示#65377;

2.3Fast-chord網絡的初始化

Fast-chord網絡初建時只需一個主機，該主機只需發布一個資源創建一個節點即可#65377;

例如設主機A上有資源ra1，經hash后算得key值為5，創建路由表，建立初始網絡，如圖2所示#65377;

2.4節點的加入和離開

新節點的加入會面臨兩種情況:a)待加入節點所屬主機已有節點加入Fast-chord環，則可直接利用已有節點的路由表建立新的節點;b)某一主機節點是首次加入Fast-chord環，則需要利用環上任一已知節點的信息作為引導信息，創建新的節點#65377;新節點創建后需要更新環上其他相關節點的路由信息，保持環上各節點路由信息的準確一致#65377;節點的離開過程類似#65377;

節點加入具體過程算法描述如下:

a)如果待加入節點n所屬主機A已有節點加入Fast-chord環，該已加入Fast-chord環節點集設為W(A)={n1，n2，n3，n4，…}，則從集合W(A)中挑選ni使得，ni

b)如果待加入節點n所屬主機A沒有節點加入Fast-chord環，則需找到已在環上創建節點的任一主機B#65377;設B已加入Fast-chord環節點集為W(B)={n1，n2，n3，n4，…}，則從集合W(B)中挑選ni，使得ni

c)調用n.join(ni)完成節點n的finger表初始化，調用n.update完成Fast-chord環的更新#65377;

例如主機C有資源rc1要加入Fast-chord環，利用hash函數算得key為23，利用已在環上創建節點的任一主機可獲得所需路由信息，假定選定的主機是A#65377;查找A的路由表集，找到順時針方向距離23最近的節點A(16)，通過A(16)的路由表初始化C(23)的路由表并向環上相關節點發送節點更新信息，如圖3#65380;4所示#65377; 

當主機C又有新的資源rc2需要加入Fast-chord環時，利用hash函數算得key值為60，由于C已有節點C(23)存在于環中，則此次無須借助其他主機即可加入Fast-chord環#65377;主機C查找自己的路由表集，找到順時針方向距離60最近的節點C(23)，利用C(23)的路由表初始化C(60)的路由表并向環上相關節點發送節點更新信息，如圖5所示#65377;

2.5節點的查找

節點的查找是在Chord查找算法基礎上進行了改進#65377;其算法的復雜度≤log 2n#65377;當每一臺主機只有一個資源需要發布時，則本算法退化為普通Chord算法#65377;

資源查找算法如下:

a)首先利用Chord算法定位下一跳位置，然后給下一跳節點發查找請求#65377;

b)當節點收到查找請求后，首先比較待查找的key與自己本身節點的key值#65377;若相同則轉d);若不同則轉c)#65377;

c)先在本地主機查找，由于本地主機創建的節點已順序鏈接，可采用二分法進行快速定位#65377;若找到則轉d);若未找到則從本地創建的所有節點中找一個順時針方向距離查詢key最近的節點，并查找這個節點的路由表，定位距離key值更近的節點#65377;若定位到更近的節點則向這個節點發送查找請求轉b)，否則返回查找失敗#65377;

d)待查找資源已找到，向請求查找節點發查找成功信息#65377;

如示例圖5中，主機A查找資源60#65377;首先在本地查找#65377;A主機不包含資源60所以不能直接命中，但A有兩個路由表A(5)#65380;A(16)，按順時針方向取距離60最近的節點A(16)#65377;查A(16)路由表，通過第六項可查得資源60所在位置#65377;

2.6Fast-chord環的存儲開銷

存儲開銷主要由路由表大小和資源定位信息數量兩部分組成，設單一路由表占據存儲空間為R，資源發布數為n，環中主機數為N，可得資源發布數與存儲開銷的函數關系為

f(n)=n×R+n(n≥N) Fast-chord網絡

n+N×RChord網絡

由于Fast-chord環的存儲開銷函數的斜率大于Chord環，故隨著發布資源的增多，Fast-chord對存儲空間的需求會大于Chord環，但仍是線性增長#65377;

2.7資源定位信息的遷移

在Chord網絡中資源定位信息會按哈希結果在整個環上分布，只有很少一部分定位信息保留在創建節點上，大部分均要進行遷移#65377;Chord環的平均資源定位信息的遷移數約為發布的資源數的一半#65377;相反，在Fast-chord網絡中每臺主機只管理自己所創建節點的資源定位信息，資源定位信息不再需要在環上遷移#65377;

3實驗結果及性能分析

針對Fast-chord網絡的激勵機制及查找路徑長度進行了模擬實驗，并與Chord網絡進行了對比分析#65377;

3.1Fast-chord環的激勵機制

Fast-chord具有一定的自主激勵機制，只有對Fast-chord環作出貢獻才能加入該環，而貢獻越多查詢時所需跳數越少，耗費的時間越短#65377;由于Fast-chord只依據發布的資源而不是主機進行散列創建節點，任意主機若加入Fast-chord環必須至少有一個資源進行發布#65377;當同一臺主機有多個資源進行發布后，由于hash函數自身具有平衡負載特性，檢索空間也會均勻分布，在檢索時加快了資源的定位速度，即發布的資源越多查找越迅速#65377;

在規模為212的Fast-chord環實驗中，共加入節點1 000個，隨著某一主機上發布資源數的增多平均跳數呈遞減趨勢，實驗結果如圖6所示#65377;

3.2查找路徑長度

為了考察Fast-chord網絡的查找路徑長度，實驗中逐一構建了節點數從64~512的Fast-chord網絡，每臺主機發布的資源數從1~4隨機產生，所查找的資源也隨機指定#65377;從圖7可以看出Fast-chord網絡的平均跳數明顯小于Chord網絡#65377;

4結束語

綜上所述，本文在分析集中目錄式#65380;非結構化和結構化對等網絡模型的基礎上，提出了一種新的快速部署的P2P網絡模型——Fast-chord#65377;該網絡在Chord資源定位算法的基礎上進行了改進，能夠更加快速命中所需資源#65377;

在資源管理上充分利用了各節點自身的管理能力，有效減少了Chord網絡中由于資源定位信息的重新部署所帶來的管理和通信方面的代價，從而更符合P2P網絡自由便捷的特點#65377;實驗表明該網絡在可擴展性#65380;高效性及實用性方面具有很強的優勢，能夠滿足應急#65380;搶險等要求即時組網的需求#65377;

參考文獻:

[1]SAROIU S， GUMMADI K P， GRIBBLE S D. Measuring and analyzing the characteristics of Napster and Gnutella hosts[J]. Multimedia Systems， 2003，2(9):170-184.

[2]LARKE I， SANDBERG O，WILEY B， et al. Freenet: a distributed anonymousinformation storage and retrieval system[C]//Proc of ICSI Workshop on Design Issues in Anonymity and Unobservability. Germany:[s.n.]， 2000:46-66.

[3]LV Q， CAO P， COHEN E， et al. Search and replication in unstructured peer-to-peer networks[C]//Proc of ACM SIGGRAPH’02. SanAntonio:[s.n.]， 2002:84-95.

[4]STOICA I， MORRIS R， KARGER D， et al. Chord: a scalable peer to peer lookup protocol for Internet applications[C]//Proc of ACM SIGCOMM. San Diego:[s.n.]， 2001:149-160.

[5]ZHAO B Y， HUANG L， STRIBLING J， et al. Tapestry: a resilient global scale overlay for service deployment[J]. IEEE Journal on Selected Areas in Communications， 2004，22(1):41-53.

[6]MAYMOUNKOV P， MAZIRES D. Kademlia: a peer to peer information system based on the xor metric[C]//Proc of the 1st International Workshop on Peer to Peer System(IPTPS’02). Cambridge:[s.n.]， 2002:53-65.

[7]胡進鋒，黎明，鄭緯民，等.帶寬自適應的P2P網絡路由協議[J].軟件學報，2005，16(5):991-999.

[8]陳貴海，須成忠，沈海英，等.一種新的常數度數的P2P覆蓋網絡[J].計算機學報，2005，28(7):1084-1095.

[9]JAIN S， MAHAJAN R， WETHERALL D. A study of the performance potential of DHT-based overlays[C]//Proc of the 4th USENIX Symp on Internet Technologies and Systems Seattle. Washington:[s.n.]， 2003:256-261.

[10]KAASHOEK M F， KARGER R. Koorde: a simple degree optimal distributed hash table[C]//Proc of the 2nd International Workshop on P2P Systems( IPIPS’03). Berkeley:[s.n.]， 2003:98-107.

第10期謝紅華，等:

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”