基于CHORD环的DHT全分布式P2P网络结构分析

曹 建

(苏州工业职业技术学院 软件与服务外包学院，江苏 苏州 215104)

基于CHORD环的DHT全分布式P2P网络结构分析

曹 建

(苏州工业职业技术学院 软件与服务外包学院，江苏 苏州 215104)

通过对CHORD算法的详细研究和分析，结合DHT全分布式P2P网络的结构要求，给出了一种基于CHORD环的DHT全分布式P2P网络算法，并给出了基础算法的伪代码.

DHT；P2P；CHORD；网络协议

对等计算(Peer-to-Peer，简称P2P)技术作为一个新的网络技术在近几年得到迅速发展，并成为计算机界关注的热门话题之一，财富杂志更将P2P技术列为影响Internet未来的四项科技之一.目前的拓扑结构关系可以将P2P网络拓扑结构分为4种：中心化拓扑结构(centralized topology)，全分布式非结构化结构(decentralized unstructured topology)，半分布式结构(partially decentralized topology)，全分布式结构化结构(decentralized structured topology).而全分布式结构化结构，也称为DHT结构，除了能够自适应结点的动态加入/退出，而且有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力，同时由于其采用了确定的拓扑结构，DHT可以提供精确的发现功能，广泛应用于全分布式P2P网络架构设计.

1 CHORD算法分析

CHORD是一种基于DHT的分布式查询算法，两者之间的关系如图1所示，2001年由麻省理工学院提出.CHORD协议使用同一个HASH算法为每个结点以及资源分别分配一个m位的标识，所有标识符分布在一个大小为2m的CHORD环结构上，标识符范围为0到2m-1，每一个资源信息根据其Resource-ID被分配到第一个在标识符空间里Node-ID值大于等于该Resource-ID的结点上.这个结点被称为Resource-ID的后继结点，即successor(Resource-ID)，资源相关信息就保存在这个后继结点上.

1.1 CHORD逻辑结构构成

在CHORD算法中，所有结点根据其Node-ID大小，逻辑上形成首尾相连成一个环形结构，在一个最大容量结点数为2m的CHORD环结构内，每个结点需要存储和维护一个具有m个其他结点信息的表格，这些信息的集合被称为路由表(finger table，也称为查询表)，表格中的结点不是直接相邻的结点，它们的间距(ID间隔)将成2i的关系排列(i表示表中的数组下标).图2为一个m=6的CHORD环结构P2P网络示意图，图中结点ID和资源ID的标识范围为[0-63]，环中每个结点维护一个路由表，表中共m个表项.资源查询定位是按照顺时针方向跳跃式进行.

1.2 主要数据结构描述

在详细描述CHORD算法的定位和路由策略前，先定义CHORD算法所需要的几个重要数据结构：

1) 后继结点列表(successor node list)，所谓后继结点(successor)是指那些结点Node-ID值≥本结点Node-ID的结点(模运算)，其中最小的那个结点叫做直接后继结点.后继结点的主要作用在于形成CHORD环结构，保证CHORD算法的正确运行.由于P2P网络中的每一个结点都是完全独立的，结点的加入和退出完全不受P2P网络控制，为提高CHORD系统的正确性和可靠性，后继结点列表由结点后续连续的若干个结点信息组成.从可靠性角度，后继结点数目越多可靠性越高，但是后继结点数目的增加同时会增加网络数据流量，加重网络负担.

2) 前驱结点(predecessor node)，指那些Node-ID值＜当前结点Node-ID的结点(模运算)，其中最小的那个结点称为直接前驱结点.前驱结点的主要作用在于保持和维护CHORD环结构的稳定性.

3) 路由表(finger table)结构，主要用于提高结点和资源信息的查询路由的速度，所以被称为路由表.CHORD算法的所有查询操作均通过操作路由表实现，路由表中各项分别保存一个跳跃区间[(n+2i-1)mod 2m，(n+2i)mod 2m)，并保存该区间内起始ID编号后的第一个后继结点信息和前驱结点信息，实现了2指数级跳跃式路由查询.通过路由表操作，含有N个结点的网络，查询需要的跳数由O(N)减少到O(log2N).这样即使在大规模的P2P网络中(例如N＝100，000，000)，查询的跳数也仅为O(8). 表1为路由表的逻辑结构内容[1]，但在实际存储时，仅需要其中的start项、successor项、predecessor项.

表1 路由表逻辑结构内容

2 CHORD主要算法描述

CHORD算法的各项功能操作都直接或间接使用到路由表，在系统运行过程中，随着结点和用户的动态加入和退出，路由表也是动态变化的，为更好地表达查询表操作算法，现设定以下几个标识：[2]

2.1 查询算法

查询算法是根据已知资源ID值(Resource-ID)找出保存该资源信息的结点，是CHORD算法的一个主要功能.最简单的方法是从当前结点以顺时针方向逐个结点进行查找，但是这种查询效率较低，在最坏的情况下，对于一个N个结点的CHORD环，需要查询N次，算法复杂度O(N).[3]

CHORD查询算法利用路由表进行跳跃式查询，查询过程是一个反复的过程，使得查询结果越来越接近于目标结点，并在O(log2N)算法复杂度内找到目标结点.首先判断是否保存在自身结点，如果是，则直接返回自身结点；否则在路由表中查询.具体算法伪代码如下：对于图3的CHORD环结构中，假设在结点8上查找资源ID为40的资源信息，具体过程如下：1) 先在结点8上查找路由表，找到最近的匹配项为ID=32的结点.然后向结点32发送查找Resource-ID=40的资源信息的请求；

