云计算中基于Chord算法的研究与改进

葛君伟，王燕峰，方义秋

（重庆邮电大学 计算机科学与技术学院，重庆400065）

0 引 言

“云计算”作为一种新兴的分布式计算模式，目前正受到人们的普遍关注。但是由于其相关技术还不成熟，人们对于云安全的种种焦虑以及不想 “云”被少数巨头控制等因素成为云计算发展的瓶颈。因此，古老的P2P技术在这样的新技术阶段就显现了它独特的优势，可以为云计算的发展显现出一份新的活力。

云计算和P2P技术应用的有效结合是未来发展的趋势，而相应网络的资源搜索是其研究的核心问题［1］。

目前研究的P2P网络主要可以分为三类：①集中式的P2P网络，例如Napster；②非结构化P2P网络，例如Gnutella［2］。这两种方案在设计初期并没有考虑运行在大规模网络环境下，可扩展性差；③结构化P2P网络，典型的算法有Chord，CAN，Pastry和Tapestry，它的优点是具有良好的可扩展性、鲁棒性以及查找的准确性，相比①、②两种网络结构，结构化的P2P网络更适用于云计算。

在结构化P2P网络资源搜索算法中，Chord算法是一种以去中心化的方式实现分布式计算应用中数据项查询定位，该算法正符合本文在云计算中引进P2P网络技术的初衷，因此也就成为基于云计算的P2P资源搜索算法的首选。然而Chord算法没有考虑到节点异构性和路由表冗余的问题，而这些问题大都和网络的拓扑结构以及路由表的结构密切相关［3］，因此，为了有效的提高资源搜索效率，本文提出一个有效的网络拓扑模型，并改进路由表结构。

1 Chord

1.1 Chord的构造与工作原理

Chord是由MIT实验室等人在2001年提出的一种结构化的P2P模型，它主要解决了根据查询消息的内容定位目标资源所在的具体位置这个问题。

在Chord环中的每个节点有一个指向前驱结点指针，指向后继结点的指针以及一张路由表，在节点n的路由表中，它的第j（1≤j≤m）项保存Chord环上顺时针距当前节点距离为2j－1的第一个节点，用finger［j］.start＝n＋2j－1（mod2m，1≤j≤m）来表示［4］。

图1给出了N8的finger表和查找k为53的过程，以N8为例，它的finger表的第一项后继结点是successor（n＋20）＝N14，第二项则是successor（n＋21）＝N14，依此类推得出直到第六项。对于Chord环上的任意节点n，查找数据对象k时，首先检查k是否存在于自身，如果是，则直接回应查找节点；否则，要检查k是否落在n和successor（n）之间，如果是，则把它的后继节点返回给查找节点；否则，节点要按照finger表来进行路由，从finger表最后一项向前比较，如果finger表中第j项的后继节点落在n和k之间，则把查找请求转发给指针表第j项的后继结点，通过递归这个过程，最终定位到k的后继节点［5］。

图1 Chord算法路由

1.2 Chord算法的不足

关于Chord算法，它也存在一些不足之处，例如：它忽略了节点的异构性和路由表冗余过大等问题，当网络规模较大时，这些问题将严重制约着网络中资源搜索的性能。

（1）节点异构方面

对于Chord系统，目前大多数研究都认为每个节点都是完全平等的，没有考虑到网络中各个节点之间的异构性，而实际P2P网络中的各个节点都存在着差异，如果忽略这些差异，Chord系统在具体的使用中将存在许多困难［6］。

（2）路由表冗余方面

从图1的Chord环可以看出，标识符空间为26＝64，上线节点的个数为10，以节点N8为开始，2i为跨度来寻找路由表中的后继结点，分别以20、21、22为跨度，找到的后继节点都是N14，也就是有接近一半的路由信息是冗余信息。

以上例子是以m＝6的情况来做的分析，一般情况下m取值为128，形成2128的环形空间，假定网络中有节点264个节点 （实际中节点数远比这要少），采用SHA－1来为节点分配关键字，可以近似的认为节点在环上是均匀分布的，则每两个节点之间的间隔是2128／264＝264，每一个节点的路由表项有m＝128项路由信息。由于一个节点的路由表相邻的两个指针表项标识符 （n＋2i－1mod2m）是以2的倍数递增的，所以大概也有64／128＝50%的信息是冗余的，这些一则造成存储空间的浪费，另则造成路由信息不能大范围的对Chord环进行覆盖，从而影响了路由的查询效率［7］。

2 设计与分析

2.1 模型构造

我们从宏观的角度来看待云计算网络，由于云计算网络是由很多个云服务器连在一起构成的，我们把一个云服务器当做网络中的一个节点，称为云节点，作为构成网络拓扑结构的基本元素。云节点在处理数据的能力、存储空间、上线时间以及带宽等方面存在着差异性［8］。

由于原始的Chord算法没有考虑到节点异构性的问题，单一的引用Chord并不适用，所以必须在此基础上进行改进。

