大型云計算系統(tǒng)中虛擬機的放置優(yōu)化算法

高燕飛　陳俊杰　強彥

摘 要： 為了減少骨干網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)流量，研究確定和優(yōu)化虛擬機在數(shù)據(jù)中心的放置問題。虛擬機放置問題是一個HL問題，但是它在大型的云計算系統(tǒng)中表現(xiàn)不能令人滿意。為了解決這個問題，重新建模，提出MF模型，利用可變聚合方法和添加有效不等式加強這個模型。通過大量的實驗表明，在運行時間和計算資源方面該模型是可行有效的。

關(guān)鍵詞： 虛擬機； 云計算； 放置問題； MF模型

中圖分類號： TN911?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）10?0013?03

Abstract： The virtual machine placement in data center is researched and optimized to reduce the data flow in the backbone networks. The virtual machine placement can be considered as a HL （hub location） problem. It is not satisfactory in the large cloud computing system. In order to solve this problem， a new MF model is proposed in this paper， which is based on the variable aggregation method and the effective inequality. The results of a large number of experiments show that the model is feasible and effective in running time and computing resources.

Keywords： virtual machine； cloud computing； placement problem； MF model

在大型云計算系統(tǒng)中， 虛擬機的放置問題主要是采用正確的方法來設(shè)計和優(yōu)化在地理分布數(shù)據(jù)中心中虛擬機的放置。本文在大規(guī)模的云計算系統(tǒng)中解決虛擬機放置問題，目的是盡量減少數(shù)據(jù)中心節(jié)點之間的通信流量[1?3]。

1 相關(guān)研究

最近幾年，許多學(xué)者都從不同的角度對這個問題進行了研究。資源配置、服務(wù)器整合和能源消耗等很多方面在文獻[4?6]已經(jīng)詳細研究。然而，這些研究在很大程度上忽略了網(wǎng)絡(luò)性能及其對虛擬機放置的影響，他們嘗試提高網(wǎng)絡(luò)連接的程度和使用動態(tài)路由協(xié)議來平衡傳輸工作量[7?9]。最新的一些研究發(fā)現(xiàn)，通過優(yōu)化數(shù)據(jù)中心的位置來減少地理分布數(shù)據(jù)中心的功耗或服務(wù)延遲[10]。

2 模型的建立

2.1 HL模型

在大型的云計算系統(tǒng)中的虛擬機放置問題，可以看作是一個變種的樞紐位置問題（Hub Location Problem，HL問題），一個由虛擬機和數(shù)據(jù)中心節(jié)點組成的圖。

事實上，HL模型是對稱的，它有一個弱下界可以影響最優(yōu)解的質(zhì)量和程序的運行時間。重新使用聚合的方法（Multi?commodity Flow Problem）可以解決最優(yōu)解的質(zhì)量和程序運行時間的問題。

2.2 MF模型

在MF模型中，上述可以用一個圖[G=N，E]來表示。其中：N表示所有節(jié)點的集合；E表示圖的邊的集合。

引入決策變量：[fihk]表示從虛擬機[i∈V]出來的循環(huán)在數(shù)據(jù)中心的流量數(shù)值；[φijh]表示從虛擬機[i∈V]出來的循環(huán)在虛擬機[j∈V]和數(shù)據(jù)中心[h∈D]之間的流量數(shù)值；[αkh]表示兩個節(jié)點k和h之間流量交換的數(shù)值。線性模型如下：

式（7）是最小化不同數(shù)據(jù)中心的流量；式（8）是虛擬機的流量等于其他虛擬機之間交換的流量；式（9）、式（10）是保證流量都是由源節(jié)點產(chǎn)生的；式（11）是保證每個虛擬機只在一個數(shù)據(jù)中心運行；式（12）是虛擬機分配到矩陣[ahi]的數(shù)據(jù)中心；式（13）是虛擬機i的流量等于i和j之間交換的流量；式（14）是i的流量等于i與其他虛擬機交換的流量；式（15）是虛擬機所占資源不超過數(shù)據(jù)中心擁有資源的數(shù)量。

2.3 有效不等式

有效不等式的目的是使目標函數(shù)[fikh]的決策變量的值與增加的有效的約束條件相結(jié)合，能夠給應(yīng)用于二值變量[σik]的分支界定算法提供更好的邊界。

命題1：對于任意的虛擬機i和數(shù)據(jù)中心k，式（16）對MF是有效的。

3 實驗部分

電腦配置CPU為Intel Xeon 3， 3 GHz，RAM為8 GB，使用CPLEX來解決、評估和對比不同的模型。

測試是在同一組實例下進行的，輸入數(shù)據(jù)為虛擬機60臺和數(shù)據(jù)中心6個。運行結(jié)果如圖1所示。

如表1所示， MF是添加了有效不等式，[MFw]沒有添加，S是CPLEX給的最優(yōu)解的值，G是與下邊界的差值（越小越好），T是運行時間。

4 結(jié) 論

通過實驗表明，本文提出的MF重新建模，利用可變聚合方法和添加有效不等式來加強這個新的模型是可行有效的。

參考文獻

[1] VALANCIUS V， LAOUTARIS N， MASSOULI? L， et al. Greening the internet with nano data centers [C]// Proceedings of the 5 th International Conference on Emerging Networking Experiments and Technologies. [S.l.： s.n.]， 2009： 37?48.

[2] CHURCH K， GREENBERG A， HAMILTON J. On delivering embarrassingly distributed cloud services [EB/OL]. [2008?09?22]. highscalability.com.

[3] DONG X， GREEN E L T. IP over WDM networks with data centers [J]. Lightwave technology journal， 2011， 29（12）： 1861?1880.

[4] SPEITKAMP B， BICHLER M A. Mathematical programming approach for server consolidation problems in virtualized data centers [J]. IEEE transactions on services computing， 2010， 3（4）： 266?278.

[5] ZHANG Bolei， QIAN Zhuhong， HUANG Wei， et al. Minimizing communication traffic in data centers with power?aware VM placement [C]// Proceedings of 2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous ComputingIEEE Computer Society. [S.l.]： IEEE， 2012： 280?285.

[6] COHEN R， LEWIN?EYTAN L， NAOR J， et al. Almost optimal virtual machine placement for traffic intense data centers [C]// Proceedings of 2013 INFOCOM. [S.l.]： IEEE， 2013： 355?359.

[7] SHYU M， WU G M， CHANG Y D， et al. Generic universal switch blocks [J]. IEEE transactions on computers， 2000， 49（4）： 348?359.

[8] GUO C， LU G， LI D， et al. BCube： A high performance，server?centric network architecture for modular data centers [J]. Sigcomm， 2009， 39（4）： 63?74.

[9] AL?FARES M， LOUKISSAS A， VAHDAT A. A scalable， commodity data center network architecture [C]// Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication. [S.l.]： ACM， 2008： 63?74.

[10] GREENBERG A， HAMILTON J R， JAIN N， et al. Vl2： A scalable and flexible data center network [C]// Proceedings of the ACM SIGCOMM 2009 conference on Data Communication. Barcelona， Spain： ACM， 2009： 51?62.