云計算環(huán)境下支持多屬性查找的混合對等網(wǎng)絡

杜曉鋒，陳世平

(1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.上海理工大學 信息化辦公室，上海 200093)

?

云計算環(huán)境下支持多屬性查找的混合對等網(wǎng)絡

杜曉鋒1，陳世平2

(1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.上海理工大學 信息化辦公室，上海 200093)

摘要針對云計算環(huán)境下，云資源的多屬性查找問題，設計了一種混合結(jié)構(gòu)的對等網(wǎng)絡。該網(wǎng)絡采用多星形拓撲結(jié)構(gòu)，將云資源以統(tǒng)一的編碼方式規(guī)范化之后部署到該網(wǎng)絡上，可較好地實現(xiàn)多屬性查找。文中描述了多屬性查找算法，分析了網(wǎng)絡性能，該網(wǎng)絡旨在降低資源查找的跳數(shù)，因此文中主要分析網(wǎng)絡查找跳數(shù)。實驗表明，資源查找跳數(shù)得到優(yōu)化，達到了預期效果。

關鍵詞云計算；多屬性查找；混合對等網(wǎng)絡

云計算是通過網(wǎng)絡為用戶提供各種方便的服務。而現(xiàn)存的大部分云提供商均只集中提供某一種云服務，例如GoogleCloudStorage提供存儲服務，GoogleAppEngine提供網(wǎng)絡應用程序服務。不同的云提供商提供不同的云資源，但用戶通常需要同時獲得多種云資源，因用戶同時需要多種云資源，因此必須將不同類型的云資源進行整合。云資源的多屬性查找就是幫助用戶快速定位云資源的關鍵技術。

為了更好的支持多屬性查找，本文吸收了結(jié)構(gòu)化對等網(wǎng)絡和非結(jié)構(gòu)化對等網(wǎng)絡的優(yōu)點，采用混合結(jié)構(gòu)的對等網(wǎng)絡。對等網(wǎng)絡中的節(jié)點都采用常年穩(wěn)定在線的云服務器構(gòu)成，每個節(jié)點的處理能力、存儲空間、穩(wěn)定性等性能均是優(yōu)秀的。因而，在研究對云資源的多屬性查找時，不需要過多考慮節(jié)點性能。

1相關研究

支持云資源查找的P2P網(wǎng)絡按照結(jié)構(gòu)劃分通?？煞譃?類：結(jié)構(gòu)化P2P網(wǎng)絡、非結(jié)構(gòu)化P2P網(wǎng)絡、分層P2P網(wǎng)絡和混合結(jié)構(gòu)化P2P網(wǎng)絡。

結(jié)構(gòu)化的P2P網(wǎng)絡是將網(wǎng)絡中的節(jié)點嚴格按照特定的結(jié)構(gòu)進行組織，整個網(wǎng)絡拓撲受到嚴格控制，網(wǎng)絡中的所有節(jié)點共同維護網(wǎng)絡拓撲的穩(wěn)定。由于網(wǎng)絡的穩(wěn)定性和節(jié)點的有規(guī)律組織，結(jié)構(gòu)化P2P網(wǎng)絡通常通過DHT將查詢請求映射到特定節(jié)點上來實現(xiàn)資源查找，結(jié)構(gòu)化P2P網(wǎng)絡中的資源查找通常速度比較快，網(wǎng)絡利用率較高，但網(wǎng)絡結(jié)構(gòu)要求嚴格，不易擴展，而且不支持多屬性區(qū)間查找。Chord[1]和CAN[2]是最常見的兩種結(jié)構(gòu)化P2P網(wǎng)絡，Chord將節(jié)點按照環(huán)形結(jié)構(gòu)組織，每個節(jié)點通過哈希的方式產(chǎn)生一個唯一的ID，查詢復雜度是θ(logN)，但只支持單屬性查找。CAN以一個多維空間方式組織節(jié)點，其不支持區(qū)間查找。

非結(jié)構(gòu)化P2P網(wǎng)絡中節(jié)點的組織方式?jīng)]有嚴格的要求，所以節(jié)點的加入和離開更加方便，網(wǎng)絡的擴展性更好。非結(jié)構(gòu)化P2P網(wǎng)絡通常采用洪泛的方式查找資源，其查找算法簡單，但會產(chǎn)生較多無用的網(wǎng)絡通，如文獻[3～5]所示。

分層的P2P網(wǎng)絡通常是利用超級節(jié)點將多層的結(jié)構(gòu)化P2P網(wǎng)絡相連，利用分層逐級降低查找的屬性資源維度，以實現(xiàn)多維屬性查找。比如文獻[6～8]。

