云計(jì)算環(huán)境下資源評(píng)級(jí)的虛擬機(jī)部署算法

劉　秀，李　燁

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

?

云計(jì)算環(huán)境下資源評(píng)級(jí)的虛擬機(jī)部署算法

劉秀，李燁

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

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

關(guān)鍵詞云計(jì)算；虛擬機(jī)部署；負(fù)載均衡；拒絕率；資源評(píng)級(jí)

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

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

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

1云平臺(tái)部署模型

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

圖1　云平臺(tái)部署模型

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

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

2基于資源評(píng)級(jí)的虛擬機(jī)部署算法

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

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

設(shè)用戶請(qǐng)求構(gòu)建一個(gè)VNF，用一組VM表示，記為(vm1,vm2,…,vmi)。VM之間的約束關(guān)系是一種業(yè)務(wù)屬性，隨著VNF的功能不同而變化。用(x1,x2,…,xi)表示VM組中某個(gè)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)系不確定。例如對(duì)于一個(gè)VM組{vm1,vm2,vm3,vm4,vm5}，其中vm1與vm2互斥，vm3與vm5屬性相合，vm4與vm5屬性相合，考慮資源均衡以及VM屬性，可以將VM組分為三簇：{vm1}；{vm2}；{vm3,vm4,vm5}。

2.2DC評(píng)級(jí)

DC評(píng)級(jí)采用DC絕對(duì)剩余資源可用度與相對(duì)剩余資源可用度共同描述，定義如下

DCR=DCRabsolute+DCRrelative

(1)

(2)

(3)

(4)

(5)

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

DCRrekuive=(1-UsagePM)×Ravg/Rdev

(6)

其中，

UsagePM=Numuse/NumDC

(7)

(8)

(9)

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

2.3PM資源均衡度評(píng)級(jí)

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

(10)

2.4宿主PM的選擇

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

3仿真分析

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

3.1算法性能指標(biāo)

定義VM部署拒絕率和DC資源均衡度兩個(gè)指標(biāo)衡量算法性能。

(1)VM部署拒絕率

Rrej=1-∑vmsuccess/∑vmrequest

(11)

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

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

(12)

(13)

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

3.2不同算法性能對(duì)比

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

表1　可用資源信息

表2　虛擬機(jī)模板種類

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

圖2　DC資源不均衡度比較

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

圖3　VM部署拒絕率比較

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

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

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

圖4　DC資源不均衡度比較

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

圖5　VM部署拒絕率比較

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

4結(jié)束語

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

參考文獻(xià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]馮少?zèng)_,邸彥強(qiáng),朱元昌,等.IaaS云計(jì)算中虛擬機(jī)部署算法研究[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012，40(S1): 359-364.

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

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

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

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

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

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

[13] 李強(qiáng),郝沁汾,肖利民,等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào),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

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

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

doi:10.16180/j.cnki.issn1007-7820.2016.07.015

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

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