Chord路由算法的分析與改進

張亞松

（武漢理工大學 計算機科學與技術學院，湖北 武漢430063）

高效的查找資源決定了P2P網絡的性能，是P2P網絡研究的重點。Chord[1]是MIT提出的基于分布式哈希表DHT（Distributed Hash Table）的資源搜索算法，在可擴展性和查找確定性方面都有比較好的表現，其他的系統還有 Pastry[2]、CAN[3]和 Tapestry[4]。 Chord 可 以 保 證 在 log2N跳數之內找到所需要的資源，但其存在路由表信息冗余以及邏輯網絡與物理網絡不匹配的問題，導致查找效率不高。

為了解決上述兩個問題，在Chord的基礎上，本文提出了一種改進的Chord路由算法。該算法將路由表中重復的路由信息刪除，加入原始路由表中覆蓋不到的半環的路由信息；為每個節點增加鄰居表，鄰居表中記錄了本節點附近節點的物理位置信息。通過鄰居表路由過程不再是由指針表單獨決定，而是由指針表和鄰居表共同決定。這樣既消除了原路由表中的冗余信息，又增大了路由表的覆蓋度，也解決了邏輯網絡和物理網絡不匹配的問題，從而提高了查找效率，降低了平均路由延遲。

1 Chord路由算法

Chord是MIT提出的基于DHT的資源搜索算法，平均路由跳數一般在log2N/2之內。在Chord系統中，節點和關鍵字都有一個m位的標識符，每個節點的ID可以通過對IP進行哈希運算得到。所有節點按照ID從小到大沿順時針方向排列成一個邏輯的標識圓環（Chord環）。節點的資源關鍵字標識符K通過對關鍵字本身進行哈希運算得到。關鍵字標識符K存放在節點ID=K或者ID=min{ID-K；ID-K>0}這樣的節點上。Chord中每個節點都有一個路由表，路由表有m條記錄，其中第i條記錄記錄了在Chord中和該節點的距離大于等于2i-1（i∈[1，m]）的最近節點。顯然，路由表只能覆蓋從本節點開始的半個環的區域。

如圖1所示，當節點8要查找 K56時，首先判斷自身ID等于8而非56；然后檢查K56沒有落在本節點和它的后繼節點之間，即 56 不在[9，15]、[16，23]、[24，28]和[40，43]區間內；然后查找路由表，找到表中最大且小于K56的節點43，把請求轉發到節點43。重復此過程，請求轉發到52，找到存放K56的后繼節點58，把請求轉發到節點58，查找結束。查找過程為8→43→52→58。

2 改進的Chord路由算法

從圖1以及路由表的構造可知，路由表中存在冗余路由信息，并且由Chord環構造的邏輯網絡和物理網絡沒有任何關聯，所以導致了平均查找跳數和平均路由延時的增加。因此，應該從這兩個方面對路由算法進行改進，即對指針表（Finger Table）進行修改以及增加鄰居表（Neighbour Table）。

2.1 修改指針表

如圖1所示，從以節點8為初始節點的路由表可以看出，有兩條冗余的路由信息。假設Chord環的大小為M=2m，節點數 N=2n(n＜m)，所有節點平均分布，節點平均冗余路由信息數量為log2(2m/2n)=m-n[5]。因為相對于大小為M的標志符空間，N個節點相對比較稀少，導致節點和它的后繼節點之間的間隔大于1，所以出現冗余路由信息無可避免。

從路由表的構造可以看出，路由表可以覆蓋從本節點開始的一半Chord環，當要查找的K存儲在另一半Chord環時，就需要更多的跳數來完成。由于路由表中每個節點平均有m-n條冗余路由信息，所以可以把冗余的路由信息刪除。如果可以用有效的路由信息替代冗余的路由信息，使路由表可以覆蓋更大的范圍，那么必然會降低查找的平均跳數，從而提高查找效率。

假設本節點為N，新的指針表的構造方法如下：

(1)用原指針表的構造方法，構造m條路由信息，從中刪除重復的路由信息，假設重復的記錄數量為P。

