对等网中Chord协议仿真及其性能分析

李斐，郭晓

(中国传媒大学 信息工程学院，北京 100024)

对等网中Chord协议仿真及其性能分析

李斐，郭晓

(中国传媒大学 信息工程学院，北京 100024)

Chord协议就是一种结构化的全分布式拓扑结构，这种类型的对等网络实现了无中心服务器的目标，但相应的就需要解决有效定位和存储特定数据的问题，Chord协议给特定的数据一个键值，将其映射到和键值对应的节点之上，这样数据的存储位置就可以很容易通过这种对应关系进行查找。这种方式解决了无中心检索服务器的文件检索问题，但对覆盖网的结构有严格的要求，同时节点的加入与离开也会影响覆盖网的结构，因此需要仿真Chord协议的性能来评估其可用性。

对等网 ；Chord协议；OverSim

1 引言

对等网是分布式的结构，理想化的对等网旨在设计一种没有集中控制和层次化组织结构的系统，系统内的节点在功能上完全对等，并且能够实现匿名参与、冗余存储、节点选择、身份认证、资源检索、分层命名等功能。在对等网需要实现的如此多的功能当中，最为基础的核心功能是数据的有效存储和检索。对等网协议的设计也都是从这个基点出发的，并由此而诞生出了不同拓扑类型的对等网。在Chord协议中数据信息存储的存储操作诗针对每一个数据文件给定一个键值，将这个键值存储到某个节点上，该节点则负责和这个键值相关的一些操作。

这些操作的次数会随着节点数量的增加和节点的加入与离开而增加，从而引起网络资源的消耗，这将影响网络的可用性，因此需要对Chord协议进行测量与评估。

2 背景理论

2.1 对等网分类

在互联网的底层物理构架中，存在不同的网络拓扑结构，包括星形结构、总线型结构、环形结构等不同的类型[1]。不同拓扑的网络，有不同的特点。而对于对等网来说，也可以根据不同的拓扑来对其进行分类，并且对于缺乏中心服务器的对等网来说，如何在这种情况下来构建并维护一个高效的拓扑结构，以实现各种功能，是一个很大的挑战。在设计一个对等网系统时，需要构造一个不同于C/S机构的非集中的覆盖网络拓扑结构，在这个过程当中，需要解决的问题包括海量节点的命名组织方式、信息在节点间的传递方式、资源的索引和定位方式以及路由策略等。在对等网的发展过程中，出现了以下几种不同拓扑类型的对等网[2]：

(1)集中式拓扑(Centralized Topology，也称为中心化拓扑)

(2)全分布式非结构化拓扑(Decentralized Unstructured Topology)

(3)全分布式拓扑(Decentralized Structured Topology)

(4)混合式拓扑(Partially Decentralized Topology)

集中式拓扑的对等网是最早出现的如图1所示，对等网先驱Napster就是其中的典型。这一类网络的拓扑类似于星形拓扑结构，所有的节点与中央检索服务器链接，从而形成一个星形结构，当然这种结构不是物理网络上的星

形结构，而是在对等网覆盖网上形成的一个虚拟的星形结构。在网络运行的过程中，所有参与节点将需要的信息(名称、地址、资源等)向中央服务器注册，中央服务器则保存所有上传的文件索引信息和拥有此文件的节点的信息，当某个节点请求某个资源时，由中央服务器进行检索，并为该节点返回存储有该文件的用户信息，之后的文件传输过程则由资源请求者和资源拥有者来完成。这种结构的对等网结构简单，便于维护，具有很强的可管理性，在资源的检索方面也具有很高的效率，可以实现复杂查询。同时该结构的对等网也有一些缺点，首先是存在单点失效问题，中央服务器的故障会导致整个网络的瘫痪，其次是虽然中央服务器不负责资源的传输，但随着网络规模的扩大，海量节点的维护和资源的更新对于中央服务器的性能也是很大的挑战。

全分布式非机构化对等网中网络拓扑是随机的，各节点也不需要根据算法来存储资源存储信息。网络中的资源检索定位依靠泛洪(flooding)来完成，网络中没有中央服务器，不同文件的检索信息也不会固定的存储于某一节点，各节点维护自身的检索信息，如果某一节点需要某资源，向其全部邻居发送查询请求，如果邻居有该资源，则将符合请求的信息返回，并继续向他们的邻居发送这一查询请求，如果没有该资源，则直接向其邻居发送这一查询请求，直到查询消息中所包含的TTL(Time To Live)值减少为0。在这种拓扑结构的对等网中，节点可以随机的加入或离开网络，而网络也不需要因此维护拓扑结构而增加开销，提高了网络的健壮性，但这种拓扑结构最大的缺点就在于查询效率太低，查询消息的数目随着邻居转发次数指数级别的增长，虽然采用BFS、随机漫步等方式减少查询路径，但改善效果有限。初代的Gnutella和Freenet都是全分布式非结构化对等网的代表。

