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

    高效的查找資源決定了P2P網(wǎng)絡的性能,，是P2P網(wǎng)絡研究的重點。Chord[1]是MIT提出的基于分布式哈希表DHT（Distributed Hash Table）的資源搜索算法,，在可擴展性和查找確定性方面都有比較好的表現(xiàn),，其他的系統(tǒng)還有Pastry[2]、CAN[3]和Tapestry[4],。Chord可以保證在log2N跳數(shù)之內(nèi)找到所需要的資源,，但其存在路由表信息冗余以及邏輯網(wǎng)絡與物理網(wǎng)絡不匹配的問題，導致查找效率不高,。
    為了解決上述兩個問題,，在Chord的基礎上，本文提出了一種改進的Chord路由算法,。該算法將路由表中重復的路由信息刪除,，加入原始路由表中覆蓋不到的半環(huán)的路由信息；為每個節(jié)點增加鄰居表,，鄰居表中記錄了本節(jié)點附近節(jié)點的物理位置信息,。通過鄰居表路由過程不再是由指針表單獨決定，而是由指針表和鄰居表共同決定,。這樣既消除了原路由表中的冗余信息,，又增大了路由表的覆蓋度，也解決了邏輯網(wǎng)絡和物理網(wǎng)絡不匹配的問題,，從而提高了查找效率,，降低了平均路由延遲。
1 Chord路由算法
    Chord是MIT提出的基于DHT的資源搜索算法,，平均路由跳數(shù)一般在log2N/2之內(nèi),。在Chord系統(tǒng)中，節(jié)點和關(guān)鍵字都有一個m位的標識符,，每個節(jié)點的ID可以通過對IP進行哈希運算得到,。所有節(jié)點按照ID從小到大沿順時針方向排列成一個邏輯的標識圓環(huán)（Chord環(huán)）。節(jié)點的資源關(guān)鍵字標識符K通過對關(guān)鍵字本身進行哈希運算得到,。關(guān)鍵字標識符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所示，當節(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,。重復此過程,，請求轉(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)絡和物理網(wǎng)絡沒有任何關(guān)聯(lián),，所以導致了平均查找跳數(shù)和平均路由延時的增加,。因此，應該從這兩個方面對路由算法進行改進,，即對指針表（Finger Table）進行修改以及增加鄰居表（Neighbour Table）,。
2.1 修改指針表
    如圖1所示，從以節(jié)點8為初始節(jié)點的路由表可以看出,，有兩條冗余的路由信息,。假設Chord環(huán)的大小為M=2m，節(jié)點數(shù)N=2n(n<m) ,，所有節(jié)點平均分布,，節(jié)點平均冗余路由信息數(shù)量為log2(2m/2n)=m-n[5]。因為相對于大小為M的標志符空間,，N個節(jié)點相對比較稀少，導致節(jié)點和它的后繼節(jié)點之間的間隔大于1,，所以出現(xiàn)冗余路由信息無可避免,。
    從路由表的構(gòu)造可以看出,，路由表可以覆蓋從本節(jié)點開始的一半Chord環(huán)，當要查找的K存儲在另一半Chord環(huán)時,，就需要更多的跳數(shù)來完成,。由于路由表中每個節(jié)點平均有m-n條冗余路由信息，所以可以把冗余的路由信息刪除,。如果可以用有效的路由信息替代冗余的路由信息,，使路由表可以覆蓋更大的范圍，那么必然會降低查找的平均跳數(shù),，從而提高查找效率,。
    假設本節(jié)點為N，新的指針表的構(gòu)造方法如下：
    (1)用原指針表的構(gòu)造方法,，構(gòu)造m條路由信息,，從中刪除重復的路由信息，假設重復的記錄數(shù)量為P,。
    (2)找到指針表中最大的后繼節(jié)點(圖1中的43),，然后找到此后繼節(jié)點的直接后繼節(jié)點D(圖1中的46)。
    (3)以節(jié)點D為起點,，構(gòu)造D的指針表,，從上到下選擇P條不重復的路由信息，將其增加到(1)中構(gòu)造的節(jié)點N的指針表后面,。
    (4)刪除D的指針表,。
    由以上構(gòu)造方法及圖1中的New Finger Table可知，新的指針表可以覆蓋原指針表覆蓋不到的另一半Chord環(huán)的絕大部分空間,，從而指針表查找的范圍增大,，平均查找跳數(shù)自然降低了。在新的指針表中,，當節(jié)點8要查找K56時,，只需要一條就可以找到存儲K56的節(jié)點58，即8→58,。
2.2 增加鄰居表
    節(jié)點的鄰居表主要用來存放在物理網(wǎng)絡中相距比較近的節(jié)點信息,。鄰居表的表項是<ID，IP>這樣的鍵值對,。鄰居表的表項信息可以利用界標簇算法[6]和往返延遲RTT（Round Trip Time）測量技術(shù)收集,。利用這種測量方法可以把在物理上距離本節(jié)點比較近的節(jié)點信息加入自己的鄰居表。為了保證有效性,，系統(tǒng)中的每個節(jié)點定時地測量距鄰居節(jié)點的距離,。因為Chord環(huán)中的節(jié)點不斷地加入和離開，所以當鄰居表表項達到最大時，應該刪除表中距本節(jié)點物理距離最遠的點,。
    本節(jié)點和鄰居節(jié)點一起稱為一個單元,，在單元中選取一個處理能力比較強的作為超級節(jié)點，單元中的節(jié)點一旦查詢結(jié)束就把查詢結(jié)果發(fā)送給超級節(jié)點進行緩存,。對緩存信息的管理可以采用先入先出,、最近最少使用的策略，這樣在下次查詢時,，可以保證在兩跳之內(nèi)找到資源,。
2.3 路由查找算法
    假設本節(jié)點為ID=N，需要定位的資源為K,，在修改了指針表,，增加了鄰居表以及超級節(jié)點時，改進的資源搜索過程如下：
    (1)首先檢查N是否等于K,，如果相等直接返回本節(jié)點的IP地址,，搜索結(jié)束；如果不相等繼續(xù)步驟(2),。
    (2)查找節(jié)點N的指針表,，看是否存在節(jié)點標識符等于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ù)都進行采樣,，設定M=224，每個節(jié)點平均隨機請求4次,，對平均查找跳數(shù)和平均路由時延進行統(tǒng)計,，得到的統(tǒng)計圖如圖2和圖3所示。實驗結(jié)果進一步說明了改進后的Chord協(xié)議因為增大了指針表的覆蓋范圍,，并且考慮了物理網(wǎng)絡與邏輯網(wǎng)絡的差異,，所以在平均查找跳數(shù)和平均路由延時方面都有一定程度的降低，提高了查詢的效率,。

    本文針對原Chord協(xié)議指針表信息冗余,，只能覆蓋Chord環(huán)一半范圍的缺點，刪除了冗余路由信息,，添加了有效的路由信息,，擴大了指針表的覆蓋范圍。針對邏輯網(wǎng)絡與物理網(wǎng)絡不匹配的問題,，在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.