具体的思想是：首先对网络中各个云节点的IP地址进行研究，把具有相同网络号的云节点归为一组，构成Chord从环。然后在每一个组中，对各个云节点的性能进行评估比较，根据其评估比较的结果，选择性能最好的云节点作为超级云节点，和其他组中的超级云节点按照Chord算法组成Chord主环［9］；选择性能仅次于超级云节点的节点作为后备云节点［10］，在本组超级云节点失效或者离开网络时，接替其工作，充当新的超级云节点。

为了后面便于描述，我们在此定义该建立的模型为MC－Chord，具体的模型结构如图2所示。

2.2 路由表的设计

图2 MC－Chord模型

在本模型中，首先超级云节点是该所属的Chord从环的一份子，所以需要一个从环finger表来表示在该从环中各个云节点之间的关系，同时，超级云节点也是Chord主环的一部分，所以还需要一个主环finger表来表示主环上各个超级云节点之间的关系。对于普通云节点来说，只需要一个从环finger来表示所在从环上各个云节点之间的关系。考虑到后备云节点的特殊性，除了要有一个表示从环云节点之间关系的从环finger表之外，还必须有一个和本组超级云节点完全一样的主环finger表。

对于以上每一个finger表，为了提高其路由效率，本文在MC－Chord的基础上，对节点的finger表计算公式进行修改，修改后的模型称为 MFC－Chord。首先对i进行分步考虑，并向公式引进一个参数d，d表示当前云节点和后继云节点之间的距离。由于一致性散列函数能够使所有的物理节点大致均匀的分布在Chord环上，所以任意云节点和它的后继云节点的距离大致都相等。

改进的计算公式如下

据统计分析，在云节点的原始finger表构造公式中，云节点finger表在 ［1，］范围内的指针项的后继指针指向都是重复的，因此通过式 （1）中的第一项表达式，消除了finger表的重复部分，只保留了一项；当i在 （，m］的范围内时，finger表项是跟原始的Chord的finger表算法一致。

以图1所示的Chord环为例，表1是以云节点的原始finger表计算公式得出的N1的finger表结构。表2则是以式 （1）计算出的N1的finger表结构，其中路由finger表公式中的参数d＝6。对比表1和表2可知，改进后N1的finger表没有冗余信息。

考虑到式 （1）得出的finger表只覆盖了半个Chord环上的云节点，为了使finger表能够大范围的覆盖Chord环，对这公式再进行修改，得到的公式为

由式 （5）得出N1的finger表结构如表3所示。

表1 原Chord的N1的finger表

表2 式 （1）得出的N1的finger表

表3 式 （2）得出的N1的finger表

对比表2和表3，式 （2）计算出的N1的finger表的覆盖范围更为广泛，而且没有出现新的冗余信息。

由于原始的finger表计算公式得出的云节点finger表存在着冗余信息，利用式 （1）消除了相应的冗余信息，但finger表的长度也随之缩短了，从而使得finger表空间未能被充分利用，由表2可以看出；式 （2）是在式 （1）的基础上进行改进，改进的效果是使得finger表的覆盖范围得到了一定程度的扩展，但finger表的空间利用率并没有得到提高，由表3可以看出。基于此，需要在式 （2）基础上再作进一步改进。

据统计分析，由式 （2）得出的finger表覆盖范围约为3／4个Chord环，则还有1／4个Chord环还没有覆盖，因此消除冗余信息之后，采取从 （2m－2m－2，2m）的范围中选取云节点添加到路由表尾部。为了保证路由表的空间能够被充分利用，选取云节点的数目就等于删除的冗余信息数；假设删除的冗余信息数为N，为了能够保证选取的云节点分布均匀，且保证选取的最后一个云节点不为起始云节点，则把 （2m－2m－2，2m－d）这个范围平均分成N份，然后从每份中选取一个云节点添加到finger表中。得到的公式如下

假设Chord环上的云节点都是均匀分布的，一般情况下，1／4个Chord环所覆盖的云节点数远大于删除的冗余信息数，所以在 （2m－2m－2，2m－d）范围内被平均分成N份后，每一份范围中所包含的云节点数必定不小于1，因此在每一份范围中选取云节点添加到finger尾部后，finger表并不会出现新的冗余信息。

由式 （3）得出N1的finger表结构如表4所示。

表4 式 （3）得出的N1的finger表

对比表3和表4，式 （3）得出的结果一方面使得云节点的finger表覆盖范围又进一步扩展了，另一方面解决了finger表空间未能充分利用的问题，并且没有出现新的冗余信息，从而提高资源查找的效率。

2.3 资源定位过程的描述

首先在从环内进行查找，如能查找到所需资源，则查找结束；否则，再进行环间查找，直到找到相应资源为止，主要步骤如下：

（1）云节点发起查询，首先在本云节点的资源列表查询，如果找到，直接返回；否则，转入 （2）。

（2）在本云节点所属的Chord从环上按照路由策略进行查找，如果能找到所需资源存放的目标云节点，则返回查询结果，否则转入 （3）。

（3）判断本云节点是否为所属从环的超级云节点，若是，则转为 （5）；否则转为 （4）。

