云環(huán)境下一種聯(lián)盟形成博弈的虛擬機(jī)遷移算法

秦海燕,彭飛,陳敏，吳楊

(1.揚(yáng)州市職業(yè)大學(xué)現(xiàn)代教育技術(shù)中心，江蘇揚(yáng)州225000；2.博世創(chuàng)新與軟件開發(fā)中心，江蘇蘇州215000)

1 引言

云計(jì)算作為一種新興的計(jì)算模型受到了廣泛的關(guān)注和應(yīng)用。服務(wù)供應(yīng)商越來越愿意將服務(wù)從本地集群遷移到云數(shù)據(jù)中心。云數(shù)據(jù)中心將虛擬化技術(shù)作為實(shí)現(xiàn)計(jì)算資源多樣化、促進(jìn)系統(tǒng)管理高效化的關(guān)鍵技術(shù)。虛擬機(jī)通過虛擬化技術(shù)創(chuàng)建，被部署在物理機(jī)上。在云場景中，服務(wù)供應(yīng)商請求資源，平臺將任務(wù)請求部署到資源池的主機(jī)中。但是，云數(shù)據(jù)中心通常無法高效運(yùn)行。效率低下主要是因?yàn)樘摂M機(jī)的分配方式不合理，導(dǎo)致物理機(jī)資源負(fù)載不平衡，一些物理機(jī)過載，一些物理機(jī)無法充分利用[1]。虛擬機(jī)遷移算法是一種幫助云供應(yīng)商提供有效、自主管理云資源的方法。虛擬機(jī)遷移使用遷移技術(shù)將負(fù)載從一臺物理機(jī)轉(zhuǎn)移到另一臺物理機(jī)，以平衡物理機(jī)之間的負(fù)載，提高物理機(jī)利用效率。

在虛擬機(jī)遷移過程中要考慮兩個(gè)關(guān)鍵問題。一方面，如何從高載物理機(jī)中選擇出待遷移的虛擬機(jī)。云平臺中，兩個(gè)位于不同物理節(jié)點(diǎn)的虛擬機(jī)的通信成本比位于同一個(gè)物理節(jié)點(diǎn)的要高，因?yàn)閿?shù)據(jù)通過內(nèi)存?zhèn)鬏敱韧ㄟ^網(wǎng)絡(luò)傳輸成本低。因此，無論是遷移還是保留高載物理機(jī)中的虛擬機(jī)，都應(yīng)該考慮通信成本。另一方面，應(yīng)該選擇哪個(gè)低載物理機(jī)來放置待遷移的虛擬機(jī)。當(dāng)有許多虛擬機(jī)需要遷移，并且有多個(gè)低載物理機(jī)滿足遷移條件時(shí)，待遷移虛擬機(jī)和低載物理機(jī)的映射關(guān)系就要考慮。

虛擬機(jī)遷移算法很多，如裝箱算法[2-3]、遺傳算法[4-5]、蟻群優(yōu)化算法[6]等。本文提出了一種基于聯(lián)盟形成博弈的虛擬機(jī)遷移算法(簡稱VMM-CFG)。聯(lián)盟博弈是一個(gè)設(shè)計(jì)公平、穩(wěn)健和高效協(xié)作策略的非常強(qiáng)大的理論[7]。聯(lián)盟形成博弈是聯(lián)盟博弈論的一個(gè)分支，與經(jīng)典博弈和聯(lián)盟圖博弈不同，網(wǎng)絡(luò)結(jié)構(gòu)和合作成本在聯(lián)盟形成博弈中起著重要作用。本文將虛擬機(jī)遷移問題建模為基于合并和拆分算法的聯(lián)盟形成博弈。首先，從高載物理機(jī)中篩選出待遷移的虛擬機(jī)。接著，待遷移的虛擬機(jī)根據(jù)相應(yīng)的約束自主形成聯(lián)盟結(jié)構(gòu)。待遷移的虛擬機(jī)可以通過不斷執(zhí)行合并和拆分操作來更新聯(lián)盟結(jié)構(gòu)，直到形成穩(wěn)定的聯(lián)盟結(jié)構(gòu)。聯(lián)盟結(jié)構(gòu)中的每個(gè)聯(lián)盟都映射到相應(yīng)的低載物理機(jī)。最后，根據(jù)待遷移的虛擬機(jī)和低載物理機(jī)之間的映射，執(zhí)行遷移。

