李斐，郭曉

(中國傳媒大學 信息工程學院，北京 100024)

對等網中Chord協(xié)議仿真及其性能分析

李斐，郭曉

(中國傳媒大學 信息工程學院，北京 100024)

Chord協(xié)議就是一種結構化的全分布式拓撲結構，這種類型的對等網絡實現(xiàn)了無中心服務器的目標，但相應的就需要解決有效定位和存儲特定數(shù)據(jù)的問題，Chord協(xié)議給特定的數(shù)據(jù)一個鍵值，將其映射到和鍵值對應的節(jié)點之上，這樣數(shù)據(jù)的存儲位置就可以很容易通過這種對應關系進行查找。這種方式解決了無中心檢索服務器的文件檢索問題，但對覆蓋網的結構有嚴格的要求，同時節(jié)點的加入與離開也會影響覆蓋網的結構，因此需要仿真Chord協(xié)議的性能來評估其可用性。

對等網 ；Chord協(xié)議；OverSim

1 引言

對等網是分布式的結構，理想化的對等網旨在設計一種沒有集中控制和層次化組織結構的系統(tǒng)，系統(tǒng)內的節(jié)點在功能上完全對等，并且能夠實現(xiàn)匿名參與、冗余存儲、節(jié)點選擇、身份認證、資源檢索、分層命名等功能。在對等網需要實現(xiàn)的如此多的功能當中，最為基礎的核心功能是數(shù)據(jù)的有效存儲和檢索。對等網協(xié)議的設計也都是從這個基點出發(fā)的，并由此而誕生出了不同拓撲類型的對等網。在Chord協(xié)議中數(shù)據(jù)信息存儲的存儲操作詩針對每一個數(shù)據(jù)文件給定一個鍵值，將這個鍵值存儲到某個節(jié)點上，該節(jié)點則負責和這個鍵值相關的一些操作。

這些操作的次數(shù)會隨著節(jié)點數(shù)量的增加和節(jié)點的加入與離開而增加，從而引起網絡資源的消耗，這將影響網絡的可用性，因此需要對Chord協(xié)議進行測量與評估。

2 背景理論

2.1 對等網分類

在互聯(lián)網的底層物理構架中，存在不同的網絡拓撲結構，包括星形結構、總線型結構、環(huán)形結構等不同的類型[1]。不同拓撲的網絡，有不同的特點。而對于對等網來說，也可以根據(jù)不同的拓撲來對其進行分類，并且對于缺乏中心服務器的對等網來說，如何在這種情況下來構建并維護一個高效的拓撲結構，以實現(xiàn)各種功能，是一個很大的挑戰(zhàn)。在設計一個對等網系統(tǒng)時，需要構造一個不同于C/S機構的非集中的覆蓋網絡拓撲結構，在這個過程當中，需要解決的問題包括海量節(jié)點的命名組織方式、信息在節(jié)點間的傳遞方式、資源的索引和定位方式以及路由策略等。在對等網的發(fā)展過程中，出現(xiàn)了以下幾種不同拓撲類型的對等網[2]：

(1)集中式拓撲(Centralized Topology，也稱為中心化拓撲)

(2)全分布式非結構化拓撲(Decentralized Unstructured Topology)

(3)全分布式拓撲(Decentralized Structured Topology)

(4)混合式拓撲(Partially Decentralized Topology)

集中式拓撲的對等網是最早出現(xiàn)的如圖1所示，對等網先驅Napster就是其中的典型。這一類網絡的拓撲類似于星形拓撲結構，所有的節(jié)點與中央檢索服務器鏈接，從而形成一個星形結構，當然這種結構不是物理網絡上的星

形結構，而是在對等網覆蓋網上形成的一個虛擬的星形結構。在網絡運行的過程中，所有參與節(jié)點將需要的信息(名稱、地址、資源等)向中央服務器注冊，中央服務器則保存所有上傳的文件索引信息和擁有此文件的節(jié)點的信息，當某個節(jié)點請求某個資源時，由中央服務器進行檢索，并為該節(jié)點返回存儲有該文件的用戶信息，之后的文件傳輸過程則由資源請求者和資源擁有者來完成。這種結構的對等網結構簡單，便于維護，具有很強的可管理性，在資源的檢索方面也具有很高的效率，可以實現(xiàn)復雜查詢。同時該結構的對等網也有一些缺點，首先是存在單點失效問題，中央服務器的故障會導致整個網絡的癱瘓，其次是雖然中央服務器不負責資源的傳輸，但隨著網絡規(guī)模的擴大，海量節(jié)點的維護和資源的更新對于中央服務器的性能也是很大的挑戰(zhàn)。

