提出用分布式哈希表(DHT)为每台云服务器产生一个唯一的节点编号, 该编号作为网络拓扑结构、检索信息存储和信息查询共同的标志符, 从而形成一个适合分布式计算的结构化P2P覆盖网。设计了新的拓扑和路由协议来解决云资源的常数跳定位问题。仿真实验表明, 经典的P2P算法平均查找跳数与网络规模成正相关, 无法依据云计算的实际需要人为地控制查找跳数; 该算法的平均查找跳数与网络规模无关, 随着网络规模的增大而趋向于设定值, 可以解决云资源的常数跳定位问题。
572 计算机应用研究 第30卷 m=2×L()c-1」-1 parent i-1 根据式(2)可知路由表人小满足云对等网络应用的要求 scuryhit=sen[i] * i-sun[i+1] 2.4路由算法 超节点路山表中应该包括所在组全部实节点和虚节点的 图3大小为5的组分裂示例 路由信息。路由信息包括节点编号、IP地址、提供服务的端口 号等。若超节点不在顶层组中,路由表中还应该有路由到顶层 由空网络开始逐一加入云节点便可以生成一个完整的云 超节点的路由信息。当网络规模非常大时,每个分组中可以由对等网络。 多个超节点用以负载均衡。 2.6节点的退出 节点定位的具体流程如图2所示。 假设需要在云对等网络中删除一个编号为K的节点,首 点接收到查询请求,发顶层超节点 先查找节点,然后进行删除操作。任一编号为K的前趋(后 比较本节点与查询节点编号一 继)必是K的左子组(右子组)中最右(左)下的节点中最后 (最前)一个节点。 Hiskey==k +不点与请终理立在模 名被堋的编号为k的节点不在最底层,则用k的前趋(或 与该组中所苄点比较 是 后继)k′取代k,然后从了组中删去K′。从最底层组*x川始 s haskey==k 删去某编号为K节点的三种情形为 转发到两个节点(其中一个有点的 nodeld大于 a)若 x > keynun≥M2-1,则只需删去K即可使删除操 key,而另外一个小于它)之间的虚拟节点 作结束。 图2定位节点流程 b)若x→ keyne=M/2-1,该组中的节点个数已是最小 任意节点在接到查洵请求时,都将该查询请求转发给顶层值,刪除K及其右虚拟节点后会破坏拓扑定义2。若米x的左 组中的超节点。超节点在接收到请求时,判断查询节点的节点(或右)邻兄弟组*y中的节点数目大于M/2-1,则将*y中 编号与自己的编号,若相同,则查找成功;若不同,则与该组中的最大(或最小)节点上移至双亲组*Pamt中,而将*prm中 所有节点进行比较。假如在比较时发现有节点编号与之相同,相应的节点下移至*x中。显然这种移动使得双亲中节点数目 则把该节点信息发送给资源请求节点。如果没有发现相同编不变;*y被移出一个节点,故其kemm减1,因它原大于M 号节点,则请求转发到两个实节点(其中一个节点的编号人于 1,故减少1个节点后 keynum仍大于等于M/2-1;而*x中 查询节点的编号,而另外一个小于它)之间的虚拟节点 已移入一个节点,故删去K后*x中仍有M2-1个节点。涉及 用图1描述节点S3到节点Sn的路由。S在接收到查找移动节点的三个组均满足拓扑定义2。请读者验证,上述操作后 Sn3节点的请求后,把此请求转发至网络顶层组的超节点S2;仍满足拓扑定义1。移动完成后,删除过程亦结束。 而后S20查询本分组的路由表后,再把请求转发给子分组的超 c)若*x及其相邻的左右组(也可能只有一个兄弟)中的 节点S35∈最后S3把请求转发至目标节点S23。 节点数目均为最小值,则上述的移动操作就不奏效,此时须*x 2.5节点的加入 和左或右组合并。不妨设*x有有邻组*y(对左邻兄弟的讨 假设需要在云对等网络中插入一个编号为k的节点,首论与此类似),在*x中删去K及其石子组后,将双亲组 先在网络中查找k,若找到则直接返回(假设不处坦相同编号 * parent中介于*x和*y之间的节点K作为中间节点,将*x 和*y中的节点一起合并为一个新的组来取代*x和米y。因 节点的插入);否则查找換作失败于最底层某分组上,然后为x和*y原各有M2-1个关键字,从双亲中移入的K抵 将K插入该分组中。若该分组原来是非满(网络中原有的节 点总数小于M-1)的,则插入K后并未违反拓扑模型的定义, 消了从*x中删除的K,故新节点中恰有2「M/2-2(≤M 故插入K后即完成了插入操作;若该分组原为满,则K插入后 1)个节点,没有破坏拓扑定义2。但由于K从双亲中移到新组 违反拓扑模型定义2,故须调整局部网络使其维持拓扑模型定 后,相当于从* parent巾删去了K,若 parent→+ keynum原大于 义不变 M2-1,则删除操作到此结束;否则,同样要通过移动* parent 调整操作。将违反定义2的分组以中间位置上的节点 的左右组中的节点或将* parent与其左右组合并的方法来维 N[M2]为划分点,该分组(不妨设为* current)为(V,N1 护拓扑定义2。最坏情况下,合并操作会向上传播至顶层, V1,…,N-1,Vw),N表示M[讨],V表示vi],将“分裂”为两顶层只有一个节点时,合并操作将会使顶层组及其两个子组合 个节点:(V,N1,V1,…,NM2-1,V2=1),该分组仍是* current 并成一个新的组,从而使整个网络减少一层 (V,Nw+…,NYv-,Vx),该分组是新产的分组*new3i仿真实验 将中间节点N2和新分组的*mew一起插入到* currenL对应 的上一层分组中。 一般情况下,用平均查找跳数来量查询性能。木文算法 其中i表示下标,当NM2和新局部网络超节点的虚拟节点 的实验是在Liux环境下,使用Java编写模拟程序来评估。为 起插已满的上层分组时,对应的上层分组也要做分裂体现本文算法的优越性,选择传统结构化对等网络具有代表性 操作。最坏的情况是,各层的分组都是满的,此时,插入过程中的经典算法(hmd进行对比。Chm算法实验是在lin境 的分裂操作一直向上传播到顶层。当顶层组分裂时,因为没有下,使用P2P仿真具eSm进行仿真实验。 上一层,故需建立一个新的顶层组,此时网络层数加1。图331实验1 为调整操作的一个示例。 第一次实验假设在路由表大小可维护的前提下,云对等网 第2期 李璞,等:一种基于对等网绉的云资源定位算法 573 络要求査找跳数不大于5,依次模拟10000、15000-65000个节之后,提出用分布式散列表来标忐云资源并设计一种新型拓扑 点的云对等网络,根据公式计算得到分组人小。 来解决云资源的常数跳定位,利用该拓扑设计基于超节点的路 根据分组大小生成网络,由生成的网络进行模拟实验得到由算法,在路由表可维护的前提下选择查找跳数的极限。最后 节点的平均査找跳数。在模拟实验中,随杋选择节点对随机产仿真实验表明,该算法的路由表维护开销远远小于其他基于超 生的节点编号P进行査投,反复进行8次,最终求得所有节点节点的P2P算法,且能满足云计算大规模应用的需要,其查找 的平均查找长度,反复进行10次取平均值。 跳数符合云资源的常数跳定位的需求。 第二次实验假设在路山表大小可维护的前提下,云对等网参考文献 络要求查找跳效不大于6,其他条件及实验次效同第一次实1. STOICA, MORRIS R, KARGER L,at. Chord: a scalable pccr-to 验。两次实验结果数据如表2所示。 peer lookup service for Inlernel applicalions [J.IEEE/ACM Trans 表2实验1仿真实验结果 on Networking,2003,11(1):17-32. 第一次实张 第二次实验 刈络规模 2. ROWSTRON A, DRUSCIIEL P Pastry: scalable, distributed object lo 分组大小平均查找跳数分组大小平为查找跳数 cation and routing for large scale peer-to-peer systems[ C]//IFIP/ 10000 5.61 AGM International Conference on Distributed Systems. Berlin: Spring 15000 5.66 er-Verlag,2001:329-350 25000 21 4.73 5.71 [3 RATNASAMY S, FRANCIS P, HANDLEY M, et al. A scalable con 5.75 tent-addressable metwork[J]. ACM SIGCOMM Computer Com munication Review, 2001, 31(4): 161-172 40000 5.81 [4 MALKHI D, NAOR M, RATAJCZAK D. Viceroy: a scalable and d 5.84 50000 24 5.86 namic emulation of the butterfly[ C]//Proc of the 21 st Annual Sympo- 55000 15 5.88 sium on Principles of Distributed Computing. New York: ACM Press 5.90 4.93 5.9 [5 KLEIS M, I UA F K, ZHOU Xiall-miny. Hierarchic al peer-Iu-peer nel- 3.2实验2 works using lightweight super peer topologies C]//Proc of the 10th 在与实验1相同网络规模和相冋实验环境下使用 PersIl Symposium on Computers and Communications. Washington DC: IEEE Cornpuler So:ielv, 2005: 143-148 仿真工具对 Chord算法进行两次仿真实验,实验结果数据如表 [6 CUPTA 1, BIRMAN K, LNGA P, et al. Kelips: building an efficient 3所小。 and stable p2P DIIT through increased memory and background over 表3实验2仿真实验结果 head[ C]//Proc of the 2nd Intemational Workshop on Peer-to-Peer 第一次实验 第二次实验 网络规模 Systcm. Berlin Springer-Vcrlag, 2003: 160-169 平灼查找跳数 平均登找跳数 0000 [7] GUPTA A, LISKOV B, RODRIGUSE R One-hop lookups for peer-to peer overlays[ C//Proc of the 1 st Symposium on Networked Syster Design and Implementation. New York: ACM Press, 2004: 113-126 7.38 [8」王必睛,贺鹏.H- Chord:基于层次划分的 Chord路白模型及算法 实现「J.计算机工栏与应用,2007,43(36):41-143 7.67 7.68 40000 7.78 7.7 [9』段世惠,王劲林,基于有限范围组播的〔 hord路由算法[J].计算 7.87 机应用,2009,29(2):514-517 nd look -ellie ork[c//Pree of the 18th In al Parallel and distributed Pl 65000 8.2 Washington DC: IEEE Computer Society, 2004: 1-10 3.3实验结论 [11] XU Ke, SONG Mei-na, ZHANG Xiao-qi, et al. A cloud computing 随着网络规模的増大,实验1中竻一次实验的平均査找跳 P[C//Proe of IEEE Into 数趋向于极限5,第二次实验最终趋向于极限6,而对于传统的 on IT in Medicine and Education. Washington dC IEEE Computer Choru算法,在两次实验中在相同网络规模下的平均查找跳数 Society,2009:427-432 并没有明显变化。 12] ZHAO Peng, HUANG Ting-lci, LIU Cai-xia, et al. Rcscarch of P2P chitecture based on cloud [C//Proc of International 从以上的两个实验结果对比可以得出,传统对等网络的平 Conference on Intelligent Computing and Integrated Systems. Wash 均査找跳数与网络规模直接相关,无法依据云环境的实际需要 ngton DC: IEEE Computer Society, 2010: 652-655 人为地控制查找跳效。本文算法的平均查找跳数与网络规模[13] SOTIRIADIS S,BSsN, ANTONOPOULOS N. Using self-led criti 无关,随着网络规模的増人而趋向于设定值。 cal friend topology based on P2P chord algorithm for node localization within cloud communities[C //Proc of International Conference on 4结束语 Intelligent Computing and Integrated Systems. Washington DC: IEEE Computer society 2011: 490-495 本文在分析了使用一个中央节点来收集和处理所有节点[14] HUANG Li-can. Semantic P2P networ: are architecture of cloud 的实时信息无法满足云计算大规模应用的需要后,提出用结构 computing[ c]// Proc of the 2nd International Conference on Networ 化对等网络来建立分布式的云资源信息存储及索引系统。在 king and Distributed Computing. Washington DC IEEE Computer So- 对传统对等网络路由算法和基于超节点路由算法优缺点比较 ciety,2011:336-339