王 慧，王 錚

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400030

基于新路由表的雙向搜索chord路由算法

王 慧，王 錚

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400030

1 引言

對(duì)等網(wǎng)絡(luò)P2P（Peer to Peer）是一種分布式網(wǎng)絡(luò)，它有別于傳統(tǒng)的C/S（Client/Server）網(wǎng)絡(luò)模式。在P2P網(wǎng)絡(luò)中，所有的計(jì)算機(jī)都以同等地位相連來(lái)共享資源，每臺(tái)計(jì)算機(jī)既能充當(dāng)客戶端，又能作為服務(wù)器向其他計(jì)算機(jī)提供資源和服務(wù)。隨著互聯(lián)網(wǎng)的廣泛應(yīng)用，P2P技術(shù)的應(yīng)用和服務(wù)已經(jīng)成為人們網(wǎng)絡(luò)生活中的重要組成部分，如分布式計(jì)算、即時(shí)通信、文件交換、協(xié)同設(shè)計(jì)等，而承載這些應(yīng)用的重要機(jī)制則是資源的搜索定位技術(shù)。

根據(jù)P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，可將P2P網(wǎng)絡(luò)資源搜索算法分為3種模式：（1）中央索引模式。利用中心索引服務(wù)器存儲(chǔ)數(shù)據(jù)的元數(shù)據(jù)信息，如Napster[1]等。這種模式缺點(diǎn)是當(dāng)系統(tǒng)中節(jié)點(diǎn)數(shù)增多時(shí)，中心索引服務(wù)器就會(huì)成為系統(tǒng)的瓶頸。（2）采用洪泛的搜索模式。每個(gè)節(jié)點(diǎn)都儲(chǔ)存自身的信息或信息索引，當(dāng)需要獲取信息時(shí)，用洪泛的方式進(jìn)行搜索，如Gnutella[2]等。用該種模式采用洪泛機(jī)制發(fā)現(xiàn)資源時(shí)，容易引起消息的泛濫而且難以擴(kuò)展。（3）分布式哈希表模式。該模式基于DHT（Distribute Hash Table）技術(shù)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定信息或特定信息的索引，當(dāng)需要進(jìn)行資源搜索時(shí)，根據(jù)節(jié)點(diǎn)中的特定信息就可以逐步地找到資源。如chord[3]、CAN[4]、Pastry[5]和Tapestry[6]等。這種模式避免了洪泛查找，提高了信息搜索的效率。

chord算法是結(jié)構(gòu)化P2P網(wǎng)絡(luò)中基于DHT技術(shù)的一

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.017.html種經(jīng)典的資源搜索算法。本文在chord算法思想基礎(chǔ)上，提出了一種基于新路由表的雙向搜索chord路由算法NFT-chord。該算法提出一種新的路由表構(gòu)造公式，利用該公式基本消除了路由表中的冗余信息并同時(shí)實(shí)現(xiàn)chord環(huán)的雙向查找。仿真實(shí)驗(yàn)結(jié)果表明，該算法減少了平均查找跳數(shù)，有效地提高了資源的查找效率。

2 chord算法介紹及相關(guān)定義

2.1 chord模型及相關(guān)定義

chord是基于相容散列[7]的一種資源搜索算法。與傳統(tǒng)的散列相比，相容散列具有更好的穩(wěn)定性和負(fù)載平衡。網(wǎng)絡(luò)中每個(gè)資源關(guān)鍵字[8]和節(jié)點(diǎn)都分別擁有一個(gè)m bit的標(biāo)識(shí)符，chord算法使用一致性哈希函數(shù)SHA-1[9]作用于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的IP，得到每個(gè)節(jié)點(diǎn)的標(biāo)識(shí)，稱為節(jié)點(diǎn)ID；同樣，使用SHA-1作用于關(guān)鍵字，得到每個(gè)網(wǎng)絡(luò)資源的標(biāo)識(shí)，稱為鍵值ID。所有的標(biāo)識(shí)符按照0到2m-1的順序排列成一個(gè)圓環(huán)，稱為chord環(huán)。

定義1（后繼節(jié)點(diǎn) successor(k)）節(jié)點(diǎn)ID大于或等于鍵值ID為k的第一個(gè)節(jié)點(diǎn)稱為后繼節(jié)點(diǎn)successor(k)，也就是在chord環(huán)上按順時(shí)針?lè)较蚓噫I值ID為k最近的節(jié)點(diǎn)。

