薛弘曄，朱天磊，羅香玉，馮 健

(西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710054)

基于資源需求分布特征的異構(gòu)云環(huán)境虛擬機(jī)放置算法

薛弘曄，朱天磊，羅香玉*，馮 健

(西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710054)

針對(duì)異構(gòu)云環(huán)境中的虛擬機(jī)放置(VMP)問題，提出一種基于虛擬機(jī)資源需求分布特征的放置算法(RDDFPA)。首先，建立基于CPU資源和內(nèi)存資源比例系數(shù)的虛擬機(jī)需求和物理機(jī)配置描述方法，并根據(jù)該比例系數(shù)對(duì)所有虛擬機(jī)進(jìn)行排序；其次，通過分析虛擬機(jī)需求與物理機(jī)配置各自在CPU資源和內(nèi)存資源比例方面的關(guān)系，確定比例分界點(diǎn)，完成虛擬機(jī)集合的劃分，每個(gè)虛擬機(jī)子集合的規(guī)模反映出對(duì)相匹配的不同配置物理機(jī)的需求比例;最后，利用啟發(fā)式算法如首次適應(yīng)(First Fit)算法完成虛擬機(jī)子集合在相匹配配置的物理機(jī)子集合上的放置。理論分析和仿真實(shí)驗(yàn)結(jié)果表明，與采用任意單一配置的物理機(jī)總數(shù)量相比，所提算法所需物理機(jī)的總臺(tái)數(shù)減少了2%～17%。RDDFPA能夠根據(jù)虛擬機(jī)資源需求分布的不同，確定各類配置物理機(jī)的數(shù)量，高效完成虛擬機(jī)的放置，在提高資源利用率的同時(shí)，降低了系統(tǒng)能耗。

云計(jì)算；數(shù)據(jù)中心；虛擬機(jī)放置；異構(gòu)云環(huán)境；能源效率

0 引言

隨著云服務(wù)市場(chǎng)的迅速發(fā)展，數(shù)據(jù)中心能耗問題愈發(fā)突出[1]。2015年，我國(guó)數(shù)據(jù)中心總量已超40萬個(gè)，年耗電量超過全社會(huì)用電量的1.5%[2]。提高數(shù)據(jù)中心服務(wù)器資源利用率，降低能耗，成為了當(dāng)前數(shù)據(jù)中心亟待解決的問題[3]。解決該問題的一個(gè)常見手段是利用虛擬化技術(shù)進(jìn)行服務(wù)整合：也就是把服務(wù)請(qǐng)求進(jìn)行整合，減少活動(dòng)物理機(jī)數(shù)量，從而提高資源利用率，減少能源消耗[4]。由此產(chǎn)生了虛擬機(jī)放置(Virtual Machine Placement, VMP)問題：根據(jù)一定的方法和策略，把虛擬機(jī)(Virtual Machine, VM)放置在最適合的物理機(jī) (Physical Machine, PM)中。

目前對(duì)于VMP的研究，一般是在假設(shè)數(shù)據(jù)中心物理機(jī)完全同構(gòu)的前提下，僅著眼于改進(jìn)放置算法本身。有些研究雖然考慮了物理機(jī)異構(gòu)，但是沒有分析虛擬機(jī)資源需求分布特征與異構(gòu)云環(huán)境之間的關(guān)聯(lián)?，F(xiàn)實(shí)生活中，數(shù)據(jù)中心往往擁有多種物理機(jī)資源配置，是一個(gè)異構(gòu)的云環(huán)境，而虛擬機(jī)需求的分布特征也多種多樣。虛擬機(jī)需求分布的變化，反映到異構(gòu)物理機(jī)上就會(huì)使得所需異構(gòu)物理機(jī)數(shù)量也發(fā)生變化。

