程亞維,劉書(shū)倫

(濟(jì)源職業(yè)技術(shù)學(xué)院信息工程系,河南濟(jì)源459000)

對(duì)等網(wǎng)絡(luò)中Chord路由算法的研究

程亞維,劉書(shū)倫

(濟(jì)源職業(yè)技術(shù)學(xué)院信息工程系,河南濟(jì)源459000)

隨著互聯(lián)網(wǎng)信息技術(shù)的不斷發(fā)展,計(jì)算機(jī)硬件性能的更新、共享,基于對(duì)等網(wǎng)絡(luò)信息定位和資源共享技術(shù)被廣泛關(guān)注.針對(duì)對(duì)等網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的分類,對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)Chord路由算法進(jìn)行了詳細(xì)分析,論述了Chord算法的優(yōu)勢(shì)和不足,結(jié)合系統(tǒng)查詢效率低下問(wèn)題,提出優(yōu)化下一跳節(jié)點(diǎn)選擇方案,提高算法的查找效率.

對(duì)等網(wǎng)絡(luò);Chord;路由算法

隨著互聯(lián)網(wǎng)信息技術(shù)的不斷發(fā)展,計(jì)算機(jī)硬件性能的更新、共享,基于對(duì)等網(wǎng)絡(luò)信息定位和資源共享技術(shù)被廣泛關(guān)注.在對(duì)等網(wǎng)絡(luò)(P2P)網(wǎng)絡(luò)中,深入挖掘網(wǎng)絡(luò)節(jié)點(diǎn)的能力,將所有資源分布式存放在各個(gè)節(jié)點(diǎn)中,不經(jīng)過(guò)中央服務(wù)器直接實(shí)現(xiàn)數(shù)據(jù)交換或服務(wù)技術(shù).網(wǎng)絡(luò)節(jié)點(diǎn)地位相同,既可以作為服務(wù)器也可以作為客戶端.

P2P網(wǎng)絡(luò)按照拓?fù)浣Y(jié)構(gòu)可以分為:以Napster系統(tǒng)為代表的依靠中央服務(wù)器管理存儲(chǔ)所有節(jié)點(diǎn)共享信息和信息查詢的集中式P2P網(wǎng)絡(luò),這種網(wǎng)絡(luò)結(jié)構(gòu)使網(wǎng)絡(luò)可管理性得到了有效提高.當(dāng)系統(tǒng)中網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模不斷擴(kuò)展時(shí),中央服務(wù)器很容易會(huì)出現(xiàn)單點(diǎn)故障,系統(tǒng)的可靠性不高;純分布式P2P網(wǎng)絡(luò)采用洪泛方式進(jìn)行搜索[1],節(jié)點(diǎn)采用廣播查詢請(qǐng)求,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)獲取查詢請(qǐng)求后搜索自身資源列表,例如Gnutella系統(tǒng).該網(wǎng)絡(luò)結(jié)構(gòu)采用廣播機(jī)制,節(jié)點(diǎn)覆蓋率高,但網(wǎng)絡(luò)中會(huì)產(chǎn)生大量冗余信息,系統(tǒng)負(fù)擔(dān)過(guò)重難以擴(kuò)展;混合式P2P網(wǎng)絡(luò)集中式體系結(jié)構(gòu)體現(xiàn)在局部,整體表現(xiàn)為分布式結(jié)構(gòu).根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)在計(jì)算能力,存儲(chǔ)空間等情況決定節(jié)點(diǎn)地位,典型代表有KaZaA系統(tǒng);結(jié)構(gòu)化P2P網(wǎng)絡(luò)采用分布式散列表進(jìn)行節(jié)點(diǎn)的映射和管理[2],每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)僅需保存特定的節(jié)點(diǎn)索引信息就能夠?qū)崿F(xiàn)資源的查找,例如Chord系統(tǒng)、CAN系統(tǒng)、Pastry系統(tǒng)等.

1 Chord路由算法

1.1 Chord概述

