一种Chord优化改进算法

摘要：Chord协议是一种典型的结构化P2P网络协议，该协议将网络虚拟为环形拓扑结构，可以实现资源的快速查找与定位，查找效率得到了很大的提高，但随着网络规模的扩大，用户节点数量的增多，Chord算法在性能和稳定性方面都存在一定的下降，文章充分分析了Chord算法存在的缺陷和不足，提出一种MDT-Chord基于拓扑结构的双向多级Chord改进算法，为今后的Chord改进研究提供一种新的思路。

关键词： Chord；拓扑结构；双向；多级

中图分类号：TP311.52 文献标识码：A 文章编号：1007-9599 （2012） 16-0000-02

1 引言

Chord协议是一种典型的结构化P2P网络协议，它将网络结构虚拟成环形拓扑结构，可以实现网络资源的快速定位与查找。但如果网络规模不断的扩大，用户节点不断的增多，Chord算法就会出现瓶颈缺陷，就会出现请求转发延迟，降低性能。文章在分析研究了现有的几种Chord的改进算法基础之上，从解决Chord协议的“缺陷”出发，提出一种MDT-Chord基于拓扑结构的双向多级Chord改进算法，为今后的Chord改进研究提供一种新的思路。

2 MDT-Chord：基于拓扑结构的多级双向Chord优化算法

（1） M-Chord算法

1）四级Chord路由算法。相对于经典Chord路由算法，四级Chord路由算法将原算法中的“finger[k].start = （ ） mod 2l （1≤k≤l）”项进一步扩展修改为新指取表中“finger[k].start = （ ） mod 2l （1≤k≤l，1≤j

改进后的算法最大转发次数从以前的 减少为 。图1为 同 随着N的增大而增长的对比图。从图可见，随着N的不断增大，Chord性能可以得到极大的提高。

2）多级Chord路由算法。根据上述分析，可以将Chord的查找级数不断提高，从而继续提高指取表的分布密度。将级数推广到多级，即M-Chord，该算法的定位和查找的跳转次数最多为 。如图2，在给定的100万个节点数的情形下，查找级数与查找路由跳数之间的曲线关系。

不断提高Chord的查找级数，而其查找的路由跳转次数则趋缓。所以如果当级数M达到一定值后，就没有必要再提高Chord级数了。通过提高级数来实现M-Chord算法，主要通过增加空间和时间复杂度来换取查找跳转次数的减少，以此来降低查找延迟，某种程度上也提高了Chord的查找效率。

3）多级Chord指取表去冗余。虽然上述M-Chord算法的查找效率有了很大的提高，但由上图2看出，其算法指取表长度较原Chord的指取表大了许多，变成了 。图3为在给定100万个Chord节点数时，不同级的Chord下，各节点所需维护指取表的长度变化图。

如果提高查找级数则会导致Chord指取表的长度成线性增长，这样不仅会导致更多内存的消耗，而且也会占用更多的带宽资源。

去冗余路由信息算法：

各节点定时查找其储存的指取表，标记相同“successor”项，标出其中的冗余信息。

删除冗余信息，只保留相同“successor”标记项中的第一项。

重新整理，构建去冗后的指取表。

（2） D-Chord算法

在Chord环上各节点的指取表中的路由信息，根据按不同的查找方向（顺、逆时针方向）从指取表“finger”表和“R_finger”中可找到4个节点的标识符“NodeID”与待查找资源的关键字哈希运算后的标识符较为接近，其中，从“finger”表中取出两个节点，从“R_finger”表中取出两个节点，且每两个标识符可以将关键字id放在其中间，这4个节点中的某个节点将可能作为查找的下一跳节点。

假定待查找资源的关键字哈希值为k，采用选取两个最近的节点，并将k值包围的选取策略，从指取表“finger表”和“R_finger表”中分别按顺时针和逆时针方向各选取两个节点n1和n2，n3和n4。

其中，n1满足式：

n3满足式：

并且，n2和n4分别是在于n1和n3之后，且不与之相等的Chord环上的节点。

这4个节点中，有一个离“k”的逻辑距离最近，于是可以把最近的节点作为下一跳Chord查找的路由。定义一个便于存储和筛选的数组：

