Chord算法改进现状研究

摘要：P2P网络中，chord搜索算法是一个研究热点。对于经典chord算法，研究者已经从各自角度进行了改进，形成了多种改进chord算法，比如，MR-chord算法、nrtochord算法、多环的chord算法。该文从多个角度对改进chord算法进行汇总研究，期望能明确chord算法的各个改进方向。

关键词：P2P；chord；对比分析

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）02-0325-02

1 chord算法概述

2001年，MIT提出了Chord算法，其核心思想就是要解决在P2P应用中遇到的基本问题——P2P网络中的资源定位问题。该算法使用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体的算法，在Chord协议中将其规定为SHA-1。

2 现有chord改进算法简介

经典chord算法固然以实现简便的优势，促进了当时的P2P网络技术的发展。随着P2P网络进一步的发展，经典chord算法也暴露出了一些不足。开发者从不同角度对经典chord算法提出了改进。近期的chord算法改进文献如下：

《基于DHT的Chord路由算法的研究与改进》[文献1]首先介绍了chord算法的路由过程，并且阐述了该算法在新节点加入操作时带来的查询效率问题：新节点加入后比加入前，查询多了一跳。这种情况在p2p网络动态性极强的情况下，对效率的影响尤为突出。因此，文章提出对新加入节点的直接前驱节点的指取表进行部分扩充的办法。

《一种改进的CHORD搜索算法》[文献2]在原有chord算法路由表不变的基础上，节点又增加了最近访问节点表和邻居节点表，每个节点都要维护三个表，增加了维护成本，但是，它却让资源搜索初，算法先在节点内部的最近访问节点表和邻居节点表中搜索，以提高搜索效率，提供了客观基础。

《P2P网络中Chord搜索算法的改进研究》[文献3]提出根据信息相关度将网络节点进行分组，形成多个二级环，并从中选出一个节点作为超级节点，每个二级环可以在本组内自治。而把所有二级环的超级节点相互连接，形成一个超级组。当一个节点发出资源搜索请求时，算法先在节点所在环内进行搜索。若找到相关节点，算法就此返回结果，并且停止；否则，算法向超级组内发出资源搜索请求，继续查找。

《基于多环的Chord改进算法》[文献4]提出MR-chord算法，该算法提出多环和组相结合的结构，组内节点有本组其它节点的相关信息，组间通过递归算法连接成环。申请搜索资源的节点先在本组内搜索（由于该节点有组内所有其它节点的相关信息，因此，该搜索过程的时间复杂度为O（1）），当算法找不到所需资源时，将请求转发出去。因此，该算法冗余较少。

《一种改进的Chord网络模型》[文献5]针对经典chord模型中，节点路由表存在一定的信息冗余和所有节点周期性执行stablize操作，印发大量消息转发两个缺陷，做了以下改进：采用动态双向路由表；路由选择方面，算法充分利用双向路由表加速定位过程；节点加入和退出方面，算法充分利用双向路由表，尽可能低免除周期性fix操作。通过算法改进，算法有效的减少了消息转发次数，提高了路由效率。

《改进的chord加入算法》[文献6]在chordfingerpns加入算法的基础上，提出改进的chord加入算法：spjoin算法。该算法通过使用加入节点的后继结点和后继结点的前驱节点的信息，减少加入节点时构造finger表需要查询的跳数，已达到减少加入算法总开销的效果。

《一种基于邻居路由表的Chord改进算法》[文献7]提出nrtochord算法，该算法中，每个节点不仅要维护一个本地的指针表，还要维护一张感知表，该表是节点通过信息互换机制，感知后继结点的指针表得来的。加入节点时，新加入节点通过远程过程调用其他节点的更新函数，更新其他节点的指针表，并从后继结点获取关键词标示符。该算法要求每个节点的后继节点信息都要有即时性。即保证后继结点的真实、可靠性。

3 现有chord改进算法的分析研究

现有chord改进算法从不同角度对经典chord算法进行改进。以实现chord算法在效率方面、信息维护方面更进一步。通过对现有chor改进算法进行比对分析，该文将现有chord算法进行如下分类：

