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

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