全分布式结构化拓扑的对等网使用一种称为分布式散列表的技术来构建拓扑、组织节点。分布式散列表(Distributed Hash Table，DHT)是一种分布式的计算方式，通过计算得到关键值(key)的集合，然后将其均匀的分布到分布式系统的所有节点上，这样能够使得检索信息高效的传递到系统中仅有的那一个存储了检索者需要key值的那个节点上。通过这一技术，对等网内的大量节点组织成一个巨大的散列表，散列表被分割成不连续的块，每个节点管理一部散列分区块，利用DHT技术，可以知道当前对等网中分布于各个节点的数据的概览，而独立于其实际位置。因此数据的位置依赖于当前的DHT状态而不固有地依赖数据本身。由于全分布式结构化对等网络摆脱了中央检索服务器，摆脱了单点失效等问题，提供了一种高效的检索机制，经典的全分布式结构化拓扑对等网包括CAN、Chord、Pastry、Tapestry等协议，目前包括BitTorrent和eMule都增加了对DHT技术的支持。

图2 混合式拓扑对等网

混合式的对等网结合了全分布对等网和集中式对等网的特点，形成一种混合的结构。在这种类型的对等网中，将参与到网络中的节点按照一定评价标准(计算能力、带宽、滞留时间等)区分为超级节点和普通节点。如图2所示，超级节点与其周围的普通节点形成一个自治域，域内采用集中目录式的结构，整个对等网中不同的域之间则通过分布式对等网的节点组织方式形成拓扑。在这种拓扑的对等网当中，被选为超级节点的节点负责维护节点的加入或离开以及域内资源检索信息的收集，如果超级节点离开网络，则由域中新的节点代替它的角色。KaZaa和Skype都是采用混合式拓扑的对等网应用。

2.2 Chord协议

Chord协议主要定义了如何查询键值的储存位置，节点加入和离开的机制，以及从节点失效中恢复等方面[3]。Chord协议使用稳定散列函数(consistent hashing)来为节点分配节点标识符Node ID和键值k。当一个节点加入到系统中时，将节点IP地址利用哈希函数产生一个节点标识符，数据的键值是将数据作为输入用哈希函数产生的。然后根据节点的标识符和数据的键值，每个节点存储一定数量的键值，由于稳定散列函数的特点，每个节点所保存的键值的数量大致是相同的，节点加入离开造成的在节点间移动的键值数也是比较少的。在拥有N个节点的Chord网络中，每个节点平均存储O(logN)个其他节点的路由信息。

节点的标识符和数据的键值都为m(m的大小必须使得不同文件得到相同键值的概率可忽略)位。节点按照标识符的顺序依次影射到一个称为Chord环的圆形地址空间上，键值k被影射到与键值相同的节点，如果没有值相同的节点，则分配给第一个后继节点(successor peer)，后继节点是指在圆形地址空间中从该值顺时针方向所遇到的第一个节点。当有新的节点加入到系统中时，为了保持键值和节点标识符的对应，被影射到该值后继节点的一些键值需要重新分配，小于该标识符的被分配给该节点后继节点的键值需要被分配给新加入节点，当有节点离开时，该节点所持有的键值则全部分配给该值的后继节点。因此有节点加入或者离开时，只对该节点的后继节点产生影响。在图3当中Chord环的m取值6，参与节点一共有10个，标识符10的后继节点是节点14，所以键值k(10)存储在14节点，如果标识符为28的节点加入到系统中来，节点32将不再存储键值k(24)，这个键值将由新的后继节点28来存储。

Chord环当中的节点需要知道怎样去联系其后继节点以完成资源的检索，资源的查询过程实际上就是键值k和节点标识符Node ID的匹配过程[4]。对于一个给定的键值，查询过程可以在Chord环中通过后继节点不断传递直到遇到存储了所需要键值信息的节点。图3中是一个检索的例子，节点8 需要查找键值54，节点8向后继节点发起查询请求，未完成查询请求时后继节点转发查询请求，最终查询完成找到键值54的存储节点，既节点56。查询由节点8和节点56之间的每一个节点转发完成的，查询的响应沿着查询路径返回。

