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

高燕飛　陳俊杰　強(qiáng)彥

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

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

中圖分類號： TN911?34； TP391 文獻(xiàn)標(biāo)識碼： 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

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

1 相關(guān)研究

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

2 模型的建立

2.1 HL模型

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

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

2.2 MF模型

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

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

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

2.3 有效不等式

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

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

3 實(shí)驗(yàn)部分

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[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.