一种基于DHT的网格动态资源查找算法

PAGE20衡水学院学报第11卷航空学报第11卷第1期衡水学院学报Vol.11,No.12009年2月JournalofHengshuiUniversityFeb.2009收稿日期：2008-09-作者简介：高艳丽(1979-),女,河北衡水市人,衡水学院经济学与管理学系助教,工学硕士.一种基于DHT的网格动态资源查找算法高艳丽（衡水学院经济学与管理学系，河北衡水053000）摘要：P2P与网格都是新型的分布式计算模型，在分析现有网格动态资源发现机制的基础上，将P2P的相关技术引入其中，提出了一种基于DHT的网格动态资源查找算法．该算法结合DHT技术和泛洪式查找技术，在实际的分布式网络之上建立一层结构化的Overlay层．实验结果表明，当用户需要在系统中获取信息时，通过该查找算法，查询只在一些特定的结点上进行，这样就避免了泛洪式查找的盲目性，因此大大提高了信息搜索的效率．关键词：网格；P2P；DHT网络；泛洪技术；动态资源查找中图分类号：TP393文献标识码：A文章编号:1673-2065(2009)0第1期高艳丽一种基于DHT的网格动态资源查找算法PAGE190引言网格作为一种分布式计算环境，目的在于利用互联网把分散在不同地理位置的各种可用空闲资源整合起来，实现计算资源、存储资源、数据资源等的全面共享，最终实现网络虚拟环境中的资源共享和协同工作．在任何资源共享的环境中，一个基本的服务就是资源发现，即当给出一个所需资源的描述，资源发现机制就返回一个与描述匹配的资源位置[1]．P2P是一种实现资源共享的分布式技术，与网格在动态性和异构性方面具有相同的特点．但它们之间存在着两点主要的不同．首先，P2P系统最初被设计时主要考虑在各个peers之间共享文件资源，而网格则要处理计算资源、存储资源、数据资源等等不同类型的资源．其次，P2P系统的动态性主要体现在系统中的结点和共享的资源，它们可以在任何时间加入或者离开，然而在网格环境中，各个结点以一种相对静态的方式连接在网络上，网格的动态性主要体现在资源状态的快速变化上．考虑到P2P系统与网格自身的特点，P2P技术与网格技术进行了有效的融合，在网格环境中利用基于DHT的P2P技术实现了对于某一类资源的多属性查询和范围查询[2-3]．然而，对于网格中的动态资源，由于它们的属性值变化非常的频繁，这就使得单纯应用DHT技术很难实现对于网格动态资源的查询．针对这一问题，本文提出一种基于DHT的网格动态资源查找算法，通过该算法能够有效地将DHT技术与动态资源查找技术相结合，从而实现网格动态资源的查找，同时对算法性能进行了分析．1相关工作当前，主要有两种P2P资源发现技术被逐渐应用到网格环境当中，一种是基于DHT的查找，另一种是泛洪式(Flooding)查找．基于DHT的查找技术主要应用在对于静态网格资源的查找，因为动态网格资源属性值的快速频繁的变化，使得DHT的更新维护变得非常困难，因此，泛洪式查找技术被用于动态网格资源的查找和静态网格资源的模糊查找．见表1．表1不同类型的资源所采用的查找技术查找方式静态网格资源动态网格资源精确查找DHTFlooding范围查找DHTFlooding模糊查询FloodingFlooding1.1 DHT概述在P2P通信中引入DHT是为了在实际网络之上建立一层结构化的Overlay层，即一个逻辑层，便于信息的查找，而不需要像Gnutella那样每次查找信息都需要泛洪．基于这种思想产生了各种不同的DHT模型，包括CAN[4]、Chord[5]、Pastry[6]、Tapestry[7]、Kademlia[8]等．这些模型的主要不同之处是对于P2P结点的组织方式，但不论使用那种模型，在结点加入DHT网络时都需要为结点哈希产生一个标识符NodeId，从而决定它在DHT网络中的位置，以及它在逻辑网络中的路由表．每个结点要维护一些资源信息，即(key,value)对，key决定存储的目标结点，value则是存储在目标结点的信息，可以是内容的索引，也可能是内容的本身．结点进行信息的插入和查找时，同样也是对信息的关键字进行哈希，产生一个键值K，找到NodeId与此键值K最接近的结点，进行操作．1.2 Chord概述Chord在2001年由麻省理工学院提出，它采用一致性哈希作为哈希算法，在Chord协议中规定为SHA-1．Chord使用一个定长m位的标识符来标识每个结点，结点按标识符从小到大顺时针组成一个环形结构，如图1所示，结点加入Chord时随机产生一个标识符NodeId，根据此NodeId由网络中已有的引导结点通过寻路找到维护此NodeId所在区域的目标结点，划分它的区域给新结点，更新其路由表，并帮助新结点建立一个新的路由表，称为finger表，表中包括m个后继结点和一个前驱结点，前驱结点即NodeId比本结点小的最近结点，设本结点NodeId为n，则m个后继结点分别为NodeId等于或大于n+20，n+21，…，n+2m-1的第一个结点，图1列举了NodeId为4的结点的finger表(m=6)．进行信息的插入和查找时，由信息的关键字key哈希得到一个键值K，由发起的结点从其后继表中选取NodeId小于此键值K的最接近的结点，然后由此结点继续按同样的方式进行寻路，直到某个结点发现此键值K在本结点NodeId和其前驱结点的NodeId之间，则由此结点进行信息的插入和查找操作．图1列举了由NodeId为4的结点N4查找键值为52的信息的寻路过程．2基于DHT的网格动态资源查找当前网格动态资源的查找方式主要有两种：一种是泛洪式资源发现方法，它广泛应用于非结构化P2P系统中；另一种是Globus的信息服务组件MDS(MonitoringandDiscoveryService)，通过它可以查询计算资源的动态属性．泛洪式资源发现方法简单、有效、查询命中率很高,并可以动态的适应实体个数的增加或减少，具有很好的扩展性．但它存在一定的问题：随着各节点不断地向其邻居节点发送请求消息，网络中的消息量将以指数级倍增，大大消耗网络带宽．MDS是集中式资源发现方法，它具有便于管理和部署的优点，但是当连接的结点数量很大时，其中心服务器有可能成为系统的瓶颈，在一定程度上影响了其扩展性．因此，这种方法无法适应大规模分布式环境的需求．基于以上情况考虑，本文提出一种基于DHT的网格动态资源查找算法，它在实际的分布式网络之上建立一层结构化的Overlay层，这样系统中每个结点只存储特定信息或特定信息的索引．当用户需要在系统中获取信息时，通过路由算法，查询只在一些特定的结点上进行,这样就避免了泛洪式查找的盲目性，因此大大提高了信息搜索的效率．图1Chord模型2.1资源查找算法描述本文采用的网络模型基于Chord模型．对于标准的Chord模型，网络中结点的标识符和资源属性的键值被映射到同一个环上，而本文的Chord模型，只有网络中结点的标识符被映射到环上，也就是说环中结点不指向任何资源，具体的动态资源查询通过每个结点的本地查询机制来处理完成．用M位定长标识网络中的结点，则Chord环最多有N=2M个结点，环上每一个结点k都有一个查询表，指向其他M个结点(k+2i-1,i=1,…,M)．同样，这M个结点也都有各自的查询表指向另外M个结点，当需要查找资源时，发出请求的结点向查询表中的M个结点都发出查询消息[9]，同理，收到消息的结点再向它表中的M个结点发出查询消息，一直重复进行，这样通过M步，环上的所有结点就都可以收到查询消息了．但是，很明显的一个问题是，一个结点将会收到多条重复的查询消息，这样就产生了大量的冗余的消息，势必造成网络带宽的浪费，严重的话将引起网络阻塞．针对这种情况，可以在每个结点的查询表中设置一个标识位，用于判断向这个结点是否发送过查询消息，初始值为0，结点收到过查询消息后，标识位设为1，这样就可避免冗余消息的产生，同时，设置一个队列用于存放被访问过的结点．例如，一个结点标识符为M位的完全Chord网络(即N=2M)，其改进的查询表如表2所示．表2查询表查询表项定义NodeIdentifier用于判断向此结点是否发送过查询消息，初始值为0，收到查询消息后设为1finger[k].start(n+2k-1)mod2m,1≤k≤erval(finger[k].start,finger[k+1].start).nodefirstnode≥n.finger[k].startSuccessor在环上离本地结点最近的后一个结点，也就是finger[1].nodePredecessor在环上离本地结点最近的前一个结点M位结点ND查找动态资源DR的路由查找算法描述如下：算法：动态资源查找输入：要查找的动态资源DR.输出：满足条件的所有结点.BeginStep1:InitQueue(Q);/*初始化辅助队列*/Step2:For(m=0;m<2M;++m)node[m].Identifier=FALSE;/*初始化网络中结点的标识位*/Step3:ND=N;/*N为发起查询的结点*/Step4:For(i=1;i<=M;i++)/*结点ND向其查询表中相应的结点发送查询消息*/If(ND.finger[i].node.Identifier==0)Then{SENDMES(ND.finger[i].node,DR);/*发送查询消息*/If(DR∈ND.finger[i].node.LocalResourceList)Then{ReturnND.finger[i].node;ND.finger[i].node.Identifier=1;EnQueue(Q,ND.finger[i].node);}/*结点入队列*/Else{ND.finger[i].node.Identifier=1;EnQueue(Q,ND.finger[i].node);}ElsegotoStep5;Step5:While(!QueueEmpty(Q)){DeQueue(Q,nd);/*队头元素出队列*/ND=nd;gotoStep4;};End2.2 算法分析通过Step2标识网络中的所有结点未被访问，该步骤所需要的时间为O(2M)，其中M为网络中结点标识符的位数，2M为所有结点的数目．在Step4中，通过判断结点的标识位，可以有效地避免查询消息向某一结点重复发送，同时与Step5相结合，保证了查询消息能够被发送到网络中的所有结点，从而所有包含要查找的动态资源DR的结点都能够被找到．在这个过程中，访问网络中的所有结点，仅仅需要发送2M-1条消息，因此该过程所需的时间为O(2M-1)．若网络中结点的个数为n，那么整个动态资源查找算法的时间复杂度为O(n)，其中n≤2M．3查询算法的实现及分析3.1 实验数据设置实验环境设置如下，CPU：Pentium(R)42.4GHz；内存：512MB；操作系统：MSWindowsXP；编程语言：java语言；集成开发环境：Eclipse3.1．改进的消息扩散算法所采用的网络模型基于Chord模型．对于标准的Chord模型，网络中结点的标识符和资源属性的键值被映射到同一个环上，而改进算法所基于的Chord模型，只有网络中结点本身的标识符被映射到环上，而对资源属性的键值不进行映射，即环中结点不指向任何资源，具体的动态资源查询通过每一个结点的本地查询机制来处理完成．模拟程序首先生成了一个具有8个节点的模拟环状网络，然后在此网络上分别执行现有的Chord消息路由算法与改进算法，得到每次查询所需发送的消息数，最后对实验结果进行分析比较．程序运行时的初始化网络图2系统初始化界面如图2．3.2 实验结果和分析假设发出资源请求的节点是N7，运行程序则能够返回网络中所有满足其查询要求的节点．在现有算法中N7首先向其查询表中的3个结点都发出查询消息，然后收到消息的结点再向自身表中的3个结点发出查询消息，这样一直重复进行下去，直到网络中的所有节点都被访问到为止．很明显，一个结点将有可能收到多条重复的查询消息，这样就产生了大量的冗余的消息，势必造成网络带宽的浪费，严重的话将引起网络阻塞．运行现有的Chord路由算法显示结果如图3．图3Chord算法运行结果通过实验，可以看出在N=8个节点的网络中，Chord路由算法总共需要发送18条消息才能访问到网络中所有节点，其中重复发送的冗余消息很多，很大程度上增加了网络通信的负担；而本文中改进的算法仅需要发送N-1=7条消息就能访问到网络中所有节点，由此可见，改进算法对网络中消息流量的减少较为明显．4结论资源发现机制是P2P系统和网格研究的关键问题之一，然而传统的基于DHT的资源发现技术很难满足网格资源动态性这一特点．针对这一情况，本文将泛洪技术与DHT技术相结合提出了一种基于DHT的网格动态资源查找算法，通过该路由算法，查询只在一些特定的结点上进行，这样就避免了泛洪图4改进算法运行结果式查找的盲目性，从而大大提高了网格动态资源搜索的效率．参考文献：[1]IAMNITCHIA.IanFoster.OnFullyDecentralizedResourceDiscoveryinGridEnvironments[C].Berlin:

Springerpress,2001:51-62.[2]CAIM,FRANKM,CHENJ,etal.MAAN:AMulti-AttributeAddressableNetworkforGridInformationServices[J].JournalofGridComputing,SpringerNetherlands,2004,2(2):3-14.[3]BASUS,BANERJEES,SHARMAPS,etal.Peer-to-peerResourceDiscoveryforGrids[C].LosAlamitos:IEEEComputerSocietypress,2005:213-220.[4]RATANSAMYS,FRANCISP,HANDLEYM,etal.Ascalablecontent-addressablenetwork[C].NewYork:ACMPress,2001:(8):161-172.[5]STOICAI,MORRISR,LIBEN-NOWELLD,etal.Chord:ascalablePeer-to-Peerlookupprotocolforinternetapplications[C].Berkeley:ACMPress,2003,11(1):17-32.[6]ROWSTROA,DRUSCHELP.Scalable,decentralizedobjectlocationandroutingforlarge-scalepeer-to-peersystems[C].Berlin,Heidelberg:Springer-Verlag,2001:329-350.[7]BenY.ZhaoLing-huang,STRIBLINGJ,etal.Tapestry:aresilientglobal-scaleoverlayforservicedeployment[J].IEEEJournalonSelectedAreasinCommunication,IEEEInc.U.S.2004,22(1):41-53.[8]MAYMOUNKOVP,MAZI’ERESD.APeer-to-PeerinformationsystembasedontheXORmetric[C].NewYork:ACMPress,2002:53-65.[9]EI-ANSARYS,AlIMAL,BRANDP,etal.EfficientBroadcastinStructuredP2PNetworks[C].Cardiff:IEEEComputerSocietyPress,2005:267-279.DHT-BasedDynamicResourceSearchAlgorithminGridEnvironmentGAOYan-li（DepartmentofEcono