針對(duì)異構(gòu)云環(huán)境下的虛擬機(jī)放置問題，本文依據(jù)虛擬機(jī)資源需求分布特征的變化并將其與異構(gòu)物理機(jī)的配置比例關(guān)系相聯(lián)系，提出一種分兩步進(jìn)行的基于虛擬機(jī)資源需求分布特征的放置算法(Resource Demand Distribution Feature based Placement Algorithm, RDDFPA)。首先，利用異構(gòu)物理機(jī)資源配置和虛擬機(jī)資源需求分布特征的比例關(guān)系對(duì)虛擬機(jī)需求集合進(jìn)行劃分，虛擬機(jī)需求子集合的變化使得不同配置物理機(jī)產(chǎn)生數(shù)量變化；其次，利用啟發(fā)式算法，在對(duì)應(yīng)配置物理機(jī)上，對(duì)劃分后的虛擬機(jī)需求進(jìn)行放置。實(shí)驗(yàn)結(jié)果表明，相比直接在同構(gòu)物理機(jī)上執(zhí)行啟發(fā)式算法進(jìn)行放置，應(yīng)用該算法在異構(gòu)云環(huán)境下進(jìn)行的虛擬機(jī)放置使用的活動(dòng)物理機(jī)數(shù)量更少，資源利用率更高，能耗更低。

1 現(xiàn)有VMP研究

VMP的難點(diǎn)在于它是一種NP-Hard問題，甚至是NP-完全問題，難以在多項(xiàng)式時(shí)間內(nèi)解決[5]。根據(jù)云環(huán)境的同構(gòu)與異構(gòu)來對(duì)現(xiàn)有研究進(jìn)行分類。

在同構(gòu)云環(huán)境基礎(chǔ)下，主要以改進(jìn)放置算法本身為主。常用算法有兩種，即啟發(fā)式算法和元啟發(fā)式算法。

啟發(fā)式算法的特點(diǎn)在于它可以在物理機(jī)和虛擬機(jī)數(shù)量較多，求最優(yōu)解難度較大、耗時(shí)較長(zhǎng)的情況下，以較小的開銷找到一個(gè)相對(duì)合理的近似解[6]。經(jīng)典的算法有首次適應(yīng)(First Fit)算法、最佳適應(yīng)(Best Fit)算法等[7]。改進(jìn)算法如Lee等[8]提出的兩個(gè)具有節(jié)能效果的啟發(fā)式服務(wù)整合算法，其目的是最大化物理機(jī)的利用率，從而減少活動(dòng)物理機(jī)數(shù)量，節(jié)約能耗。

元啟發(fā)式算法的特點(diǎn)在于該類算法能較好地找出全局最優(yōu)解，但是其時(shí)間復(fù)雜度較高，導(dǎo)致可擴(kuò)展性和實(shí)時(shí)性較差[6]。較為常見的元啟發(fā)式算法有蟻群算法：Gao等[9]把同構(gòu)環(huán)境下虛擬機(jī)的放置問題看作一個(gè)多目標(biāo)優(yōu)化問題，提出了一種多目標(biāo)蟻群算法，以降低系統(tǒng)的能源消耗、提高物理機(jī)的資源利用率。還有諸如遺傳算法[10]和模擬退火算法[11]等。

針對(duì)異構(gòu)云環(huán)境，目前的研究相對(duì)較少。Beloglazov等[12]考慮了異構(gòu)性問題，提出一個(gè)能源感知的資源分配啟發(fā)式算法，將虛擬機(jī)放置在一個(gè)使系統(tǒng)能源消耗增加最少的物理機(jī)上。但該算法只考慮CPU需求，并沒有考慮所需資源的多維性。周東清等[4]考慮了資源的多維性，提出一個(gè)啟發(fā)式算法，在異構(gòu)物理機(jī)上利用權(quán)重來分配虛擬機(jī)，同時(shí)保持一定的負(fù)載均衡。Shi等[13]考慮了服務(wù)器的異構(gòu)性，提出了按照物理機(jī)不同資源配比進(jìn)行虛擬機(jī)分配的啟發(fā)式算法。這些研究都沒有考慮到虛擬機(jī)需求的分布變化，并將其與異構(gòu)物理機(jī)的配置或數(shù)量相聯(lián)系。

2 異構(gòu)云環(huán)境下資源需求分布的具體描述

2.1 虛擬機(jī)資源需求分布的具體描述