图3 节点查询过程

图4 finger table生成过程

如果所有的查询都是由这种方式完成，显然会在系统内产生极大的查询消息，因此每个节点会保存一个称为finger table的路由表格，其生成过程如图4所示。首先，m是键值和节点标识符的位数，在节点n的路由表中第i条路由条目包括了该节点标识符的值n与2i-1的和所对应键值的存储节点s，即s=successor(n+2i-1)，1≤i≤m。finger table中的路由条目包含了目标节点Chord环的标识符和IP地址以及端口等信息。表1中显示了节点8的finger table，第一条路由条目指向了节点14，因为(8+20)mod 26=9，键值9的后继节点是节点14，因此第一条路由条目指向了节点14。同样的，最后一条路由条目指向了节点42，因为(8+25)mod 26=40，而标识符40的后继节点是42。在这种方式下，每个节点存储少量对等节点信息，并且对于相隔越近的后继节点，保存其路由信息的概率越大，当然，finger table所包含的路由信息不足以使节点直接确定任意一个键值的后继节点。例如节点8无法确定键值35的后继节点，因为键值35的后继节点不在节点8的finger table中。当节点8查询键值35时，可以查看其路由表，在路由表中选择和键值35最近的后继节点，既节点32来发起查询请求，不必从其最近的后继节点14来发起查询请求。

表1 节点8的finger table

在Chord当中，有新节点加入时，某些节点需要改变其后继节点的信息，为了保证系统的可用性，节点及时更新其后继节点信息是非常重要的，因此Chord协议会定期更新节点的后继节点信息和finger table路由表。由于Chord协议依赖于参与所有节点都知道其后继节点这一事实，因此当一个节点的后继节点失效时，存在着节点无法知道新后继节点的可能性，而且在这种情况下是无法去获取新后继节点的信息的。为了避免这种情况的发生，每个节点保持一个大小为r的后继节点表格，当中包含了r个后继节点的信息，当前后继节点失效时，从表格中依次选择下一个节点作为新的后继节点。假设每一个节点的失效概率是p，那么所有r个后继节点失效的概率是pr，r的增大会增加系统的鲁棒性。

3 仿真试验

3.1 仿真环境

仿真实验采用了OverSim仿真框架，OverSim是一个基于OMNeT++的覆盖网仿真框架，是事件驱动的仿真平台[5]，具有灵活可扩展的特性，最大可以支持100000个对等节点的仿真，OverSim可以仿真结构化和非结构化的对等网络，例如Chord[6]、Kademila、Pastry、Bamboo、Koorde、Gia等。 OverSim利用OMNeT++的图形接口来可视化覆盖网结构、底层网络的结构和数据包的传输，从而可以直观的调试[7]。OverSim提供了数据收集和统计模块，方便后续的数据处理与分析。

3.2 仿真参数设置

Chord协议可以以迭代或者递归的方式来实现，迭代方式的查询请求会根据节点的finger table中的信息来进行查询，每一次移动都会更接近目标节点，递归方式的查询节点将查询请求转发到下一个节点，直到查询请求到达键值的后继节点，在仿真过程中设置为迭代查询方式。

OverSim的底层拓扑设置为SimpleUnderlay，这是一种简化的平面网络结构，SimpleUnderlay为每个节点分配底层网络坐标，数据包的延迟基于源节点和目的节点的坐标距离计算。

在仿真过程中节点数目会逐渐增加，不断有新的节点加入到网络当中。系统的数据统计模块会收集每一次事件的相关信息，在仿真停止后以文本形式输出，后续的数据可视化可以用其他工具完成。仿真分为两次进行，第一次设置Chord环节点数为100个，当节点增加到100个时停止仿真，从第一仿真的结果中选取20次观察进行分析。第二次设置Chord环节点数为1000个，当节点数增加到1000个时停止仿真。从第二次仿真结果中选择25次观察进行分析。

3.3 仿真结果及分析

从图5、图6两次实验结果的统计图中可以看出节点加入到Chord环中的难度与Chord环的大小无关，在实验中，当Chord环的参与节点数达到50个以上时，等待参与到Chord中的节点一直维持在10个左右。这样的结果符合Chord网络的特点，即节点加入chord网络只引起一小部分节点所持有键值的变动，不会造成网络大规模地震荡。

