摘  要： 為提高數(shù)據(jù)中心的資源利用率并降低能耗,，提出了面向低能耗的虛擬機(jī)部署和遷移策略,，包括虛擬機(jī)初始部署算法BT-MPA和虛擬機(jī)動(dòng)態(tài)遷移算法MMT-MMA。BT-MPA算法基于回溯法實(shí)現(xiàn)虛擬機(jī)集合和主機(jī)集合的最優(yōu)初始映射,，MMT-MMA算法基于最小遷移時(shí)間策略實(shí)現(xiàn)虛擬機(jī)動(dòng)態(tài)遷移,。仿真驗(yàn)證了所提出策略能夠在降低數(shù)據(jù)中心總能耗的同時(shí)避免了不必要的遷移開銷。

　　關(guān)鍵詞： 數(shù)據(jù)中心,；虛擬機(jī),；動(dòng)態(tài)部署；低能耗,；動(dòng)態(tài)遷移

0 引言

　　隨著云計(jì)算的快速發(fā)展,，數(shù)據(jù)中心能源成本不斷上漲[1]。在2011年,，我國數(shù)據(jù)中心總耗電量已經(jīng)占到全社會(huì)用電量的1.5%[2],。高能耗的主要原因在于設(shè)備數(shù)量增加和資源使用率低[3]。

　　目前數(shù)據(jù)中心常用的節(jié)能技術(shù)有：動(dòng)態(tài)電壓頻率調(diào)整（Dynamic Voltage and Frequency Scaling,，DVFS）和虛擬化技術(shù)[4],。其中虛擬化技術(shù)能夠?qū)⒁粋€(gè)服務(wù)器虛擬成多個(gè)服務(wù)器，提高資源的利用率,，降低成本[5],。

　　目前有許多關(guān)于虛擬機(jī)部署和遷移算法的研究。參考文獻(xiàn)[4]提出了一種面向系統(tǒng)能耗優(yōu)化的虛擬機(jī)部署算法,，該算法能夠有效降低能耗,，但最終部署結(jié)果不是最優(yōu)結(jié)果。參考文獻(xiàn)[6]為了降低能耗給出了一種節(jié)能算法,，并提到遷移時(shí)間的概念,，但在遷移虛擬機(jī)時(shí)沒有考慮遷移時(shí)間。參考文獻(xiàn)[7]提出一種虛擬機(jī)放置方案,，該方案能夠優(yōu)化能源效率,，但沒有涉及遷移問題。

　　基于當(dāng)前研究,，本文提出了面向低能耗的虛擬機(jī)部署和遷移策略,，目的是在最小化數(shù)據(jù)中心能耗的同時(shí)保證服務(wù)質(zhì)量,。該策略一方面利用回溯法部署虛擬機(jī),，使開啟物理機(jī)的數(shù)量最小,；另一方面為了適應(yīng)虛擬機(jī)的動(dòng)態(tài)變化和避免資源過度聚合,，根據(jù)最小遷移時(shí)間策略動(dòng)態(tài)遷移虛擬機(jī),，最小遷移時(shí)間策略通過貪心算法和動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)。

1 虛擬機(jī)動(dòng)態(tài)部署

　　1.1 虛擬機(jī)部署問題

　　可將虛擬機(jī)部署問題描述為：數(shù)據(jù)中心有n臺(tái)主機(jī)和m臺(tái)等待部署的虛擬機(jī),，每臺(tái)主機(jī)和虛擬機(jī)均配置k種資源,，目標(biāo)是完成部署后總能耗最小，其中虛擬機(jī)的資源總和不能超越主機(jī)的資源上限,，虛擬機(jī)最多只能被部署到一個(gè)主機(jī)上,。

　　以上描述等價(jià)為：D=（H1，…,，Hn）,，Hi=（hri1，…,，hrik）,，V=（vm1，…,，vmm）,，vmj=（vrjl，…,，vrjk）,，其中1≤i≤n，1≤j≤m,。

　　其中,，h（j）是虛擬機(jī)j被分配到的主機(jī)，vrjl是虛擬機(jī)j的第l種資源量,，hril是主機(jī)i的第l種資源量,，powi是主機(jī)i的能耗。對(duì)于集成DVFS技術(shù)的主機(jī),，開啟時(shí)可根據(jù)參考文獻(xiàn)[8]提出的能耗模型計(jì)算powi：

　　powi=pmin+（pmax-pmin）×ui（2）

　　其中,，ui是主機(jī)i的CPU利用率，pmin是空閑狀態(tài)下的能耗,，pmax是ui最大時(shí)的能耗,。

　　1.2 基于回溯法的虛擬機(jī)動(dòng)態(tài)部署算法