虛擬機(jī)需求集合由一系列的虛擬機(jī)需求組成，定義為Svm。Svm中的每個(gè)虛擬機(jī)需求對(duì)不同類型資源需求往往具有偏向性。按照偏向性，可把集合中的虛擬機(jī)劃分為兩類：CPU處理能力偏重的計(jì)算密集型和內(nèi)存空間偏重的數(shù)據(jù)密集型。假設(shè)第k個(gè)虛擬機(jī)包括兩種資源需求：CPU處理能力CPUvmk和內(nèi)存空間MEMvmk，CPU處理能力的單位為每秒百萬條指令(Million Instructions Per Second, MIPS)，內(nèi)存空間(MEMory, MEM)的單位為GB。虛擬機(jī)需求配置比例計(jì)算公式為：

ratevmk=CPUvmk/MEMvmk

(1)

根據(jù)每個(gè)虛擬機(jī)的配置比例ratevm，從小到大對(duì)Svm內(nèi)的虛擬機(jī)需求進(jìn)行排序，便得到一個(gè)排序后的虛擬機(jī)資源需求分布序列sortedListvm={vm1,vm2,…,vmn}。

2.2 異構(gòu)云環(huán)境的具體描述

本文中，異構(gòu)云環(huán)境由兩種具有不同資源偏向性且和虛擬機(jī)資源需求分布相對(duì)契合的物理機(jī)組成。結(jié)合實(shí)際，選出兩種物理機(jī)構(gòu)成異構(gòu)物理機(jī)組pairpm={pmleft,pmright}。其中pmleft為數(shù)據(jù)密集型，配置比例為：

ratepmleft=CPUpmleft/MEMpmleft

(2)

另一種物理機(jī)pmright為計(jì)算密集型，配置比例ratepmright大于ratepmleft。

2.3 虛擬機(jī)資源需求分布的跨度分類

虛擬機(jī)資源需求分布的變化，體現(xiàn)為序列sortedListvm分布范圍的不同，在以資源配置的比例為坐標(biāo)的數(shù)軸上，即表現(xiàn)為從ratevm1至ratevmn的區(qū)間長(zhǎng)度。依據(jù)區(qū)間長(zhǎng)度在數(shù)軸上做橢圓，來表示sortedListvm的分布范圍，本文稱其為分布跨度。而根據(jù)物理機(jī)資源配置的比例也可以在該數(shù)軸上標(biāo)識(shí)異構(gòu)物理機(jī)組的位置。至此，數(shù)軸就可以直觀地展示出sortedListvm和pairpm的關(guān)系。根據(jù)虛擬機(jī)需求分布可能出現(xiàn)的情況，并結(jié)合異構(gòu)物理機(jī)組的配置比例，如圖1所示，大體可以使用四種跨度情況來囊括。

圖1 跨度情況分類Fig. 1 Span situation classification

2.4 問題描述

在本文提出的算法中，通過研究異構(gòu)物理機(jī)組和虛擬機(jī)資源需求分布特征之間的資源比例關(guān)系，在執(zhí)行虛擬機(jī)放置算法之前對(duì)虛擬機(jī)資源需求分布進(jìn)行劃分處理，從而更好地放置虛擬機(jī)，達(dá)到減少活動(dòng)物理機(jī)、節(jié)約能耗的效果。具體問題可以分解為以下幾個(gè)部分：

1)依據(jù)虛擬機(jī)資源需求集合特征和異構(gòu)物理機(jī)組的關(guān)系，判定跨度情況；

2)劃分虛擬機(jī)資源需求集合，使其分別與兩種異構(gòu)物理機(jī)相匹配；

3)在兩種物理機(jī)上分別進(jìn)行虛擬機(jī)放置。

3 算法描述

本文提出的RDDFPA具體可以分為兩大階段：

第一階段 依據(jù)虛擬機(jī)需求分布和物理機(jī)資源配比的關(guān)系，在排序后的sortedListvm上取得一個(gè)劃分點(diǎn)；

第二階段 在取得劃分點(diǎn)后，將劃分后的虛擬機(jī)需求分別在相應(yīng)側(cè)物理機(jī)上使用啟發(fā)式算法進(jìn)行放置。

其中第一階段可以細(xì)分為：比例數(shù)軸的預(yù)處理；確定虛擬機(jī)資源需求分布跨度；獲取虛擬機(jī)序列分界點(diǎn)；判斷劃分點(diǎn)。

3.1 比例數(shù)軸的預(yù)處理

