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

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