《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > Chord路由算法的分析與改進
Chord路由算法的分析與改進
來源:微型機與應(yīng)用2012年第8期
張亞松
(武漢理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,湖北 武漢430063)
摘要: 在P2P網(wǎng)絡(luò)中,如何高效地查找需要的資源是關(guān)系P2P網(wǎng)絡(luò)性能的關(guān)鍵。傳統(tǒng)的Chord的路由表信息冗余,查找效率不高,且不考慮實際物理網(wǎng)絡(luò)的拓撲結(jié)構(gòu),因此使邏輯拓撲與物理拓撲不匹配,導(dǎo)致了較大的網(wǎng)路延遲。提出一種改進的Chord路由算法,該算法在一定程度上解決了上述兩個問題,提高了搜索查詢的效率。
Abstract:
Key words :

摘 要: 在P2P網(wǎng)絡(luò)中,如何高效地查找需要的資源是關(guān)系P2P網(wǎng)絡(luò)性能的關(guān)鍵。傳統(tǒng)的Chord路由表信息冗余,查找效率不高,且不考慮實際物理網(wǎng)絡(luò)的拓撲結(jié)構(gòu),因此使邏輯拓撲與物理拓撲不匹配,導(dǎo)致了較大的網(wǎng)路延遲。提出一種改進的Chord路由算法,該算法在一定程度上解決了上述兩個問題,提高了搜索查詢的效率。
關(guān)鍵詞: 對等網(wǎng)絡(luò);Chord;路由;拓撲匹配

    高效的查找資源決定了P2P網(wǎng)絡(luò)的性能,是P2P網(wǎng)絡(luò)研究的重點。Chord[1]是MIT提出的基于分布式哈希表DHT(Distributed Hash Table)的資源搜索算法,在可擴展性和查找確定性方面都有比較好的表現(xiàn),其他的系統(tǒng)還有Pastry[2]、CAN[3]和Tapestry[4]。Chord可以保證在log2N跳數(shù)之內(nèi)找到所需要的資源,但其存在路由表信息冗余以及邏輯網(wǎng)絡(luò)與物理網(wǎng)絡(luò)不匹配的問題,導(dǎo)致查找效率不高。
    為了解決上述兩個問題,在Chord的基礎(chǔ)上,本文提出了一種改進的Chord路由算法。該算法將路由表中重復(fù)的路由信息刪除,加入原始路由表中覆蓋不到的半環(huán)的路由信息;為每個節(jié)點增加鄰居表,鄰居表中記錄了本節(jié)點附近節(jié)點的物理位置信息。通過鄰居表路由過程不再是由指針表單獨決定,而是由指針表和鄰居表共同決定。這樣既消除了原路由表中的冗余信息,又增大了路由表的覆蓋度,也解決了邏輯網(wǎng)絡(luò)和物理網(wǎng)絡(luò)不匹配的問題,從而提高了查找效率,降低了平均路由延遲。
1 Chord路由算法
    Chord是MIT提出的基于DHT的資源搜索算法,平均路由跳數(shù)一般在log2N/2之內(nèi)。在Chord系統(tǒng)中,節(jié)點和關(guān)鍵字都有一個m位的標(biāo)識符,每個節(jié)點的ID可以通過對IP進行哈希運算得到。所有節(jié)點按照ID從小到大沿順時針方向排列成一個邏輯的標(biāo)識圓環(huán)(Chord環(huán))。節(jié)點的資源關(guān)鍵字標(biāo)識符K通過對關(guān)鍵字本身進行哈希運算得到。關(guān)鍵字標(biāo)識符K存放在節(jié)點ID=K或者ID=min{ID-K;ID-K>0}這樣的節(jié)點上。Chord中每個節(jié)點都有一個路由表,路由表有m條記錄,其中第i條記錄記錄了在Chord中和該節(jié)點的距離大于等于2i-1(i∈[1,m])的最近節(jié)點。顯然,路由表只能覆蓋從本節(jié)點開始的半個環(huán)的區(qū)域。
    如圖1所示,當(dāng)節(jié)點8要查找K56時,首先判斷自身ID等于8而非56;然后檢查K56沒有落在本節(jié)點和它的后繼節(jié)點之間,即56不在[9,15]、[16,23]、[24,28]和[40,43]區(qū)間內(nèi);然后查找路由表,找到表中最大且小于K56的節(jié)點43,把請求轉(zhuǎn)發(fā)到節(jié)點43。重復(fù)此過程,請求轉(zhuǎn)發(fā)到52,找到存放K56的后繼節(jié)點58,把請求轉(zhuǎn)發(fā)到節(jié)點58,查找結(jié)束。查找過程為8→43→52→58。