如圖1所示，本文以pmleft的資源比例ratepmleft和pmright的資源比例ratepmright之間的中點(diǎn)作為數(shù)軸的中心點(diǎn)，稱為異構(gòu)物理機(jī)組中心點(diǎn)center。center的作用在于：依據(jù)不同配置的pairpm確定相應(yīng)的center，由此可以界定虛擬機(jī)資源需求的偏向性，即位于center左側(cè)的虛擬機(jī)資源需求為計(jì)算密集型，位于右側(cè)則被認(rèn)為是數(shù)據(jù)密集型。

根據(jù)ratepmleft和ratepmright，在數(shù)軸上標(biāo)識(shí)出pairpm的具體位置，得出比例跨度[ratepmleft,ratepmright]，并依據(jù)它確定數(shù)軸的異構(gòu)物理機(jī)組中心點(diǎn)center。

center的具體取值方式為：center并非數(shù)軸上兩種物理機(jī)之間的距離中點(diǎn)，而是比例中點(diǎn)，此例中center應(yīng)位于1/1處。對(duì)兩側(cè)物理機(jī)的CPU處理能力之和與內(nèi)存空間之和求商，便可得到正確的center比值ratecenter，即使用式(3)計(jì)算:

(3)

3.2 確定虛擬機(jī)資源需求分布跨度

在sortedListvm={vm1,vm2,…,vmn}中，取得首尾兩個(gè)虛擬機(jī)需求的比例ratevm1以及ratevmn，據(jù)此確定sortedListvm在數(shù)軸上的分布跨度為[ratevm1,ratevmn]。將[ratevm1,ratevmn]和pairpm比例跨度[ratepmleft,ratepmright]進(jìn)行對(duì)比，即可確定虛擬機(jī)資源需求分布跨度情況。必須使得pairpm跨度情況為圖1(c)或圖1(d)所示，即pairpm的比例跨度[ratepmleft,ratepmright]需要滿足以下條件：ratevmn>ratecenter或ratecenter>ratevm1。

3.3 跨度情況3下的分界點(diǎn)獲取

(4)

在比例Lsumratevmk與左側(cè)物理機(jī)資源配置比例ratepmleft最為接近或完全相同時(shí)，遍歷停止，并記錄下當(dāng)前vmk的編號(hào)k，也就是左側(cè)虛擬機(jī)需求的分界點(diǎn)POINTleft。

從右側(cè)開始對(duì)sortedListvm進(jìn)行倒序遍歷，以最右側(cè)虛擬機(jī)作為起點(diǎn)vm1，計(jì)算：

(5)

使用與左側(cè)類似方法得到右側(cè)分界點(diǎn)POINTright。

3.4 跨度情況3下的劃分點(diǎn)判斷

當(dāng)取得兩側(cè)分界點(diǎn)后，又面臨兩種可能：分界點(diǎn)相交或不相交。

(6)

在不相交的情況下，兩側(cè)都能達(dá)到各自最佳匹配位置。對(duì)于不相交的序列部分overlapList={vma,…,vmb}，則要判斷它與center的比例ratecenter的關(guān)系，如圖2所示。

圖2 劃分點(diǎn)判定情況分類Fig. 2 Classification of divide point determination situation

①當(dāng)ratevmb≤ratecenter，即overlapList位于center左側(cè)時(shí)，則劃分點(diǎn)Divide應(yīng)定為右側(cè)分界點(diǎn)POINTright；

②當(dāng)ratevma≥ratecenter，即位于center右側(cè)時(shí)，劃分點(diǎn)Divide應(yīng)定為左側(cè)分界點(diǎn)POINTleft；

③當(dāng)ratevma≤ratecenter≤ratevmb時(shí)，則應(yīng)以center的位置作為劃分點(diǎn)Divide。

3.5 跨度情況4下的分界與劃分

跨度情況4下，只需判斷出對(duì)應(yīng)側(cè)虛擬機(jī)序列分界點(diǎn)即可完成劃分處理。還是以左側(cè)為例：獲得的分界點(diǎn)POINTleft位于center左側(cè)時(shí)，使用center作為Divide；當(dāng)分界點(diǎn)POINTleft位于center右側(cè)時(shí)，以此POINTleft作為Divide。

3.6 對(duì)劃分后的序列進(jìn)行放置