　　虛擬機(jī)部署問題大多是基于貪心算法進(jìn)行優(yōu)化，但該問題不具有貪心選擇性質(zhì),，通過一系列局部最優(yōu)選擇并不能得到整體最優(yōu)解,。為了最小化能耗，本文基于回溯法提出了一個(gè)虛擬機(jī)部署算法BT-MPA,?；厮莘ㄔ谔摂M機(jī)部署問題的解空間子集樹中按照深度優(yōu)先策略搜索，若搜索過程中當(dāng)前的擴(kuò)展節(jié)點(diǎn)不滿足不等式（1）則跳過,，否則進(jìn)入該子樹繼續(xù)搜索,，直至找到最優(yōu)解[9],。

　　BT-MPA的步驟是：首先將主機(jī)按照開啟關(guān)閉狀態(tài)排序，相同狀態(tài)的主機(jī)按照可用資源大小降序排列,；接著依次選擇主機(jī),，用回溯法從虛擬機(jī)集合中選出最優(yōu)子集部署到主機(jī)中；然后從集合中移除已被部署的虛擬機(jī),，繼續(xù)以上步驟直至虛擬機(jī)集合為空,。

2 虛擬機(jī)動(dòng)態(tài)遷移

　　虛擬機(jī)遷移問題可分為兩個(gè)子問題：何時(shí)觸發(fā)遷移和選擇哪些虛擬機(jī)遷移。

　　2.1 觸發(fā)遷移

　　本文設(shè)定資源利用率上限閾值Tup和下限閾值Tdown,，當(dāng)主機(jī)處于以下情況時(shí)觸發(fā)遷移：（1）資源利用率大于Tup,，說明主機(jī)處于過載狀態(tài)，需遷出某些虛擬機(jī),，以避免降低用戶體驗(yàn),；（2）資源利用率小于Tdown，需遷出所有虛擬機(jī)并關(guān)閉主機(jī),，以降低能耗,。由于虛擬機(jī)對(duì)CPU的競(jìng)爭(zhēng)最為激烈，故遷移時(shí)僅考慮CPU資源,，用MIPS指標(biāo)來衡量,。

　　2.2 選擇虛擬機(jī)

　　過載主機(jī)中虛擬機(jī)的選擇有隨機(jī)和最小遷移時(shí)間（Minimum Migration Time，MMT）兩種策略,。MMT策略是選擇遷移時(shí)間最小的虛擬機(jī)集合遷出,，它等價(jià)于選擇一組總遷移時(shí)間最大的虛擬機(jī)集合留在主機(jī)上：

　　其中，uj（cpu）是虛擬機(jī)j使用的CPU和主機(jī)總CPU的比值[7],，mtj是遷移時(shí)間,，用虛擬機(jī)內(nèi)存與所在主機(jī)空閑帶寬的比值衡量[3]。式（3）具有最優(yōu)子結(jié)構(gòu)性質(zhì),，能夠使用貪心和動(dòng)態(tài)規(guī)劃算法來解決,。

　　2.2.1 貪心選擇策略

　　使用貪心算法解決MMT問題的步驟是：首先將虛擬機(jī)按照遷移時(shí)間與MIPS的比值非降序排列，然后依次選擇虛擬機(jī)加入遷出隊(duì)列,，直至主機(jī)的CPU利用率不大于Tup,。該算法的時(shí)間復(fù)雜度為O（nlogn）[9]。

　　2.2.2 動(dòng)態(tài)規(guī)劃選擇策略

　　動(dòng)態(tài)規(guī)劃將問題分解成若干子問題,，通過結(jié)合子問題的解得到最終解[9],。假設(shè)F（j，ri）是子問題的最優(yōu)解,，則可以建立如下遞歸關(guān)系：

　　F（j,，ri）=max{F（j-1，ri）,，F(xiàn)（j-1,，ri-mj）+mtj}，ri≥mjF（j-1,，ri）,，                     ri<mj（4）

　　其中，F(xiàn)（j,，ri）指的是當(dāng)主機(jī)CPU值為ri,，虛擬機(jī)集合為1，…,，j時(shí)的最大遷移時(shí)間,，mj是虛擬機(jī)j的CPU資源值。

　　該策略能得到式（3）的最優(yōu)解,，最優(yōu)解對(duì)應(yīng)的虛擬機(jī)就是留在主機(jī)上的最優(yōu)集合,。該算法的時(shí)間復(fù)雜度是O（2n）[9]。

　　2.3 虛擬機(jī)遷移算法

　　本文基于以上策略提出了虛擬機(jī)遷移算法MMT-MMA,，具體步驟是：周期性地檢測(cè)開啟主機(jī)的CPU利用率,，如果大于Tup，則使用虛擬機(jī)選擇策略得到遷出虛擬機(jī)集合,，將其加入遷出隊(duì)列,；如果小于Tdown，則將其上的虛擬機(jī)全部加入遷出隊(duì)列,，最后將遷出的虛擬機(jī)隊(duì)列按照BT-MPA算法重新部署,。

