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

李斐，郭曉

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

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

李斐，郭曉

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

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

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

1 引言

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

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

2 背景理論

2.1 對等網(wǎng)分類

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

(1)集中式拓?fù)?Centralized Topology，也稱為中心化拓?fù)?

(2)全分布式非結(jié)構(gòu)化拓?fù)?Decentralized Unstructured Topology)

(3)全分布式拓?fù)?Decentralized Structured Topology)

(4)混合式拓?fù)?Partially Decentralized Topology)

集中式拓?fù)涞膶Φ染W(wǎng)是最早出現(xiàn)的如圖1所示，對等網(wǎng)先驅(qū)Napster就是其中的典型。這一類網(wǎng)絡(luò)的拓?fù)漕愃朴谛切瓮負(fù)浣Y(jié)構(gòu)，所有的節(jié)點(diǎn)與中央檢索服務(wù)器鏈接，從而形成一個星形結(jié)構(gòu)，當(dāng)然這種結(jié)構(gòu)不是物理網(wǎng)絡(luò)上的星

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

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

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

圖2 混合式拓?fù)鋵Φ染W(wǎng)

混合式的對等網(wǎng)結(jié)合了全分布對等網(wǎng)和集中式對等網(wǎng)的特點(diǎn)，形成一種混合的結(jié)構(gòu)。在這種類型的對等網(wǎng)中，將參與到網(wǎng)絡(luò)中的節(jié)點(diǎn)按照一定評價(jià)標(biāo)準(zhǔn)(計(jì)算能力、帶寬、滯留時(shí)間等)區(qū)分為超級節(jié)點(diǎn)和普通節(jié)點(diǎn)。如圖2所示，超級節(jié)點(diǎn)與其周圍的普通節(jié)點(diǎn)形成一個自治域，域內(nèi)采用集中目錄式的結(jié)構(gòu)，整個對等網(wǎng)中不同的域之間則通過分布式對等網(wǎng)的節(jié)點(diǎn)組織方式形成拓?fù)?。在這種拓?fù)涞膶Φ染W(wǎng)當(dāng)中，被選為超級節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)責(zé)維護(hù)節(jié)點(diǎn)的加入或離開以及域內(nèi)資源檢索信息的收集，如果超級節(jié)點(diǎn)離開網(wǎng)絡(luò)，則由域中新的節(jié)點(diǎn)代替它的角色。KaZaa和Skype都是采用混合式拓?fù)涞膶Φ染W(wǎng)應(yīng)用。

2.2 Chord協(xié)議

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

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

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

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

圖4 finger table生成過程

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

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

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

3 仿真試驗(yàn)

3.1 仿真環(huán)境

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

3.2 仿真參數(shù)設(shè)置

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

OverSim的底層拓?fù)湓O(shè)置為SimpleUnderlay，這是一種簡化的平面網(wǎng)絡(luò)結(jié)構(gòu)，SimpleUnderlay為每個節(jié)點(diǎn)分配底層網(wǎng)絡(luò)坐標(biāo)，數(shù)據(jù)包的延遲基于源節(jié)點(diǎn)和目的節(jié)點(diǎn)的坐標(biāo)距離計(jì)算。

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

3.3 仿真結(jié)果及分析

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

圖5 實(shí)驗(yàn)一中節(jié)點(diǎn)參與情況統(tǒng)計(jì)

圖6 實(shí)驗(yàn)二中節(jié)點(diǎn)參與情況統(tǒng)計(jì)

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

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

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

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

4 總結(jié)

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

[1]謝希仁. 計(jì)算機(jī)網(wǎng)絡(luò)[M]. 北京：電子工業(yè)出版社，2009.

[2]管磊. P2P技術(shù)揭秘[M]. 北京：清華大學(xué)出版社，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]張震，王曉明. 對等網(wǎng)中Chord資源查找算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2006，42(11)：147-152.

(責(zé)任編輯：王 謙)

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-)，男(漢族)，山西長治人，中國傳媒大學(xué)碩士研究生.E-mail：375401532@qq.com