2 改進的Chord路由算法
    從圖1以及路由表的構(gòu)造可知,路由表中存在冗余路由信息,并且由Chord環(huán)構(gòu)造的邏輯網(wǎng)絡(luò)和物理網(wǎng)絡(luò)沒有任何關(guān)聯(lián),所以導(dǎo)致了平均查找跳數(shù)和平均路由延時的增加。因此,應(yīng)該從這兩個方面對路由算法進行改進,即對指針表(Finger Table)進行修改以及增加鄰居表(Neighbour Table)。
2.1 修改指針表
    如圖1所示,從以節(jié)點8為初始節(jié)點的路由表可以看出,有兩條冗余的路由信息。假設(shè)Chord環(huán)的大小為M=2m,節(jié)點數(shù)N=2n(n<m) ,所有節(jié)點平均分布,節(jié)點平均冗余路由信息數(shù)量為log2(2m/2n)=m-n[5]。因為相對于大小為M的標(biāo)志符空間,N個節(jié)點相對比較稀少,導(dǎo)致節(jié)點和它的后繼節(jié)點之間的間隔大于1,所以出現(xiàn)冗余路由信息無可避免。
    從路由表的構(gòu)造可以看出,路由表可以覆蓋從本節(jié)點開始的一半Chord環(huán),當(dāng)要查找的K存儲在另一半Chord環(huán)時,就需要更多的跳數(shù)來完成。由于路由表中每個節(jié)點平均有m-n條冗余路由信息,所以可以把冗余的路由信息刪除。如果可以用有效的路由信息替代冗余的路由信息,使路由表可以覆蓋更大的范圍,那么必然會降低查找的平均跳數(shù),從而提高查找效率。
    假設(shè)本節(jié)點為N,新的指針表的構(gòu)造方法如下:
    (1)用原指針表的構(gòu)造方法,構(gòu)造m條路由信息,從中刪除重復(fù)的路由信息,假設(shè)重復(fù)的記錄數(shù)量為P。
    (2)找到指針表中最大的后繼節(jié)點(圖1中的43),然后找到此后繼節(jié)點的直接后繼節(jié)點D(圖1中的46)。
    (3)以節(jié)點D為起點,構(gòu)造D的指針表,從上到下選擇P條不重復(fù)的路由信息,將其增加到(1)中構(gòu)造的節(jié)點N的指針表后面。
    (4)刪除D的指針表。
    由以上構(gòu)造方法及圖1中的New Finger Table可知,新的指針表可以覆蓋原指針表覆蓋不到的另一半Chord環(huán)的絕大部分空間,從而指針表查找的范圍增大,平均查找跳數(shù)自然降低了。在新的指針表中,當(dāng)節(jié)點8要查找K56時,只需要一條就可以找到存儲K56的節(jié)點58,即8→58。
2.2 增加鄰居表
    節(jié)點的鄰居表主要用來存放在物理網(wǎng)絡(luò)中相距比較近的節(jié)點信息。鄰居表的表項是<ID,IP>這樣的鍵值對。鄰居表的表項信息可以利用界標(biāo)簇算法[6]和往返延遲RTT(Round Trip Time)測量技術(shù)收集。利用這種測量方法可以把在物理上距離本節(jié)點比較近的節(jié)點信息加入自己的鄰居表。為了保證有效性,系統(tǒng)中的每個節(jié)點定時地測量距鄰居節(jié)點的距離。因為Chord環(huán)中的節(jié)點不斷地加入和離開,所以當(dāng)鄰居表表項達到最大時,應(yīng)該刪除表中距本節(jié)點物理距離最遠的點。
    本節(jié)點和鄰居節(jié)點一起稱為一個單元,在單元中選取一個處理能力比較強的作為超級節(jié)點,單元中的節(jié)點一旦查詢結(jié)束就把查詢結(jié)果發(fā)送給超級節(jié)點進行緩存。對緩存信息的管理可以采用先入先出、最近最少使用的策略,這樣在下次查詢時,可以保證在兩跳之內(nèi)找到資源。
