优化型Kademlia的设计研究

ISSN 1009 3044E-mail: xic@cce.net.cnComputer Knowledge and Technology电脑知识与技术htp://ww.nzs.net.nVol.7, No.32, November 2011.Tel:+86- -551- 56909635690964优化型Kademlia的设计研究王震(辽东学院信息技术学院,辽宁丹东1800)0摘要:通过对DHT路由算法中的Kademlia技术的系统分析,提出了一种基于P2P覆盖网络的优化Kademlia路由算法的架构。针对于DHT的构造和路由方法的改进,从整体角度出发,提出了优化型Kademlia的路由算法,它的实现是建立在Kademlia核心路由的基础上。在设计中,分别在Planetim、路由层服务层、应用层等不同的网络环境中利用节点的异构性进行设计,采用新的技术对路由进行改进,以更好的实现路由层的负载均衢以及在很高的网络波动条件下提高DTH性能。关键词:DHT;Kademlia;路由算法;节点;P2P中图分类号:TP311文献标识码:A 文章编号:1009 3042011)32-7932-03The Design of Optimized KademliaWANG Zhen(The Information Technology Insticute, Liaodong Universiy, Dandong 118003, China)Abstract: By the Kademlia DHT routing algorithm technology systems analyis, This paper proposes an routing algorithm opimizationfnamework based on Kadenlia P2P overlay network .For improvement in the DHT structure and routing methods , fom the overll per-spective, This paper proposes opimized Kademlia rouing alorithm, is implemcnation is based on the Kademlia routing baced on the core.In the design, respectively, in PlanetSim, routing layer, servicc layer, pplication layer, using dfferent network nodes in heterogeneous envi-ronment of the design, the use of new technologies to improve the rouing. the routing layer to achieve better load balancing and fluctua-tions in conditions of high network performance to improve DTH.Key words: DHT; Kademli; rouing algorithm; node; P2PDHT(分布式哈希表)是- -种分布式存储方法,在不需要服务器的情况下.每个客户端负责-个小范围的路由,并负责存储- -小部分数据,从而实现整个DHT网络的寻址和存储。Kademlia 是DHT中的主流技术之- - ,在结构化P2P系统有着广泛的应用。DHT实际上是- -个由广域范围.大量节点共同维护的巨大散列表。散列表被分割成不连续的块,每个节点被分配给一个属于自己的散列块,并成为这个散列块的管理者。DHT的节点既是动态的，节点数量也是巨大的,因此非中心化和自组织成为两个设计的重要目标。由于重叠网络采用了确定性拓扑结构,DHT可以提供精确的发现。只要目标节点存在于网络中,DHT总能发现它,而且发现的准确性得到了保证。DHT的的主流系统有Kademlie Pasty Tapesty、Chord.CAN等。1 DHT算法与Kademlia技术的分析DHT类结构最大的问题是DHT的维护机制较为复杂.尤其是节点颊繁加人.退出造成的CHURN会极大增加DHT的维护代价以及不能吻合节点的异质性要求。DHT的主流技术在路由查找效率、负载均衡和CHURN这3个方面也都有不同表现。任何分布式路由算法的目的都是为了能够得到更快的路由以及在相同时间内更有效的对未知的P2P网络进行管理。目前一些较流行的DHT例如Chord.CAN .Pasty .Tapesty和Kademlia以及-些其它的DHT或多或少存在以下一些缺点:1)它们都假定P2P网络中的所有节点拥有相同的带宽和其它的资源,没有考虑到P2P网络中节点的高度异构性这个性质。2)- -些协议由于在设计的时候就没有考虑到P2P网络中CHURN较差的情况,结果就是它们不能很好的处理CHURN问题。3)负载均衡在路由层并没有被很好的实现，在改进的算法中将通过多种有效的方法解决节点超载的问题,这些有效的手段包括考虑节点的异质性对节点进行分类,对类型不同的节点分别进行节点ID的均匀分布以及虚拟服务器技术。本论文的工作重点就是通过分析上述DHT的构造和路由方法以及上述提出的问题来构造一-个新的 DHT路由算法。2优化型Kademlia的设计为了解决CHURN向题,需要设计-个可以应用于任何KBR层路由协议上的-一个通用DHT框架解决方案,这就要对Kadenlia进行优化设计,进而达到在CHURN为90%左右的时候查找成功率将大于95%,查找偏差小于5%。2.2体系架构2.2.1 PlanetSim整个P2P系统的体系架构来源于PlanetSim,在PlaneSim中,开发者可以工作在覆盖层中进行创造和测试逻辑算法或者创建和测试新的服务。PlaneSim 的架构为三层的层次结构,应用层在最上层建立在路由服务上,该路由服务由下层的路由层提供,可以在中国煤化工YHCNMHG收稿日期:2011-09 -27作者简介:王震(1972-),男,辽宁人,删教授,硕士,多年主要从事计算机及软件开发的教学、科研工作。7932电 软件计计开资.......本栏目责任编辑:谢嫒媛第7卷第32期(2011年11月)Computer Knowledge and Technology电脑知识与技术应用层直接开发应用程序。PlanetSim 的架构如图1所示。Nitra [ [PAST]↑ 的n新算法将在路由层里的覆盖网(Overlay)中进行设计,最终对上层提供统一的Comnon API",在服务层中通过调用下层提供的DOLRC接口来实现优化的Kademlia路由算法,通过PlaneSim模拟网络环境对新的算法进行测试。2.2.2路由层NverlayBR层对所有的结构化网络提供相同的基本性能,该层管理仿真蒂ProtooLond Blnmoing麟(EntioeP2P系统中路由所有相关的功能。该层划分为两个子层,分别是底层网络(Network)子层和覆盖网(Overlay)子层。覆盖网层有3个Hotiwork .模块:图1 PlanetSim 的体系架构1)ID Managemento它负责处理节点ID的分配，它使P2P网络中的节点在ID空间中都能均匀的分布,这有助于KBR层和高层的负载均衡。2)Routing Protocolo负责P2P的路由,优化的Kademlia将在这里工作。3)Load Balancing Engine。在查找过程中一些节 点比其它一些节点所负担的工作量要多的多,该模块负责对这些节点进行负载均衡。2.2.3服务层.表1 Service 层接口该层处于应用和路由层的中间,为不同的应用DHTCAST提供可重用的上层服务,例如DHT、DOLR和put(key, data)publishobjectId)join(groupId)CAST。这些服务使用路由层提供的Common API接口。该层也为上层的应用层提供自己的一系列接remove(key)unpubli sh (objeetId)leave(groupId)口,该层的接口"如表1。valuezget (key)sendToObj (msg, objeted, [n]) Mlulti/anyeast (asg, groupId2.2.4应用层.该层由-些应用组成.例如VoD.CFS、PAST和Scribe等,这些应用使用下两层提供的服务。大多数应用使用服务层提供的服务,只有一些很少的系统应用直接调用KBR的服务。2.3采用的新技术2.3.1节点分类在该P2P系统中按照节点的能力将它们划分为普通对等节点和超级对等节点和巨型对等节点。通过考虑影响-一个对等节点的各种参数来计算该节点的异构因素标准(H1)。用B当作节点的可用带宽,T为节点在网络中的运行时间比率,C作为CPU的性能,M为节点内存的大小,S为各种路由表储存容量,那么对等节点的HF以参数B, T, C, M的函数如下:H, =func(B,T.C,M,S)在公式(1)中,参数B、T和S在计算中占有重要的成分,因为B是Internet中节点主要关心的问题,T则代表了对等节点的稳定度，S表现一个节点的存储容量。在这里可以忽略参数C和M带来的影响,那么公式()可以简化为:H, =func(B,T,S)(2)按照公式(2),每个节点都要维持不同大小的路由表.其中带宽.运行时间和存储容量越大的节点其路由表的大小也就越大。在计算HF的时候,我们将P2P网络中的节点按照普通节点、超级节点和巨型节点进行分别计算。2.3.2超级对等节点和巨型对等节点超级节点和巨型节点就是网络中那些可以利用更多资源拥有更强大性能的节点,二者基本的不同点在于巨型节点由P2P网络运营者或管理者所提供，并且在P2P网络中巨型节点拥有更高的运行时间和性能"。巨型节点的存储容量和超级节点相似，在当前的仿真中利用巨型节点的主要目的是用来实现负载均衡。2.3.3节点分布通常较多的P2P系统采用根据节点的IP地址和端口来产生节点ID或用随机数来产生”。这就使当P2P网络中节点增多的时候节点ID分布并不均匀,最终导致某个ID空间中少数节点有很高的负载(查找热区或者查找失败"。考虑到这点,论文中将采用一一个较实用的方法,将节点的分布分为两层,超级节点层和普通节点层。每个节点加入网络时首先检测自己的性能.根据该性能来决定加入到哪一-层。 这种ID分配策略可以使ID平均的分布。2.3.4对路由的改进对原有协议里的路由机制进行改进,新的路由机制将减少节点对带宽的占用并提供较高的CHURN弹性,改进包括以下几点:1)并行递归查找。2)在查找中学习,对查找状态进行动态的更新。查找状态可以从MCNL和RHNL中获得。3)基于先验式反应式移除路由表中失效的表项。4)采用从LPT和BT中选择亲近的节点的技术间。(注:LPT和 BT为不同5)对LPT中XOR距离接近的节点进行相关的路由维护。中国煤化工6)最大化节点间相互交换维护信息的容量”。TYRCNMHG2.3.5节点异构性在本系统设计中,节点根据自己性能的大小来决定可以维护信息的多少,维护的信息包括两个方面:BT .LPT和PT所占的大小;本栏目责任编辑:谢媛媛w...:软件设计开发: 7933Computer Knowedge and Technology电脯匆识与技术第7卷第32期(2011年 11月)节点在查找时如果负载过大,节点将丢弃剩余的消息来保证自己的查找性能"。这条因素在模拟器中并没有考虑,仅停留在理论研究阶段。2.3.6 路由层的负载均衡设计该技术的目的就是避免某个节点在它的ID空间中查找工作量超过它所能承受的范围.如果仅仅采用上节所采用的一旦超过负载能力就丢弃消息的做法,那么整个P2P网络的质量将会下降并且查找失败率将上升。通过实现KBR层的负载均衡机制可以解决这个问题,该机制的实现就是在KBR层通过定位超载节点并且让这些超载节点加入ID空间附近的一些节点中,这样就可以实现局部的负载平衡。该机制可以通过共享负载来减低节点的负载,并且可以改善网络波动下的网络性能"。3结论本论文在分析DHT的构造和路由方法基础上来构造- -个新的DHT路由算法,系统设计的目标是采用新的技术对路由进行改进实现路由层的负载均衡。通过将优化的Kademlia网络协议的引人构架了通用DHT框架解决方案.就可以得到更快的路由以及在相同时间内更有效的对未知的P2P网络进行管理。通常的P2P网络在一一个较稳定的网络中总能表现出良好的性能,当网络中CHURN率较高时这些协议的性能明显的降低,如何在高CHURN下设计- -个性能好的DHT算法是个具有挑战性的工作。在本论文中主要的工作重点放在如何在CHURN率-一直偏高的情况下,算法仍旧表现出高性能,最终的结果也基本达到了预先的设想。参考文献:[1] Dabek F.Zhao B,Druschel PetalTowards a common API for structured peer-to peer overaycsC.B.rele.Calfiri.Prc. IPTPS 2003,2003.[2]聂秀英IP网络内容分发技术[.电信科学20(1):36-38.[3]雷葆华,杨明川.P2P技术的组网模式与业务探讨J]电信技术2011):23 -27.[4] Tian Ruixiong,Xiong Yongqiang,Zhang Qian,et al.Hybrid Overlay Structure Based on Random walks[Z4l.[5] Castro M,Druschel P,Hu Y C,et al.Rowstron.expiting Network Proximity in Peer-to-Peer Overlay Network[R],Camvridge,UKTechnicalReport MSR-TR 2002-82, Microsoft Research,2002[6] Dobuzhskaya M,Liu R,Roewe J,et al,Zebr: Peer To Peer Multicast for live Streaming Video[C].MIT,2004.[7] Portmann M,Ardon S,Senae P,et al.PEOST: A programmable structured peer-to-peer overlay network[CV/Zurich SwitzerLand:Proceed-ings of the Fourth IEEE Intermational Conference on Peer To Peer Computing,2004.[8] Ledlie J.Selzer M.Distributed, Secure Load Balancign with Skew, Heterogeneity, and Churn[R]Harvard Technical Report TR- -31-04,2004.[9] Kenthapadi K,Manku G S.Decentralized algoithms using both local and random probes for P2P load balancing[CV/Proc. 17th ACM Sym-posium on Parallel Algorithms and Architectures(SPAA '05),2005.(上接第7931页)5自动化测试结果用Robot工具来录制和回放测试用例脚本的执行速度至少是人工操作的3倍以上执行结果可以在操作日志中查询,这样就能更好的验证整个用例设计的合理性。当测试过程中需要大批量执行某些测试项时,其执行速度和效率的优势更是人工所不能比拟的,充分体现了自动化测试的特点。特别适用于回归测试，目前在BSS系统测试中已得到了初步的应用。6需解决的问题在系统不够稳定的情况下,经常会由于一个未录制界面的异常出现或-个已录制界面的长期不出现.而使整个BOROT脚本无法运行。而且由于现场环境的复杂性,有时无法用设置Robot验证点的方法来判断站点初始化或系统运行的正确性,而只能用人力来观察,这样就使Robot脚本执行自动化程度大大降低了。7结束语Rational Robot是伴随着软件测试技术发展起来的自动化测试工具,是进行现代软件测试的有效手段。本文根据Rationl Robot的特点着重讲述了它的测试过程以及测试脚本的运用,为今后软件测试工作提供了更加灵活、充分的方法。[1] 曹薇.软件测试M].北京:清华大学出版社,2008.中国煤化工[1] Esentials of Functional Testing with Rational Robot User's Manual[Z_2003..MYHCNMHG7934蛹 软件设计开发=mm==.--本栏目责任编辑:谢媛媛