Chord路由算法的分析與改進(jìn)

張亞松

（武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢430063）

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

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

1 Chord路由算法

Chord是MIT提出的基于DHT的資源搜索算法，平均路由跳數(shù)一般在log2N/2之內(nèi)。在Chord系統(tǒng)中，節(jié)點(diǎn)和關(guān)鍵字都有一個(gè)m位的標(biāo)識(shí)符，每個(gè)節(jié)點(diǎn)的ID可以通過(guò)對(duì)IP進(jìn)行哈希運(yùn)算得到。所有節(jié)點(diǎn)按照ID從小到大沿順時(shí)針?lè)较蚺帕谐梢粋€(gè)邏輯的標(biāo)識(shí)圓環(huán)（Chord環(huán)）。節(jié)點(diǎn)的資源關(guān)鍵字標(biāo)識(shí)符K通過(guò)對(duì)關(guān)鍵字本身進(jìn)行哈希運(yùn)算得到。關(guān)鍵字標(biāo)識(shí)符K存放在節(jié)點(diǎn)ID=K或者ID=min{ID-K；ID-K>0}這樣的節(jié)點(diǎn)上。Chord中每個(gè)節(jié)點(diǎn)都有一個(gè)路由表，路由表有m條記錄，其中第i條記錄記錄了在Chord中和該節(jié)點(diǎn)的距離大于等于2i-1（i∈[1，m]）的最近節(jié)點(diǎn)。顯然，路由表只能覆蓋從本節(jié)點(diǎn)開(kāi)始的半個(gè)環(huán)的區(qū)域。

如圖1所示，當(dāng)節(jié)點(diǎn)8要查找 K56時(shí)，首先判斷自身ID等于8而非56；然后檢查K56沒(méi)有落在本節(jié)點(diǎn)和它的后繼節(jié)點(diǎn)之間，即 56 不在[9，15]、[16，23]、[24，28]和[40，43]區(qū)間內(nèi)；然后查找路由表，找到表中最大且小于K56的節(jié)點(diǎn)43，把請(qǐng)求轉(zhuǎn)發(fā)到節(jié)點(diǎn)43。重復(fù)此過(guò)程，請(qǐng)求轉(zhuǎn)發(fā)到52，找到存放K56的后繼節(jié)點(diǎn)58，把請(qǐng)求轉(zhuǎn)發(fā)到節(jié)點(diǎn)58，查找結(jié)束。查找過(guò)程為8→43→52→58。

2 改進(jìn)的Chord路由算法

從圖1以及路由表的構(gòu)造可知，路由表中存在冗余路由信息，并且由Chord環(huán)構(gòu)造的邏輯網(wǎng)絡(luò)和物理網(wǎng)絡(luò)沒(méi)有任何關(guān)聯(lián)，所以導(dǎo)致了平均查找跳數(shù)和平均路由延時(shí)的增加。因此，應(yīng)該從這兩個(gè)方面對(duì)路由算法進(jìn)行改進(jìn)，即對(duì)指針表（Finger Table）進(jìn)行修改以及增加鄰居表（Neighbour Table）。

2.1 修改指針表

如圖1所示，從以節(jié)點(diǎn)8為初始節(jié)點(diǎn)的路由表可以看出，有兩條冗余的路由信息。假設(shè)Chord環(huán)的大小為M=2m，節(jié)點(diǎn)數(shù) N=2n(n＜m)，所有節(jié)點(diǎn)平均分布，節(jié)點(diǎn)平均冗余路由信息數(shù)量為log2(2m/2n)=m-n[5]。因?yàn)橄鄬?duì)于大小為M的標(biāo)志符空間，N個(gè)節(jié)點(diǎn)相對(duì)比較稀少，導(dǎo)致節(jié)點(diǎn)和它的后繼節(jié)點(diǎn)之間的間隔大于1，所以出現(xiàn)冗余路由信息無(wú)可避免。

從路由表的構(gòu)造可以看出，路由表可以覆蓋從本節(jié)點(diǎn)開(kāi)始的一半Chord環(huán)，當(dāng)要查找的K存儲(chǔ)在另一半Chord環(huán)時(shí)，就需要更多的跳數(shù)來(lái)完成。由于路由表中每個(gè)節(jié)點(diǎn)平均有m-n條冗余路由信息，所以可以把冗余的路由信息刪除。如果可以用有效的路由信息替代冗余的路由信息，使路由表可以覆蓋更大的范圍，那么必然會(huì)降低查找的平均跳數(shù)，從而提高查找效率。

假設(shè)本節(jié)點(diǎn)為N，新的指針表的構(gòu)造方法如下：

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

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

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

(4)刪除D的指針表。

由以上構(gòu)造方法及圖1中的New Finger Table可知，新的指針表可以覆蓋原指針表覆蓋不到的另一半Chord環(huán)的絕大部分空間，從而指針表查找的范圍增大，平均查找跳數(shù)自然降低了。在新的指針表中，當(dāng)節(jié)點(diǎn)8要查找K56時(shí)，只需要一條就可以找到存儲(chǔ)K56的節(jié)點(diǎn)58，即 8→58。

2.2 增加鄰居表