3 仿真實(shí)驗(yàn)和分析

　　3.1 實(shí)驗(yàn)環(huán)境

　　為驗(yàn)證本文提出算法的有效性，進(jìn)行了兩組仿真實(shí)驗(yàn),，每組實(shí)驗(yàn)均進(jìn)行15次,，取平均值作為最終結(jié)果。實(shí)驗(yàn)設(shè)置Tup為0.8,，Tdown為0.2,。

　　首先在仿真系統(tǒng)中建立1個(gè)數(shù)據(jù)中心和20臺(tái)主機(jī)，主機(jī)的資源根據(jù)表1隨機(jī)配置,。

　　系統(tǒng)中需部署的虛擬機(jī)數(shù)量范圍是[10,，80]，增加步長為10,，虛擬機(jī)的資源根據(jù)表2隨機(jī)配置,。

　　虛擬機(jī)上運(yùn)行的應(yīng)用負(fù)載按照占用虛擬機(jī)資源的比例可分為輕、中,、重三型,，不同型號(hào)虛擬機(jī)上運(yùn)行負(fù)載的概率空間相同，如表3所示,。

　　3.2 實(shí)驗(yàn)結(jié)果

　　圖1是使用本文提出的BT-MPA算法與基于貪心算法的Greedy-MPA進(jìn)行虛擬機(jī)部署后的能耗比較圖,，從圖可知BT-MPA在節(jié)能方面優(yōu)于常用的Greedy-MPA,，數(shù)據(jù)中心總能耗相對(duì)于Greedy-MPA算法平均降低9.7%，達(dá)到了更好的節(jié)能效果,。

　　圖2是使用不同的虛擬機(jī)選擇策略進(jìn)行動(dòng)態(tài)遷移的結(jié)果,。從圖可看出，基于MMT選擇策略的遷移時(shí)間遠(yuǎn)遠(yuǎn)低于RC策略,，貪心選擇策略的遷移時(shí)間相對(duì)于RC策略平均減少48%,，動(dòng)態(tài)規(guī)劃選擇策略相對(duì)于RC策略平均降低57%，動(dòng)態(tài)規(guī)劃相對(duì)于貪心選擇策略平均降低18%,。這也與理論相符合,，動(dòng)態(tài)規(guī)劃較貪心選擇策略結(jié)果更優(yōu)，但時(shí)間復(fù)雜度更大,，因此數(shù)據(jù)中心可綜合考慮遷移時(shí)間和計(jì)算時(shí)間來選擇具體策略,。

4 結(jié)論

　　為降低數(shù)據(jù)中心的能耗，本文提出了虛擬機(jī)部署算法BT-MPA和虛擬機(jī)遷移算法MMT-MMA,。通過仿真驗(yàn)證了BT-MPA能夠有效降低數(shù)據(jù)中心總能耗,，實(shí)現(xiàn)節(jié)能減排的目的，同時(shí)表明了MMT-MMA能夠有效減少虛擬機(jī)遷移時(shí)間,，避免不必要的遷移開銷,。本文在觸發(fā)遷移時(shí)使用的是固定閾值，為了更靈活地應(yīng)對(duì)負(fù)載變化,，接下來將針對(duì)自適應(yīng)閾值展開研究,。

參考文獻(xiàn)

　　[1] SCHULZ G. 綠色虛擬數(shù)據(jù)中心[M].韓毅剛，李亞娜,，王歡,，譯.北京：人民郵電出版社，2010.

　　[2] 王肇國,，易涵,，張為華.基于機(jī)器學(xué)習(xí)特性的數(shù)據(jù)中心能耗優(yōu)化方法[J].軟件學(xué)報(bào)，2014,，25（7）：1432-1447.

　　[3] BELOGLAZOV A,， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computat-ion： Practice and Experience， 2012（24）：1397-1420.

　　[4] 王加昌,，曾輝,，何騰蛟，等.面向數(shù)據(jù)中的虛擬機(jī)部署及優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,，2013,，33（10）：2772-2777.

　　[5] 高林，宋相倩，王潔萍.云計(jì)算及其關(guān)鍵技術(shù)研究[J].微型機(jī)與應(yīng)用,，2011,，30（10）：5-7.

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

　　[7] 董健康，王洪波.IaaS環(huán)境下改進(jìn)能源效率和網(wǎng)絡(luò)性能的虛擬機(jī)放置方法[J].通信學(xué)報(bào),，2014，35（1）：72-81.

　　[8] 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）：755-768.

　　[9] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社,，2012.