2) 结点32发现Resource-ID=40的资源信息没有保存在本机，查询自己的路由表，找到最接近的匹配项为ID=38的结点，返回ID=38的结点信息；

3) 重复1)、2)的过程，直到在结点42上找到Resource-ID=40的资源信息，因为结点42在目前的CHORD环结构中是40的直接后继，返回Resource-ID=40的资源信息给结点8，查询过程结束，查询示意图如图3所示.

在每一步查找中，距离目标结点的距离都被大约缩小了一半，因此对于一个含有N个结点的环，整个查找复杂度为O(log2N).

2.2 结点加入与退出算法

在动态P2P网络中，结点的加入和退出不受任何限制，而且结点的加入和退出都将局部破坏CHORD环结构，加入退出算法必须能够在这一动态过程中保持正确的查找效能.

结点的加入机制通过CHORD环结构中的前驱结点指针实现，新结点的加入，CHORD环结构必须完成3个内容：

1) 初始化加入结点的指针表和前驱结点信息.当一个结点申请加入CHORD环时，必须借助于一个已存在的环内结点进行引导，且结点加入后必须保证CHORD环结构的完整性和稳定性，根据算法，接入结点应该是加入结点的直接后继结点.结点首先根据既定算法生成Node-ID，然后向环内一个已存在结点发出加入申请，环内结点根据加入结点的Node-ID判断自己是否是正确的接入结点，如果是，则执行结点注册；如果不是，则查找正确的接入结点(查找过程与Resource-ID查找过程类似，只不过这里查找的是Node-ID，也是一个逐步靠近的过程，在O(log2N)事件复杂度内找到正确接入结点)，执行加入过程.申请加入结点根据返回消息判断是否申请成功，若申请成功，则将正确接入结点的前驱结点设为自己的前驱结点，将正确结点加上舍去正确接入结点最后一个结点信息的后继结点链设为加入结点的后继结点链(正确结点设为直接后继结点)，根据正确接入结点的路由表信息结合本地结点设置本地路由表；

2) 修改正确接入结点的前驱结点信息和路由表信息.新结点的加入局部破坏了CHORD环结构，需要修改相应指针恢复CHORD环结构.正确接入结点需修改其直接前驱结点为新加入结点，并需修改路由表信息，以反映新结点的加入，并在稳定性进程到来时将该信息发送出去；

3) 转发相应资源信息.新结点加入后，还必须将应该有新结点保存的资源信息从正确接入结点转存到新加入结点中.

结点的退出主要通过CHORD环结构中的后继结点指针实现，CHORD环结构仅需要将该结点内所有保存资源信息转存到其直接后继结点，直接后继结点修改其前驱结点指针，保证CHORD环结构的完整性.

3 CHORD算法优点分析

根据以上分析，基于CHORD算法的DHT-P2P网络具有如下优点：

1) 负载平衡，这一优点来自于一致性哈希，也就是一致性哈希中提到的平衡性.所有的结点以同等的概率分担系统负荷，从而可以避免某些结点负载过大的情况；

2) 分布性，CHORD是纯分布式系统，结点之间完全平等并完成同样的工作.这使得CHORD具有很高的鲁棒性，可以抵御DoS攻击；

3) 可扩展性，CHORD协议的开销随着系统规模(结点总数N)的增加而按照O(log2N)的比例增加.因此CHORD可以用于大规模的系统；

4) 可用性，CHORD协议要求结点根据网络的变化动态的更新查询表，因此能够及时恢复路由关系，使得查询可以可靠地进行；

5) 命名的灵活性，CHORD并未限制查询内容的结构，因此应用层可以灵活地将内容映射到键值空间而不受协议的限制.

4 结论

通过对CHORD环结构的基本分析，结合DHT-P2P网络特征，将CHORD环结构与DHT-P2P网络综合运用，在分析CHORD环结构功能的基础上，对P2P中网络资源查找和结点加入退出所涉及的相关概念进行了重新定义，并对算法过程进行了详细分析和阐述，最后对基于Chord环结构的DHT-P2P网络优点进行了简单的分析.

[1]BRYAN D，LOWEKAMP B，JENNINGS C. A P2P approach to SIP registration and resource location，draft-bryan-sipping-p2p-02[C]//Internet Engineering Task Force，College of William and Mary，Cisco Systems，San Diego：March 5，2006.

[2]JOHNSTON A，SINNREICh H. Draft-johnston-sipping-p2p-ipcom-02[C]//Internet Engineering Task Force，SIP，P2P，and Internet Communications，San Diego：March 5，2006

[3]STOICA I，MORRIS R，KARGER D，et al. A scalable Peer-to-Peer lookup service for internet applications[C].San Diego ：ACM SIGCOMM 2001，CA August 2001.

[4]SINGH K，SCHULZRINNE H. Peer-to-peer Internet telephony using SIP：technical report of CUCS-044-04[R]. New York： 2005.

Analysis the DHT-P2P Net Structure Based on CHORD

CAO Jian

(The Software and Service Outsourcing Section，Suzhou Institute of Industrial Technology，Suzhou 215104，China)

Through research and analysis the CHORD algorithm in detail，and combined with DHT distributed P2P network structure，the algorithm for DHT-P2P Net Structure which based on CHORD ring and the pseudo code are designed.

DHT；P2P；CHORD；network protocol

TP311

A

1008-5475(2012)03-0042-04

2012-04-20;

2012-05-29

上海市基础研究重点资助项目(08JC1409200)

曹 建(1979-)，男，江苏盐城人，工程师，硕士，主要从事P2P网络、多媒体网络、网络安全方向研究.

(责任编辑: 李 华)