基于Chord算法的研究与改进

摘要：由于Chord算法在选择路由时并未考虑结点间的物理拓扑关系，消息转发的路由跳数只是基于逻辑特性而跟物理位置无关，而提高系统的网络性能的关键则正是减少消息转发的跳数。本文根据小世界网络的启发，通过对Chord算法的研究，分析了结构化网络各种算法的优缺点，提出了一种基于Chord算法的优化和改进。

关键词：P2P网络；Chord算法；搜索

中图分类号：TP393.04 文献标识码：A文章编号：1007-9599(2011)07-0000-02

Research and Improvement of Chord Algorithm

Li Daitong

(Shenyang Pharmaceutical University Dean's Office,Sheyang110016,China)

Abstract:The Chord algorithm did not consider in the choice of routes between nodes when the physical topology,message routing hops forward characteristics is based on logic has nothing to do with the physical location,and improve network performance is the key to reduce the message is forwarded hop number.Based on small world network,inspired by Chord algorithm to analyze the structure of the network advantages and disadvantages of each algorithm,a method based on the optimization and improvement of Chord.

Keywords:P2P network;Chord Algorithm;Search

一、P2P覆盖网络介绍

P2P（Peer-to-Peer）一种不通过中央服务器而将一些独立的计算机资源组织起来，通过Internet运行于个人计算机上，以实现共享文件和资源的应用。

目前，Web网络的主要技术模式还是C/S结构的，如图1.1所示，位于中心位置的就是作为Server的服务器端。中心服务器接收互联网上其他PC的各种请求，并处理各种数据，提供各种服务。对于一台与服务器连接的PC机来说，这台PC机就是客户机，这种客户端（Client）和服务器（Server）组成的网络模式就是C/S模式。

P2P模式打破了传统的C/S模式：它使得一切网络成员享有自由、平等、互联的功能。强调Peer之间的“对等性”，即P2P系统中每个Peer都兼有服务器和客户端两种身份。图1.1和图1.2反映出从C/S结构到P2P结构的转变。

图1.1 C/S模式

Fig. 1.1 C/S mode

图1.2 P2P模式

Fig. 1.2 P2P mode

二、结构化P2P网络

目前，常用的结构化P2P网络都是采用分布式哈希表DHT（Distributed Hash Table），它是一种分布式存储方法。在不需要中央服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部门数据，从而实现整个DHT网络的寻址和存储。哈希函数指的是把不同长度的输入通过哈希算法，转换成固定长度的输出，这个输出就是通常所说的哈希值。更重要的性质是哈希函数是不可逆的，不可能通过哈希值来确定输入值。目前，流行的DHT算法有Chord、Can、Pastry等，本文将主要研究Chord算法及其改进。

三、Chord算法介绍

Chord算法是2001年由麻省理工学院提出的一种分布式查找算法，其核心思想就是在P2P网络中高效地定位存储特定资源的节点。在Chord算法中，给定一个对象的关键字key，Chord将关键字映射到相应的结点上，由这个结点来负责存储该对象的。通过使用散列函数将每个结点的信息进行散列运算得到一个唯一的结点标识符（Node ID），同时对每个资源的信息进行散列运算得到唯一的key值，而Chord中关键字key与结点的映射关系是将关键字key存储在结点标识符等于或者大于key值得第一个结点上。当需要查找资源时，采用同样的方法，先通过散列运算得到资源的key值，然后根据key与结点的映射关系，就可以快速定位到存储资源的结点。

四、Chord算法存在的问题

（一）结点间的物理链路

Chord算法将所有结点映射到一维空间，使用统一的结点标识符来查找关键字。结点标识符是根据该结点的IP地址或者端口通过Hash函数获得。因此，物理邻居结点之间的逻辑距离完全是随机的。也就是说Chord算法在构建网络时并没有考虑到结点之间实际的物理拓扑关系，这样可能会导致在实际网络中物理距离很近的2个结点通过散列函数映射在覆盖网络上却相距很远，从而导致较高的延迟并拥塞网络。

（二）结点的性能

由于Chord网络是根据Hash值来确定网络连接，没有考虑到结点的性能差异，对于P2P网络中所有的结点都赋予了同样的责任。导致高性能的结点没有发挥自身的能力，或者低性能结点成为了系统的瓶颈。

五、Chord算法的改进

根据以上Chord算法存在的问题，这里提出了一种分布式结构化的搜索算法，称为Schord算法，首先对现有的Chord搜索算法进行了扩充与改进，通过建立附加子环的网络模型改进，并在超级结点上增加路由表项，对查询信息进行最短路由，来减少查询信息在网络中的游荡，提高查询命中率和查询速度。

（一）Schord算法搜索原理

在SChord拓扑结构中，每个结点首先判断自身是一个普通结点还是超级结点。因为发起搜索的结点可能是外环的普通结点，也可能是内环的超级结点，根据结点不同，采用的搜索机制也不同。下面根据发起查询结点的不同，分别来讨论。

1.超级结点发起的搜索

在SChord网络结构中，如果是超级结点发起的查询，首先在超级结点自己的目录索引表进行查询，如果发现资源，则直接返回查询结束。如果未找到资源，该超级结点就把查询请求信息，沿着内环顺时针方向，发送到下一个超级结点。这个后续的超级结点也是对自己的目录索引表查询，如果发现资源则返回结果，查询结束。如果未发现则继续向下一个超级结点发送请求，直到内环所有的超级结点都遍历结束。如果仍未查到资源，发起查询的超级结点就把该请求发送的外环的普通结点上，并在外环以普通的Chord搜索算法进行查找，直到找到该资源或者返回空结果。

具体搜索步骤如下：

（1）判断该资源的是否在超级结点N上，如果发现资源转（6）搜索结束，返回该资源。如果不在，转（2）。

（2）由超级结点N把该请求发送到与之相连顺时针的物理路径最短的下一个超级结点N+1上。

（3）超级结点N+1搜索自己的目录索引表，如果发现资源则返回给超级结点N，转（6）。如果未发现，继续把搜索消息顺时针发送。直到遍历整个子环上所有的超级结点。

（4）如果发现资源则返回给超级结点N。如果未发现资源，则由超级结点把该请求发送至与之相连的外环普通结点上。

（5）在由普通结点组成的Chord外环，依照Chord算法进行搜索，如果发现资源，则把该资源返回给超级结点N。如果未发现，则把“未发现资源”的信息返回给超级结点N。

（6）搜索完毕。

2.普通结点发起的搜索

在SChord外环中，当一个普通结点n收到查询对某个资源的请求时，首先对这个资源名称进行散列运算，得到关键字标识符，由于结点都是维护了其前向结点和路由信息，所以首先判断key值是否落在n-1结点和n结点之间，如果是，则结点n就是该资源的后向结点，说明该资源就在结点n上，搜索结束。

如果key值未落到n-1结点和n结点之间，则结点n把查询请求发送到与之相连的内环上的超级结点由超级结点N进行搜索目录索引表，如果搜索到资源，则把资源返回给查询结点，否则按照顺时针方向发送到下一个超级结点，直到搜索到资源为止。如果在所有的超级结点都未搜索到资源，这里的执行方法和“超级结点发起的搜索”类似。直到搜索到资源为止。

具体搜索步骤如下：

（1）判断该资源的hash值是否在结点n-1到结点n上，如果发现资源转（6）搜索结束，返回该资源。如果不在，转（2）。

（2）把该请求发送到与之相连的超级结点上

（3）超级结点N搜索自己的目录索引表，如果发现资源则返回给请求结点，转（6）。如果未发现，把搜索消息发送到下一个物理路径最短的超级结点N+1。

（4）如果在超级结点N+1上，发现资源则返回给超级结点N，并有N返回给请求结点n。如果未发现资源，则继续转发该请求，直至遍历整个子环上的所有超级结点。

（5）如果在整个子环的超级结点上都未搜索到资源，则由超级结点N返回给请求结点n。

（6）搜索完毕。

（二）Schord算法仿真结果

采用P2Psim工具对Schord算法进行仿真评估，为了对比Schord算法和Chord算法在路由跳数和物理延迟方面的优劣，分别作了两类几组不同的测试。

第一类模拟结点个数设置为200、500、800、1100、1400和1700。该实验主要对两种算法在资源查找过程中，统计从一个结点到另一个结点路由跳数，并进行对比。由图5.2所示，改进算法Schord的路由跳数减少了30%，这样大大提升了查询速度。

结点数量 200 500 800 1100 1400 1700

Chord算法 7 8 10 12 12 13

Schord算法 5 5 6 6 7 8

图5.1路由跳数

第二类模拟实验基于不同随机种子发起的测试，共进行5组，每组测试设置3000个普通结点，以及600个超级结点。在仿真实验中，结点随机的加入和离开。由图5.2所示，平均延迟约减少20%。由此可见，Schord算法查询延迟因为物理邻居结点间的延迟减少而减少。

延迟 1 2 3 4 5

Chord算法 2.87 2.65 2.71 2.70 2.66

Schord算法 2.16 2.15 2.14 2.17 2.18

图5.2延迟统计

六、结语

在以上的仿真实验中，只是简单的选取了低延迟结点作为子环上的超级结点。还有些问题有待更深入的探讨和分析。

（一）该算法的安全问题

由于该算法为了提高搜索命中率和减少搜索时间，过分依赖于超级结点的表现，如果超级结点遭受到攻击，对于整个SChord系统影响都较大，与之相连的外环普通结点都会频繁更改自身路由表，这是一个重要的问题。

（二）结点的加入和离开

当结点出现“抖动”情况，则会频繁的加入和离开系统，整个P2P网络就会频繁的更新指针表信息，占用额外的网络流量。

P2P搜索算法是近年来研究的热点，各种新的算法和模型不断的涌现。但是，在查询效率和安全性上都还有很大的改善空间，如果要想P2P搜索技术超过现在的集中式搜索技术的Google、百度等搜索引擎，还需要付出更多的努力。

参考文献：

[1]Gerhard W.Peer-to-Peer Web Search[A].ncylopedia of Database Systems[C].ew York,SA,009,082-2085

[2]Han D,u Y.Keyword Search in Unstructured Peer-to-Peer Networks [A].andbook of Peer-to-Peer Networking[C] New York,SA,010,05-426

[3]Debora D,ristides G.ext Generation Search[A],Computer Communication and Networks[C].London,K,010.373-401

[4]张春红.P2P技术全面解析[M].京:人民邮电出版社,010.35-78