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

程亞維,劉書倫

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

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

程亞維,劉書倫

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

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

對等網絡;Chord;路由算法

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

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

1 Chord路由算法

1.1 Chord概述

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

表1 Chord節點n的路由表結構

1.2 查詢過程

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

圖1 Chord的節點路由表及查找

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

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

n.find_successor(id)

n'=find_predecessor(id);

return n'.successor;

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

n.find_predecessor(id)

n'=n;

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

n'=n'.closest_preceding_finger(id);

return n;

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

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

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

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

#define successor finger[1].node

//節點n加入Chord環

n.join(n')

if(n')

init_finger_table(n');

update_other();

else

for i=1 tom

finger[i].node=n;

predecessor=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環中所有那些路由表因該引用n的節點狀態

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);

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

2 Chord算法分析

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

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

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

3 結論

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

[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路由協議Chord的研究[D].北京:北京郵電大學碩士學位論文,2010.

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

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

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

[6]曹建.基于CHORD環的DHT全分布式P2P網絡結構分析[J].蘇州市職業大學學報,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-),女,回族,河南濟源人,濟源職業技術學院信息工程系教師,主要從事計算機網絡方面的研究.