判定劃分點(diǎn)Divide后，sortedListvm被分為兩個(gè)子集合。兩個(gè)子集合的資源需求的大小對(duì)應(yīng)了pairpm中相應(yīng)配置物理機(jī)數(shù)量對(duì)比。使用同構(gòu)情況下的啟發(fā)式算法對(duì)Divide左側(cè)的虛擬機(jī)需求子集合在pmleft上進(jìn)行放置， Divide右側(cè)虛擬機(jī)需求子集合在pmright上進(jìn)行放置。至此得到具體的虛擬機(jī)需求放置結(jié)果，得出具體需要的兩種活動(dòng)物理機(jī)數(shù)量。

4 仿真實(shí)驗(yàn)及分析

對(duì)本文提出的RDDFPA性能進(jìn)行評(píng)估實(shí)驗(yàn)，并與不經(jīng)劃分直接在同構(gòu)環(huán)境下進(jìn)行放置的常規(guī)方法進(jìn)行對(duì)比。統(tǒng)一使用First Fit算法作為雙方使用的啟發(fā)式算法。將每10 000個(gè)虛擬機(jī)需求作為一組數(shù)據(jù)，隨機(jī)取20組進(jìn)行實(shí)驗(yàn)。假設(shè)虛擬機(jī)的CPU需求以及MEM需求都在0～8內(nèi)隨機(jī)取值，虛擬機(jī)資源需求分布跨度中點(diǎn)在CPU和MEM資源比例為1∶1的位置。通過調(diào)整資源配置構(gòu)成不同異構(gòu)物理機(jī)組，來模擬sortedListvm和pairpm的不同搭配情況。假設(shè)5組異構(gòu)物理機(jī)組，左側(cè)物理機(jī)稱為A，右側(cè)物理機(jī)稱為B，并逐漸增大每一組資源配置比例之間的差異。5組配置如下：

組合一：

A:CPUleft=8 MIPS,MEMleft=10 GB,rateleft=4∶5

B:CPUright=10 MIPS,MEMright=8 GB,rateright=5∶4

組合二：

A:CPUleft=8 MIPS，MEMleft=12 GB，rateleft=2∶3

B:CPUright=12 MIPS，MEMright=8 GB，rateright=3∶2

組合三：

A:CPUleft=8 MIPS，MEMleft=16 GB，rateleft=1∶2

B:CPUright=16 MIPS，MEMright=8 GB，rateright=2∶1

組合四：

A:CPUleft=8 MIPS，MEMleft=32 GB，rateleft=1∶4

B:CPUright=32 MIPS，MEMright=8 GB，rateright=4∶1

組合五：

A:CPUleft=8 MIPS，MEMleft=40 GB，rateleft=1∶5

B:CPUright=40 MIPS，MEMright=8 GB，rateright=5∶1

其中：CPUleft、MEMleft、rateleft分別代表左側(cè)A的CPU資源、內(nèi)存資源以及配置比例。右側(cè)B相關(guān)符號(hào)意義與A近似。

使用本文提出的RDDFPA進(jìn)行放置，所需要的兩種異構(gòu)物理機(jī)的臺(tái)數(shù)之和，與直接在某一種物理機(jī)上進(jìn)行放置所需要的同構(gòu)物理機(jī)臺(tái)數(shù)對(duì)比如圖3所示。

圖3 物理機(jī)放置結(jié)果比較Fig. 3 Comparison of physical machine placement results

根據(jù)圖3中的數(shù)據(jù)，對(duì)隨機(jī)數(shù)據(jù)集中20組數(shù)據(jù)的結(jié)果取平均值，得出不同異構(gòu)物理機(jī)組合與單一配置物理機(jī)A、B相比節(jié)約的物理機(jī)臺(tái)數(shù)與百分比，來展示實(shí)際算法應(yīng)用的效果，如表1所示。

從組合一到組合三，異構(gòu)物理機(jī)組的CPU和內(nèi)存資源配比從8∶10和10∶8一直擴(kuò)大到8∶16和16∶8。隨著異構(gòu)物理機(jī)組差距增大，優(yōu)化效果也從對(duì)比僅使用A時(shí)節(jié)約大概121臺(tái)，比例約為2%，以及對(duì)比僅使用B時(shí)節(jié)約大概209臺(tái)，比例約為3%，逐漸提升到對(duì)比左右側(cè)均能節(jié)約大概900臺(tái)，節(jié)約比例均約為17%。但是從組合四和組合五中也可以看出，在擴(kuò)大兩側(cè)物理機(jī)資源配比差異時(shí)，優(yōu)化效果并非隨之線性擴(kuò)大，而是逐漸趨于平穩(wěn)，應(yīng)將配置差異限定在一定范圍內(nèi)。