混合P2P網(wǎng)絡是結(jié)構(gòu)化P2P網(wǎng)絡和非結(jié)構(gòu)化P2P網(wǎng)絡相結(jié)合，綜合兩者各自的優(yōu)點而建立的一種P2P網(wǎng)絡結(jié)構(gòu)。其相對結(jié)構(gòu)化P2P網(wǎng)絡有更好的可擴展性，能支持多屬性區(qū)間查找，相對于非結(jié)構(gòu)化P2P網(wǎng)絡具有較少的無用網(wǎng)絡通信，比如文獻[9～11]。綜合各方研究成果，本文采用混合P2P網(wǎng)絡，能很好地支持多屬性查找。

2系統(tǒng)設計

2.1資源編碼表

本文針對的是多屬性云資源，云資源具有多種屬性，而每種屬性的云資源均有各自的描述方式，為方便多屬性查找，需要將多屬性云資源進行統(tǒng)一編碼，建立資源編碼表。

將n維屬性云資源看作一個資源空間，每種屬性代表該資源空間的一個維度，每個維度上再進行r個區(qū)間的劃分，代表每種屬性的值區(qū)間，這樣便形成了rn個多維屬性區(qū)間。假設一類云資源具有內(nèi)存和帶寬兩種屬性，其中內(nèi)存屬性的值有1GB，2GB，3GB，4GB，帶寬的值有100Mbit·s-1，200Mbit·s-1，300Mbit·s-1，400Mbit·s-1，則可建立如圖1所示的資源編碼表。其中，縱軸代表內(nèi)存，橫軸代表帶寬，每個屬性維度劃分4個區(qū)間，分別用2bit來編碼，則每個多維屬性區(qū)間便可用4bit編碼來表示。圖1中 編碼的屬性區(qū)間就表示“內(nèi)存=1GB，帶寬=100Mbit·s-1”的云資源，其是資源空間中各維度屬性值都最小的屬性區(qū)間，稱為原點屬性區(qū)間。通過資源編碼表的方式，多屬性云資源就能實現(xiàn)統(tǒng)一編碼，再與網(wǎng)絡結(jié)構(gòu)相結(jié)合即可實現(xiàn)多屬性查找。

圖1　二維屬性資源編碼表

2.2網(wǎng)絡拓撲結(jié)構(gòu)

該文設計的網(wǎng)絡拓撲結(jié)構(gòu)是一個多星型的混合P2P網(wǎng)絡結(jié)構(gòu)，如圖2所示，是對應圖1所示的資源編碼表得到的網(wǎng)絡拓撲圖。圖中帶編號的橢圓代表資源簇，所謂資源簇就是具有相同屬性組合及屬性值區(qū)間的所有節(jié)點的聚集，每個資源簇內(nèi)部是按照非結(jié)構(gòu)化P2P網(wǎng)絡組織節(jié)點的。圖中用同種連線相連的資源簇組成一個星型，各個星形之間彼此相連，最終形成了一個多星型的混合P2P網(wǎng)絡結(jié)構(gòu)。

圖2　網(wǎng)絡拓撲圖

2.3邊緣區(qū)間

將n維資源空間中具有某一屬性維度上最小屬性值的屬性區(qū)間稱為邊緣區(qū)間。如圖1中豎線陰影部分是具有帶寬這個維度最小屬性值的邊緣區(qū)間，橫線陰影部分是具有內(nèi)存這個屬性維度上最小屬性值的邊緣區(qū)間，而(0000)區(qū)間同時是內(nèi)存和帶寬兩個維度的最小值。邊緣區(qū)間對應的資源簇都是每個星形結(jié)構(gòu)的中心資源簇。所有的邊緣區(qū)間對應的資源簇都會與原點中心簇直接相連。如圖2中，(0000)，(0001)，(0010)，(0100)，(1000)，(1100)屬性區(qū)間對應的資源簇就都和原點屬性區(qū)間對應的資源簇相連。邊緣區(qū)間的概念將在資源查找用被利用，能優(yōu)化最大查詢跳數(shù)。

2.4相似區(qū)間

該文將某一屬性維度編碼不同而其他維度屬性編碼相同的屬性區(qū)間稱為相似區(qū)間，如圖1中的任一行或任一列的4個屬性區(qū)間都是相似區(qū)間。相似區(qū)間對應的資源簇屬于同一個星形結(jié)構(gòu)，相似區(qū)間的概念將在資源查找算法中被利用。