節(jié)點(diǎn)的鄰居表主要用來(lái)存放在物理網(wǎng)絡(luò)中相距比較近的節(jié)點(diǎn)信息。鄰居表的表項(xiàng)是＜ID，IP>這樣的鍵值對(duì)。鄰居表的表項(xiàng)信息可以利用界標(biāo)簇算法[6]和往返延遲RTT（Round Trip Time）測(cè)量技術(shù)收集。利用這種測(cè)量方法可以把在物理上距離本節(jié)點(diǎn)比較近的節(jié)點(diǎn)信息加入自己的鄰居表。為了保證有效性，系統(tǒng)中的每個(gè)節(jié)點(diǎn)定時(shí)地測(cè)量距鄰居節(jié)點(diǎn)的距離。因?yàn)镃hord環(huán)中的節(jié)點(diǎn)不斷地加入和離開(kāi)，所以當(dāng)鄰居表表項(xiàng)達(dá)到最大時(shí)，應(yīng)該刪除表中距本節(jié)點(diǎn)物理距離最遠(yuǎn)的點(diǎn)。

本節(jié)點(diǎn)和鄰居節(jié)點(diǎn)一起稱為一個(gè)單元，在單元中選取一個(gè)處理能力比較強(qiáng)的作為超級(jí)節(jié)點(diǎn)，單元中的節(jié)點(diǎn)一旦查詢結(jié)束就把查詢結(jié)果發(fā)送給超級(jí)節(jié)點(diǎn)進(jìn)行緩存。對(duì)緩存信息的管理可以采用先入先出、最近最少使用的策略，這樣在下次查詢時(shí)，可以保證在兩跳之內(nèi)找到資源。

2.3 路由查找算法

假設(shè)本節(jié)點(diǎn)為ID=N，需要定位的資源為K，在修改了指針表，增加了鄰居表以及超級(jí)節(jié)點(diǎn)時(shí)，改進(jìn)的資源搜索過(guò)程如下：

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

(2)查找節(jié)點(diǎn)N的指針表，看是否存在節(jié)點(diǎn)標(biāo)識(shí)符等于K的后繼節(jié)點(diǎn)，如果存在，直接返回該后繼節(jié)點(diǎn)的IP地址，搜索結(jié)束；否則，繼續(xù)步驟(3)。

(3)如果節(jié)點(diǎn)N是超級(jí)節(jié)點(diǎn)，檢查是否存在K的記錄，如果存在，搜索結(jié)束；否則，繼續(xù)步驟(4)；如果 N不是超級(jí)節(jié)點(diǎn)，把請(qǐng)求轉(zhuǎn)發(fā)至超級(jí)節(jié)點(diǎn)。

(4)查找節(jié)點(diǎn)N的指針表和鄰居表，分別找到最接近K的節(jié)點(diǎn) N1和 N2，比較 N1和 N2，選擇物理距離與 K較近的一個(gè)作為下一跳的節(jié)點(diǎn)，將搜索請(qǐng)求轉(zhuǎn)發(fā)到這個(gè)節(jié)點(diǎn)上。

通過(guò)上述過(guò)程搜索到所需要的資源后，主動(dòng)上傳資源的定位信息到超級(jí)節(jié)點(diǎn)，保存在緩存中，這樣下次搜索時(shí)就可以迅速地定位了。

3 仿真實(shí)驗(yàn)與結(jié)果分析

在Linux系統(tǒng)下，采用P2PSim仿真平臺(tái)對(duì)原Chord協(xié)議和改進(jìn)后的Chord協(xié)議進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)中主要對(duì)平均查找跳數(shù)和平均路由延遲這兩方面進(jìn)行了比較。實(shí)驗(yàn)對(duì) 10 組(256，512，1 024，2 048，4 096，6 000，8 192，10 000，13 000，16 384)數(shù)據(jù)都進(jìn)行采樣，設(shè)定 M=224，每個(gè)節(jié)點(diǎn)平均隨機(jī)請(qǐng)求4次，對(duì)平均查找跳數(shù)和平均路由時(shí)延進(jìn)行統(tǒng)計(jì)，得到的統(tǒng)計(jì)圖如圖2和圖3所示。實(shí)驗(yàn)結(jié)果進(jìn)一步說(shuō)明了改進(jìn)后的Chord協(xié)議因?yàn)樵龃罅酥羔槺淼母采w范圍，并且考慮了物理網(wǎng)絡(luò)與邏輯網(wǎng)絡(luò)的差異，所以在平均查找跳數(shù)和平均路由延時(shí)方面都有一定程度的降低，提高了查詢的效率。

本文針對(duì)原Chord協(xié)議指針表信息冗余，只能覆蓋Chord環(huán)一半范圍的缺點(diǎn)，刪除了冗余路由信息，添加了有效的路由信息，擴(kuò)大了指針表的覆蓋范圍。針對(duì)邏輯網(wǎng)絡(luò)與物理網(wǎng)絡(luò)不匹配的問(wèn)題，在Chord協(xié)議中增加了鄰居表，使節(jié)點(diǎn)在路由時(shí)可以選擇物理距離相對(duì)比較近的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)請(qǐng)求?？傮w來(lái)說(shuō)改進(jìn)后的Chord協(xié)議的平均查找跳數(shù)和平均路由延時(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.