全分布式非機構化對等網中網絡拓撲是隨機的，各節(jié)點也不需要根據(jù)算法來存儲資源存儲信息。網絡中的資源檢索定位依靠泛洪(flooding)來完成，網絡中沒有中央服務器，不同文件的檢索信息也不會固定的存儲于某一節(jié)點，各節(jié)點維護自身的檢索信息，如果某一節(jié)點需要某資源，向其全部鄰居發(fā)送查詢請求，如果鄰居有該資源，則將符合請求的信息返回，并繼續(xù)向他們的鄰居發(fā)送這一查詢請求，如果沒有該資源，則直接向其鄰居發(fā)送這一查詢請求，直到查詢消息中所包含的TTL(Time To Live)值減少為0。在這種拓撲結構的對等網中，節(jié)點可以隨機的加入或離開網絡，而網絡也不需要因此維護拓撲結構而增加開銷，提高了網絡的健壯性，但這種拓撲結構最大的缺點就在于查詢效率太低，查詢消息的數(shù)目隨著鄰居轉發(fā)次數(shù)指數(shù)級別的增長，雖然采用BFS、隨機漫步等方式減少查詢路徑，但改善效果有限。初代的Gnutella和Freenet都是全分布式非結構化對等網的代表。

全分布式結構化拓撲的對等網使用一種稱為分布式散列表的技術來構建拓撲、組織節(jié)點。分布式散列表(Distributed Hash Table，DHT)是一種分布式的計算方式，通過計算得到關鍵值(key)的集合，然后將其均勻的分布到分布式系統(tǒng)的所有節(jié)點上，這樣能夠使得檢索信息高效的傳遞到系統(tǒng)中僅有的那一個存儲了檢索者需要key值的那個節(jié)點上。通過這一技術，對等網內的大量節(jié)點組織成一個巨大的散列表，散列表被分割成不連續(xù)的塊，每個節(jié)點管理一部散列分區(qū)塊，利用DHT技術，可以知道當前對等網中分布于各個節(jié)點的數(shù)據(jù)的概覽，而獨立于其實際位置。因此數(shù)據(jù)的位置依賴于當前的DHT狀態(tài)而不固有地依賴數(shù)據(jù)本身。由于全分布式結構化對等網絡擺脫了中央檢索服務器，擺脫了單點失效等問題，提供了一種高效的檢索機制，經典的全分布式結構化拓撲對等網包括CAN、Chord、Pastry、Tapestry等協(xié)議，目前包括BitTorrent和eMule都增加了對DHT技術的支持。

圖2 混合式拓撲對等網

混合式的對等網結合了全分布對等網和集中式對等網的特點，形成一種混合的結構。在這種類型的對等網中，將參與到網絡中的節(jié)點按照一定評價標準(計算能力、帶寬、滯留時間等)區(qū)分為超級節(jié)點和普通節(jié)點。如圖2所示，超級節(jié)點與其周圍的普通節(jié)點形成一個自治域，域內采用集中目錄式的結構，整個對等網中不同的域之間則通過分布式對等網的節(jié)點組織方式形成拓撲。在這種拓撲的對等網當中，被選為超級節(jié)點的節(jié)點負責維護節(jié)點的加入或離開以及域內資源檢索信息的收集，如果超級節(jié)點離開網絡，則由域中新的節(jié)點代替它的角色。KaZaa和Skype都是采用混合式拓撲的對等網應用。

2.2 Chord協(xié)議

Chord協(xié)議主要定義了如何查詢鍵值的儲存位置，節(jié)點加入和離開的機制，以及從節(jié)點失效中恢復等方面[3]。Chord協(xié)議使用穩(wěn)定散列函數(shù)(consistent hashing)來為節(jié)點分配節(jié)點標識符Node ID和鍵值k。當一個節(jié)點加入到系統(tǒng)中時，將節(jié)點IP地址利用哈希函數(shù)產生一個節(jié)點標識符，數(shù)據(jù)的鍵值是將數(shù)據(jù)作為輸入用哈希函數(shù)產生的。然后根據(jù)節(jié)點的標識符和數(shù)據(jù)的鍵值，每個節(jié)點存儲一定數(shù)量的鍵值，由于穩(wěn)定散列函數(shù)的特點，每個節(jié)點所保存的鍵值的數(shù)量大致是相同的，節(jié)點加入離開造成的在節(jié)點間移動的鍵值數(shù)也是比較少的。在擁有N個節(jié)點的Chord網絡中，每個節(jié)點平均存儲O(logN)個其他節(jié)點的路由信息。

