Chord算法的研究与改进

【 摘 要 】 Chord算法是结构化P2P系统资源定位算法中最受关注的算法之一。本文在Full-Chord算法的基础上，将指针表中相同项作为一项进行存储，减少了存储冗余并且能够存储整个系统的信息，并利用PeerSim类库仿真了存储冗余减少后的Chord算法。

【 关键词 】 Chord；P2P；Full-Chord；PeerSim

Research and Improvement of Chord Algorithm

Yang Yan-hong

（Kunshan Dengyun Technology Professional College JiangsuKunshan 215300）

【 Abstract 】 Chord algorithm that is the resource location algorithm of the structured P2P systems is concerned mostly.In this thesis， Full-Chord algorithm is improved by only storing the same information once time in the finger table. The improved algorithm can reduce storage and maintain information of the system.The class library of PeerSim is used to simulate the improved Chord algorithm and the Sec-Chord algorithm.

【 Keywords 】 chord；p2p；full-chord；peersim

1 引言

Chord 算法是基于DHT的结构化P2P网络资源定位算法。Chord的突出优点是：算法简单，系统扩展性好，文件查找过程的通信开销和系统维护的状态随着系统总节点数增加成指数关系。到目前为止，研究学者在Chord算法上已经做过很多研究工作，如参考文献[2]提出建立分层的Chord环，将带宽大、稳定性好的超级节点提升为管理层，将性能一般的节点作为普通层；参考文献[3]提出了Full-Chord算法，使节点维护的指针表存储的信息涉及到整个系统等。

2 基本Chord算法的分析

Chord资源定位算法分为几个部分：环的建立；路由表的存储；节点的加入、退出、失效及环的维护。

2.1 Chord环的建立

Chord算法运用Hash函数（Consistent Hashing） 将文件关键字分配给系统中的节点，Chord算法采用的Hash函数是SHA-1，该函数在第二章做过详细介绍。在Chord算法中，若节点ID和文件关键字是m bit的标识符（如不特别之处，后文中m与此相同），则系统的大小为2m，参与系统的节点个数小于等于2m。如图1所示。

2.2 Chord查找算法

Chord的简单查找算法是，系统中每个节点只维护其后继节点的ID和IP地址。进行查找时，查找消息通过后继节点指针在环上传递，直到查找消息中的关键字K落在某节点和其后继节点之间，查找结束。

如图2所示，节点N1发起查找k=8的关键字。N1的标识符大于8，N1不存储关键字8，便将查找消息传递给自己的后继节点N3，依次循环下去，直到关键字8落在N5和N10之间，按照环的建立过程，可知关键字8存储在节点10上，查找结束。……