王 慧，王 錚

重慶大學 計算機學院，重慶 400030

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

王 慧，王 錚

重慶大學 計算機學院，重慶 400030

1 引言

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

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

chord算法是結構化P2P網(wǎng)絡中基于DHT技術的一

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

2 chord算法介紹及相關定義

2.1 chord模型及相關定義

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

定義1（后繼節(jié)點 successor(k)）節(jié)點ID大于或等于鍵值ID為k的第一個節(jié)點稱為后繼節(jié)點successor(k)，也就是在chord環(huán)上按順時針方向距鍵值ID為k最近的節(jié)點。

定義2（前繼節(jié)點 predecessor(k)）節(jié)點ID小于鍵值ID為k的第一個節(jié)點稱為前繼節(jié)點 predecessor(k)，也就是在chord環(huán)上按逆時針方向距鍵值ID為k最近的節(jié)點。

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

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

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

圖1 chord路由模型

2.2 chord算法路由過程

當節(jié)點ID為nodeK的節(jié)點收到查詢鍵值ID為key的請求時：

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

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

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

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

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

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

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

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

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

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

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

從圖3的路由表中可以發(fā)現(xiàn)，對于節(jié)點8路由表項已基本實現(xiàn)表項對應的節(jié)點均勻分布且沒有冗余項，但是該路由表項中所對應的節(jié)點范圍只是節(jié)點8按順時針方向的chord前半圈，這是因為路由因子乘上的是因數(shù)2i-1，表示的是chord環(huán)半圈的范圍。為了使整個chord環(huán)都能實現(xiàn)，同時考慮到雙向查找可以有效減少查找跳數(shù)[12]的特性，對路由表進一步改進得到反向構造公式：

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

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

3.2 NFT-chord算法路由過程

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

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

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

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

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

圖4 NFT-chord路由模型

3.3 算法性能分析

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

定理1chord算法找到目標節(jié)點nodeD要訪問的節(jié)點數(shù)最多為O(lbN)。

證明假設節(jié)點nodeP為 predecessor(nodeD)。

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

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

綜上所述，chord算法找到目標節(jié)點nodeD訪問的節(jié)點數(shù)最多為O(lbN)。

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

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

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

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

定理3NFT-chord算法提出的路由表構造公式基本消除chord算法中路由表的冗余項。

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

4 仿真實驗分析

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

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

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

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

5 結束語

本文針對結構化的P2P資源搜索算法問題，提出了一種新的算法（算法NFT-chord），該算法通過引用路由因子，基本刪除了chord路由表中冗余信息，并且實現(xiàn)了chord環(huán)的雙向查找。對于chord環(huán)上節(jié)點均勻分布的P2P網(wǎng)絡，該算法在構造路由表所花費的代價方面比雙向路由表算法要少，并且在查找資源所需平均跳數(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]李士寧，夏貽勇，杜艷麗.對等網(wǎng)絡中DHT搜索算法綜述[J].計算機應用研究，2008，25（6）：1611-1615.

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

[10]成培，胡峰松，栗智.基于Chord的結構化P2P路由改進算法[J].計算機工程與設計，2009，30（1）：63-65.

[11]祁玉，張新有.chord路由表結構的分析與改進[J].計算機工程與設計，2010，31（6）：1170-1172.

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

[13]劉曉鋒，吳亞娟，鐘樂海.Chord路由表結構的改進與優(yōu)化[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

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

結構化對等（P2P）網(wǎng)絡；新路由表；雙向搜索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—），女，碩士研究生，主要研究領域為分布式系統(tǒng)、網(wǎng)絡路由算法、網(wǎng)絡通信；王錚（1953—），男，副教授，碩士生導師，主要研究方向為嵌入式操作系統(tǒng)、分布式系統(tǒng)、軟件自動生成。E-mail：tracyh1988@163.com

2013-01-05

2013-03-11

1002-8331（2014）23-0095-05