定義2（前繼節(jié)點(diǎn) predecessor(k)）節(jié)點(diǎn)ID小于鍵值ID為k的第一個(gè)節(jié)點(diǎn)稱為前繼節(jié)點(diǎn) predecessor(k)，也就是在chord環(huán)上按逆時(shí)針?lè)较蚓噫I值ID為k最近的節(jié)點(diǎn)。

定義3（路由表finger table）網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都需要維護(hù)一張路由表，每張路由表最多有m個(gè)表項(xiàng)。chord算法中節(jié)點(diǎn)ID為n的路由表的第i項(xiàng)[10]為：

finger(i)=(n+2i-1)mod2m，1≤ i≤ m （1）

圖1中的finger table為chord算法下節(jié)點(diǎn) N8的路由表。

圖1 chord路由模型

2.2 chord算法路由過(guò)程

當(dāng)節(jié)點(diǎn)ID為nodeK的節(jié)點(diǎn)收到查詢鍵值ID為key的請(qǐng)求時(shí)：

（1）當(dāng)前節(jié)點(diǎn)檢查目標(biāo)鍵值ID是否落在自身節(jié)點(diǎn)ID與后繼節(jié)點(diǎn)ID之間，如果是，那么后繼節(jié)點(diǎn)就是存儲(chǔ)目標(biāo)鍵值ID信息的節(jié)點(diǎn)，查找結(jié)束，否則轉(zhuǎn)至（2）。

（2）當(dāng)前節(jié)點(diǎn)查找自身的路由表，找到表中節(jié)點(diǎn)ID最大但不超過(guò)key的第一個(gè)節(jié)點(diǎn)，并將這個(gè)查詢請(qǐng)求轉(zhuǎn)發(fā)給該節(jié)點(diǎn)，返回（1）。

圖1所示是一個(gè)m=6的chord環(huán)，當(dāng)節(jié)點(diǎn)8查找鍵值54時(shí)，節(jié)點(diǎn)8首先檢查鍵值是否在節(jié)點(diǎn)8和節(jié)點(diǎn)14之間，發(fā)現(xiàn)不是后再查找自身的路由表，將請(qǐng)求轉(zhuǎn)發(fā)到節(jié)點(diǎn)42，然后反復(fù)查詢，最終經(jīng)過(guò)3次轉(zhuǎn)發(fā)，找到54的后繼節(jié)點(diǎn)56。

3 基于新路由表的雙向搜索chord路由算法NFT-chord

3.1 新路由表的構(gòu)造觀察圖1中節(jié)點(diǎn)8的路由表，可以發(fā)現(xiàn)表中存在著信息冗余的情況，即路由表中有多項(xiàng)都對(duì)應(yīng)同一個(gè)節(jié)點(diǎn)，造成了存儲(chǔ)空間不必要的浪費(fèi)。文獻(xiàn)[11]對(duì)chord算法路由表的構(gòu)造方式進(jìn)行深入分析，在公式（1）的2i-1

前乘上一個(gè)基數(shù)d，得到一個(gè)新的路由表構(gòu)造公式（節(jié)點(diǎn)ID為n的路由表的第 j項(xiàng)）：

公式（2）中的d表示節(jié)點(diǎn) j的后繼節(jié)點(diǎn)與其的邏輯距離值，公式（2）中的i值由 j和d決定。因此，圖1中的節(jié)點(diǎn)N8的路由表改進(jìn)為圖2所示。

圖2 圖1中節(jié)點(diǎn)N8的路由表

從圖2中不難看出，該路由表雖然解決了信息冗余的問(wèn)題，但路由表項(xiàng)對(duì)應(yīng)的節(jié)點(diǎn)大多在節(jié)點(diǎn)8附近，而對(duì)于遠(yuǎn)離節(jié)點(diǎn)8的節(jié)點(diǎn)路由表沒(méi)有很好的處理（圖2表現(xiàn)在節(jié)點(diǎn)ID為32到節(jié)點(diǎn)ID為1之間節(jié)點(diǎn)都需要先跳到節(jié)點(diǎn)32上）。分析后發(fā)現(xiàn)，公式（2）可簡(jiǎn)化為：