图5 实验一中节点参与情况统计

图6 实验二中节点参与情况统计

事件数是指在网络当中包括节点加入，资源查询，节点之间交换资源等所有的节点间信息交换动作，这个数值在一定程度上可以反映当前网络的通信负担。从图7，图8两次实验结果的统计图中可以看到事件数目随着节点数目的增加而增加，事件数的增长慢于指数函数，但是稍快于线性函数，在实验所选择规模大小的网络中避免了非结构化全分布式对等网络内通信负担随节点数指数级增加的问题。Chord协议当中查询信息平均需要O(logN)来完成查询请求，节点加入与离开会产生O(log2N)条更改通知信息，因此随着节点数增加的事件数更多的是节点间交换数据的信息。

图7 实验一中事件数的增长情况

图8 实验二中事件数的增长情况

在实验过程中还存在诸多的不足，是下一步工作需要改进的方向。实验中各节点是完全平等的，即假设所有节点的计算能力和带宽是一致的，这显然不符合真实的网络环境，试验由于参数设置和仿真协议的原因，在试验中Chord环只有节点加入而没有节点退出，没有对这种更为动态的网络环境进行仿真，以上都是下一步的仿真实验可以考虑提高的地方。

4 总结

本文从对等网的分类出发，在介绍典型的对等网络之后对Chord协议进行了介绍和分析。Chord协议解决了对等网中数据存储节点选择的问题，并且由每个节点维护一个路由表来实现高效的覆盖网路由。为了验证Chord协议的有效性和可用性，通过OverSim平台进行了简单的仿真，实验结果表明Chord协议在节点加入方面和抑制通信消耗增长从而实现系统可扩展性方面能够达到Chord协议的设计目标，是一种高效可扩展的完全分布结构化对等网。

[1]谢希仁. 计算机网络[M]. 北京：电子工业出版社，2009.

[2]管磊. P2P技术揭秘[M]. 北京：清华大学出版社，2011.

[3]Ion Stoica，R Morris，David Liben-Nowell，etal. Chord：a scalable peer-to-peer lookup protocol for internet applications[J]. IEEE ACM Transactions on Networking，2003，11(1)：17-32.

[4]Lua E K，Crowcroft J，Pias M，et al. A Survey and comparison of peer-to-peer overlay netword schemes[J]. IEEE Communications Surveys & Tutorials，2005，7(2)：72-93.

[5]Baumgart I，Heep B，Krause S. OverSim：A Flexible Overlay Network Simulation Framework[C].IEEE Global Internet Symposium，2007：79-84.

[6]Furness J，Chowdhury F，Kolberg M. An Evaluation of EpiChord in OverSim[C].International Conference on Network Communication, 2014：3-19.

[7]Munoz Gea J P，Malgosa Sanahuja J，Manzanares Lopez P，et al. Simulation of a P2P Application Using OverSim[C].International Conference on Advances in Future Internet,IEEE，2009：53-60.

[8]Yi Zhong MA，Ding H Y，Yong Quan M，et al. Research and plan improvement of Chord algorithm in structured P2P network resource search[J]. Electronic Design Engineering，2010，(05)：14-18.

[9]Ding S，Zhao X. Analysis and improvement on Chord protocol for structured P2P[C].IEEE International Conference on Communication Software and Networks.，2011：214-218.

[10]张震，王晓明. 对等网中Chord资源查找算法研究[J]. 计算机工程与应用，2006，42(11)：147-152.

(责任编辑：王 谦)

SimulationandPerformanceAnalysisofChordProtocolinPeertoPeerNetworks

LI Fei，GUO Xiao

(Information Engineering School，Communication University of China，Beijing 100024，China)

The Chord is one of the fully distributed topology structured P2P network，this type of P2P network has no central server，but the protocol need to solve the problem of efficiently data storage and locate node. Chord protocol give a key to each file，the key/file pair stores at a node which map the key. And data can be easily searched by this correspondence. This method solves the file retrieval problem，but there are strict requirements on the structure of overlay network，and the nodes join and leave will also affect the structure of overlay network. It is necessary to simulate the performance of Chord protocol，assess its availability，and find the way to improve.

peer to peer networks；Chord protocol；OverSim

TP393.04

A

1673-4793(2017)05-0027-06

2017-05-12

李斐(1994-)，男(汉族)，山西长治人，中国传媒大学硕士研究生.E-mail：375401532@qq.com