劉　秀，李　燁

(上海理工大學 光電信息與計算機工程學院，上海200093)

?

云計算環(huán)境下資源評級的虛擬機部署算法

劉秀，李燁

(上海理工大學 光電信息與計算機工程學院，上海200093)

摘要針對虛擬機(VM)大范圍集群部署時容易引發(fā)數(shù)據(jù)中心(DC)總體負載不均衡、VM部署拒絕率居高不下等問題。提出一種基于資源評級的VM部署算法，根據(jù)構(gòu)建VNF的VM之間的親和關(guān)系、物理機之間的拓撲關(guān)系及鏈路的帶寬，選擇出最適合部署VNF的一臺或多臺物理機(PM)。仿真結(jié)果表明，在資源相同的情況下，該算法較已有算法具有更高的資源均衡度和更低的部署拒絕率。

關(guān)鍵詞云計算；虛擬機部署；負載均衡；拒絕率；資源評級

虛擬機技術(shù)[1-2](VirtualMachine，VM)的出現(xiàn)提高了云計算平臺的資源利用率。但隨著云端VM數(shù)目的增多，減少VM部署時的性能開銷、縮短用戶等待時間、利用有限的資源部署更多的VM等問題，成為虛擬機快速部署時面臨的新挑戰(zhàn)。

針對上述問題，運營商和學者提出了多種部署算法。大多數(shù)算法選擇將VM部署在性能最優(yōu)的物理機(PhysicalMachine，PM)上，由于不同用戶對負載指標要求的差異[3]，采用不同的優(yōu)化目標，比如減短用戶響應(yīng)時間、降低部署資源開銷等。文獻[4]提出的iVDA算法根據(jù)底層物理資源容量和動態(tài)負載的映射關(guān)系來選擇宿主機，減少VM部署過程中模板鏡像復(fù)制時間，對多VM快速部署效用不明顯。文獻[5]采用改進的遺傳算法使PM物理資源利用達到最大化，但未考慮用戶請求部署的VM之間的約束關(guān)系，不利于VM集群的部署。文獻[6]提出擴展降序最佳適應(yīng)算法，利用初始長度概念，將宿主機和VM資源量化，在減少宿主機的數(shù)量上優(yōu)勢明顯，但會引起宿主PM資源使用不均衡。文獻[7]提出PM-LB算法根據(jù)承載業(yè)務(wù)對資源依賴程度不同設(shè)定資源權(quán)重向量，計算待部署VM與PM性能向量的相對距離，選擇最近的PM作為宿主機。算法具有較強的業(yè)務(wù)靈活性，但沒有考慮VM之間的業(yè)務(wù)關(guān)聯(lián)性，不利于NFV的構(gòu)建。

本文提出一種基于云資源評級的VM部署算法RRPA，根據(jù)構(gòu)建VNF的VM的親和關(guān)系、PM拓撲關(guān)系選擇出最適合部署VNF的若干臺PM。算法旨在提升VM集群部署成功率以及DC資源均衡度。

1云平臺部署模型

云平臺將地理位置分散的、異構(gòu)的PM資源集中起來[8]，根據(jù)功能不同可分為不同種類的云。本文采用的VM部署模型是計算云平臺上一種常見的金字塔結(jié)構(gòu)，如圖1所示。計算云由若干數(shù)據(jù)中心(DataCenter，DC)和電信云編排器(CarrierCloudOrchestrator，CCO)組成。CCO作為調(diào)度中心，主要用于數(shù)據(jù)處理和存儲，一般由多個DC共享。DC是一個邏輯概念，是由PM組成的計算機系統(tǒng)和PM之間的通信系統(tǒng)。每個DC包含一個或多個虛擬機管理器(VMManager，VMM)。

圖1　云平臺部署模型

CCO存有調(diào)度范圍內(nèi)所有DC的拓撲關(guān)系，包括DC外聯(lián)路由器個數(shù)、鏈路帶寬等參數(shù)，并保存DC內(nèi)所有PM的4種主要資源：CPU、內(nèi)存、磁盤空間及網(wǎng)卡帶寬。除此之外，CCO中也保存有VM規(guī)格參數(shù)表。VM規(guī)格參數(shù)由VM所需資源種類和大小組成。按照資源規(guī)格占用比例不同將VM分類，如存儲VM磁盤容量大，用于轉(zhuǎn)發(fā)信令的VM所需CPU個數(shù)相對較多等。