當(dāng)路由表項(xiàng)數(shù) j不斷增加（也就是處于路由表中靠后的表項(xiàng)），公式（3）所得值的增大幅度也不斷增大，造成了路由表后半部分表項(xiàng)的對(duì)應(yīng)節(jié)點(diǎn)覆蓋少。為解決這一問(wèn)題，對(duì)路由表的構(gòu)造方式重新分析，假設(shè)chord環(huán)的大小為2m，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N=2n(m＞n)，且所有節(jié)點(diǎn)均勻分布，那么任意2個(gè)相鄰節(jié)點(diǎn)之間的間隔 Δ=2m/2n，從圖1中的路由表可以看出，最容易出現(xiàn)信息冗余的是路由表的前幾項(xiàng)，要想使路由表從第1項(xiàng)開(kāi)始就沒(méi)有冗余信息并且基本實(shí)現(xiàn)路由表項(xiàng)節(jié)點(diǎn)的均勻分布，當(dāng)i=1時(shí)，就要使 λ×2i-1≥Δ，得到路由因子 λ≥Δ，進(jìn)而求得 λ≥2m-n，取λ為2m-n。由新構(gòu)造方式所得的路由表如圖3所示。

圖3 圖1中節(jié)點(diǎn)N8的新路由表

從圖3的路由表中可以發(fā)現(xiàn)，對(duì)于節(jié)點(diǎn)8路由表項(xiàng)已基本實(shí)現(xiàn)表項(xiàng)對(duì)應(yīng)的節(jié)點(diǎn)均勻分布且沒(méi)有冗余項(xiàng)，但是該路由表項(xiàng)中所對(duì)應(yīng)的節(jié)點(diǎn)范圍只是節(jié)點(diǎn)8按順時(shí)針?lè)较虻腸hord前半圈，這是因?yàn)槁酚梢蜃映松系氖且驍?shù)2i-1，表示的是chord環(huán)半圈的范圍。為了使整個(gè)chord環(huán)都能實(shí)現(xiàn)，同時(shí)考慮到雙向查找可以有效減少查找跳數(shù)[12]的特性，對(duì)路由表進(jìn)一步改進(jìn)得到反向構(gòu)造公式：

在綜合考慮了路由表的正向、反向和路由因子等多種因素后，最終新路由表的構(gòu)造公式表示為：

其中nodeK表示當(dāng)前節(jié)點(diǎn)ID，i表示節(jié)點(diǎn)nodeK路由表中第i項(xiàng)，路由因子λ為2m-n，從新的路由表公式中可以看出，公式（4）和（6）所得的鍵值 ID∈(nodeK，nodeK+ 2m-1)，公式（5）和（7）所得的鍵值 ID∈(nodeK+2m-1，nodeK+2m)。圖4中節(jié)點(diǎn)8的路由表為新路由表，可以看出，新路由表中已經(jīng)沒(méi)有冗余項(xiàng)并且表項(xiàng)中的節(jié)點(diǎn)基本實(shí)現(xiàn)選取跳轉(zhuǎn)節(jié)點(diǎn)的均勻分布。

3.2 NFT-chord算法路由過(guò)程

當(dāng)前節(jié)點(diǎn)為nodeK，要查找鍵值ID為nodeD的資源，即要查找successor(nodeD)，NFT-chord算法的查找過(guò)程如下：

（1）判斷nodeD是否屬于(node當(dāng)前節(jié)點(diǎn)ID+2m-1，node當(dāng)前節(jié)點(diǎn)ID+2m)，如果是，轉(zhuǎn)至（3），否則繼續(xù)執(zhí)行。

（2）按照chord環(huán)順時(shí)針判斷 nodeD是否屬于(node當(dāng)前節(jié)點(diǎn)ID，successor(node當(dāng)前節(jié)點(diǎn)ID))，如果是，那 么successor(node當(dāng)前節(jié)點(diǎn)ID)即為所求的節(jié)點(diǎn)，查找結(jié)束。否則查找所在節(jié)點(diǎn)的路由表，在路由表第1至第n項(xiàng)中找到小于nodeD的最大鍵值ID對(duì)應(yīng)的節(jié)點(diǎn)node1和路由表中大于nodeD的最小鍵值ID對(duì)應(yīng)的節(jié)點(diǎn)node2，如果|nodeD-node1|＜ |node2-nodeD|，將請(qǐng)求轉(zhuǎn)發(fā)至節(jié)點(diǎn)node1，返回（1），如果 |nodeD-node1|≥ |node2-nodeD|，則將請(qǐng)求轉(zhuǎn)發(fā)至node2，返回（1）。