（4）本云节点将查询请求发至所属从环的超级云节点。

（5）超级云节点在Chord主环上按照路由查找策略进行查找目标云节点所属从环的超级云节点，如果成功，则转下一步；否则，查询失败。

（6）目标云节点所属从环的超级云节点按照路由查找策略在所属的从环进行查找目标云节点，如果能找到，则查询成功，返回查询结果；否则，查询失败。

3 仿 真

本次实验主要对Chord、MC－Chord和 MFC－Chord 3种模型在相同的环境下进行仿真，实验的环境如下：

（1）操作系统：windows xp

（2）机器配置：CPU 2.2GHZ，2.0G 内存

（3）实验工具：Eclipse （JDK1.5）

（4）仿真模拟器：Peersim

Peersim仿真软件是一个模拟P2POverlay网络的通用网络模拟器，并且支持结构化和非结构化两种网络模拟，采用的是JAVA语言进行开发，是BISON项目的一部分，目前主要有两种模拟方式：Cycle－Base和Event－Driven。

对于平均查询跳数实验，本文设置1000，2000，4000，6000，8000，10000个节点，每个节点上有10个文件，分别对3种模型进行30次实验，得到每种模型的平均查询跳数，并进行对比，结果如图3所示。

图3 平均查询跳数比较

由图3可以看出，MFC－Chord与Chord、MC－Chord相比，平均路由跳数有所减少，并且随着节点数的增加，MFC－Chord曲线较Chord更为平缓，与MC－Chord曲线趋向于平行。因此MFC－Chord的查询效率优于Chord和MC－Chord。

对于平均查询延迟实验，本文设置500，1000，2000，4000，6000，8000，10000个节点，每个节点上有10个文件，分别对三种模型进行30次实验，得到的每种模型的平均延迟，并进行对比，结果如图4所示。

图4 平均查询延迟比较

由图4可以看出，MFC－Chord与Chord、MC－Chord相比，平均延迟有所减少，并且随着节点数的增加，MFCChord的平均延迟较Chord减少的更加明显，与MC－Chord相比，平均延迟的减少值趋向于一个常值，因此MFCChord的资源查找效率要优于Chord和MC－Chord。

4 结束语

本文在云计算中引进P2P技术，把云服务器充当P2P网络的网络节点，最终建立了MFC－Chord模型，此模型一方面通过构建超级云节点，解决在Chord系统中没有考虑的节点异构性的问题，另一方面通过对Chord路由表算法的改进，减少路由表的冗余信息，扩展了路由表的覆盖范围。实验证明本模型可以有效降低平均查询跳数和平均延迟，从而提高资源搜索的效率。

［1］Ozalp Babaoglu，Moreno Marzolla，Michele Tamburini，et al.Design and implementation of a P2Pcloud system ［C］／／Technical Report UBLCS，2011.

［2］JIA Zhaoqing，YOU Jinyuan.Research of unstructured P2P search algorithms and trust mechanism ［D］.Shanghai：Shanghai Jiaotong University，2008 （in Chinese）. ［贾兆庆，尤晋元.非结构化P2P中搜索算法及信任机制研究 ［D］.上海：上海交通大学，2008.］

［3］JIANG Shouxu，HAN Xixian，LI Jianzhong.Chord system based on super nodes ［J］.Mini－Micro Computer Systems，2007，28 （2）：266－270 （in Chinese）. ［姜守旭，韩希先，李建中.基于超节点的Chord系统 ［J］.小型微型计算机系统，2007，28 （2）：266－270.］

［4］Bartosz Biskupski，Jim Dowling，Jan Sacha.Properties and mechanisms of self－organizing MANET and P2Psystems ［J］.ACM Transactions on Autonomous and Adaptive Systems，2007，2 （1）：1－34.

［5］Stratis Ioannidis，Peter Marbach.On the design of hybrid peerto－peer system ［J］.ACM SIGMETRICS Performance Review，2008，36 （1）：157－158.

［6］Gao W L，Zhang G H，Wang M W，et al.An agricultural information sharing system based on P2Pnetwork technology ［J］.Intelligent Automation and Soft Computing，2010，16 （6）：945－951.

［7］Liu L，Xu J，Russell D，et al.Efficient and scalable search on scale－free P2Pnetworks ［J］.Peer－to－Peer Networking and Applications，2009，2 （2）：98－108.

［8］Zhang Yu，Cao Yuanda，Cheng Baodong.A layered P2Pnetwork topology based on physical network topology ［C］／／Dalian：4th International Conference on Wireless Communications，Networking and Mobile Computing，2008：1－4.

［9］Yu S，Yu J，Kamil K，et a1.DR－Chord－F an efficient doublering chord protocol［C］／／Ummuqi，China：Proc 7th 1EEE Int Conf Grid and Coop Comput，2007.

［10］Kim C S，Lee S，Han J I，et al.DChord：An efficient and robust peer to peer lookup system ［J］.Malaysian Journal of Computer Science，2010，23 （1）：37－48.