對等網絡中Chord路由算法的研究

程亞維,劉書倫

(濟源職業(yè)技術學院信息工程系,河南濟源459000)

對等網絡中Chord路由算法的研究

程亞維,劉書倫

(濟源職業(yè)技術學院信息工程系,河南濟源459000)

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

對等網絡;Chord;路由算法

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

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

1 Chord路由算法

1.1 Chord概述

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

表1 Chord節(jié)點n的路由表結構

1.2 查詢過程

當節(jié)點收到鍵值查詢請求時,首先確定節(jié)點本身是否負責存儲目標鍵值,如果沒有,根據路由表的記錄將查詢請求轉發(fā)到離存儲目標鍵值最近的節(jié)點,如此下去,直到找到負責存儲目標鍵值的節(jié)點.由n個節(jié)點組成的Chord環(huán)可以在O(log n)跳數內實現資源定位.節(jié)點n8根據路由表逐步查詢鍵值k54的節(jié)點,見圖1.

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

Chord網絡對數據對象查詢的偽代碼如下:

//由節(jié)點n查找與數據對象ID匹配的后繼節(jié)點

n.find_successor(id)

n'=find_predecessor(id);

return n'.successor;

//由節(jié)點n查找與數據對象ID匹配的前驅節(jié)點

n.find_predecessor(id)

n'=n;

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

n'=n'.closest_preceding_finger(id);

return n;

//返回路由表中里數據對象ID最近的節(jié)點

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é)點的加入和退出

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

結點n加入Chord環(huán)時,通過調用join(n')函數來實現,節(jié)點加入算法偽代碼如下:

#define successor finger[1].node

//節(jié)點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é)點的路由表

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é)點狀態(tài)

n.update_other()

for i=1 tom

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

p.update_finger_table(n,i);

//如果n是p的路由表的第i項,則用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);

當節(jié)點n請求退出時,將節(jié)點n的路由表移交給的節(jié)點n的后繼節(jié)點來維護.系統(tǒng)中的節(jié)點都擁有一張由r個最近的后繼節(jié)點組成的列表,來保證在節(jié)點離開后系統(tǒng)的查詢服務仍然得進行[4],并將列表中的第一個節(jié)點來替代退出的節(jié)點.

2 Chord算法分析

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

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

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

3 結論

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

[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]徐丹陽.基于DHT的結構化P2P路由協(xié)議Chord的研究[D].北京:北京郵電大學碩士學位論文,2010.

[3]成培,胡峰松,粟智.基于Chord的結構化P2P路由改進算法[J].計算機工程與設計,2009,30(1):63-65.

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

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

[6]曹建.基于CHORD環(huán)的DHT全分布式P2P網絡結構分析[J].蘇州市職業(yè)大學學報,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

(責任編輯:歐愷)

2014-03-28

河南省科技攻關計劃項目(132102210229).

程亞維(1986-),女,回族,河南濟源人,濟源職業(yè)技術學院信息工程系教師,主要從事計算機網絡方面的研究.