（3）按照chord環(huán)逆時(shí)針判斷 nodeD是否屬于(node當(dāng)前節(jié)點(diǎn)ID，predecessor(node當(dāng)前節(jié)點(diǎn)ID))，如果是，那么node當(dāng)前節(jié)點(diǎn)ID即為所求的節(jié)點(diǎn)，查找結(jié)束。否則查找節(jié)點(diǎn)node當(dāng)前節(jié)點(diǎn)ID的路由表，在路由表第n至第m項(xiàng)（或第2n項(xiàng)）中找出小于nodeD的最大鍵值ID對(duì)應(yīng)的節(jié)點(diǎn)node3和路由表中大于nodeD的最小鍵值ID對(duì)應(yīng)的節(jié)點(diǎn) node4，如果 |nodeD-node3|＜ |node4-nodeD|，將請(qǐng)求轉(zhuǎn)發(fā)至節(jié)點(diǎn) node3，返回（1）否則如果 |nodeD-node3|≥|node4-nodeD|，將請(qǐng)求轉(zhuǎn)發(fā)至 node4，返回（1）。

圖4中節(jié)點(diǎn)8的路由表使用新構(gòu)造公式所得，節(jié)點(diǎn)8查找鍵值54時(shí)，按照NFT-chord算法過(guò)程，只需一跳就能定位到節(jié)點(diǎn)56，比chord算法跳數(shù)減少了2步，提高了搜索效率。

圖4 NFT-chord路由模型

3.3 算法性能分析

在節(jié)點(diǎn)個(gè)數(shù)為N的網(wǎng)絡(luò)中，當(dāng)前節(jié)點(diǎn)為nodeK，所要查找鍵值ID為key，且successor(key)=nodeD。

定理1chord算法找到目標(biāo)節(jié)點(diǎn)nodeD要訪問(wèn)的節(jié)點(diǎn)數(shù)最多為O(lbN)。

證明假設(shè)節(jié)點(diǎn)nodeP為 predecessor(nodeD)。

當(dāng)nodeK=nodeP，那么節(jié)點(diǎn)nodeK的后繼節(jié)點(diǎn)即為所要查找的節(jié)點(diǎn)nodeD，查找結(jié)束。

當(dāng)nodeK≠nodeP，則節(jié)點(diǎn)nodeK在它的路由表中由前向后查找最接近keyD的前繼節(jié)點(diǎn)nodeP。若節(jié)點(diǎn)nodeP落在節(jié)點(diǎn)nodeK的第i項(xiàng)指針區(qū)間[n +2i-1，n+2i]，因?yàn)檫@個(gè)區(qū)間非空（有節(jié)點(diǎn)nodeP存在），節(jié)點(diǎn)nodeK將尋找第i項(xiàng)指針區(qū)間內(nèi)的第一個(gè)節(jié)點(diǎn)nodeF，在nodeK和nodeF之間的距離至少是2i-1，但是nodeF和nodeP都落在節(jié)點(diǎn)nodeK的第i指針區(qū)間內(nèi)，也就是說(shuō)它們之間的距離最多是2i-1，意味著從nodeF到nodeP的距離最多是nodeK到nodeP距離的一半。在初始的最大距離為2m的情況下，查找的每一步都等分處理查詢節(jié)點(diǎn)nodeK和nodeP的距離，那么在m跳之后必然會(huì)到達(dá)nodeP，查找結(jié)束。

綜上所述，chord算法找到目標(biāo)節(jié)點(diǎn)nodeD訪問(wèn)的節(jié)點(diǎn)數(shù)最多為O(lbN)。

定理2NFT-chord算法找到目標(biāo)節(jié)點(diǎn)nodeD所需的平均查找跳數(shù)少于chord算法[13]。

