杜曉鋒，陳世平

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

?

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

杜曉鋒1，陳世平2

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

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

關鍵詞云計算；多屬性查找；混合對等網絡

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

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

1相關研究

支持云資源查找的P2P網絡按照結構劃分通常可分為4類：結構化P2P網絡、非結構化P2P網絡、分層P2P網絡和混合結構化P2P網絡。

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

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

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

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

2系統(tǒng)設計

2.1資源編碼表

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

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

圖1　二維屬性資源編碼表

2.2網絡拓撲結構

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

圖2　網絡拓撲圖

2.3邊緣區(qū)間

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

2.4相似區(qū)間

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

3資源查找

3.1多屬性查找算法

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

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

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

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

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

圖3　查詢算法示例圖

3.2性能分析

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

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

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

4實驗

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

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

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

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

5結束語

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

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

參考文獻

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

[2]RatnasamyS，FrancisP，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-)，男，碩士研究生。研究方向：計算機網絡。陳世平(1964-)，男，教授，博士生導師。研究方向：計算機網絡等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.014

中圖分類號TP391

文獻標識碼A

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