由以上對(duì)比實(shí)驗(yàn)可以看出，本文提出的RDDFPA，在異構(gòu)物理機(jī)的資源配置具有一定差異時(shí)，相比單一配置物理機(jī)較為顯著地減少了活動(dòng)物理機(jī)數(shù)量，同時(shí)節(jié)約了能耗。

表1 不同組合相對(duì)單一配置的實(shí)驗(yàn)結(jié)果Tab. 1 Experimental results of different combinations relative to single configurations

5 結(jié)語(yǔ)

針對(duì)異構(gòu)云環(huán)境下的虛擬機(jī)放置問題，本文提出一種利用變化的虛擬機(jī)資源需求分布特征與異構(gòu)物理機(jī)配置的比例關(guān)系，對(duì)虛擬機(jī)需求進(jìn)行劃分,使得虛擬機(jī)子集合的變化反映為對(duì)應(yīng)異構(gòu)物理機(jī)數(shù)量變化，再對(duì)其放置的方法。實(shí)驗(yàn)結(jié)果表明，所提的算法能夠在異構(gòu)物理機(jī)配置差異較大且虛擬機(jī)資源分布和物理機(jī)資源配比相互較為契合的前提下，有效減少活動(dòng)物理機(jī)的總數(shù)量，達(dá)到較好的優(yōu)化效果。未來可以進(jìn)一步研究在虛擬機(jī)分布的跨度和物理機(jī)配置偏離時(shí)如何避免算法退化的問題。

References)

[1] 谷立靜,周伏秋,孟輝.我國(guó)數(shù)據(jù)中心能耗及能效水平研究[J].中國(guó)能源,2010,32(11):42-45.(GU L J, ZHOU F Q, MENG H. Research on energy consumption and energy efficiency of data center in our country [J]. Energy of China, 2010, 32(11): 42-45.)

[2] 佚名.國(guó)家綠色數(shù)據(jù)中心試點(diǎn)工作方案[J].石油和化工節(jié)能,2015(3):1-4.(ANONYMITY. National green data center pilot program [J]. Petroleum & Chemical Energy Conservation, 2015(3): 1-4.)

[3] 葉可江,吳朝暉,姜曉紅,等.虛擬化云計(jì)算平臺(tái)的能耗管理[J].計(jì)算機(jī)學(xué)報(bào),2012,35(6):1262-1285.(YE K J, WU C H, JIANG X H, et al. Power management of virtualized cloud computing platform [J]. Chinese Journal of Computers, 2012, 35(6): 1262-1285.)

[4] 周東清,佀慶乾.異構(gòu)云平臺(tái)中能源有效的虛擬機(jī)部署研究[J].計(jì)算機(jī)科學(xué),2015,42(3):81-84.(ZHOU D Q, SI Q Q. Energy-efficient virtual machine placement for heterogeneous cloud platform [J]. Computer Science, 2015, 42(3): 81-84.)

[5] AROCA J A, ANTA A F, MOSTEIRO M A, et al. Power-efficient assignment of virtual machines to physical machines [J]. Future Generation Computer Systems, 2016, 54(C): 82-94.

[6] 童俊杰,赫罡,符剛.虛擬機(jī)放置問題的研究綜述[J].計(jì)算機(jī)科學(xué),2016,43(6A):249-254.(TONG J J, HE G, FU G. Research survey of virtual machine placement problem [J]. Computer Science, 2016, 43(6A): 249-254.)

