2007年9月
September 2007
—123—
计 算 机 工 程Computer Engineering 第33 第17期
Vol 卷.33 No.17 ·网络与通信·
文章编号：1000—3428(2007)17—0123—02
文献标识码：A
中图分类号：TP393
改进的Chord 加入算法
任小金1,2，古志民1
(1. 北京理工大学计算机科学技术学院，北京 100081；2. 河南大学网络信息中心，开封 475001)
摘 要：Chord 系统在节点频繁加入或离开网络时，会造成大量的开销。为了降低这种加入开销，该文提出了一种新的加入算法——SPJoin ，减少了总的加入开销，使结点能更快速地加入网络。理论分析表明，SPJoin 在构造加入节点的每一个finger 时，需要通过查询获得finger 项的概率小于1/2log N ，最坏情况下，加入节点构造finger table 的开销为O (log N loglog N )跳。模拟实验结果表明，SPJoin 在很大程度上减少了加入开销，基本不影响网络的查询性能。 关键词：P2P ；Chord ；后继；前驱
Improved Chord Joining Algorithm
REN Xiao-jin 1,2, GU Zhi-min 1
(1.School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081;
2. Network Information Center, Henan University, Kaifeng 475001)
【Abstract 】Frequently join or leave of node in Chord system must increase the maintenance overhead. To decrease the overhead, a new join algorithm, namely SPJoin, is proposed. SPJoin reduces the total join overheads. Theory analysis shows the probability of lookup finger entry is less than 1/2log N when SPJoin constructs each finger entry. In the worst case, the lookup hops that the joining node constructs the finger table is O (log N loglog N ). The simulation shows that compared to
ChordFingerPNS, SPJoin can decrease the join overheads greatly while slightly affected the lookup performance.
【Key words 】P2P; Chord; successor; predecessor
对等网络(P2P)的一个重要特征是用户可以随时加入、离开网络，这种特征方便了用户，但却给结构化P2P 网络带来巨大的维护开销。主要原因是当节点加入网络时，由于要构建路由表，因此其需要在网络中进行查询，从而产生了开销。查询开销评估主要基于以下度量指标：查询跳数和查询延迟，一次查询操作总的查询延迟是每一跳查询延迟的总和。
结构化P2P 网络的一个典型系统是Chord [1]。对于一个有N 个节点的网络，Chord 在节点加入时为构建它的路由表其查询
开销为O (log 2
N )跳，另外，由于其没有考虑真实网络中节点的位置信息，其总的延迟可能是巨大的。很多方法对Chord 的加入算法进行了改进，2-chord halved [2]通过使用前驱信息，使它在构建路由表时查询跳数为O (log N loglog N )，但它同样没有考虑节点在真实网络中的位置信息。R-Chord [3]、ChordFingerPNS [4]系统减少了查询的延迟，但在节点加入时需要的查询跳数为O (log 2N )。为减小节点在加入网络时造
成的开销，本文提出了一种新的节点加入算法——SPJoin ，该方法是基于ChordFingerPNS 的加入算法，能有效地减少加入开销。
1 ChordFingerPNS 加入算法分析
Chord 是一种结构化P2P 系统，在Chord 中每个节点维护其前驱(predecessor)、后继(successor)和一个指针表(finger table)，指针表中第i 项的内容为[n +2i , n +2i +1](0≤i <m ；n 为节点的ID ；m 为标识符位数内的第1个节点)。为提高Chord 的健壮性，Chord 中每一个节点还维护一个后继列，后继列数一般为2log N (N 为网络中节点数量)。Chord 的加入算法必须初始化它的指针表，指针表项数为O (log N )。这个过程可以分为两步，
首先节点通过一个已知的节点查到它的后继，然后通过后继查finger table 中的每一项来构造它的finger table ，由于查询开销是O (log N )跳，因此这个初始化过程的开销为O (log 2N )跳。ChordFingerPNS 加入算法对Chord 的加入算法进行了修改，当节点n 加入网络时，它的第i 个finger 项选择[n +2i , n +2i +1)中前x 个节点中与n 的响应时间最小的节点作为它的第i 项finger 。x 为可配置的参数。ChordFingerPNS 的查询算法与Chord 相同。这样ChordFingerPNS 在构建每一个finger 项时减少了每一跳的查询延迟，从而减少了总的加入开销。
2 改进的加入算法——SPJoin
2.1 ChordFingerPNS 加入算法的不足
ChordFingerPNS 虽然减少了查询时每一跳的延迟，但其在构建finger table 时的跳数开销与Chord 相同，因此，总的加入延迟仍然很大。
2.2 SPJoin 算法描述
SPJoin 是对ChordFingerPNS 加入算法的改进，它通过使用加入节点的后继和后继的前驱中的信息来减少加入节点在构建finger table 时需要的查询跳数，从而减少总的加入开销。
算法 (1)在网络中到加入节点的后继，并取得后继以及后继
的前驱的finger table 以及它们的后继列，
后继列记为succlist 。假设加入节点的ID 为a ，其后继为succ(a)，后继的前驱为pre(a)，计算加入节点的第i 个finger 。
作者简介：任小金(1974－)，男，博士研究生，主研方向：对等网络和网格计算；古志民，教授、博士生导师
收稿日期：2006-09-12 E-mail ：rxj@henu.edu
(2)依次计算succ(a )，pre(a)的finger table 和succlist 中是否有[a+2i , a+2i +1]范围内的节点，如果有，则计算这些节点到a 的响应时间，并选择与a 之间最小响应时间的节点作为a 的第i 个 finger ，然后继续计算下一个finger 。如果没有，则通过pre(a)的第i 个finger 来查询a 的第i 个finger ，查询算法与ChordFingerPNS 相同，然后继续计算下一个finger 。 2.3 算法分析
假设节点之间的平均距离为d ；加入节点的ID 为a ，后继为succ(a )，后继的前驱为pre(a )。SPJoin 算法分析如下：
(1)加入节点构建第i 项finger 时可以直接从后继的finger table 和succlist 获得的概率大于1-1/2log N 。
1)当2i < (2log N +1)*d 时，因为succ(a)的succlist 有2log N 个，所以节点a 到succ(a)的最后一个后继之间的距离为(2log N +1)*d 。由于succ(a)到succ(a)的最后一个后继之间除了succ(a)节点和后继列中的节点外不存在其它节点，因此a 的第i 个finger 要么可以从succ(a)以及它的后继列中获得，要么这个finger 不存在，因此，当2i <(2log N +1)*d 时，a 的第i 个finger 可以由succ(a)以及它的后继列确定，即此时可以从后继获得的概率为1。
2)当2i ≥(2log N +1)*d 时，假设第i 项finger 需要进行查询获得的概率为P(i )。图1中标出了a ，succ(a)，pre(a)以及a+2i ，a+2i +1等之间的位置关系，考虑succ(a)和a 之间的关系，由图1可以看出，当succ(a)的第i 个finger 在succ(a)+2i 和a+2i +1之间时，succ(a)的第i 个finger 就可以作为a 的第i 个fing
er 的一个候选，如果succ(a)的第i 个finger 在a+2i +1和succ(a)+2i +1之间，此时a 的第i 个finger 不能由succ(a)的第i 个finger 确定。分析succ(a)的第i 个finger 落在(a+2i +1，succ(a)+2i +1)区间的概率P(d)，a+2i +1到succ(a)+2i +1之间距离为(succ(a)+2i +1)-(a+2i +1)=d ，而(succ(a)+2i +1)-(succ(a)+2i ) =2i ，则P(d)= d/2i ，又由于Chord 的后继列节点数一般为2log N 个，因此当2i ≥(2log N +1)*d 时，P(d )≤d /((2log N +1)*d ) = 1/(2log N +1)。因此a 的第i 项finger 需要进行查询的概率P(i)=P(d )≤1/(2log N +1)< 1/2log N 。
a+2i
a+2i +1
i +1
图1 距离关系
由上述分析可知，加入节点构建第i 项finger 时可以直接从后继的finger table 和succlist 获得的概率大于1-1/2log N 。
由于后继的前驱与加入节点之间的距离为d ，因此从后继的前驱的finger table 和succlist 获得第i 项finger 的情况与从后继获得情况相同。
(2)当加入节点构建第i 项finger 时，不能从后继或后继的前驱中获得时需要的查询跳数为O (loglog N )。当加入节点不能从后继或者后继的前驱节点中得到第i 项的finger 时，此时需要通过查询到第i 项finger ，在ChordFingerPNS 中使用后继节点来查询a+2i 的x 个连续的后继，查询跳数开销为O (log N )。在SPJoin 算法中不使用后继节点来查询，而使用文献[2]中的方法通过后继的前驱的第i 项finger 来查询，查询算法与ChordFingerPNS 的查询算法相同。在文献[2]中证明了连续的节点之间的最大距离为2m log N /N ，在这个距离中，节点的最大数量为4log N 。SPJoin 在构建第i 个finger 项时使用pre(a)的第i 个fin
ger 在网络中查a+2i 的前x 个后继，而由于(a+2i )- (Pre(a)+2i )=d ，因此它们之间有节点的最大数量为4log N ，此时，查询开销为O (loglog N )跳。所以，当加入节点的第i 项finger 不能从后继或后继的前驱中获得时需要的查询跳数为O (loglog N )。如果所有finger 项都不能从后继和后继的前驱中获得，由于需要构造的finger 项数为O (log N )，因此在最坏情况下，其总的查询开销为O (log N loglog N )跳。
(3)SPJoin 算法基本不影响查询性能。ChordFingerPNS 由于使用了PNS(proximity neighbor selection)技术，使ChordFingerPNS 在查询的每一跳中都能转向较小延迟的节点，从而减少了总的查询延迟。而在SPJoin 中如果第i 个finger 是从后继或者后继的前驱中获得的，那么该finger 到加入节点的响应时间不一定小于通过查询方式获得，这样有可能增加总的查询操作的延迟，对此，通过分析和模拟实验证明其对于查询性能的影响不大，因为：1)可从后继和后继的前驱中的信息选择到加入节点延迟最小的作为加入节点的第i 个finger ；2)由于P2P 网络呈现小世界现象，网络中节点的finger 是性能比较好的节点的概率比较大，因此选为a 的finger 相对比较好。如果正好是一个到a 的响应时间较大的节点，则可以通过查询构造该finger 项，或在节点加入网络后通过经过它的路由信息对finger 进一步优化，模拟实验表明，该方法是可行的。
3 模拟实验结果
本文基于MIT 的p2psim [5]模拟器，通过修改ChordFingerPNS 的加入算法来实现本文的加入算法，并和ChordFingerPNS 在加入开销和查询性能两方面进行了比较。
在实验中，网络拓扑使用pdos.csail.mit.edu/p2psim/ kingdata/old-data/中的拓扑，拓扑节点数分别为128、256、512、1 024、2 048，在同等条件下分别对ChordFingerPNS 和SPJoin 进行了测试。在节点依次加入网络并全部加入系统后，开始查询操作，随机产生查询关键字。图2所示为两种加入算法在网络中增加的开销的比较。
500
10001500
李民基2000
2500
节点数
加入开销 x 106
图2 两种加入算法的开销比较
由图2可知，ChordFingerPNS 随着网络中节点的增多，
加入开销迅速增加，而SPJoin 加入开销增长缓慢，因为，在ChordFingerPNS 中随着节点的增加在构造加入节点的finger table 时需要查询的次数也随着增加，而SPJoin 在很大程度上则减少了这种查询次数。
（下转第130页）
—124
—
发布评论