1）类1：通过对维护信息的改进，提高chord算法在节点加入、退出方面的效率。

P2P网络的动态性，导致了P2P网络节点的在线时间的不固定性和节点加入的即时性。这种情况要求算法要尽可能的将新加入节点的信息加入到相关节点的finger table中去，将已经离线节点的信息及时告知相关节点。这两种操作都会引起chord算法效率下降，特别是大规模P2P网络，这种情况更为严重。基于此，该分类以对维护信息的调整为契机，期望在节点加入、退出时，尽可能减少相应成本。该分类的文档有：《基于DHT的Chord路由算法的研究与改进》、《一种基于邻居路由表的Chord改进算法》和《改进的chord加入算法》。

2）类2：通过对维护信息的改进，提高chord算法在资源搜索方面的效率。

P2P网络的规模具有可扩展性，其节点众多，信息资源更是数不胜数。如何让P2P网络中的资源有序化，让算法减少跳数。是该种分类的改进思路。比如，《一种改进的CHORD搜索算法》提出在节点原有finger table不变的基础上，每个节点再增加两张表：最近访问节点表和邻居节点表。资源搜索时，算法先从最近访问节点表和邻居节点表中进行搜索，搜索不到时，节点再进行资源搜索消息转发。

该分类的文档有：《一种改进的CHORD搜索算法》、《P2P网络中Chord搜索算法的改进研究》、《基于多环的Chord改进算法》

3）类3：通过网络模型的改进，提高消息转发性能，减少查询跳数，进而提高算法效率。

任何一个算法都以一定的网络模型为基础，网络模型的优化程度，直接影响到算法的效率。尽管经典chord算法的网络模型具有简便和易于实现两种特性。但是，该算法的模型仍有可进一步优化的空间。于是，该分类从此下手，减少消息拒绝转发次数，提高消转发有效转发次数。减少查询跳数。以达到提高算法效率的目的。

该分类的文档有：《一种改进的Chord网络模型》、《G-Chord：一种基于Chord的路由改进算法》、《DM-Chord：基于Chord的路由改进算法》、《动态多路由Chord路由算法的研究与实现》、《基于Chord的结构化P2P路由改进算法》

4 结束语

Chord算法是P2P网络研究的一个核心问题。各种改进方法层出不穷。由于的滞后性、所掌握资料的局部性和研究人员的个人原因（比如，研究方法），chord算法改进现状分类有一定的局限性。研究人员希望抛砖引玉，与大家交流彼此的认识。同时，研究人员也希望通过该文章，为以后的chord算法改进工作明确方向添一份力。

参考文献：

[1] 张铁强，舒小润.基于DHT的Chord路由算法的研究与改进[J].电脑知识与技术，2009（29）：8153-8154.

[2] 李士宁，夏贻勇，倪红波，等.一种改进的CHORD搜索算法[J].计算机工程与应用，2008（22）：139-142.

[3] 曹磊，张玉梅，吴晓军，等.P2P网络中Chord搜索算法的改进研究[J].计算机应用研究，2014.

[4] 李建军，熊选东，谭晓贞.基于多环的Chord改进算法[J].计算机工程，2010（2）：116-118.

[5] 邓杰文.一种改进的Chord网络模型[J].计算机应用与软件，2010（2）：247-248，260.

[6] 任小金，古志民.改进的Chord加入算法[J].计算机工程，2007（17）：123-124，130.

[7] 戴彬，王芙蓉，刘见.一种基于邻居路由表的Chord改进算法[J].华中科技大学学报：自然科学版，2009（2）：49-52.

[8] 成培，胡峰松，粟智.基于Chord的结构化P2P路由改进算法[J].计算机工程与设计，2009（1）：63-65.

[9] 郝黎明，陆松年，杨树堂等.DM-Chord：基于Chord的路由改进算法[J].计算机工程，2009（1）：4-6.

[10] 何可佳.动态多路由Chord路由算法的研究与实现[J].微计算机信息，2009（30）：192-193，201.

[11] 陈刚，吴国新，杨望.G-Chord：一种基于Chord的路由改进算法[J].东南大学学报：自然科学版，2007（1）：9-12.