3資源查找

3.1多屬性查找算法

(1)當某個節(jié)點 接收到用戶的查詢請求，首先將查詢請求的資源轉(zhuǎn)換成對應的資源編碼，然后比對是否是該節(jié)點自身所在的資源簇，若是轉(zhuǎn)到步驟(2)，若請求的資源不是該節(jié)點所在的資源簇，則轉(zhuǎn)到步驟(3);

(2)在資源簇中用洪泛的方式查找資源節(jié)點，若找到，則在節(jié)點與用戶之間建立直接連接，將資源提交給用戶，若未找到滿足要求的節(jié)點，則返回查詢失敗。在簇中查找時會采取負載均衡措施，比如判斷節(jié)點是否超負載，若超過負載，就將查詢轉(zhuǎn)發(fā)給其他節(jié)點，這不是本文研究重點，不再贅述;

(3)判斷節(jié)點 所在的資源區(qū)間和用戶請求的資源區(qū)間是否是相似區(qū)間，如果是相似區(qū)間，說明節(jié)點N所在的資源簇和請求的資源簇屬于同一個星形，接著判斷節(jié)點N所在資源簇和目標資源簇中是否有中心資源簇，若存在，說明兩者直接相連，N直接將請求轉(zhuǎn)發(fā)給目標資源簇，然后執(zhí)行步驟(2)，如果不存在，則N將請求轉(zhuǎn)發(fā)給中心資源簇，再由中心資源簇轉(zhuǎn)發(fā)給目標資源簇，執(zhí)行步驟(2)；若N所在的資源區(qū)間和用戶請求的資源區(qū)間不是相似區(qū)間，則執(zhí)行步驟(4);

(4)若節(jié)點N所在的屬性區(qū)間和目標資源簇對應的屬性區(qū)間都是邊緣區(qū)間，則節(jié)點N將請求轉(zhuǎn)發(fā)給原點屬性區(qū)間對應的資源簇，再由原點屬性區(qū)間對應的資源簇轉(zhuǎn)發(fā)給目標資源簇，因所有的邊緣區(qū)間對應的資源簇均與原點屬性區(qū)間對應的資源簇相連；若節(jié)點N所在的屬性區(qū)間和目標資源簇對應的屬性區(qū)間不是邊緣區(qū)間，則節(jié)點N所在的資源簇將請求轉(zhuǎn)發(fā)給其所在星形結(jié)構(gòu)的中心資源簇，由于中心資源簇對應的屬性區(qū)間都是邊緣區(qū)間，而所有的邊緣區(qū)間都和原點屬性區(qū)間對應的資源簇相連，所以將請求進一步轉(zhuǎn)發(fā)給原點屬性區(qū)間對應的資源簇，由該資源簇轉(zhuǎn)發(fā)給與目標資源簇在一個星形結(jié)構(gòu)的中心資源簇，再由該中心資源簇轉(zhuǎn)發(fā)給目標資源簇，由于每個資源簇都連接多個星形，和多個中心資源簇相連，所以存在多條路徑，可設計算法選擇最優(yōu)線路，該文算法只任意選擇一條，其他路徑作為備用線路。最后執(zhí)行步驟(2)。

假設存在一個如圖1所示的資源空間，網(wǎng)絡拓撲情況如圖2所示，(0111)屬性區(qū)間對應的資源簇中的某個節(jié)點S接收到用戶的查詢請求“內(nèi)存=3GB，帶寬=300Mbit·s-1”，節(jié)點N得到查詢請求對應的屬性區(qū)間編碼是(1010)，并不是自身所在的資源簇，所以判斷(0111)和(1010)這兩個屬性區(qū)間是否為相似區(qū)間，若發(fā)現(xiàn)不是，將查詢請求轉(zhuǎn)發(fā)給S所在資源簇相連的中心資源簇(0011)和(0100)兩個屬性區(qū)間對應的資源簇，本文中算法選擇了(0011)屬性區(qū)間對應的資源簇，由該資源簇將請求轉(zhuǎn)發(fā)給原點屬性區(qū)間(0000)對應的資源簇，再由原點屬性區(qū)間(0000)對應的資源簇將請求轉(zhuǎn)發(fā)給與目標資源簇(1010)相連的中心資源簇(0010)或(1000)，本文算法選擇(0010)，最后由(0010)屬性區(qū)間對應的資源簇將請求轉(zhuǎn)發(fā)給目標資源簇，在目標資源簇內(nèi)采用洪泛方式查找資源，提供給用戶。整個查詢過程如圖3所示，其中實線箭頭線表示該算法實際使用的線路，虛線箭頭線表示備用線路，箭頭線上的數(shù)字表示查詢步驟的順序。

