李斐，郭曉

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

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

李斐，郭曉

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

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

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

1 引言

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

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

2 背景理論

2.1 對(duì)等網(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)。而對(duì)于對(duì)等網(wǎng)來(lái)說(shuō)，也可以根據(jù)不同的拓?fù)鋪?lái)對(duì)其進(jìn)行分類，并且對(duì)于缺乏中心服務(wù)器的對(duì)等網(wǎng)來(lái)說(shuō)，如何在這種情況下來(lái)構(gòu)建并維護(hù)一個(gè)高效的拓?fù)浣Y(jié)構(gòu)，以實(shí)現(xiàn)各種功能，是一個(gè)很大的挑戰(zhàn)。在設(shè)計(jì)一個(gè)對(duì)等網(wǎng)系統(tǒng)時(shí)，需要構(gòu)造一個(gè)不同于C/S機(jī)構(gòu)的非集中的覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，在這個(gè)過(guò)程當(dāng)中，需要解決的問(wèn)題包括海量節(jié)點(diǎn)的命名組織方式、信息在節(jié)點(diǎn)間的傳遞方式、資源的索引和定位方式以及路由策略等。在對(duì)等網(wǎng)的發(fā)展過(guò)程中，出現(xiàn)了以下幾種不同拓?fù)漕愋偷膶?duì)等網(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ù)涞膶?duì)等網(wǎng)是最早出現(xiàn)的如圖1所示，對(duì)等網(wǎng)先驅(qū)Napster就是其中的典型。這一類網(wǎng)絡(luò)的拓?fù)漕愃朴谛切瓮負(fù)浣Y(jié)構(gòu)，所有的節(jié)點(diǎn)與中央檢索服務(wù)器鏈接，從而形成一個(gè)星形結(jié)構(gòu)，當(dāng)然這種結(jié)構(gòu)不是物理網(wǎng)絡(luò)上的星

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

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

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

圖2 混合式拓?fù)鋵?duì)等網(wǎng)

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

2.2 Chord協(xié)議

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

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

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

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

圖4 finger table生成過(guò)程

如果所有的查詢都是由這種方式完成，顯然會(huì)在系統(tǒng)內(nèi)產(chǎn)生極大的查詢消息，因此每個(gè)節(jié)點(diǎn)會(huì)保存一個(gè)稱為finger table的路由表格，其生成過(guò)程如圖4所示。首先，m是鍵值和節(jié)點(diǎn)標(biāo)識(shí)符的位數(shù)，在節(jié)點(diǎn)n的路由表中第i條路由條目包括了該節(jié)點(diǎn)標(biāo)識(shí)符的值n與2i-1的和所對(duì)應(yīng)鍵值的存儲(chǔ)節(jié)點(diǎn)s，即s=successor(n+2i-1)，1≤i≤m。finger table中的路由條目包含了目標(biāo)節(jié)點(diǎn)Chord環(huán)的標(biāo)識(shí)符和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)識(shí)符40的后繼節(jié)點(diǎn)是42。在這種方式下，每個(gè)節(jié)點(diǎn)存儲(chǔ)少量對(duì)等節(jié)點(diǎn)信息，并且對(duì)于相隔越近的后繼節(jié)點(diǎn)，保存其路由信息的概率越大，當(dāng)然，finger table所包含的路由信息不足以使節(jié)點(diǎn)直接確定任意一個(gè)鍵值的后繼節(jié)點(diǎn)。例如節(jié)點(diǎn)8無(wú)法確定鍵值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來(lái)發(fā)起查詢請(qǐng)求，不必從其最近的后繼節(jié)點(diǎn)14來(lái)發(fā)起查詢請(qǐng)求。

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

3 仿真試驗(yàn)

3.1 仿真環(huán)境

仿真實(shí)驗(yàn)采用了OverSim仿真框架，OverSim是一個(gè)基于OMNeT++的覆蓋網(wǎng)仿真框架，是事件驅(qū)動(dòng)的仿真平臺(tái)[5]，具有靈活可擴(kuò)展的特性，最大可以支持100000個(gè)對(duì)等節(jié)點(diǎn)的仿真，OverSim可以仿真結(jié)構(gòu)化和非結(jié)構(gòu)化的對(duì)等網(wǎng)絡(luò)，例如Chord[6]、Kademila、Pastry、Bamboo、Koorde、Gia等。 OverSim利用OMNeT++的圖形接口來(lái)可視化覆蓋網(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é)議可以以迭代或者遞歸的方式來(lái)實(shí)現(xiàn)，迭代方式的查詢請(qǐng)求會(huì)根據(jù)節(jié)點(diǎn)的finger table中的信息來(lái)進(jìn)行查詢，每一次移動(dòng)都會(huì)更接近目標(biāo)節(jié)點(diǎn)，遞歸方式的查詢節(jié)點(diǎn)將查詢請(qǐng)求轉(zhuǎn)發(fā)到下一個(gè)節(jié)點(diǎn)，直到查詢請(qǐng)求到達(dá)鍵值的后繼節(jié)點(diǎn)，在仿真過(guò)程中設(shè)置為迭代查詢方式。

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