VMM是PM上的應(yīng)用程序，當收到CCO下發(fā)的策略指令后，VM的創(chuàng)建、刪除、遷移以及資源的分配或釋放都由VMM來決策。CCO是系統(tǒng)的大腦，VMM是系統(tǒng)的中心樞紐，PM節(jié)點整個系統(tǒng)的基礎(chǔ)，不僅為VM創(chuàng)建提供軟件技術(shù)支持和底層硬件資源支持，也是VM啟動和運行的載體[9-11]。

2基于資源評級的虛擬機部署算法

在分布式系統(tǒng)[12]中，選擇放置VM的宿主PM，不僅要考慮宿主PM資源是否充足，還有對部署位置、資源依賴程度等的要求。RRPA算法根據(jù)各VM的親和關(guān)系將其分成若干簇，并根據(jù)各種資源對VM上承載業(yè)務(wù)的依賴性計算出PM和DC的資源評級值，評級值越高可用資源越多，資源使用越均衡。

2.1基于親和關(guān)系的VM聚簇

設(shè)用戶請求構(gòu)建一個VNF，用一組VM表示，記為(vm1,vm2,…,vmi)。VM之間的約束關(guān)系是一種業(yè)務(wù)屬性，隨著VNF的功能不同而變化。用(x1,x2,…,xi)表示VM組中某個VM與其他VM之間的親和關(guān)系，其中xi∈{-1,0,1}。xi=-1表示VMi與該VM屬性相斥，不能部署在同一PM上；xi=1表示VMi與該VM屬性相合，屬性相合的VM之間具有較高的通信流量，部署在同一PM上可以提高VM的工作效率；xi=0表示VMi與VM親和關(guān)系不確定。例如對于一個VM組{vm1,vm2,vm3,vm4,vm5}，其中vm1與vm2互斥，vm3與vm5屬性相合，vm4與vm5屬性相合，考慮資源均衡以及VM屬性，可以將VM組分為三簇：{vm1}；{vm2}；{vm3,vm4,vm5}。

2.2DC評級

DC評級采用DC絕對剩余資源可用度與相對剩余資源可用度共同描述，定義如下

DCR=DCRabsolute+DCRrelative

(1)

(2)

(3)

(4)

(5)

(2)相對剩余資源可用度量化定義為

DCRrekuive=(1-UsagePM)×Ravg/Rdev

(6)

其中，

UsagePM=Numuse/NumDC

(7)

(8)

(9)

相對剩余資源可用度取決于待部署的VNF對資源的需求，UsagePM為將VM組按照約束關(guān)系聚簇后，所需最少的PM數(shù)占DC內(nèi)PM數(shù)的比例；Utilizationj為DC內(nèi)PM總資源減去VNF所需資源后的剩余可用資源；Ravg是資源平均值，nres是算法中評估的資源種類；ndev是所有資源可用度絕對偏差。DCR的大小反應(yīng)了DC的資源剩余和NFV對DC資源均衡利用的影響。DC內(nèi)剩余資源越多，資源利用越平均，DCR越大。

2.3PM資源均衡度評級

VM聚簇部署時，選擇宿主PM時除了考慮資源是否充足之外的另一個重要因素是資源使用是否均衡，定義PM資源均衡度評級量化公式(PMResourceLevelingRating，PRLR)如下

(10)

2.4宿主PM的選擇

CCO將用戶請求的VM組按照聚簇規(guī)則重組為若干VM簇，并計算出調(diào)度范圍內(nèi)的所有DC的DCR和每個DC內(nèi)PM的PRLR。部署VM簇時，選擇DCR高的DC和DC內(nèi)PRLR值低的PM進行部署，更PM的剩余資源Utilization。若選擇的DC內(nèi)所有PM資源都不足以提供該VM簇部署所需資源，將VM簇拆分成單個VM，并盡可能的將同一用戶請求的VM部署在同一是相鄰的PM上，以減少通信鏈路跳數(shù)、縮短用戶響應(yīng)時間、降低功率消耗。

3仿真分析

采用離散事件機理的云仿真平臺，該平臺提供圖形化的界面配置，利用網(wǎng)絡(luò)建模的方式來提高客戶仿真構(gòu)建、運行與分析效率。