2 問題模型

如圖1所示，數(shù)據(jù)中心由v臺虛擬機(jī)部署在p臺物理機(jī)上構(gòu)成，P={1,2,...,p}表示物理機(jī)集合，V={1,2,...,v}表示虛擬機(jī)集合。物理機(jī)i∈P與虛擬機(jī)j∈V的映射關(guān)系用xij表示，如果xij= 1，表示虛擬機(jī)j∈V部署在物理機(jī)i∈P上。VMi={j|xij=1,?j∈V}表示部署在物理機(jī)i上的虛擬機(jī)集合；函數(shù)f(j)表示虛擬機(jī)j∈V所在的物理機(jī)。

圖1 數(shù)據(jù)中心結(jié)構(gòu)示例圖

圖Gi=(VMi,Ei)表示部署在物理機(jī)i上的虛擬機(jī)間的數(shù)據(jù)通信結(jié)構(gòu)，若虛擬機(jī)j,k∈VMi間存在數(shù)據(jù)通信，則存在邊(j,k) ∈Ei，權(quán)值wjk為其數(shù)據(jù)通信量。G={G1,G2,...,Gp}表示所有物理機(jī)的數(shù)據(jù)通信結(jié)構(gòu)。

每個(gè)虛擬機(jī)j∈V均配置一定量的物理資源，如CPU、內(nèi)存和網(wǎng)絡(luò)等，不失一般性，本文僅考慮內(nèi)存資源。mj表示虛擬機(jī)j所需的內(nèi)存資源量，Mi和Mi′分別表示物理機(jī)i∈P的最大內(nèi)存容量和負(fù)載安全閾值表示物理機(jī)i∈P實(shí)際的內(nèi)存使用量，即：

若Mi′<≤Mi，則稱物理機(jī)i∈P是高負(fù)載的；否則是低負(fù)載的。高載物理機(jī)集合表示為H={i|Mi′<≤Mi,i∈P}，低載物理機(jī)集合表示為L={i|≤Mi′,i∈P}。虛擬機(jī)遷移最主要的目標(biāo)是最小化高載物理機(jī)數(shù)目 ||H，實(shí)現(xiàn)負(fù)載均衡[1]。

3 基于聯(lián)盟形成博弈的虛擬機(jī)遷移方法

考慮到動(dòng)態(tài)遷移的實(shí)時(shí)性以及時(shí)間性能要求，本文研究設(shè)計(jì)一種基于聯(lián)盟形成博弈的遷移方法，具體方法如圖2 所示。1)制定選擇規(guī)則，從高載物理機(jī)中篩選出待遷移的虛擬機(jī)；2)待遷移虛擬機(jī)之間運(yùn)用聯(lián)盟形成博弈理論自主演化形成穩(wěn)定的聯(lián)盟，最終完成聯(lián)盟與低載物理機(jī)間的映射，并實(shí)現(xiàn)遷移。

圖2 一種基于聯(lián)盟形成博弈的遷移方法

3.1 虛擬機(jī)選擇算法

待遷移虛擬機(jī)選擇算法目標(biāo)有兩個(gè)：1)使高載物理機(jī)的實(shí)際資源使用量不高于負(fù)載安全閾值；2)使通信緊密的虛擬機(jī)保留在原物理機(jī)，即將與其他虛擬機(jī)無通信或通信較少的虛擬機(jī)遷出。算法的具體描述見算法1。對于每個(gè)高載物理機(jī)i∈H，首先計(jì)算每個(gè)虛擬機(jī)j∈VMi的通信量cj，即與該物理機(jī)中其他虛擬機(jī)之間的數(shù)據(jù)通信量之和：