(2)找到指針表中最大的后繼節點(圖1中的43)，然后找到此后繼節點的直接后繼節點 D(圖1中的46)。

(3)以節點D為起點，構造D的指針表，從上到下選擇P條不重復的路由信息，將其增加到(1)中構造的節點N的指針表后面。

(4)刪除D的指針表。

由以上構造方法及圖1中的New Finger Table可知，新的指針表可以覆蓋原指針表覆蓋不到的另一半Chord環的絕大部分空間，從而指針表查找的范圍增大，平均查找跳數自然降低了。在新的指針表中，當節點8要查找K56時，只需要一條就可以找到存儲K56的節點58，即 8→58。

2.2 增加鄰居表

節點的鄰居表主要用來存放在物理網絡中相距比較近的節點信息。鄰居表的表項是＜ID，IP>這樣的鍵值對。鄰居表的表項信息可以利用界標簇算法[6]和往返延遲RTT（Round Trip Time）測量技術收集。利用這種測量方法可以把在物理上距離本節點比較近的節點信息加入自己的鄰居表。為了保證有效性，系統中的每個節點定時地測量距鄰居節點的距離。因為Chord環中的節點不斷地加入和離開，所以當鄰居表表項達到最大時，應該刪除表中距本節點物理距離最遠的點。

本節點和鄰居節點一起稱為一個單元，在單元中選取一個處理能力比較強的作為超級節點，單元中的節點一旦查詢結束就把查詢結果發送給超級節點進行緩存。對緩存信息的管理可以采用先入先出、最近最少使用的策略，這樣在下次查詢時，可以保證在兩跳之內找到資源。

2.3 路由查找算法

假設本節點為ID=N，需要定位的資源為K，在修改了指針表，增加了鄰居表以及超級節點時，改進的資源搜索過程如下：

(1)首先檢查N是否等于K，如果相等直接返回本節點的IP地址，搜索結束；如果不相等繼續步驟(2)。

(2)查找節點N的指針表，看是否存在節點標識符等于K的后繼節點，如果存在，直接返回該后繼節點的IP地址，搜索結束；否則，繼續步驟(3)。

(3)如果節點N是超級節點，檢查是否存在K的記錄，如果存在，搜索結束；否則，繼續步驟(4)；如果 N不是超級節點，把請求轉發至超級節點。

(4)查找節點N的指針表和鄰居表，分別找到最接近K的節點 N1和 N2，比較 N1和 N2，選擇物理距離與 K較近的一個作為下一跳的節點，將搜索請求轉發到這個節點上。

通過上述過程搜索到所需要的資源后，主動上傳資源的定位信息到超級節點，保存在緩存中，這樣下次搜索時就可以迅速地定位了。

3 仿真實驗與結果分析

在Linux系統下，采用P2PSim仿真平臺對原Chord協議和改進后的Chord協議進行了實驗。實驗中主要對平均查找跳數和平均路由延遲這兩方面進行了比較。實驗對 10 組(256，512，1 024，2 048，4 096，6 000，8 192，10 000，13 000，16 384)數據都進行采樣，設定 M=224，每個節點平均隨機請求4次，對平均查找跳數和平均路由時延進行統計，得到的統計圖如圖2和圖3所示。實驗結果進一步說明了改進后的Chord協議因為增大了指針表的覆蓋范圍，并且考慮了物理網絡與邏輯網絡的差異，所以在平均查找跳數和平均路由延時方面都有一定程度的降低，提高了查詢的效率。

本文針對原Chord協議指針表信息冗余，只能覆蓋Chord環一半范圍的缺點，刪除了冗余路由信息，添加了有效的路由信息，擴大了指針表的覆蓋范圍。針對邏輯網絡與物理網絡不匹配的問題，在Chord協議中增加了鄰居表，使節點在路由時可以選擇物理距離相對比較近的節點進行轉發請求?？傮w來說改進后的Chord協議的平均查找跳數和平均路由延時都有一定的降低，提高了查找效率。

[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，FRANCIS 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.