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

2014-08-03 15:23:18王慧，王錚

計算機工程與應用 2014年23期

關鍵詞：資源

王慧，王錚

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

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

王慧，王錚

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

1 引言

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

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

chord算法是結構化P2P網絡中基于DHT技術的一

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

2 chord算法介紹及相關定義

2.1 chord模型及相關定義

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

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

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

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

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

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

圖1 chord路由模型

2.2 chord算法路由過程

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

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

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

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

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

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

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

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

圖2 圖1中節點N8的路由表

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

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

圖3 圖1中節點N8的新路由表

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

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

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

3.2 NFT-chord算法路由過程

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

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

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

圖4 NFT-chord路由模型

3.3 算法性能分析

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗分析

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

圖5 網絡節點數和平均查找跳數關系圖

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

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

5 結束語

本文針對結構化的P2P資源搜索算法問題，提出了一種新的算法（算法NFT-chord），該算法通過引用路由因子，基本刪除了chord路由表中冗余信息，并且實現了chord環的雙向查找。對于chord環上節點均勻分布的P2P網絡，該算法在構造路由表所花費的代價方面比雙向路由表算法要少，并且在查找資源所需平均跳數方面比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]李士寧，夏貽勇，杜艷麗.對等網絡中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路由表結構的改進與優化[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）網絡資源高效搜索問題，提出了一種基于新路由表的雙向搜索chord路由算法。該算法為解決chord算法路由表中存在著大量冗余信息，查找資源效率低下等缺點，提出了一個新的路由表構造公式。該公式首次加入路由因子概念，充分考慮了網絡中節點個數和資源個數對路由表的影響，在不增加路由表項的前提下，不僅基本刪除了路由表的冗余項，還實現了chord環的雙向查找以減少平均查找跳數。實驗仿真結果表明，該算法基本消除了路由表中的冗余信息，減少了平均查找跳數，有效地提高了資源的查找效率。

結構化對等（P2P）網絡；新路由表；雙向搜索chord路由算法；路由因子；資源高效搜索

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—），女，碩士研究生，主要研究領域為分布式系統、網絡路由算法、網絡通信；王錚（1953—），男，副教授，碩士生導師，主要研究方向為嵌入式操作系統、分布式系統、軟件自動生成。E-mail：tracyh1988@163.com

2013-01-05

2013-03-11

1002-8331（2014）23-0095-05