一種基于DHT的網(wǎng)格動態(tài)資源查找算法

PAGE20衡水學(xué)院學(xué)報第11卷航空學(xué)報第11卷第1期衡水學(xué)院學(xué)報Vol.11,No.12009年2月JournalofHengshuiUniversityFeb.2009收稿日期：2008-09-作者簡介：高艷麗(1979-),女,河北衡水市人,衡水學(xué)院經(jīng)濟學(xué)與管理學(xué)系助教,工學(xué)碩士.一種基于DHT的網(wǎng)格動態(tài)資源查找算法高艷麗（衡水學(xué)院經(jīng)濟學(xué)與管理學(xué)系，河北衡水053000）摘要：P2P與網(wǎng)格都是新型的分布式計算模型，在分析現(xiàn)有網(wǎng)格動態(tài)資源發(fā)現(xiàn)機制的基礎(chǔ)上，將P2P的相關(guān)技術(shù)引入其中，提出了一種基于DHT的網(wǎng)格動態(tài)資源查找算法．該算法結(jié)合DHT技術(shù)和泛洪式查找技術(shù)，在實際的分布式網(wǎng)絡(luò)之上建立一層結(jié)構(gòu)化的Overlay層．實驗結(jié)果表明，當(dāng)用戶需要在系統(tǒng)中獲取信息時，通過該查找算法，查詢只在一些特定的結(jié)點上進行，這樣就避免了泛洪式查找的盲目性，因此大大提高了信息搜索的效率．關(guān)鍵詞：網(wǎng)格；P2P；DHT網(wǎng)絡(luò)；泛洪技術(shù)；動態(tài)資源查找中圖分類號：TP393文獻標(biāo)識碼：A文章編號:1673-2065(2009)0第1期高艷麗一種基于DHT的網(wǎng)格動態(tài)資源查找算法PAGE190引言網(wǎng)格作為一種分布式計算環(huán)境，目的在于利用互聯(lián)網(wǎng)把分散在不同地理位置的各種可用空閑資源整合起來，實現(xiàn)計算資源、存儲資源、數(shù)據(jù)資源等的全面共享，最終實現(xiàn)網(wǎng)絡(luò)虛擬環(huán)境中的資源共享和協(xié)同工作．在任何資源共享的環(huán)境中，一個基本的服務(wù)就是資源發(fā)現(xiàn)，即當(dāng)給出一個所需資源的描述，資源發(fā)現(xiàn)機制就返回一個與描述匹配的資源位置[1]．P2P是一種實現(xiàn)資源共享的分布式技術(shù)，與網(wǎng)格在動態(tài)性和異構(gòu)性方面具有相同的特點．但它們之間存在著兩點主要的不同．首先，P2P系統(tǒng)最初被設(shè)計時主要考慮在各個peers之間共享文件資源，而網(wǎng)格則要處理計算資源、存儲資源、數(shù)據(jù)資源等等不同類型的資源．其次，P2P系統(tǒng)的動態(tài)性主要體現(xiàn)在系統(tǒng)中的結(jié)點和共享的資源，它們可以在任何時間加入或者離開，然而在網(wǎng)格環(huán)境中，各個結(jié)點以一種相對靜態(tài)的方式連接在網(wǎng)絡(luò)上，網(wǎng)格的動態(tài)性主要體現(xiàn)在資源狀態(tài)的快速變化上．考慮到P2P系統(tǒng)與網(wǎng)格自身的特點，P2P技術(shù)與網(wǎng)格技術(shù)進行了有效的融合，在網(wǎng)格環(huán)境中利用基于DHT的P2P技術(shù)實現(xiàn)了對于某一類資源的多屬性查詢和范圍查詢[2-3]．然而，對于網(wǎng)格中的動態(tài)資源，由于它們的屬性值變化非常的頻繁，這就使得單純應(yīng)用DHT技術(shù)很難實現(xiàn)對于網(wǎng)格動態(tài)資源的查詢．針對這一問題，本文提出一種基于DHT的網(wǎng)格動態(tài)資源查找算法，通過該算法能夠有效地將DHT技術(shù)與動態(tài)資源查找技術(shù)相結(jié)合，從而實現(xiàn)網(wǎng)格動態(tài)資源的查找，同時對算法性能進行了分析．1相關(guān)工作當(dāng)前，主要有兩種P2P資源發(fā)現(xiàn)技術(shù)被逐漸應(yīng)用到網(wǎng)格環(huán)境當(dāng)中，一種是基于DHT的查找，另一種是泛洪式(Flooding)查找．基于DHT的查找技術(shù)主要應(yīng)用在對于靜態(tài)網(wǎng)格資源的查找，因為動態(tài)網(wǎng)格資源屬性值的快速頻繁的變化，使得DHT的更新維護變得非常困難，因此，泛洪式查找技術(shù)被用于動態(tài)網(wǎng)格資源的查找和靜態(tài)網(wǎng)格資源的模糊查找．見表1．表1不同類型的資源所采用的查找技術(shù)查找方式靜態(tài)網(wǎng)格資源動態(tài)網(wǎng)格資源精確查找DHTFlooding范圍查找DHTFlooding模糊查詢FloodingFlooding1.1 DHT概述在P2P通信中引入DHT是為了在實際網(wǎng)絡(luò)之上建立一層結(jié)構(gòu)化的Overlay層，即一個邏輯層，便于信息的查找，而不需要像Gnutella那樣每次查找信息都需要泛洪．基于這種思想產(chǎn)生了各種不同的DHT模型，包括CAN[4]、Chord[5]、Pastry[6]、Tapestry[7]、Kademlia[8]等．這些模型的主要不同之處是對于P2P結(jié)點的組織方式，但不論使用那種模型，在結(jié)點加入DHT網(wǎng)絡(luò)時都需要為結(jié)點哈希產(chǎn)生一個標(biāo)識符NodeId，從而決定它在DHT網(wǎng)絡(luò)中的位置，以及它在邏輯網(wǎng)絡(luò)中的路由表．每個結(jié)點要維護一些資源信息，即(key,value)對，key決定存儲的目標(biāo)結(jié)點，value則是存儲在目標(biāo)結(jié)點的信息，可以是內(nèi)容的索引，也可能是內(nèi)容的本身．結(jié)點進行信息的插入和查找時，同樣也是對信息的關(guān)鍵字進行哈希，產(chǎn)生一個鍵值K，找到NodeId與此鍵值K最接近的結(jié)點，進行操作．1.2 Chord概述Chord在2001年由麻省理工學(xué)院提出，它采用一致性哈希作為哈希算法，在Chord協(xié)議中規(guī)定為SHA-1．Chord使用一個定長m位的標(biāo)識符來標(biāo)識每個結(jié)點，結(jié)點按標(biāo)識符從小到大順時針組成一個環(huán)形結(jié)構(gòu)，如圖1所示，結(jié)點加入Chord時隨機產(chǎn)生一個標(biāo)識符NodeId，根據(jù)此NodeId由網(wǎng)絡(luò)中已有的引導(dǎo)結(jié)點通過尋路找到維護此NodeId所在區(qū)域的目標(biāo)結(jié)點，劃分它的區(qū)域給新結(jié)點，更新其路由表，并幫助新結(jié)點建立一個新的路由表，稱為finger表，表中包括m個后繼結(jié)點和一個前驅(qū)結(jié)點，前驅(qū)結(jié)點即NodeId比本結(jié)點小的最近結(jié)點，設(shè)本結(jié)點NodeId為n，則m個后繼結(jié)點分別為NodeId等于或大于n+20，n+21，…，n+2m-1的第一個結(jié)點，圖1列舉了NodeId為4的結(jié)點的finger表(m=6)．進行信息的插入和查找時，由信息的關(guān)鍵字key哈希得到一個鍵值K，由發(fā)起的結(jié)點從其后繼表中選取NodeId小于此鍵值K的最接近的結(jié)點，然后由此結(jié)點繼續(xù)按同樣的方式進行尋路，直到某個結(jié)點發(fā)現(xiàn)此鍵值K在本結(jié)點NodeId和其前驅(qū)結(jié)點的NodeId之間，則由此結(jié)點進行信息的插入和查找操作．圖1列舉了由NodeId為4的結(jié)點N4查找鍵值為52的信息的尋路過程．2基于DHT的網(wǎng)格動態(tài)資源查找當(dāng)前網(wǎng)格動態(tài)資源的查找方式主要有兩種：一種是泛洪式資源發(fā)現(xiàn)方法，它廣泛應(yīng)用于非結(jié)構(gòu)化P2P系統(tǒng)中；另一種是Globus的信息服務(wù)組件MDS(MonitoringandDiscoveryService)，通過它可以查詢計算資源的動態(tài)屬性．泛洪式資源發(fā)現(xiàn)方法簡單、有效、查詢命中率很高,并可以動態(tài)的適應(yīng)實體個數(shù)的增加或減少，具有很好的擴展性．但它存在一定的問題：隨著各節(jié)點不斷地向其鄰居節(jié)點發(fā)送請求消息，網(wǎng)絡(luò)中的消息量將以指數(shù)級倍增，大大消耗網(wǎng)絡(luò)帶寬．MDS是集中式資源發(fā)現(xiàn)方法，它具有便于管理和部署的優(yōu)點，但是當(dāng)連接的結(jié)點數(shù)量很大時，其中心服務(wù)器有可能成為系統(tǒng)的瓶頸，在一定程度上影響了其擴展性．因此，這種方法無法適應(yīng)大規(guī)模分布式環(huán)境的需求．基于以上情況考慮，本文提出一種基于DHT的網(wǎng)格動態(tài)資源查找算法，它在實際的分布式網(wǎng)絡(luò)之上建立一層結(jié)構(gòu)化的Overlay層，這樣系統(tǒng)中每個結(jié)點只存儲特定信息或特定信息的索引．當(dāng)用戶需要在系統(tǒng)中獲取信息時，通過路由算法，查詢只在一些特定的結(jié)點上進行,這樣就避免了泛洪式查找的盲目性，因此大大提高了信息搜索的效率．圖1Chord模型2.1資源查找算法描述本文采用的網(wǎng)絡(luò)模型基于Chord模型．對于標(biāo)準(zhǔn)的Chord模型，網(wǎng)絡(luò)中結(jié)點的標(biāo)識符和資源屬性的鍵值被映射到同一個環(huán)上，而本文的Chord模型，只有網(wǎng)絡(luò)中結(jié)點的標(biāo)識符被映射到環(huán)上，也就是說環(huán)中結(jié)點不指向任何資源，具體的動態(tài)資源查詢通過每個結(jié)點的本地查詢機制來處理完成．用M位定長標(biāo)識網(wǎng)絡(luò)中的結(jié)點，則Chord環(huán)最多有N=2M個結(jié)點，環(huán)上每一個結(jié)點k都有一個查詢表，指向其他M個結(jié)點(k+2i-1,i=1,…,M)．同樣，這M個結(jié)點也都有各自的查詢表指向另外M個結(jié)點，當(dāng)需要查找資源時，發(fā)出請求的結(jié)點向查詢表中的M個結(jié)點都發(fā)出查詢消息[9]，同理，收到消息的結(jié)點再向它表中的M個結(jié)點發(fā)出查詢消息，一直重復(fù)進行，這樣通過M步，環(huán)上的所有結(jié)點就都可以收到查詢消息了．但是，很明顯的一個問題是，一個結(jié)點將會收到多條重復(fù)的查詢消息，這樣就產(chǎn)生了大量的冗余的消息，勢必造成網(wǎng)絡(luò)帶寬的浪費，嚴重的話將引起網(wǎng)絡(luò)阻塞．針對這種情況，可以在每個結(jié)點的查詢表中設(shè)置一個標(biāo)識位，用于判斷向這個結(jié)點是否發(fā)送過查詢消息，初始值為0，結(jié)點收到過查詢消息后，標(biāo)識位設(shè)為1，這樣就可避免冗余消息的產(chǎn)生，同時，設(shè)置一個隊列用于存放被訪問過的結(jié)點．例如，一個結(jié)點標(biāo)識符為M位的完全Chord網(wǎng)絡(luò)(即N=2M)，其改進的查詢表如表2所示．表2查詢表查詢表項定義NodeIdentifier用于判斷向此結(jié)點是否發(fā)送過查詢消息，初始值為0，收到查詢消息后設(shè)為1finger[k].start(n+2k-1)mod2m,1≤k≤erval(finger[k].start,finger[k+1].start).nodefirstnode≥n.finger[k].startSuccessor在環(huán)上離本地結(jié)點最近的后一個結(jié)點，也就是finger[1].nodePredecessor在環(huán)上離本地結(jié)點最近的前一個結(jié)點M位結(jié)點ND查找動態(tài)資源DR的路由查找算法描述如下：算法：動態(tài)資源查找輸入：要查找的動態(tài)資源DR.輸出：滿足條件的所有結(jié)點.BeginStep1:InitQueue(Q);/*初始化輔助隊列*/Step2:For(m=0;m<2M;++m)node[m].Identifier=FALSE;/*初始化網(wǎng)絡(luò)中結(jié)點的標(biāo)識位*/Step3:ND=N;/*N為發(fā)起查詢的結(jié)點*/Step4:For(i=1;i<=M;i++)/*結(jié)點ND向其查詢表中相應(yīng)的結(jié)點發(fā)送查詢消息*/If(ND.finger[i].node.Identifier==0)Then{SENDMES(ND.finger[i].node,DR);/*發(fā)送查詢消息*/If(DR∈ND.finger[i].node.LocalResourceList)Then{ReturnND.finger[i].node;ND.finger[i].node.Identifier=1;EnQueue(Q,ND.finger[i].node);}/*結(jié)點入隊列*/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標(biāo)識網(wǎng)絡(luò)中的所有結(jié)點未被訪問，該步驟所需要的時間為O(2M)，其中M為網(wǎng)絡(luò)中結(jié)點標(biāo)識符的位數(shù)，2M為所有結(jié)點的數(shù)目．在Step4中，通過判斷結(jié)點的標(biāo)識位，可以有效地避免查詢消息向某一結(jié)點重復(fù)發(fā)送，同時與Step5相結(jié)合，保證了查詢消息能夠被發(fā)送到網(wǎng)絡(luò)中的所有結(jié)點，從而所有包含要查找的動態(tài)資源DR的結(jié)點都能夠被找到．在這個過程中，訪問網(wǎng)絡(luò)中的所有結(jié)點，僅僅需要發(fā)送2M-1條消息，因此該過程所需的時間為O(2M-1)．若網(wǎng)絡(luò)中結(jié)點的個數(shù)為n，那么整個動態(tài)資源查找算法的時間復(fù)雜度為O(n)，其中n≤2M．3查詢算法的實現(xiàn)及分析3.1 實驗數(shù)據(jù)設(shè)置實驗環(huán)境設(shè)置如下，CPU：Pentium(R)42.4GHz；內(nèi)存：512MB；操作系統(tǒng)：MSWindowsXP；編程語言：java語言；集成開發(fā)環(huán)境：Eclipse3.1．改進的消息擴散算法所采用的網(wǎng)絡(luò)模型基于Chord模型．對于標(biāo)準(zhǔn)的Chord模型，網(wǎng)絡(luò)中結(jié)點的標(biāo)識符和資源屬性的鍵值被映射到同一個環(huán)上，而改進算法所基于的Chord模型，只有網(wǎng)絡(luò)中結(jié)點本身的標(biāo)識符被映射到環(huán)上，而對資源屬性的鍵值不進行映射，即環(huán)中結(jié)點不指向任何資源，具體的動態(tài)資源查詢通過每一個結(jié)點的本地查詢機制來處理完成．模擬程序首先生成了一個具有8個節(jié)點的模擬環(huán)狀網(wǎng)絡(luò)，然后在此網(wǎng)絡(luò)上分別執(zhí)行現(xiàn)有的Chord消息路由算法與改進算法，得到每次查詢所需發(fā)送的消息數(shù)，最后對實驗結(jié)果進行分析比較．程序運行時的初始化網(wǎng)絡(luò)圖2系統(tǒng)初始化界面如圖2．3.2 實驗結(jié)果和分析假設(shè)發(fā)出資源請求的節(jié)點是N7，運行程序則能夠返回網(wǎng)絡(luò)中所有滿足其查詢要求的節(jié)點．在現(xiàn)有算法中N7首先向其查詢表中的3個結(jié)點都發(fā)出查詢消息，然后收到消息的結(jié)點再向自身表中的3個結(jié)點發(fā)出查詢消息，這樣一直重復(fù)進行下去，直到網(wǎng)絡(luò)中的所有節(jié)點都被訪問到為止．很明顯，一個結(jié)點將有可能收到多條重復(fù)的查詢消息，這樣就產(chǎn)生了大量的冗余的消息，勢必造成網(wǎng)絡(luò)帶寬的浪費，嚴重的話將引起網(wǎng)絡(luò)阻塞．運行現(xiàn)有的Chord路由算法顯示結(jié)果如圖3．圖3Chord算法運行結(jié)果通過實驗，可以看出在N=8個節(jié)點的網(wǎng)絡(luò)中，Chord路由算法總共需要發(fā)送18條消息才能訪問到網(wǎng)絡(luò)中所有節(jié)點，其中重復(fù)發(fā)送的冗余消息很多，很大程度上增加了網(wǎng)絡(luò)通信的負擔(dān)；而本文中改進的算法僅需要發(fā)送N-1=7條消息就能訪問到網(wǎng)絡(luò)中所有節(jié)點，由此可見，改進算法對網(wǎng)絡(luò)中消息流量的減少較為明顯．4結(jié)論資源發(fā)現(xiàn)機制是P2P系統(tǒng)和網(wǎng)格研究的關(guān)鍵問題之一，然而傳統(tǒng)的基于DHT的資源發(fā)現(xiàn)技術(shù)很難滿足網(wǎng)格資源動態(tài)性這一特點．針對這一情況，本文將泛洪技術(shù)與DHT技術(shù)相結(jié)合提出了一種基于DHT的網(wǎng)格動態(tài)資源查找算法，通過該路由算法，查詢只在一些特定的結(jié)點上進行，這樣就避免了泛洪圖4改進算法運行結(jié)果式查找的盲目性，從而大大提高了網(wǎng)格動態(tài)資源搜索的效率．參考文獻：[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