節(jié)點的標識符和數(shù)據(jù)的鍵值都為m(m的大小必須使得不同文件得到相同鍵值的概率可忽略)位。節(jié)點按照標識符的順序依次影射到一個稱為Chord環(huán)的圓形地址空間上，鍵值k被影射到與鍵值相同的節(jié)點，如果沒有值相同的節(jié)點，則分配給第一個后繼節(jié)點(successor peer)，后繼節(jié)點是指在圓形地址空間中從該值順時針方向所遇到的第一個節(jié)點。當有新的節(jié)點加入到系統(tǒng)中時，為了保持鍵值和節(jié)點標識符的對應，被影射到該值后繼節(jié)點的一些鍵值需要重新分配，小于該標識符的被分配給該節(jié)點后繼節(jié)點的鍵值需要被分配給新加入節(jié)點，當有節(jié)點離開時，該節(jié)點所持有的鍵值則全部分配給該值的后繼節(jié)點。因此有節(jié)點加入或者離開時，只對該節(jié)點的后繼節(jié)點產生影響。在圖3當中Chord環(huán)的m取值6，參與節(jié)點一共有10個，標識符10的后繼節(jié)點是節(jié)點14，所以鍵值k(10)存儲在14節(jié)點，如果標識符為28的節(jié)點加入到系統(tǒng)中來，節(jié)點32將不再存儲鍵值k(24)，這個鍵值將由新的后繼節(jié)點28來存儲。

Chord環(huán)當中的節(jié)點需要知道怎樣去聯(lián)系其后繼節(jié)點以完成資源的檢索，資源的查詢過程實際上就是鍵值k和節(jié)點標識符Node ID的匹配過程[4]。對于一個給定的鍵值，查詢過程可以在Chord環(huán)中通過后繼節(jié)點不斷傳遞直到遇到存儲了所需要鍵值信息的節(jié)點。圖3中是一個檢索的例子，節(jié)點8 需要查找鍵值54，節(jié)點8向后繼節(jié)點發(fā)起查詢請求，未完成查詢請求時后繼節(jié)點轉發(fā)查詢請求，最終查詢完成找到鍵值54的存儲節(jié)點，既節(jié)點56。查詢由節(jié)點8和節(jié)點56之間的每一個節(jié)點轉發(fā)完成的，查詢的響應沿著查詢路徑返回。

圖3 節(jié)點查詢過程

圖4 finger table生成過程

如果所有的查詢都是由這種方式完成，顯然會在系統(tǒng)內產生極大的查詢消息，因此每個節(jié)點會保存一個稱為finger table的路由表格，其生成過程如圖4所示。首先，m是鍵值和節(jié)點標識符的位數(shù)，在節(jié)點n的路由表中第i條路由條目包括了該節(jié)點標識符的值n與2i-1的和所對應鍵值的存儲節(jié)點s，即s=successor(n+2i-1)，1≤i≤m。finger table中的路由條目包含了目標節(jié)點Chord環(huán)的標識符和IP地址以及端口等信息。表1中顯示了節(jié)點8的finger table，第一條路由條目指向了節(jié)點14，因為(8+20)mod 26=9，鍵值9的后繼節(jié)點是節(jié)點14，因此第一條路由條目指向了節(jié)點14。同樣的，最后一條路由條目指向了節(jié)點42，因為(8+25)mod 26=40，而標識符40的后繼節(jié)點是42。在這種方式下，每個節(jié)點存儲少量對等節(jié)點信息，并且對于相隔越近的后繼節(jié)點，保存其路由信息的概率越大，當然，finger table所包含的路由信息不足以使節(jié)點直接確定任意一個鍵值的后繼節(jié)點。例如節(jié)點8無法確定鍵值35的后繼節(jié)點，因為鍵值35的后繼節(jié)點不在節(jié)點8的finger table中。當節(jié)點8查詢鍵值35時，可以查看其路由表，在路由表中選擇和鍵值35最近的后繼節(jié)點，既節(jié)點32來發(fā)起查詢請求，不必從其最近的后繼節(jié)點14來發(fā)起查詢請求。

表1 節(jié)點8的finger table

