基于資源需求分布特征的異構云環境虛擬機放置算法

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

(西安科技大學 計算機科學與技術學院，西安 710054)

基于資源需求分布特征的異構云環境虛擬機放置算法

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

(西安科技大學 計算機科學與技術學院，西安 710054)

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

云計算；數據中心；虛擬機放置；異構云環境；能源效率

0 引言

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

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

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

1 現有VMP研究

VMP的難點在于它是一種NP-Hard問題，甚至是NP-完全問題，難以在多項式時間內解決[5]。根據云環境的同構與異構來對現有研究進行分類。

在同構云環境基礎下，主要以改進放置算法本身為主。常用算法有兩種，即啟發式算法和元啟發式算法。

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

元啟發式算法的特點在于該類算法能較好地找出全局最優解，但是其時間復雜度較高，導致可擴展性和實時性較差[6]。較為常見的元啟發式算法有蟻群算法：Gao等[9]把同構環境下虛擬機的放置問題看作一個多目標優化問題，提出了一種多目標蟻群算法，以降低系統的能源消耗、提高物理機的資源利用率。還有諸如遺傳算法[10]和模擬退火算法[11]等。

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

2 異構云環境下資源需求分布的具體描述

2.1 虛擬機資源需求分布的具體描述

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

ratevmk=CPUvmk/MEMvmk

(1)

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

2.2 異構云環境的具體描述

本文中，異構云環境由兩種具有不同資源偏向性且和虛擬機資源需求分布相對契合的物理機組成。結合實際，選出兩種物理機構成異構物理機組pairpm={pmleft,pmright}。其中pmleft為數據密集型，配置比例為：

ratepmleft=CPUpmleft/MEMpmleft

(2)

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

2.3 虛擬機資源需求分布的跨度分類

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

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

2.4 問題描述

在本文提出的算法中，通過研究異構物理機組和虛擬機資源需求分布特征之間的資源比例關系，在執行虛擬機放置算法之前對虛擬機資源需求分布進行劃分處理，從而更好地放置虛擬機，達到減少活動物理機、節約能耗的效果。具體問題可以分解為以下幾個部分：

1)依據虛擬機資源需求集合特征和異構物理機組的關系，判定跨度情況；

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

3)在兩種物理機上分別進行虛擬機放置。

3 算法描述

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

第一階段 依據虛擬機需求分布和物理機資源配比的關系，在排序后的sortedListvm上取得一個劃分點；

第二階段 在取得劃分點后，將劃分后的虛擬機需求分別在相應側物理機上使用啟發式算法進行放置。

其中第一階段可以細分為：比例數軸的預處理；確定虛擬機資源需求分布跨度；獲取虛擬機序列分界點；判斷劃分點。

3.1 比例數軸的預處理

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

根據ratepmleft和ratepmright，在數軸上標識出pairpm的具體位置，得出比例跨度[ratepmleft,ratepmright]，并依據它確定數軸的異構物理機組中心點center。

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

(3)

3.2 確定虛擬機資源需求分布跨度

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

3.3 跨度情況3下的分界點獲取

(4)

在比例Lsumratevmk與左側物理機資源配置比例ratepmleft最為接近或完全相同時，遍歷停止，并記錄下當前vmk的編號k，也就是左側虛擬機需求的分界點POINTleft。

從右側開始對sortedListvm進行倒序遍歷，以最右側虛擬機作為起點vm1，計算：

(5)

使用與左側類似方法得到右側分界點POINTright。

3.4 跨度情況3下的劃分點判斷

當取得兩側分界點后，又面臨兩種可能：分界點相交或不相交。

(6)

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

圖2 劃分點判定情況分類Fig. 2 Classification of divide point determination situation

①當ratevmb≤ratecenter，即overlapList位于center左側時，則劃分點Divide應定為右側分界點POINTright；

②當ratevma≥ratecenter，即位于center右側時，劃分點Divide應定為左側分界點POINTleft；