[7] PIRES F L, BARN B. A virtual machine placement taxonomy [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2015: 159-168.

[8] LEE Y C, ZOMAYA A Y. Energy efficient utilization of resources in cloud computing systems [J]. Journal of Supercomputing, 2012, 60(2): 268-280.

[9] GAO Y Q, GUAN H B, QI Z W, et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing [J]. Journal of Computer & System Sciences, 2013, 79(8): 1230-1242.

[10] ZHENG Q H, LI R, LI X Q, et al. A multi-objective biogeography-based optimization for virtual machine placement [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2015: 687-696.

[11] WU Y Q, TANG M L, FRASER W. A simulated annealing algorithm for energy efficient virtual machine placement [C]// Proceedings of the 2012 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2012: 1245-1250.

[12] BELOGLAZOV A, ABAWAJY J, BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing [J]. Future Generation Computer Systems, 2012, 28(5): 755-768.

[13] SHI J Y, DONG F, ZHANG J H, et al. Two-phase online virtual machine placement in heterogeneous cloud data center [C]// Proceedings of the 2015 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2015: 1369-1374.

This work is partially supported by the Natural Science Foundation of Shaanxi Province (2017JQ6053), the Scientific Research Program Funded by Shaanxi Provincial Education Department (15JK1468), the Ph. D. Start-up Fund of Xi’an University of Science and Technology (2015QDJ031).

XUEHongye, born in 1960, Ph. D., professor. His research interests include network and high performance processing, image real-time processing.

ZHUTianlei, born in 1992, M. S. candidate. His research interests include distributed and parallel computing.

LUOXiangyu, born in 1984, Ph. D., lecturer. Her research interests include distributed and parallel computing, fault-tolerant theory.

FENGJian, born in 1973, Ph. D., associate professor. Her research interests include complex network, network security.

Virtualmachineplacementalgorithmforheterogeneouscloudenvironmentbasedonresourcedemanddistributionfeature

XUE Hongye, ZHU Tianlei, LUO Xiangyu*, FENG Jian

(CollegeofComputerScienceandTechnology,Xi’anUniversityofScienceandTechnology,Xi’anShaanxi710054,China)

Focusing on the problem of Virtual Machine Placement (VMP) in heterogeneous cloud environment, a Resource Demand Distribution Feature based Placement Algorithm (RDDFPA) for virtual machines was proposed. Firstly, a method of describing virtual machine requirements and physical machine configuration based on scale factor of CPU resource and memory resource was established. Based on the scale factor, all the virtual machines were sorted. Secondly, by analyzing the proportion relationship of virtual machine requirements and physical machine configuration in the CPU resources and memory resources, the proportion demarcation point was determined, and the partition of virtual machine set was completed. The requirement proportion of matched physical machines with different configurations was reflected by the size of each virtual machine subset.Finally, by using the heuristic algorithm such as the First Fit algorithm, the virtual machine subset was placed on the subset of physical machines with matched configuration. Theoretical analysis and simulation experimental results show that, compared with the total number of physical machines with any single configuration, the total number of physical machines required by the proposed algorithm is reduced by 2%-17%.The proposed RDDFPA can determine the number of physical machines with various configurations according to the distribution of virtual machine resource requirements, and efficiently complete the placement of virtual machines, which can improve the resource utilization rate and reduce the system energy consumption.

cloud computing; data center; Virtual Machine Placement (VMP); heterogeneous cloud environment; energy efficiency

2017- 06- 22;

2017- 08- 23。

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2017JQ6053);陜西省教育廳專項(xiàng)科學(xué)研究計(jì)劃項(xiàng)目(15JK1468);西安科技大學(xué)博士啟動(dòng)基金資助項(xiàng)目 (2015QDJ031)。

薛弘曄(1960—)，男，陜西扶風(fēng)人，教授，博士，CCF會(huì)員，主要研究方向：網(wǎng)絡(luò)與高性能處理、圖像實(shí)時(shí)處理； 朱天磊(1992—)，男，河南商丘人，碩士研究生，主要研究方向：分布式與并行計(jì)算； 羅香玉(1984—)，女，河北寧晉人，講師，博士，CCF會(huì)員，主要研究方向：分布式與并行計(jì)算、容錯(cuò)理論； 馮健(1973—)，女，陜西西安人，副教授，博士，CCF會(huì)員，主要研究方向：復(fù)雜網(wǎng)絡(luò)、網(wǎng)絡(luò)安全。

1001- 9081(2017)12- 3386- 05

10.11772/j.issn.1001- 9081.2017.12.3386

(*通信作者電子郵箱luoxiangyu@xust.edu.cn)

TP301.6

A