然后，根據(jù)通信量cj進(jìn)行升序排列。如果序列中第一個(gè)虛擬機(jī)遷出，該物理機(jī)仍然高載，則將該虛擬機(jī)加入待遷移虛擬機(jī)集合VMList，繼續(xù)判斷下一個(gè)虛擬機(jī)，直到該物理機(jī)低載。依次遍歷所有高載物理機(jī)。

算法1 虛擬機(jī)選擇算法輸入：H,G輸出：VMList 1. VMList ←?2.for i ∈H do 3.for j ∈VMi do 4.cj =∑(j,k) ∈Eiwjk 5.end for 6.VMi′←{ j|cj is sorted by an ascending sort}7.for j ∈VMi′do 8.if∑k ∈VMi′{ j}mk ≥Mi′then 9.VMList ←VMList ?{ j},VMi′←VMi′{ j}10.end if 11.end for 12.end for

3.2 虛擬機(jī)聯(lián)盟形成算法

篩選出待遷移的虛擬機(jī)集合后，要考慮如何將這些虛擬機(jī)遷移到低載物理機(jī)，即待遷移虛擬機(jī)與低載物理機(jī)間的二次映射問題，類似于裝箱問題[2]和二次分配問題[8]，是NP難問題。在映射過程中，既要考慮物理機(jī)的內(nèi)存容量，又要考慮網(wǎng)絡(luò)通信成本。

本節(jié)運(yùn)用聯(lián)盟形成博弈理論，讓待遷移虛擬機(jī)自主形成虛擬機(jī)群，整體映射到同一個(gè)低載物理機(jī)。下面給出一些定義：

定義1：待遷移虛擬機(jī)集合VMList的任意子集稱為聯(lián)盟C?VMList，若 存 在 一 個(gè) 低 載 物 理 機(jī)i∈L，使 得，則聯(lián)盟C為有效聯(lián)盟。VMList的一個(gè)劃分稱 為 聯(lián) 盟 結(jié) 構(gòu) ∏={C1,C2,...Ch}，滿 足Cg?Cl=?,?g,l∈{1,2,...,h},g≠l且∪k∈{1,2,...,h}Ck=VMList。Σ(Π) 表 示所有可能的聯(lián)盟結(jié)構(gòu)。同樣，若聯(lián)盟結(jié)構(gòu)∏內(nèi)所有聯(lián)盟均為有效聯(lián)盟，則Π稱為有效聯(lián)盟結(jié)構(gòu)。

定義2：給定聯(lián)盟結(jié)構(gòu)Π ∈Σ(Π)，其值v(Π)定義為所有虛擬機(jī)之間總的通信成本，即：

d(f(j),f(k))表示物理機(jī)f(j)和f(k)的單位通信成本，如果j和k部署在同一個(gè)物理機(jī)，則d(f(j),f(k)) = 0。

定義3：給定聯(lián)盟結(jié)構(gòu)Π 和Π′，∏優(yōu)于∏′當(dāng)且僅當(dāng)v(Π)

依據(jù)上述兩種操作，聯(lián)盟形成過程如下：首先，將每個(gè)待遷移虛擬機(jī)視為單一聯(lián)盟，形成初始聯(lián)盟結(jié)構(gòu)。接著隨機(jī)選擇兩個(gè)聯(lián)盟并判斷能否合并，若滿足合并條件則合并，直到不存在任意兩個(gè)聯(lián)盟能合并為止。在某個(gè)低載物理機(jī)中的資源足以支持新聯(lián)盟的條件下，新聯(lián)盟被映射到相應(yīng)的低載物理機(jī)中。映射過程由算法2 中的MapProcess(·)執(zhí)行。隨后遍歷任意聯(lián)盟，判斷是否存在其劃分滿足分割條件，若滿足則進(jìn)行分割，將分割的聯(lián)盟分別映射到低載物理機(jī)。最后，迭代執(zhí)行上述合并和分割過程，直到達(dá)到迭代次數(shù)或聯(lián)盟結(jié)構(gòu)無變化為止。算法的具體描述見算法2。