③當ratevma≤ratecenter≤ratevmb時，則應以center的位置作為劃分點Divide。

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

跨度情況4下，只需判斷出對應側虛擬機序列分界點即可完成劃分處理。還是以左側為例：獲得的分界點POINTleft位于center左側時，使用center作為Divide；當分界點POINTleft位于center右側時，以此POINTleft作為Divide。

3.6 對劃分后的序列進行放置

判定劃分點Divide后，sortedListvm被分為兩個子集合。兩個子集合的資源需求的大小對應了pairpm中相應配置物理機數量對比。使用同構情況下的啟發式算法對Divide左側的虛擬機需求子集合在pmleft上進行放置， Divide右側虛擬機需求子集合在pmright上進行放置。至此得到具體的虛擬機需求放置結果，得出具體需要的兩種活動物理機數量。

4 仿真實驗及分析

對本文提出的RDDFPA性能進行評估實驗，并與不經劃分直接在同構環境下進行放置的常規方法進行對比。統一使用First Fit算法作為雙方使用的啟發式算法。將每10 000個虛擬機需求作為一組數據，隨機取20組進行實驗。假設虛擬機的CPU需求以及MEM需求都在0～8內隨機取值，虛擬機資源需求分布跨度中點在CPU和MEM資源比例為1∶1的位置。通過調整資源配置構成不同異構物理機組，來模擬sortedListvm和pairpm的不同搭配情況。假設5組異構物理機組，左側物理機稱為A，右側物理機稱為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分別代表左側A的CPU資源、內存資源以及配置比例。右側B相關符號意義與A近似。

使用本文提出的RDDFPA進行放置，所需要的兩種異構物理機的臺數之和，與直接在某一種物理機上進行放置所需要的同構物理機臺數對比如圖3所示。

圖3 物理機放置結果比較Fig. 3 Comparison of physical machine placement results

根據圖3中的數據，對隨機數據集中20組數據的結果取平均值，得出不同異構物理機組合與單一配置物理機A、B相比節約的物理機臺數與百分比，來展示實際算法應用的效果，如表1所示。

從組合一到組合三，異構物理機組的CPU和內存資源配比從8∶10和10∶8一直擴大到8∶16和16∶8。隨著異構物理機組差距增大，優化效果也從對比僅使用A時節約大概121臺，比例約為2%，以及對比僅使用B時節約大概209臺，比例約為3%，逐漸提升到對比左右側均能節約大概900臺，節約比例均約為17%。但是從組合四和組合五中也可以看出，在擴大兩側物理機資源配比差異時，優化效果并非隨之線性擴大，而是逐漸趨于平穩，應將配置差異限定在一定范圍內。

由以上對比實驗可以看出，本文提出的RDDFPA，在異構物理機的資源配置具有一定差異時，相比單一配置物理機較為顯著地減少了活動物理機數量，同時節約了能耗。

表1 不同組合相對單一配置的實驗結果Tab. 1 Experimental results of different combinations relative to single configurations

5 結語

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

References)

[1] 谷立靜,周伏秋,孟輝.我國數據中心能耗及能效水平研究[J].中國能源,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] 佚名.國家綠色數據中心試點工作方案[J].石油和化工節能,2015(3):1-4.(ANONYMITY. National green data center pilot program [J]. Petroleum & Chemical Energy Conservation, 2015(3): 1-4.)

[3] 葉可江,吳朝暉,姜曉紅,等.虛擬化云計算平臺的能耗管理[J].計算機學報,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] 周東清,佀慶乾.異構云平臺中能源有效的虛擬機部署研究[J].計算機科學,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].計算機科學,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。

陜西省自然科學基礎研究計劃項目(2017JQ6053);陜西省教育廳專項科學研究計劃項目(15JK1468);西安科技大學博士啟動基金資助項目 (2015QDJ031)。

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

1001- 9081(2017)12- 3386- 05

10.11772/j.issn.1001- 9081.2017.12.3386

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

TP301.6

A