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

王 慧，王 铮

重庆大学 计算机学院，重庆 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），否则继续执行。

（2）按照chord环顺时针判断 nodeD是否属于(node当前节点ID，successor(node当前节点ID))，如果是，那 么successor(node当前节点ID)即为所求的节点，查找结束。否则查找所在节点的路由表，在路由表第1至第n项中找到小于nodeD的最大键值ID对应的节点node1和路由表中大于nodeD的最小键值ID对应的节点node2，如果|nodeD-node1|＜ |node2-nodeD|，将请求转发至节点node1，返回（1），如果 |nodeD-node1|≥ |node2-nodeD|，则将请求转发至node2，返回（1）。

（3）按照chord环逆时针判断 nodeD是否属于(node当前节点ID，predecessor(node当前节点ID))，如果是，那么node当前节点ID即为所求的节点，查找结束。否则查找节点node当前节点ID的路由表，在路由表第n至第m项（或第2n项）中找出小于nodeD的最大键值ID对应的节点node3和路由表中大于nodeD的最小键值ID对应的节点 node4，如果 |nodeD-node3|＜ |node4-nodeD|，将请求转发至节点 node3，返回（1）否则如果 |nodeD-node3|≥|node4-nodeD|，将请求转发至 node4，返回（1）。

图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路由算法；路由因子；资源高效搜索

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—），女，硕士研究生，主要研究领域为分布式系统、网络路由算法、网络通信；王铮（1953—），男，副教授，硕士生导师，主要研究方向为嵌入式操作系统、分布式系统、软件自动生成。E-mail：tracyh1988@163.com

2013-01-05

2013-03-11

1002-8331（2014）23-0095-05