3.1算法性能指標

定義VM部署拒絕率和DC資源均衡度兩個指標衡量算法性能。

(1)VM部署拒絕率

Rrej=1-∑vmsuccess/∑vmrequest

(11)

其中，vmsuccess為部署成功的VM個數(shù)，vmrequest為待部署VM個數(shù)。Rrej越小，VM部署成功率越高。

(2)資源不均衡度。由于頻繁申請或釋放資源，會造成資源碎片，導(dǎo)致雖然總的空閑資源滿足要求，但無法申請到用戶所需大小的資源。定義DC內(nèi)平均資源利用率和資源利用標準差為

(12)

(13)

式中，n為DC內(nèi)PM數(shù)目；Utilizationi為第i臺PM的資源利用率。σ為資源不均衡度，其取值越大，資源利用越不均衡。

3.2不同算法性能對比

一個計算云由調(diào)度中心CCO和26臺PM構(gòu)成，PM之間通過路由器連接，VMM運行在其中一臺PM上。PM資源規(guī)格及數(shù)目如表1所示，用戶請求的虛擬機種類及數(shù)目比例如表2所示，VM之間兩兩親和。在仿真場景上分別添加50,100,150,200和250個VM，輸出各場景下VM部署的拒絕率以及DC資源均衡度。

表1　可用資源信息

表2　虛擬機模板種類

與GREED、POLLING以及ALUScore算法進行對比研究。GREED和POLLING是典型的裝箱問題啟發(fā)式算法，區(qū)別在于前者是First-Fit式，按照PM信息在調(diào)度中心保存的順序開始部署，這樣最大程度利用了排位靠前的PM的資源。POLLING算法依序詢問每一個PM可用剩余資源，VM部署結(jié)束后詢問下一個PM。ALUScore算法利用PM各類資源利用率K次方和計算出PM的資源可用度，根據(jù)資源可用度大小從高到低依次選擇。RRPA算法不考慮資源依賴對資源均衡度及部署拒絕率的影響，資源權(quán)重向量取值WT=(1/3,1/3,1/3)T，實驗結(jié)果如圖2和圖3所示。

圖2　DC資源不均衡度比較

由圖2可見，當部署VM數(shù)目較少、PM資源充足時，RRPA算法優(yōu)勢不明顯，但隨著部署VM數(shù)目增多，PM可用資源逐漸減少，DC內(nèi)資源不均衡度顯著低于其它3種算法。GREED算法的DC資源不均衡度最為嚴重，這是因為其First-Fit特性使得排位靠前的PM資源使用達到最大閾值。當部署VM的數(shù)目增加到一定數(shù)目時，資源不均衡度的變化會逐漸趨于平緩。POLLING算法按照PM排位依序選擇部署的宿主機，當部署VM數(shù)目較少時，有良好的資源均衡度。但受VM之間拓撲約束與親和約束的影響，均衡度隨VM部署個數(shù)增多而逐漸降低。ALUScore算法完全根據(jù)PM剩余資源多少部署VM，當VM增多時，資源浪費明顯，資源不均衡度急速上升。

圖3　VM部署拒絕率比較

圖3顯示RRPA算法的部署拒絕率遠低于其它算法。由于RRPA算法的聚簇部署特性，將屬性相近的VM聚簇部署，減少了因?qū)傩韵喑舛鸬牟渴鹗?。同時，聚簇部署還可以減少部署空間搜索，提高網(wǎng)絡(luò)寬帶利用率。

3.3資源權(quán)重對算法性能的影響

驗證VM資源依賴對DC內(nèi)資源均衡度及VM部署拒絕率的影響，表2中VM請求各類型VM占有比例及資源需求，結(jié)合經(jīng)驗值取資源權(quán)重向量WT=(0.42,0.38,0.2)T，實驗結(jié)果圖4和圖5所示。

圖4　DC資源不均衡度比較

由圖4可見，在部署資源充足的情況下，加權(quán)RRPA算法與不加權(quán)RRPA算法相比，DC內(nèi)資源不均衡度低至少1%。隨著部署資源的減少，不加權(quán)算法的資源不均衡度波動較大，而加權(quán)算法相對穩(wěn)定。

圖5　VM部署拒絕率比較