在Chord當中，有新節(jié)點加入時，某些節(jié)點需要改變其后繼節(jié)點的信息，為了保證系統(tǒng)的可用性，節(jié)點及時更新其后繼節(jié)點信息是非常重要的，因此Chord協(xié)議會定期更新節(jié)點的后繼節(jié)點信息和finger table路由表。由于Chord協(xié)議依賴于參與所有節(jié)點都知道其后繼節(jié)點這一事實，因此當一個節(jié)點的后繼節(jié)點失效時，存在著節(jié)點無法知道新后繼節(jié)點的可能性，而且在這種情況下是無法去獲取新后繼節(jié)點的信息的。為了避免這種情況的發(fā)生，每個節(jié)點保持一個大小為r的后繼節(jié)點表格，當中包含了r個后繼節(jié)點的信息，當前后繼節(jié)點失效時，從表格中依次選擇下一個節(jié)點作為新的后繼節(jié)點。假設每一個節(jié)點的失效概率是p，那么所有r個后繼節(jié)點失效的概率是pr，r的增大會增加系統(tǒng)的魯棒性。

3 仿真試驗

3.1 仿真環(huán)境

仿真實驗采用了OverSim仿真框架，OverSim是一個基于OMNeT++的覆蓋網仿真框架，是事件驅動的仿真平臺[5]，具有靈活可擴展的特性，最大可以支持100000個對等節(jié)點的仿真，OverSim可以仿真結構化和非結構化的對等網絡，例如Chord[6]、Kademila、Pastry、Bamboo、Koorde、Gia等。 OverSim利用OMNeT++的圖形接口來可視化覆蓋網結構、底層網絡的結構和數(shù)據(jù)包的傳輸，從而可以直觀的調試[7]。OverSim提供了數(shù)據(jù)收集和統(tǒng)計模塊，方便后續(xù)的數(shù)據(jù)處理與分析。

3.2 仿真參數(shù)設置

Chord協(xié)議可以以迭代或者遞歸的方式來實現(xiàn)，迭代方式的查詢請求會根據(jù)節(jié)點的finger table中的信息來進行查詢，每一次移動都會更接近目標節(jié)點，遞歸方式的查詢節(jié)點將查詢請求轉發(fā)到下一個節(jié)點，直到查詢請求到達鍵值的后繼節(jié)點，在仿真過程中設置為迭代查詢方式。

OverSim的底層拓撲設置為SimpleUnderlay，這是一種簡化的平面網絡結構，SimpleUnderlay為每個節(jié)點分配底層網絡坐標，數(shù)據(jù)包的延遲基于源節(jié)點和目的節(jié)點的坐標距離計算。

在仿真過程中節(jié)點數(shù)目會逐漸增加，不斷有新的節(jié)點加入到網絡當中。系統(tǒng)的數(shù)據(jù)統(tǒng)計模塊會收集每一次事件的相關信息，在仿真停止后以文本形式輸出，后續(xù)的數(shù)據(jù)可視化可以用其他工具完成。仿真分為兩次進行，第一次設置Chord環(huán)節(jié)點數(shù)為100個，當節(jié)點增加到100個時停止仿真，從第一仿真的結果中選取20次觀察進行分析。第二次設置Chord環(huán)節(jié)點數(shù)為1000個，當節(jié)點數(shù)增加到1000個時停止仿真。從第二次仿真結果中選擇25次觀察進行分析。

3.3 仿真結果及分析

從圖5、圖6兩次實驗結果的統(tǒng)計圖中可以看出節(jié)點加入到Chord環(huán)中的難度與Chord環(huán)的大小無關，在實驗中，當Chord環(huán)的參與節(jié)點數(shù)達到50個以上時，等待參與到Chord中的節(jié)點一直維持在10個左右。這樣的結果符合Chord網絡的特點，即節(jié)點加入chord網絡只引起一小部分節(jié)點所持有鍵值的變動，不會造成網絡大規(guī)模地震蕩。

圖5 實驗一中節(jié)點參與情況統(tǒng)計

圖6 實驗二中節(jié)點參與情況統(tǒng)計

事件數(shù)是指在網絡當中包括節(jié)點加入，資源查詢，節(jié)點之間交換資源等所有的節(jié)點間信息交換動作，這個數(shù)值在一定程度上可以反映當前網絡的通信負擔。從圖7，圖8兩次實驗結果的統(tǒng)計圖中可以看到事件數(shù)目隨著節(jié)點數(shù)目的增加而增加，事件數(shù)的增長慢于指數(shù)函數(shù)，但是稍快于線性函數(shù)，在實驗所選擇規(guī)模大小的網絡中避免了非結構化全分布式對等網絡內通信負擔隨節(jié)點數(shù)指數(shù)級增加的問題。Chord協(xié)議當中查詢信息平均需要O(logN)來完成查詢請求，節(jié)點加入與離開會產生O(log2N)條更改通知信息，因此隨著節(jié)點數(shù)增加的事件數(shù)更多的是節(jié)點間交換數(shù)據(jù)的信息。