Chord協(xié)議旨在提供一個(gè)適合P2P網(wǎng)絡(luò)的分布式查找服務(wù)資源的環(huán)境,在2001年由麻省理工學(xué)院提出.在Chord網(wǎng)絡(luò)中,通過(guò)一致性哈希函數(shù)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)IP地址進(jìn)行運(yùn)算,獲取每個(gè)節(jié)點(diǎn)的標(biāo)識(shí),即節(jié)點(diǎn)ID.對(duì)關(guān)鍵字進(jìn)行哈希運(yùn)算獲得網(wǎng)絡(luò)資源的標(biāo)識(shí),稱為鍵值ID.對(duì)所有節(jié)點(diǎn)ID進(jìn)行排序,按照從小到大以順時(shí)針?lè)较蚪M成一個(gè)單向的Chord環(huán).在Chord環(huán)中,每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都需要維護(hù)一張最多含有m個(gè)表項(xiàng)的路由表,路由表的第k條記錄為在地址空間中和該節(jié)點(diǎn)的距離大等于2k(0≤k≤m,地址空間為0到2m-1)的最近節(jié)點(diǎn)[3].表1列出Chord節(jié)點(diǎn)n的路由表結(jié)構(gòu).

表1 Chord節(jié)點(diǎn)n的路由表結(jié)構(gòu)

1.2 查詢過(guò)程

當(dāng)節(jié)點(diǎn)收到鍵值查詢請(qǐng)求時(shí),首先確定節(jié)點(diǎn)本身是否負(fù)責(zé)存儲(chǔ)目標(biāo)鍵值,如果沒(méi)有,根據(jù)路由表的記錄將查詢請(qǐng)求轉(zhuǎn)發(fā)到離存儲(chǔ)目標(biāo)鍵值最近的節(jié)點(diǎn),如此下去,直到找到負(fù)責(zé)存儲(chǔ)目標(biāo)鍵值的節(jié)點(diǎn).由n個(gè)節(jié)點(diǎn)組成的Chord環(huán)可以在O(log n)跳數(shù)內(nèi)實(shí)現(xiàn)資源定位.節(jié)點(diǎn)n8根據(jù)路由表逐步查詢鍵值k54的節(jié)點(diǎn),見(jiàn)圖1.

圖1 Chord的節(jié)點(diǎn)路由表及查找

Chord網(wǎng)絡(luò)對(duì)數(shù)據(jù)對(duì)象查詢的偽代碼如下:

//由節(jié)點(diǎn)n查找與數(shù)據(jù)對(duì)象ID匹配的后繼節(jié)點(diǎn)

n.find_successor(id)

n'=find_predecessor(id);

return n'.successor;

//由節(jié)點(diǎn)n查找與數(shù)據(jù)對(duì)象ID匹配的前驅(qū)節(jié)點(diǎn)

n.find_predecessor(id)

n'=n;

while(id?(n',n'.successor])

n'=n'.closest_preceding_finger(id);

return n;

//返回路由表中里數(shù)據(jù)對(duì)象ID最近的節(jié)點(diǎn)

n.closest_preceding_finger(id);

for i=m down to 1

if(finger[i].node?(n,id))

return finger[i].node; return n;

1.3 節(jié)點(diǎn)的加入和退出

在Chord網(wǎng)絡(luò)中,節(jié)點(diǎn)可以隨時(shí)加入或離開(kāi),每個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)始終正確.并且為了能夠快速地找到資源,節(jié)點(diǎn)的路由表需要隨時(shí)都是最新的.當(dāng)節(jié)點(diǎn)n需要加入Chord網(wǎng)絡(luò)時(shí),首先定義節(jié)點(diǎn)n的前驅(qū)和路由表項(xiàng),通過(guò)已知節(jié)點(diǎn)查找新節(jié)點(diǎn)n指針表的各表項(xiàng).然后調(diào)用相關(guān)函數(shù),完成對(duì)已存在節(jié)點(diǎn)的前驅(qū)及路由表的更新.最后告訴其后繼節(jié)點(diǎn)將由節(jié)點(diǎn)n負(fù)責(zé)的資源關(guān)鍵字索引傳遞給n.