證明對(duì)NFT-chord算法的路由表構(gòu)造公式（5）（6）（7）（8）進(jìn)行分析不難看出，無(wú)論是 n≤m/2還是 n＞m/2的情況，路由表的構(gòu)造公式是一樣的，主要的區(qū)別在于路由表的項(xiàng)數(shù)。

當(dāng)n≤m/2時(shí)，利用公式（5）當(dāng)i=n，得到 finger(n)= nodeK+2m-n×2n-1=nodeK+2m-1，已經(jīng)完成chord環(huán)正向查找的最大范圍，也就是說(shuō)此時(shí)路由表正向的項(xiàng)數(shù)為n，同理，反向的項(xiàng)數(shù)也為n，所以整個(gè)路由表的項(xiàng)數(shù)為2n。

當(dāng) n＞m/2時(shí)，利用公式（7）當(dāng) i=n時(shí)同樣得到finger(n)=nodeK+2m-1，完成chord環(huán)正向查找的最大范圍，此時(shí)路由表正向的項(xiàng)數(shù)為n，但利用公式（8）計(jì)算反向的時(shí)候，由于m＞n，當(dāng)i=m+1時(shí)，finger(m+1)= nodeK+2m-n×2m+1-1=nodeK+2m+m-n＞nodeK+2m，也就是說(shuō)此時(shí)路由表表項(xiàng)已經(jīng)完成了chord環(huán)一圈的查找，無(wú)需再計(jì)算，故此時(shí)反向的表項(xiàng)應(yīng)為m，所以整個(gè)路由表的項(xiàng)數(shù)為m+n。

定理3NFT-chord算法提出的路由表構(gòu)造公式基本消除chord算法中路由表的冗余項(xiàng)。

證明在chord環(huán)的大小為2m，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N= 2n(m＞n)，且所有節(jié)點(diǎn)均勻分布在chord環(huán)的網(wǎng)絡(luò)中，任意2個(gè)相鄰節(jié)點(diǎn)之間的間隔Δ=2m/2n，假設(shè)當(dāng)前節(jié)點(diǎn)為nodeK，那么利用chord算法構(gòu)造的路由表表項(xiàng)節(jié)點(diǎn)依次為 nodeK+1，nodeK+2，nodeK+4，nodeK+8，…，如果nodeK與nodeK的后繼節(jié)點(diǎn)在chord環(huán)上相差的邏輯距離大于2，路由表的第1項(xiàng)和第2項(xiàng)所對(duì)應(yīng)的節(jié)點(diǎn)就是相同的，出現(xiàn)信息冗余的情況。由于路由表中越靠前的表項(xiàng)中相鄰節(jié)點(diǎn)之間的邏輯距離越小，就很容易出現(xiàn)信息冗余的情況，而在NFT-chord算法中構(gòu)造路由表時(shí)加入路由因子λ，這樣路由表項(xiàng)節(jié)點(diǎn)依次為nodeK+2m-n，nodeK+2×2m-n，nodeK+4×2m-n，…，顯然，從第 1項(xiàng)開(kāi)始，節(jié)點(diǎn)間的邏輯距離就大于等于Δ，在節(jié)點(diǎn)均勻分布的chord網(wǎng)絡(luò)中很難出現(xiàn)信息冗余的情況。

4 仿真實(shí)驗(yàn)分析