圖3　查詢算法示例圖

3.2性能分析

本文主要優(yōu)化多屬性查找的跳數(shù)，因此主要對該網(wǎng)絡的多屬性查詢的查找跳數(shù)進行分析，文中所述的查詢跳數(shù)是指從接受請求的節(jié)點所在的資源簇找到目標資源簇所化的跳數(shù)，而資源簇內(nèi)部的洪泛查找不予考慮。

由上述查找算法可看出，當目標資源簇就是接受請求節(jié)點所在的資源簇時，查詢跳數(shù)為0，當目標資源簇與接受查詢請求節(jié)點所在的資源簇在同一個星形結(jié)構(gòu)中，且其中有一個是中心資源簇，或其中一個資源簇對應的屬性區(qū)間是原點屬性區(qū)間，而另一個資源簇對應的屬性區(qū)間是邊緣區(qū)間時，則查詢跳數(shù)為1。當目標資源簇與接受查詢請求的節(jié)點所在的資源簇在同一個星形結(jié)構(gòu)中，且均不為中心資源簇，或兩個資源簇對應的屬性區(qū)間都為邊緣區(qū)間，且其中沒有原點屬性區(qū)間時，查詢跳數(shù)為2，當目標資源簇對應的屬性區(qū)間與接受查詢請求節(jié)點所在資源簇對應的屬性區(qū)間中有一個是邊緣區(qū)間且不為原點屬性區(qū)間，而另一個不是邊緣區(qū)間，則查詢跳數(shù)為3，最復雜的情況就是如示例所示的情況，查詢跳數(shù)為4。

這些查詢跳數(shù)情況不僅針對二維資源空間有效，對于一個n維的資源空間，同樣如此，因該文的查詢算法相當于從一個n維空間的單元子空間出發(fā)，對某一維作投影，得到本文所述的邊緣區(qū)間，然后轉(zhuǎn)發(fā)給原點屬性區(qū)間，由原點屬性區(qū)間轉(zhuǎn)發(fā)給目標區(qū)間在某一維度的投影,即邊緣區(qū)間，再由該邊緣區(qū)間轉(zhuǎn)發(fā)給目標區(qū)間，因此，該文提出的算法的最大查詢跳數(shù)是θ(4)級的，而文獻[10]中設計的系統(tǒng)的最大查詢跳數(shù)是θ(2n)級，其中n代表屬性維度,得到了優(yōu)化。

4實驗

實驗環(huán)境為CPU主頻3.40GHz，內(nèi)存2GB，Linux操作系統(tǒng)，JDK1.6，在1.0.5版本的PeerSim上用Java實現(xiàn)的一個模擬環(huán)境。

該文實驗的目的在于檢測網(wǎng)絡最大查詢跳數(shù)，并與文獻[10]中的MAMSO系統(tǒng)的最大查詢跳數(shù)進行對比。實驗中，網(wǎng)絡節(jié)點數(shù)分別為1000個，3 000個，5 000個，7 000個，9 000個和11 000個，在每種網(wǎng)絡規(guī)模下，屬性種類數(shù)分別有2種，3種，4種和5種，每個屬性分8個值區(qū)間，每組實驗做10次，取平均值，圖4是在該文設計的網(wǎng)絡結(jié)構(gòu)下的結(jié)果圖，圖5是MAMSO系統(tǒng)下的結(jié)果圖，由圖4可知，網(wǎng)絡規(guī)模和屬性種類數(shù)都對最大查詢跳數(shù)沒有影響，最大查詢跳數(shù)始終為4跳。由圖5可知，在MAMSO系統(tǒng)中，網(wǎng)絡規(guī)模對于最大查詢跳數(shù)沒有影響，但最大查詢跳數(shù)隨著屬性種類數(shù)變化，是屬性種類數(shù)量的2倍。對比圖4和圖5所示的實驗結(jié)果可知，該文中的系統(tǒng)將最大查詢跳數(shù)從 級降低到了 ，實現(xiàn)了優(yōu)化。

圖4　該文系統(tǒng)實驗結(jié)果圖

圖5　該文系統(tǒng)實驗結(jié)果圖

5結(jié)束語