2.3 路由查找算法
    假設(shè)本節(jié)點為ID=N,需要定位的資源為K,在修改了指針表,增加了鄰居表以及超級節(jié)點時,改進的資源搜索過程如下:
    (1)首先檢查N是否等于K,如果相等直接返回本節(jié)點的IP地址,搜索結(jié)束;如果不相等繼續(xù)步驟(2)。
    (2)查找節(jié)點N的指針表,看是否存在節(jié)點標(biāo)識符等于K的后繼節(jié)點,如果存在,直接返回該后繼節(jié)點的IP地址,搜索結(jié)束;否則,繼續(xù)步驟(3)。
    (3)如果節(jié)點N是超級節(jié)點,檢查是否存在K的記錄,如果存在,搜索結(jié)束;否則,繼續(xù)步驟(4);如果N不是超級節(jié)點,把請求轉(zhuǎn)發(fā)至超級節(jié)點。
    (4)查找節(jié)點N的指針表和鄰居表,分別找到最接近K的節(jié)點N1和N2,比較N1和N2,選擇物理距離與K較近的一個作為下一跳的節(jié)點,將搜索請求轉(zhuǎn)發(fā)到這個節(jié)點上。
    通過上述過程搜索到所需要的資源后,主動上傳資源的定位信息到超級節(jié)點,保存在緩存中,這樣下次搜索時就可以迅速地定位了。
3 仿真實驗與結(jié)果分析
    在Linux系統(tǒng)下,采用P2PSim仿真平臺對原Chord協(xié)議和改進后的Chord協(xié)議進行了實驗。實驗中主要對平均查找跳數(shù)和平均路由延遲這兩方面進行了比較。實驗對10組(256,512,1 024,2 048,4 096,6 000,8 192,10 000,13 000,16 384)數(shù)據(jù)都進行采樣,設(shè)定M=224,每個節(jié)點平均隨機請求4次,對平均查找跳數(shù)和平均路由時延進行統(tǒng)計,得到的統(tǒng)計圖如圖2和圖3所示。實驗結(jié)果進一步說明了改進后的Chord協(xié)議因為增大了指針表的覆蓋范圍,并且考慮了物理網(wǎng)絡(luò)與邏輯網(wǎng)絡(luò)的差異,所以在平均查找跳數(shù)和平均路由延時方面都有一定程度的降低,提高了查詢的效率。

 

 

    本文針對原Chord協(xié)議指針表信息冗余,只能覆蓋Chord環(huán)一半范圍的缺點,刪除了冗余路由信息,添加了有效的路由信息,擴大了指針表的覆蓋范圍。針對邏輯網(wǎng)絡(luò)與物理網(wǎng)絡(luò)不匹配的問題,在Chord協(xié)議中增加了鄰居表,使節(jié)點在路由時可以選擇物理距離相對比較近的節(jié)點進行轉(zhuǎn)發(fā)請求??傮w來說改進后的Chord協(xié)議的平均查找跳數(shù)和平均路由延時都有一定的降低,提高了查找效率。
參考文獻
[1] STOICA I,MORRIS R,KARGER D,et al.Chord:a scalable peer-to-peer lookup protocol for internet applications[C]. Procedings of ACM SIGCOMM 2001,New York,USA:ACM  Press,2001:149-160.
[2] ROWSTRON A,DRUSCHEL P.Pastry:scalable distributed object location and routing for large-scale peer-to-peer systems[C].18th IFIP/ACM Int Conference on Distributed System Platforms,2001:329-350.
[3] RATNASAMY S,F(xiàn)RANCIS P,HANDLEY M,et al.A scalable content-addressable network[C].Govindan R.Proc of the ACM SIGCOMM.New York:ACM Press,2001:161-172.
[4] Zhao B Y,Huang Ling,STRIBLING J,et al.Tapestry:a resilient global-scale overlay for service deployment[J]. IEEE Journal on Selected Areas in Communications,2004,22(1):41-53.
[5] CASTRO M,DRUSCHEL P,HU Y C,et al.Exploiting  network proximity in peer-to-peer overlay networks[R]. Technical Report MSR-TR-2002-82,2002.
[6] Wang Biqing.Research and improvement of Chord routing algorithm[J].Computer Engineering and Applications,2010,46(14):112-114.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。