結(jié)點(diǎn)n加入Chord環(huán)時(shí),通過(guò)調(diào)用join(n')函數(shù)來(lái)實(shí)現(xiàn),節(jié)點(diǎn)加入算法偽代碼如下:

#define successor finger[1].node

//節(jié)點(diǎn)n加入Chord環(huán)

n.join(n')

if(n')

init_finger_table(n');

update_other();

else

for i=1 tom

finger[i].node=n;

predecessor=n;

//初始化本地節(jié)點(diǎn)的路由表

n.init_finger_table(n')

finger[1].node=n'.find_successor(finger[1].start);

predecessor=successor.predecessor;

successor.predecessor=n;

for i=1 tom-1

if(finger[i+1].start∈[n.finger[i].node])

finger[i+1].node=n.finger[i].node;

else

finger[i+1].node=n'.find_successor(finger[i+1].start);

//更新Chord環(huán)中所有那些路由表因該引用n的節(jié)點(diǎn)狀態(tài)

n.update_other()

for i=1 tom

p=find_predecessor(n-2i-1);

p.update_finger_table(n,i);

//如果n是p的路由表的第i項(xiàng),則用n更新p的路由表

p.update_finger_table(n,i)

if(n∈[p,finger[i].node))

finger[i].node=n;

p=predecessor;

p.update_finger_table(n,i);

當(dāng)節(jié)點(diǎn)n請(qǐng)求退出時(shí),將節(jié)點(diǎn)n的路由表移交給的節(jié)點(diǎn)n的后繼節(jié)點(diǎn)來(lái)維護(hù).系統(tǒng)中的節(jié)點(diǎn)都擁有一張由r個(gè)最近的后繼節(jié)點(diǎn)組成的列表,來(lái)保證在節(jié)點(diǎn)離開(kāi)后系統(tǒng)的查詢服務(wù)仍然得進(jìn)行[4],并將列表中的第一個(gè)節(jié)點(diǎn)來(lái)替代退出的節(jié)點(diǎn).

2 Chord算法分析

Chord算法具有5個(gè)優(yōu)點(diǎn):(1)Chord路由算法采用一致性散列算法,所有節(jié)點(diǎn)分擔(dān)相同的系統(tǒng)負(fù)荷,避免某些節(jié)點(diǎn)負(fù)載過(guò)大.(2)節(jié)點(diǎn)之間地位平等且工作相同,具有很高的頑健性,能夠抗御Dos攻擊.(3)隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量規(guī)模的不斷擴(kuò)展,Chord系統(tǒng)的開(kāi)銷將按照O(log(n))的比例不斷增加[5].(4)各個(gè)節(jié)點(diǎn)能夠根據(jù)網(wǎng)絡(luò)的動(dòng)態(tài)變化及時(shí)更新路由表,有效恢復(fù)路由關(guān)系,確保各節(jié)點(diǎn)之間查詢能夠可靠進(jìn)行.(5)由于Chord算法不限定查詢內(nèi)容結(jié)構(gòu),應(yīng)用層可以靈活地將內(nèi)容映射到鍵值空間[6].

Chord算法雖然有明顯的優(yōu)勢(shì),但是它仍然存在不足之處:(1)在Chord系統(tǒng)中,不管各節(jié)點(diǎn)之間的性能差異多大,承擔(dān)的責(zé)任都是相同的,例如資源存儲(chǔ)、查詢等.低性能節(jié)點(diǎn)的存在將導(dǎo)致請(qǐng)求響應(yīng)時(shí)間增長(zhǎng),系統(tǒng)性能低下等問(wèn)題.隨著網(wǎng)絡(luò)的不斷擴(kuò)大,網(wǎng)絡(luò)節(jié)點(diǎn)也隨之增多,由于各網(wǎng)絡(luò)節(jié)點(diǎn)之間存著不同的性能差異,系統(tǒng)查詢效率因性能較低的節(jié)點(diǎn)而受到影響,阻礙系統(tǒng)查找進(jìn)度,從而引發(fā)系統(tǒng)性能瓶頸.(2)在P2P網(wǎng)絡(luò)中,任何時(shí)刻都會(huì)有節(jié)點(diǎn)的加入或退出,為保證節(jié)點(diǎn)路由表的準(zhǔn)確性,當(dāng)有節(jié)點(diǎn)加入或退出時(shí)都需要及時(shí)對(duì)相關(guān)節(jié)點(diǎn)的路由表進(jìn)行更新.由n個(gè)節(jié)點(diǎn)組成的Chord系統(tǒng),當(dāng)某一節(jié)點(diǎn)加入或離開(kāi)系統(tǒng)時(shí),需要通過(guò)O (log 2n)次信息交換來(lái)重建節(jié)點(diǎn)路由信息及分配相關(guān)文件.在系統(tǒng)中,如果節(jié)點(diǎn)加入或離開(kāi)非常頻繁的話,整個(gè)網(wǎng)絡(luò)資源將會(huì)消耗在節(jié)點(diǎn)路由信息更新和文件重定位上,造成系統(tǒng)寬帶浪費(fèi)和查詢效率降低.

結(jié)合Chord系統(tǒng),低性能節(jié)點(diǎn)帶來(lái)的系統(tǒng)查詢效率低下問(wèn)題,可通過(guò)在系統(tǒng)中添加對(duì)各節(jié)點(diǎn)之間物理延時(shí)的感知,選擇最優(yōu)的下一跳節(jié)點(diǎn),從而減低查找時(shí)延,提高算法的查找效率.

3 結(jié)論

結(jié)合結(jié)構(gòu)化P2P網(wǎng)絡(luò)特征,將Chord算法與P2P網(wǎng)絡(luò)綜合運(yùn)用,在詳細(xì)分析Chord路由算法的基礎(chǔ)上,對(duì)網(wǎng)絡(luò)資源的查找及網(wǎng)絡(luò)節(jié)點(diǎn)的加入和退出算法進(jìn)行概述,并對(duì)Chord算法的優(yōu)勢(shì)和不足進(jìn)行分析,提出優(yōu)化下一跳節(jié)點(diǎn)選擇方案,降低系統(tǒng)查找時(shí)延.

[1]王慧,王錚.基于新路由表的雙向搜索Chord路由算法[EB/OL].(2013-04-18)[2013-08-18].http://www.cnki.net/kcms/detail/ 11.2127.TP.20130418.1618.017.htm l.

[2]徐丹陽(yáng).基于DHT的結(jié)構(gòu)化P2P路由協(xié)議Chord的研究[D].北京:北京郵電大學(xué)碩士學(xué)位論文,2010.

[3]成培,胡峰松,粟智.基于Chord的結(jié)構(gòu)化P2P路由改進(jìn)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(1):63-65.

[4]宗平,徐鴿.基于DHT的Chord路由算法改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(9):139-142.

[5]張文,趙子路.P2P網(wǎng)絡(luò)技術(shù)原理與C++開(kāi)發(fā)案例[M].北京:人民郵電出版社,2008.

[6]曹建.基于CHORD環(huán)的DHT全分布式P2P網(wǎng)絡(luò)結(jié)構(gòu)分析[J].蘇州市職業(yè)大學(xué)學(xué)報(bào),2012,23(3):42-45.

On the Chord in peer-to-peer network routing algorithm

CHENG Ya-wei,LIU Shu-lun
(Departmentof Information Engineering,Jiyuan Vocational and Technical College, Jiyuan 459000,Henan,China)

With the continuous development of the Internet information technology and computer hardware performance updating,sharing,network information positioning and resource sharing technology based on peerto-peer have been widely concerned.Based on the classification of the peer-to-peer network topology,Chord of structured P2P network routing algorithm is analyzed in detail,and the paper discusses the advantages and disadvantages of Chord algorithm by dealing with the system queries inefficiency problem,to propose to optimize the next hop node option to improve search efficiency of the algorithm.

peer-to-peer network;Chord;routing algorithm

TP393

:A

:1007-5348(2014)06-0016-04

(責(zé)任編輯:歐愷)

2014-03-28

河南省科技攻關(guān)計(jì)劃項(xiàng)目(132102210229).

程亞維(1986-),女,回族,河南濟(jì)源人,濟(jì)源職業(yè)技術(shù)學(xué)院信息工程系教師,主要從事計(jì)算機(jī)網(wǎng)絡(luò)方面的研究.