仿真實(shí)驗(yàn)采用P2Psim[14]模擬工具，P2Psim是MIT推出的開(kāi)源仿真軟件，以離散事件為基礎(chǔ)來(lái)進(jìn)行模擬，模擬一個(gè)程序需要三個(gè)文件，一個(gè)拓?fù)浣Y(jié)構(gòu)文件、一個(gè)代碼文件和一個(gè)產(chǎn)生事件的文件。在linux redhat9.0下安裝P2Psim，分別對(duì)chord算法、文獻(xiàn)[12]提出的雙向chord算法和本文提出的NFT-chord算法進(jìn)行模擬。之所以選擇與文獻(xiàn)[12]中的算法相比較是因?yàn)樵撍惴▽?shí)現(xiàn)了chord的雙向查找且改進(jìn)效果較好，但是沒(méi)有考慮到網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)和資源個(gè)數(shù)對(duì)路由表的影響，對(duì)于節(jié)點(diǎn)稀疏型網(wǎng)絡(luò)和節(jié)點(diǎn)密集型網(wǎng)絡(luò)沒(méi)有很好地區(qū)別處理，因此該算法改進(jìn)的性能是有限的，而且文獻(xiàn)[12]提出的路由表的構(gòu)造方式過(guò)于復(fù)雜。而本文提出的NFT-chord算法引入路由因子λ，對(duì)于稀疏型網(wǎng)絡(luò)和密集型網(wǎng)絡(luò)取不同的值，有效地提高了網(wǎng)絡(luò)的查找效率。本文模擬環(huán)境chord環(huán)的大小 m=24，即鍵值數(shù) 2m=224= 16 777 216。依次模擬1 000至10 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，得到每個(gè)網(wǎng)絡(luò)的平均查找跳數(shù)。在對(duì)每個(gè)網(wǎng)絡(luò)的實(shí)驗(yàn)中，每個(gè)節(jié)點(diǎn)對(duì)一個(gè)隨機(jī)產(chǎn)生的鍵值key進(jìn)行查找，重復(fù)100次，最后求出所有節(jié)點(diǎn)的平均查找跳數(shù)，重復(fù)20次，得到圖5所示的實(shí)驗(yàn)曲線。

圖5 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和平均查找跳數(shù)關(guān)系圖

從算法的路由表構(gòu)造方式來(lái)說(shuō)，chord算法和NFT-chord算法都是按照提出的公式直接構(gòu)造出所需的路由表，而文獻(xiàn)[12]提出的雙向chord算法構(gòu)造路由表首先要先按照chord算法構(gòu)造出正向路由表，再刪除冗余表項(xiàng)，然后構(gòu)造反向路由表，同樣再刪除冗余表項(xiàng)，最后將兩個(gè)表合并處理。不難看出，雙向chord算法構(gòu)造路由表明顯比chord算法和NFT-chord算法復(fù)雜得多，特別是對(duì)于網(wǎng)路節(jié)點(diǎn)數(shù)N較大的chord網(wǎng)絡(luò)，構(gòu)造節(jié)點(diǎn)路由表的代價(jià)過(guò)大。

從算法的平均查找跳數(shù)來(lái)說(shuō)，圖5中可以看出：當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù) N≤4 000，NFT-chord算法明顯比chord算法平均跳數(shù)少，比雙向chord算法略少；而當(dāng)N＞4 000，NFT-chord算法曲線雖然與雙向chord曲線逐漸逼近，但仍比chord的平均跳數(shù)少。NFT-chord曲線與雙向chord曲線的逼近是因?yàn)楫?dāng)m一定時(shí)，N越大，NFT-chord中的路由因子λ就越接近1，故而NFT-chord算法所構(gòu)造的路由表與雙向chord就越相近，平均查找跳數(shù)也就越相近。該圖體現(xiàn)了NFT-chord算法更適用于在節(jié)點(diǎn)數(shù)遠(yuǎn)小于鍵值數(shù)的chord網(wǎng)絡(luò)中，由于路由因子λ的加入，充分考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)和資源個(gè)數(shù)對(duì)路由表的影響，有效地降低了平均查找跳數(shù)，提高了資源查找效率。

5 結(jié)束語(yǔ)

本文針對(duì)結(jié)構(gòu)化的P2P資源搜索算法問(wèn)題，提出了一種新的算法（算法NFT-chord），該算法通過(guò)引用路由因子，基本刪除了chord路由表中冗余信息，并且實(shí)現(xiàn)了chord環(huán)的雙向查找。對(duì)于chord環(huán)上節(jié)點(diǎn)均勻分布的P2P網(wǎng)絡(luò)，該算法在構(gòu)造路由表所花費(fèi)的代價(jià)方面比雙向路由表算法要少，并且在查找資源所需平均跳數(shù)方面比chord算法更少，查找效率更高。

[1]Napster-file sharing system[EB/OL].（2002-12-10）.http：// www.napster.com/.

[2]Gnutella website[EB/OL].（2004-09-21）.http：//gnutella.wego. com.

[3]Stoica I，Morris R，Liben-Nowell D，et al.Chord：a scalable peer-to-peer lookup protocol for Internet applications[J].IEEE/ACM Transactions on Networking，2003，11（1）：17-32.