圖7 實驗一中事件數(shù)的增長情況

圖8 實驗二中事件數(shù)的增長情況

在實驗過程中還存在諸多的不足，是下一步工作需要改進的方向。實驗中各節(jié)點是完全平等的，即假設所有節(jié)點的計算能力和帶寬是一致的，這顯然不符合真實的網絡環(huán)境，試驗由于參數(shù)設置和仿真協(xié)議的原因，在試驗中Chord環(huán)只有節(jié)點加入而沒有節(jié)點退出，沒有對這種更為動態(tài)的網絡環(huán)境進行仿真，以上都是下一步的仿真實驗可以考慮提高的地方。

4 總結

本文從對等網的分類出發(fā)，在介紹典型的對等網絡之后對Chord協(xié)議進行了介紹和分析。Chord協(xié)議解決了對等網中數(shù)據(jù)存儲節(jié)點選擇的問題，并且由每個節(jié)點維護一個路由表來實現(xiàn)高效的覆蓋網路由。為了驗證Chord協(xié)議的有效性和可用性，通過OverSim平臺進行了簡單的仿真，實驗結果表明Chord協(xié)議在節(jié)點加入方面和抑制通信消耗增長從而實現(xiàn)系統(tǒng)可擴展性方面能夠達到Chord協(xié)議的設計目標，是一種高效可擴展的完全分布結構化對等網。

[1]謝希仁. 計算機網絡[M]. 北京：電子工業(yè)出版社，2009.

[2]管磊. P2P技術揭秘[M]. 北京：清華大學出版社，2011.

[3]Ion Stoica，R Morris，David Liben-Nowell，etal. Chord：a scalable peer-to-peer lookup protocol for internet applications[J]. IEEE ACM Transactions on Networking，2003，11(1)：17-32.

[4]Lua E K，Crowcroft J，Pias M，et al. A Survey and comparison of peer-to-peer overlay netword schemes[J]. IEEE Communications Surveys & Tutorials，2005，7(2)：72-93.

[5]Baumgart I，Heep B，Krause S. OverSim：A Flexible Overlay Network Simulation Framework[C].IEEE Global Internet Symposium，2007：79-84.

[6]Furness J，Chowdhury F，Kolberg M. An Evaluation of EpiChord in OverSim[C].International Conference on Network Communication, 2014：3-19.

[7]Munoz Gea J P，Malgosa Sanahuja J，Manzanares Lopez P，et al. Simulation of a P2P Application Using OverSim[C].International Conference on Advances in Future Internet,IEEE，2009：53-60.

[8]Yi Zhong MA，Ding H Y，Yong Quan M，et al. Research and plan improvement of Chord algorithm in structured P2P network resource search[J]. Electronic Design Engineering，2010，(05)：14-18.

[9]Ding S，Zhao X. Analysis and improvement on Chord protocol for structured P2P[C].IEEE International Conference on Communication Software and Networks.，2011：214-218.

[10]張震，王曉明. 對等網中Chord資源查找算法研究[J]. 計算機工程與應用，2006，42(11)：147-152.

(責任編輯：王 謙)

SimulationandPerformanceAnalysisofChordProtocolinPeertoPeerNetworks

LI Fei，GUO Xiao

(Information Engineering School，Communication University of China，Beijing 100024，China)

The Chord is one of the fully distributed topology structured P2P network，this type of P2P network has no central server，but the protocol need to solve the problem of efficiently data storage and locate node. Chord protocol give a key to each file，the key/file pair stores at a node which map the key. And data can be easily searched by this correspondence. This method solves the file retrieval problem，but there are strict requirements on the structure of overlay network，and the nodes join and leave will also affect the structure of overlay network. It is necessary to simulate the performance of Chord protocol，assess its availability，and find the way to improve.

peer to peer networks；Chord protocol；OverSim

TP393.04

A

1673-4793(2017)05-0027-06

2017-05-12

李斐(1994-)，男(漢族)，山西長治人，中國傳媒大學碩士研究生.E-mail：375401532@qq.com