算法2 待遷移虛擬機(jī)聯(lián)盟形成算法輸入：VMList輸出：Π 1.Π ={{ j} j ∈VMList}2.repeat//Merge Process 3.repeat 4.Select coalition Ci,Cj ∈Π randomly 5.MapProcess(Ci ?Cj)6.if Ci ?Cj ? m{Ci,Cj}then 7.Ci ←{Ci,Cj},Cj ←?8.end if 9.until There are no two coalitions satisfying the merging condition//Split Process 10.for all Ci ∈Π and|Ci| > 1 do 11.for all the partitions {Cj,Ck} of Ci where both Cj,Ck are effective coalitions do 12.MapProcess(Cj),MapProcess(Ck)13.if{Cj,Ck}? sCithen 14.Ci ←Cj,Π ←Π ?Ck 15.end if 16.end for 17.end for 18.until Π no change or loop number is reached

4 基于聯(lián)盟形成博弈的虛擬機(jī)遷移方法

本節(jié)中，根據(jù)遷移前后高載物理機(jī)的數(shù)量的變化、物理機(jī)負(fù)載標(biāo)準(zhǔn)差的變化來評估VMM-CFG的性能。

4.1 參數(shù)設(shè)置

假設(shè)有x個(gè)物理機(jī)。對于每個(gè)物理機(jī)，容量最小為200，容量最大為300。物理機(jī)容量和閾值之間的差值隨機(jī)分布在(0,50]。物理機(jī)的最大通信帶寬為50。假設(shè)有3x個(gè)虛擬機(jī)，用戶所需的最小和最大虛擬機(jī)數(shù)量分別為4和8。虛擬機(jī)所需的資源從10到20不等。

4.2 結(jié)果分析

由圖3 可知，隨著物理機(jī)數(shù)量的增加，高載物理機(jī)數(shù)量也成比例地增加。基于VMM-CFG算法遷移后，高載物理機(jī)的數(shù)量明顯下降，實(shí)現(xiàn)了物理機(jī)間負(fù)載均衡的目標(biāo)，且隨著物理機(jī)數(shù)量的增加，高載物理機(jī)數(shù)量的降幅增加，這意味著物理機(jī)規(guī)模越大，物理機(jī)間的負(fù)載均衡效果越明顯。因此，VMM-CFG算法更適合于物理機(jī)數(shù)量龐大的云環(huán)境下。

圖3 遷移前后高載物理機(jī)的數(shù)量和物理機(jī)負(fù)載的標(biāo)準(zhǔn)差變化

在虛擬機(jī)遷移前，物理機(jī)負(fù)載的標(biāo)準(zhǔn)差數(shù)值較大。虛擬機(jī)遷移后，物理機(jī)負(fù)載的標(biāo)準(zhǔn)差降幅明顯，這說明VMM-CFG 算法實(shí)現(xiàn)了物理機(jī)間的負(fù)載均衡，且效果明顯。另外，隨著物理機(jī)數(shù)量增加，物理機(jī)負(fù)載的標(biāo)準(zhǔn)差趨于平穩(wěn)，這意味著物理機(jī)的規(guī)模越大，物理機(jī)的負(fù)載更加均衡。

5 結(jié)論

本文研究了云數(shù)據(jù)中心的虛擬機(jī)遷移問題。在虛擬機(jī)遷移過程中，主要考慮了兩個(gè)問題：哪些虛擬機(jī)應(yīng)該從高載物理機(jī)中遷移；待遷移的虛擬機(jī)應(yīng)該放置在哪些低載物理機(jī)上。為了最大限度地降低通信成本，減少高載物理機(jī)的數(shù)量，將基于聯(lián)盟形成博弈的虛擬機(jī)遷移算法引入虛擬機(jī)遷移中。仿真結(jié)果表明，VMM-CFG算法在實(shí)現(xiàn)物理機(jī)負(fù)載均衡方面具有優(yōu)勢。