[4]Rowstorn A，Druschel P.Pastry：scalable，decentralized object location and routing for large-scale peer-to-peer systems[C]//Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms（Middleware 2001），Heidelberg，Germany，2001.

[5]Zhao B Y，Ling H，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.

[6]Maymounkov P，Mazieres D.Kademliaemlia：a peer-to-peer information system based on the XOR metric[C]//Proceedings of the 1st International Workshop on Peer-to-Peer Systems（IPTPS’02），Cambridge，MA，2002.

[7]Karger D，Lehamn E，Leightom F，et al.Consistent hashing and random trees：distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proceedings of the 29th Annual ACM Symposium on Theory of Computing，El Paso，TX，1997：654-663.

[8]李士寧，夏貽勇，杜艷麗.對(duì)等網(wǎng)絡(luò)中DHT搜索算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（6）：1611-1615.

[9]FIPS 180-1.Secure hash standard[R].US：Department of Commerce/NiST，1995.

[10]成培，胡峰松，栗智.基于Chord的結(jié)構(gòu)化P2P路由改進(jìn)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（1）：63-65.

[11]祁玉，張新有.chord路由表結(jié)構(gòu)的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（6）：1170-1172.

[12]王必晴.Chord路由算法的研究與改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（14）：112-114.

[13]劉曉鋒，吳亞娟，鐘樂(lè)海.Chord路由表結(jié)構(gòu)的改進(jìn)與優(yōu)化[J].計(jì)算機(jī)工程，2007，33（21）：102-104.

[14]P2Psim[EB/OL].（2006-09-07）.http：//Pdos.csail.mit.edu/ p2psim/.

WANG Hui,WANG Zheng

College of Computer Science,Chongqing University,Chongqing 400030,China

A bidirectional search chord routing algorithm based on new finger table is proposed according to the issue of searching resources efficiently in structured P2P network.This algorithm puts forward a new finger table structure formula to solve the problem of overmuch redundancy and low searching efficiency.On the premise of not increasing the finger table’s item,the new formula proposes routing factor and makes full use of the average distance between nodes in chord ring.The new finger table not only has no redundancy items,but also achieves bidirectional search in chord ring to reduce the average lookup path length.The simulation results show that this algorithm removes the redundancy information,reduces the average lookup path length and gets higher efficiency.

structured Peer to Peer（P2P）network;new finger table;bidirectional search chord routing algorithm;routing factor;resources efficient search

針對(duì)結(jié)構(gòu)化P2P（Peer to Peer）網(wǎng)絡(luò)資源高效搜索問(wèn)題，提出了一種基于新路由表的雙向搜索chord路由算法。該算法為解決chord算法路由表中存在著大量冗余信息，查找資源效率低下等缺點(diǎn)，提出了一個(gè)新的路由表構(gòu)造公式。該公式首次加入路由因子概念，充分考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)和資源個(gè)數(shù)對(duì)路由表的影響，在不增加路由表項(xiàng)的前提下，不僅基本刪除了路由表的冗余項(xiàng)，還實(shí)現(xiàn)了chord環(huán)的雙向查找以減少平均查找跳數(shù)。實(shí)驗(yàn)仿真結(jié)果表明，該算法基本消除了路由表中的冗余信息，減少了平均查找跳數(shù)，有效地提高了資源的查找效率。

結(jié)構(gòu)化對(duì)等（P2P）網(wǎng)絡(luò)；新路由表；雙向搜索chord路由算法；路由因子；資源高效搜索

A

TP393

10.3778/j.issn.1002-8331.1301-0006

WANG Hui,WANG Zheng.Bidirectional search chord routing algorithm based on new finger table.Computer Engineering and Applications,2014,50（23）：95-99.

王慧（1988—），女，碩士研究生，主要研究領(lǐng)域?yàn)榉植际较到y(tǒng)、網(wǎng)絡(luò)路由算法、網(wǎng)絡(luò)通信；王錚（1953—），男，副教授，碩士生導(dǎo)師，主要研究方向?yàn)榍度胧讲僮飨到y(tǒng)、分布式系統(tǒng)、軟件自動(dòng)生成。E-mail：tracyh1988@163.com

2013-01-05

2013-03-11

1002-8331（2014）23-0095-05