面向低能耗的虛擬機(jī)部署和遷移策略

田苗苗，李 ?。ㄖ袊?guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系，安徽 合肥 230026）

面向低能耗的虛擬機(jī)部署和遷移策略

田苗苗，李 俊
（中國(guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系，安徽 合肥 230026）

為提高數(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í)避免了不必要的遷移開銷。

數(shù)據(jù)中心；虛擬機(jī)；動(dòng)態(tài)部署；低能耗；動(dòng)態(tài)遷移

0 引言

隨著云計(jì)算的快速發(fā)展，數(shù)據(jù)中心能源成本不斷上漲［1］。在2011年，我國(guó)數(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≤其中，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：其中，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(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ī)遷移算法MMTMMA，具體步驟是：周期性地檢測(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ī)配置。

表1 主機(jī)配置

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

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

表2 虛擬機(jī)配置

表3 應(yīng)用負(fù)載

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í)間來選擇具體策略。

圖1 虛擬機(jī)部署算法比較

圖2 虛擬機(jī)遷移算法比較

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)閾值展開研究。

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

［2］王肇國(guó)，易涵，張為華.基于機(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.

圖6 服務(wù)器測(cè)試視頻數(shù)據(jù)

其中圖6（a）是移動(dòng)監(jiān)控設(shè)備對(duì)采集的視頻數(shù)據(jù)經(jīng)過電子穩(wěn)像處理過的連續(xù)3幀視頻數(shù)據(jù)，圖6（b）是與圖（a）相對(duì)應(yīng)的未經(jīng)過設(shè)備端穩(wěn)像處理的視頻數(shù)據(jù)。由圖6可以看出電子穩(wěn)像操作解決了拍攝視頻時(shí)的抖動(dòng)問題。將前端移動(dòng)監(jiān)控設(shè)備在不同的地方進(jìn)行測(cè)試，系統(tǒng)都可以穩(wěn)定運(yùn)行。本系統(tǒng)可以廣泛地應(yīng)用于一些無法鋪設(shè)線路的偏遠(yuǎn)地區(qū)，解決了傳統(tǒng)監(jiān)控系統(tǒng)中難以鋪設(shè)線路的問題。

參考文獻(xiàn)

［1］何岳.移動(dòng)監(jiān)控系統(tǒng)研究［J］.信息通信，2012（5）：126-127.

［2］姚楠，余勁.基于云的電力監(jiān)控視頻故障管理系統(tǒng)設(shè)計(jì)［J］.電子技術(shù)應(yīng)用，2014，40（6）：140-142.

［3］楊陽，胡永輝.移動(dòng)監(jiān)控終端無線傳輸系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.時(shí)間頻率學(xué)報(bào)，2011，34（1）：27-32.

［4］梁振濤，樊澤明，任永亮，等.基于單片機(jī)的移動(dòng)監(jiān)控系統(tǒng)硬件設(shè)計(jì)［J］.微型機(jī)與應(yīng)用，2014，33（2）：25-30.

［5］葛虎龍，李安平.高清抖動(dòng)視頻的實(shí)時(shí)穩(wěn)像算法［J］.信息通信，2013（6）：41-43.

［6］黃九林.基于塊匹配和直線特征的視頻穩(wěn)像方法研究［D］.大連：大連理工大學(xué)，2014.

（收稿日期：2015-03-28）

作者簡(jiǎn)介：

楊云龍（1988-），男，碩士研究生，主要研究方向：多媒體數(shù)字通信。

孟利民（1963-），女，博士，教授，主要研究方向：無線通信與網(wǎng)絡(luò)、智能信息系統(tǒng)、網(wǎng)絡(luò)管理、多媒體數(shù)字通信與網(wǎng)絡(luò)。

Virtual machine deployment and migration strategy for saving energy

Tian Miaomiao，Li Jun
（Department of Automation，University of Science and Technology of China，Hefei 230026，China）

To improve data center′s resources utilization and reduce energy costs，a virtual machine deployment and migration strategy for saving energy has been proposed.The strategy includes a virtual machine deployment algorithm named BT-MPA and migration algorithm named MMT-MMA.BT-MPA achieves initial map from virtual machines to hosts optimally based on backtracking algorithm，MMT-MMA migrates virtual machines dynamically by using the minimum migration time strategy.Simulation results prove the strategy can reduce total energy consumption of data center and avoid unnecessary migration overhead.

data center；virtual machine；dynamic deployment；low energy consumption；dynamic migration

TP391.9

A

1674-7720（2015）18-0023-03

田苗苗，李俊.面向低能耗的虛擬機(jī)部署和遷移策略［J］.微型機(jī)與應(yīng)用，2015，34（18）：23-25，31.

2015-04-20）

田苗苗（1991-），女，碩士研究生，主要研究方向：云計(jì)算。

李?。?973-），男，博士，副教授，主要研究方向：網(wǎng)絡(luò)控制。