圖5顯示資源權(quán)重對VM部署成功率的影響?？傮w來說，加權(quán)后部署的資源均衡度更高，從而降低了VM部署拒絕率。

4結(jié)束語

針對如何提高VM部署成功率并均衡DC內(nèi)資源的問題，提出一種基于資源評級的VM部署算法。利用VM約束關(guān)系聚類部署，壓縮資源占用空間，減少資源消耗；利用資源對DC及PM評級排序，使DC內(nèi)資源均衡使用，并提高部署成功率。仿真結(jié)果驗證了算法的有效性，如果將RRPA靜態(tài)算法與VM遷移的動態(tài)算法結(jié)合，將有可能大幅降低PM使用數(shù)目，對節(jié)省硬件和軟件資源使用起到關(guān)鍵作用。

參考文獻

[1]ZhiyunRen,XiaoSong.Avirtualmachinedeploymentapproachusingknowledgecurvesincloudsimulation[C].HongKong:IndustrialInformatics, 2012.

[2]UhligR,NeigerG,RodgersD,etal.IntelVirtualizationTechnology[J].Computer, 2005(38): 48-56.

[3]GuoYudong,WangXiaorui,WeiyuDong,etal.Acooperativemodelvirtual-machinemonitorbasedonmulti-coreplatform[C].Xi’an:FutureComputerandCommunication, 2010.

[4]HuangFeng,LiDongsheng.Efficientvirtualmachinedeploymentinlargescaleresourceenvironment[J].ParallelandDistributedSystems, 2012(72): 752-757.

[5]ZhongH,TaoK,ZhangXJ.Anapproachtooptimizedresourceschedulingalgorithmforopen-sourcecloudsystem[C].Beijing:TheFifthChinaGridAnnualConference,2010.

[6]馮少沖,邸彥強,朱元昌,等.IaaS云計算中虛擬機部署算法研究[J].華中科技大學學報：自然科學版, 2012，40(S1): 359-364.

[7]楊星,馬自堂,孫磊. 云環(huán)境下基于性能向量的虛擬機部署算法[J].計算機應(yīng)用, 2012(1):16-19.

[8]師雪霖,徐恪. 云虛擬機資源分配的效用最大化模型[J].計算機學報, 2013,36(2): 252-262.

[9]魏亮,黃韜,陳建亞,等.基于工作負載預(yù)測的虛擬機整合算法[J].電子與信息學報,2013,35(6):1271-1276.

[10] 張蓓蓓,陳寧江,胡丹丹. 基于BP神經(jīng)網(wǎng)絡(luò)負載預(yù)測的虛擬機部署策略[J].華中科技大學學報:自然科學版, 2012,40(S1):120-123.

[11]LaurikainenR,LaitinenJ,LenhtovuoriP,etal.Improvingtheefficiencyofdeployingvirtualmachinesinacloudenvironment[J].CloudandServiceComputer，2012(2): 232-239.

[12] 周舟,胡志剛.云環(huán)境下面向能耗降低的虛擬機部署算法[J].華南理工大學學報:自然科學版, 2014,42(5):109-114.

[13] 李強,郝沁汾,肖利民,等. 云計算中虛擬機放置的自適應(yīng)管理與多目標優(yōu)化[J]. 計算機學報,2011,34(12):2253-2264.

Algorithm for Virtual Machine Deployment in Cloud Computing Environment Based on Resource Rating

LIUXiu,LIYe

(SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,

Shanghai200093,China)

AbstractMany problems may occur during a large scale deployment of VMs, such as overall load imbalance in data center and high VM deployment rejection rate. This paper proposes a resources rating based placement algorithm (RRPA). By considering the affinity relationship between VMs, the topological relationship between PMs, and the connection link bandwidth, one or several PMs mostly appropriate for VNFs deployment are chosen. The simulation results show that RRPA has a higher degree of resource equilibrium and lower rejection rate of deployment than existing methods under the same condition.

Keywordscloud computing; VM deployment; load balance; rejection rate; resources rating

收稿日期:2015- 11- 18

基金項目:滬江基金資助項目(C14002)

作者簡介:劉秀(1991-)，女，碩士研究生。研究方向：云計算。李燁(1974-)，男，博士，高級工程師。研究方向：信息融合等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.015

中圖分類號TP391

文獻標識碼A

文章編號1007-7820(2016)07-051-04