摘 要： 在P2P網(wǎng)絡(luò)中,，如何高效地查找需要的資源是關(guān)系P2P網(wǎng)絡(luò)性能的關(guān)鍵,。傳統(tǒng)的Chord的路由表信息冗余，查找效率不高,，且不考慮實(shí)際物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),，因此使邏輯拓?fù)渑c物理拓?fù)洳黄ヅ洌瑢?dǎo)致了較大的網(wǎng)路延遲,。提出一種改進(jìn)的Chord路由算法,，該算法在一定程度上解決了上述兩個(gè)問(wèn)題，提高了搜索查詢的效率,。
關(guān)鍵詞： 對(duì)等網(wǎng)絡(luò),；Chord；路由,；拓?fù)淦ヅ?/p>

    高效的查找資源決定了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í)針方向排列成一個(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)開始的半個(gè)環(huán)的區(qū)域。
    如圖1所示,，當(dāng)節(jié)點(diǎn)8要查找K56時(shí),，首先判斷自身ID等于8而非56；然后檢查K56沒有落在本節(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ò)沒有任何關(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)開始的一半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)不斷地加入和離開，所以當(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)求,。總體來(lái)說(shuō)改進(jìn)后的Chord協(xié)議的平均查找跳數(shù)和平均路由延時(shí)都有一定的降低,，提高了查找效率,。
參考文獻(xiàn)
[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.