在路由选择时，为了确保下一跳的方向，可设计一个能存储所有节点选取方向的数组，且下标与数组A对应，定义“k”在节点的逆时针方向为“-1”， 顺时针方向为“+1”：

D = [+1，-1，-1，1]

该算法选取下一跳路由的策略如下：首先，计算所选取的4个节点与“k”的逻辑距离，讲数据存储于数组A；然后，对数组A进行查找操作，把最小项标记下标即“ni”选为Chord的下一跳；最后根据“D[i]”的值来确定查找方向，当D[i] = 1时按顺时针方向，否则按逆时针方向。

（3） MD-Chord算法

结合以上提出两种算法，提出“MD-Chord”多级双向Chord改进算法。由于上述两算法不仅能优化指取表，而且还能减少路由的跳转次数。这样，将“M-Chord”算法与“D-Chord”算法融合，可以更大程度的减少路由跳转，减小查找延迟，极大的提高查找效率。

（4） T-Chord算法

主要是在的节点中添加一个邻居表，使得Chord系统在进行路由跳转过程中选取路由时也会受到邻居表信息的影响。在物理拓扑最近和逻辑最近之间通过一个平衡来决定选择下一跳的路由。不仅可以有效的减少多余的路由跳转，还能大大降低查找延迟。

建立邻居表可以采用试探法、泛洪技术、界标簇集等方法，可以根据实际情况来确定路由表的建立。

T-Chord算法具体作用如下：

当Chord选择下一跳转发路由时，

ⅰ.假如能在邻居表或指取表中找到目标节点，则该节点直接作为下一跳；否则执行（2）。

ⅱ.在指取表中找出小于且最近于目标节点的后继节点，作为可能的下一跳。

ⅲ.以上述同样的方式从节点邻居表中选取可能的下一跳。

ⅳ.比较选取的两节点，如果为同一节点，则该节点为下一跳，否则（5）。

ⅴ.比较两节点与目标节点的距离，最近距离的节点的作为下一跳。

（5） MDT-Chord算法

由于在上述“MD-Chord”改进算法中没有考虑拓扑结构，所以查找中仍有绕路的问题出现，可能导致查找效率不高。于是本文提出一种基于拓扑结构的多级双向Chord改进算法，即“MDT-Chord”算法。该算法选取下一跳路由的策略是：在“MD-Chord”算法选择下一跳路由的基础上将“T-Chord”算法加入优化。在“MD-Chord”算法选择下一跳路由时，同时在节点存储的邻居表中选取两个节点n5和n6，并要求n5满足：

n6位于n5之后，且不与n5相等。从而扩展了数组“A”和查找方向控制数组“D”，扩展后的数组为：

D = [+1，-1，-1，+1，+1，-1]

于是在选择下一跳路由时，先查找到距离最小的项A[i]，方向定为D[i]，因此可以确定下一跳的节点为A[i]，同时查找方向也确定了，这是考虑了逻辑距离优化和实际拓扑的结果。

3 结束语

文章对Chord算法进行详细的分析和研究，完成了对提出的多种改进算法的研究，在查找方向、指取表扩展、指取表冗余和考虑网络拓扑物理结构等方面做了改进优化。并且，完成了“MDT-Chord”基于拓扑结构的多级双向Chord改进算法的详细设计。

参考文献：

[1]Yuan Jian， Ren Yong， Shan Xiu-ming. Self-Organized criticality in a computer network model. Physics Review， 2000，61（2）：1067-1071.

[2]F. Harrell， YF. Hu. Survey of Locating & Routing in Peer-to-Peer Systems. Tech Report， CSE-221， University of California， San Diego， 2002.3.

[3]张浩，金海，聂江武等. Dual-Chord：一种更加有效的分布式哈希表[J].小型微型计算机系统，2006（8）：14501-1454.

[作者简介]梁建武（1963-），男（汉族），湖南长沙人，硕士，高级工程师，主要研究方向为信号处理，网络安全与认证；贺鹏彬（1981-），男（土家族），湖南津市人，在读硕士，现就职于中国人民96212部队，主要研究方向为通信与信息系统；王军（1981-），男（汉族），湖北荆州人，在读硕士，现就职于中国人民96212部队，主要研究方向为通信与信息系统

基金项目：获国家自然科学基金（60773013）资助