在仿真過(guò)程中節(jié)點(diǎn)數(shù)目會(huì)逐漸增加，不斷有新的節(jié)點(diǎn)加入到網(wǎng)絡(luò)當(dāng)中。系統(tǒng)的數(shù)據(jù)統(tǒng)計(jì)模塊會(huì)收集每一次事件的相關(guān)信息，在仿真停止后以文本形式輸出，后續(xù)的數(shù)據(jù)可視化可以用其他工具完成。仿真分為兩次進(jìn)行，第一次設(shè)置Chord環(huán)節(jié)點(diǎn)數(shù)為100個(gè)，當(dāng)節(jié)點(diǎn)增加到100個(gè)時(shí)停止仿真，從第一仿真的結(jié)果中選取20次觀察進(jìn)行分析。第二次設(shè)置Chord環(huán)節(jié)點(diǎn)數(shù)為1000個(gè)，當(dāng)節(jié)點(diǎn)數(shù)增加到1000個(gè)時(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)的大小無(wú)關(guān)，在實(shí)驗(yàn)中，當(dāng)Chord環(huán)的參與節(jié)點(diǎn)數(shù)達(dá)到50個(gè)以上時(shí)，等待參與到Chord中的節(jié)點(diǎn)一直維持在10個(gè)左右。這樣的結(jié)果符合Chord網(wǎng)絡(luò)的特點(diǎn)，即節(jié)點(diǎn)加入chord網(wǎng)絡(luò)只引起一小部分節(jié)點(diǎn)所持有鍵值的變動(dòng)，不會(huì)造成網(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)間信息交換動(dòng)作，這個(gè)數(shù)值在一定程度上可以反映當(dāng)前網(wǎng)絡(luò)的通信負(fù)擔(dān)。從圖7，圖8兩次實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)圖中可以看到事件數(shù)目隨著節(jié)點(diǎn)數(shù)目的增加而增加，事件數(shù)的增長(zhǎng)慢于指數(shù)函數(shù)，但是稍快于線性函數(shù)，在實(shí)驗(yàn)所選擇規(guī)模大小的網(wǎng)絡(luò)中避免了非結(jié)構(gòu)化全分布式對(duì)等網(wǎng)絡(luò)內(nèi)通信負(fù)擔(dān)隨節(jié)點(diǎn)數(shù)指數(shù)級(jí)增加的問(wèn)題。Chord協(xié)議當(dāng)中查詢信息平均需要O(logN)來(lái)完成查詢請(qǐng)求，節(jié)點(diǎn)加入與離開(kāi)會(huì)產(chǎn)生O(log2N)條更改通知信息，因此隨著節(jié)點(diǎn)數(shù)增加的事件數(shù)更多的是節(jié)點(diǎn)間交換數(shù)據(jù)的信息。

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

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

在實(shí)驗(yàn)過(guò)程中還存在諸多的不足，是下一步工作需要改進(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)加入而沒(méi)有節(jié)點(diǎn)退出，沒(méi)有對(duì)這種更為動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境進(jìn)行仿真，以上都是下一步的仿真實(shí)驗(yàn)可以考慮提高的地方。

4 總結(jié)

本文從對(duì)等網(wǎng)的分類出發(fā)，在介紹典型的對(duì)等網(wǎng)絡(luò)之后對(duì)Chord協(xié)議進(jìn)行了介紹和分析。Chord協(xié)議解決了對(duì)等網(wǎng)中數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)選擇的問(wèn)題，并且由每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)路由表來(lái)實(shí)現(xiàn)高效的覆蓋網(wǎng)路由。為了驗(yàn)證Chord協(xié)議的有效性和可用性，通過(guò)OverSim平臺(tái)進(jìn)行了簡(jiǎn)單的仿真，實(shí)驗(yàn)結(jié)果表明Chord協(xié)議在節(jié)點(diǎn)加入方面和抑制通信消耗增長(zhǎng)從而實(shí)現(xiàn)系統(tǒng)可擴(kuò)展性方面能夠達(dá)到Chord協(xié)議的設(shè)計(jì)目標(biāo)，是一種高效可擴(kuò)展的完全分布結(jié)構(gòu)化對(duì)等網(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]張震，王曉明. 對(duì)等網(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-)，男(漢族)，山西長(zhǎng)治人，中國(guó)傳媒大學(xué)碩士研究生.E-mail：375401532@qq.com