該文設計了一個多星型結(jié)構(gòu)的混合P2P網(wǎng)絡，支持多屬性查找，提出了邊緣屬性區(qū)間和相似屬性區(qū)間等概念，設計了資源查找算法，成功將查詢最大跳數(shù)降到了常數(shù)級。但是，當系統(tǒng)中的屬性維度較多，每個維度上屬性值區(qū)間數(shù)較多時，就會產(chǎn)生較多的邊緣屬性區(qū)間，由于所有的邊緣屬性區(qū)間對應的資源簇都會和原點屬性區(qū)間對應的資源簇直接相連，因此就會大幅增加網(wǎng)絡連接，同時增加原點屬性區(qū)間對應資源簇節(jié)

點的負載?？赏ㄟ^進一步細化邊緣屬性區(qū)間的定義，來減少邊緣屬性區(qū)間的數(shù)量，從而優(yōu)化整個系統(tǒng)網(wǎng)絡。

參考文獻

[1]StoicaI，MorrisR，KargerDetal.Chord:Ascalablepeer-to-peerlookupserviceforInternetapplications[C].SanDiego,CA:AcmSigcomm2001Conference, 2001.

[2]RatnasamyS，F(xiàn)rancisP，HandleyM，etal.Ascalablecontent-addressablenetwork[C].SanDiego,CA:AcmSigcomm2001Conference, 2001.

[3]JinHai，NingXiaomin.Improvingsearchinpeer-to-peerliteraturesharingsystemsviasemanticsmallworld[C].Napoli,Italy: 2007 15thEuromicroInternationalConferenceonParallelDistributedandNetwork-basedProcessing，2007.

[4]QuWenyu,ZhouWanlei,KitsuregawaM.Sharablefilesearchinginunstructuredpeer-to-peersystems[J].JournalofSupercomputing,2010,51(2): 149-66.

[5]MirtaheriSL,SharifiM.Anefficientresourcediscoveryframeworkforpureunstructuredpeer-to-peersystems[J].ComputerNetworks，2014,59(3): 213-226.

[6]AdityaKurve,ChristopherGriffin,DavidJMiller,etal.Optimizingclusterformationinsuper-peernetworksvialocalincentivedesign[J].Peer-to-PeerNetworkingandApplications,2015,8(1):1-21.

[7]BeverlyYangB,Garcia-MolinaH.Designingasuper-peernetwork[C].Bangalore,India:Proceedings19thInternationalConferenceonDataEngineering,2003.

[8]WatanabeK,HayashibaraN,TakizawaM.Asuperpeer-basedtwo-layerP2PoverlaynetworkwiththeCBFstrategy[C].Vienna,Australia: 2007 5thInternationalConferenceonComplexIntelligentandSoftwareIntensiveSystems,2007.

[9]PapadakisHarris,TrunfioPaolo,TaliaDomenico.DesignandimplementationofahybridP2P-basedgridresourcediscoverysystem[C].Heraklion,Greece:JointWorkshoponMakingGridsWorks, 2007.

[10]YuYoufu,LaiHuanchou.Asemi-strucuredoverlayformulti-attributerangequeriesincloudcomputing[C].HongKong,China:IEEE13thInternationalConferenceonComputationalScienceandEngineering,2010.

[11]LaiKuanchou,YuYoufu.Ascalablemulti-attributehybridoverlayforrangequeriesonthecloud[J].InformationSystemFontier,2012(14):895-908.

A Hybrid P2P Overlay for Multi-attribute Queries in Cloud Computing

DUXiaofeng1,CHENShiping2

(1.SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai

20009,China; 2.InformationOffice,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

AbstractTo resolve the multi-attribute queries of cloud resource in cloud computing, a hybrid P2P overlay is proposed in this paper. The overlay is based on the combination of multi-star topology. Multi-attribute queries will be achieved if the normalized cloud resource is deployed to the overlay. In the paper, the algorithm for multi-attribute queries and the performance of the network are described. The overlay is designed to reduce the number of hops in resource searching, so the analysis to the number of hops is the point in the paper. The experimental results show that the number of hops in the overlay is reduced as respected.

Keywordscloud computing; multi-attribute queries; hybrid P2P overlay

收稿日期:2015- 11- 18

基金項目:國家自然科學基金資助項目(61170277, 61472256)；上海市教委科研創(chuàng)新重點基金資助項目(12zz137)；上海市一流學科建設基金資助項目(S1201YLXK)

作者簡介:杜曉鋒(1990-)，男，碩士研究生。研究方向：計算機網(wǎng)絡。陳世平(1964-)，男，教授，博士生導師。研究方向：計算機網(wǎng)絡等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.014

中圖分類號TP391

文獻標識碼A

文章編號1007-7820(2016)07-047-05