一種通信距離最小化的虛擬機(jī)分配算法

阮志強(qiáng),陳志德

（1.閩江學(xué)院 福建 福州350108；2.福建師范大學(xué) 福建 福州350108）

一種通信距離最小化的虛擬機(jī)分配算法

阮志強(qiáng)1,陳志德2

（1.閩江學(xué)院 福建 福州350108；2.福建師范大學(xué) 福建 福州350108）

為了解決云資源分配過程中虛擬機(jī)通信距離較大，造成用戶計(jì)算任務(wù)完成時(shí)間延長(zhǎng)問題，提出一種最短通信距離的虛擬機(jī)分配算法。云資源管理器能夠根據(jù)用戶指定的虛擬機(jī)條件，將計(jì)算任務(wù)分割到合適的數(shù)據(jù)中心及其內(nèi)部服務(wù)器，大大縮短了虛擬機(jī)之間的通信距離。仿真實(shí)驗(yàn)表明，與現(xiàn)有的貪婪算法和隨機(jī)方法相比，提出的方法通信量更少，執(zhí)行速度更快。

云計(jì)算；資源分配；虛擬機(jī)；延遲

資源分配是云計(jì)算自動(dòng)化管理軟件的核心功能之一，用戶通常請(qǐng)求云為其分配虛擬機(jī)以完成計(jì)算任務(wù)。由于傳統(tǒng)的數(shù)據(jù)中心由于距離較大，需要經(jīng)過多個(gè)服務(wù)運(yùn)營(yíng)商，延遲會(huì)有很大的差異，而分布式數(shù)據(jù)中心[1]可以降低訪問延遲。但是，云自動(dòng)化軟件的資源分配算法對(duì)用戶程序的性能有直接的影響，因?yàn)橛袝r(shí)需要將同一個(gè)計(jì)算任務(wù)的資源分配到多個(gè)相對(duì)較小的數(shù)據(jù)中心。即使一個(gè)數(shù)據(jù)中心能夠滿足用戶請(qǐng)求，從容錯(cuò)性角度考慮，用戶也不希望將所有的虛擬機(jī)設(shè)置在同一個(gè)數(shù)據(jù)中心內(nèi)部。

數(shù)據(jù)中心內(nèi)部可以看作分層結(jié)構(gòu)，每個(gè)機(jī)架有一些固定的刀片服務(wù)器，每個(gè)刀片服務(wù)器由一些處理器組成(單核、雙核或多核)。同一刀片上不同處理機(jī)上的虛擬機(jī)可以直接通信，而同一機(jī)架上的不同刀片服務(wù)器上的機(jī)器需借助機(jī)架頂部交換機(jī)實(shí)現(xiàn)通信，兩個(gè)機(jī)架之間則使用聚合交換機(jī)。如果機(jī)架位置相隔較遠(yuǎn)，可能需要多層的聚合交換機(jī)?？梢?，某個(gè)應(yīng)用程序的虛擬機(jī)之間的通信延遲取決于調(diào)度的物理機(jī)器的位置。

將單個(gè)虛擬機(jī)分配給某個(gè)數(shù)據(jù)中心及其內(nèi)部的某個(gè)CPU屬于圖劃分問題，該問題是將圖分成大小相等的片，使得兩個(gè)片之間的連通最少。另一個(gè)相關(guān)問題是最小k-切割問題，是將圖分成k個(gè)集合，并最小化邊的權(quán)值。如果集合的大小沒有給出，而集合的個(gè)數(shù)必須是r，那么問題在多項(xiàng)式時(shí)間內(nèi)可解[2]。如果r作為輸入的一部分，問題是NP難或存在2-2r近似算法[3]。當(dāng)給定集合的大小和固定值r，存在3-近似算法。

文中的目標(biāo)是減少數(shù)據(jù)中心之間以及數(shù)據(jù)中心內(nèi)部的通信量，同時(shí)最小化數(shù)據(jù)包傳遞的路徑長(zhǎng)度，以提高服務(wù)性能。整個(gè)資源分配過程可分為以下4步：

1)數(shù)據(jù)中心選擇：確定放置用戶虛擬機(jī)的數(shù)據(jù)中心。根據(jù)用戶請(qǐng)求條件和系統(tǒng)可用性，用戶虛擬機(jī)可能會(huì)被放置在多個(gè)數(shù)據(jù)中心。如何找到一個(gè)數(shù)據(jù)中心子集，滿足資源需求的同時(shí)最小化數(shù)據(jù)中心之間的路徑長(zhǎng)度，是本文要解決的第一個(gè)問題。這是因?yàn)樘摂M機(jī)之間通信延遲越大，任務(wù)完成時(shí)間越滯后，從而影響用戶總體完成時(shí)間。

2)任務(wù)分割：一旦確定好滿足用戶請(qǐng)求的候選數(shù)據(jù)中心，需要為每個(gè)虛擬機(jī)指派一個(gè)數(shù)據(jù)中心。這一步的目標(biāo)是最小化數(shù)據(jù)中心之間的通信量。

3)機(jī)架、刀片和處理器選擇：為每一個(gè)選中的數(shù)據(jù)中心確定物理計(jì)算資源，同樣的，優(yōu)先選擇機(jī)架間通信量的最低的物理機(jī)器。

4)虛擬機(jī)放置：將每個(gè)虛擬機(jī)放置在物理資源上（機(jī)架、刀片、處理器），并最小化虛擬機(jī)之間跨機(jī)架的通信量。

1 數(shù)據(jù)中心選擇

數(shù)據(jù)中心選擇問題可用看作子圖選擇問題，給定一個(gè)完全圖G=(V,E,w,l)，頂點(diǎn)V表示數(shù)據(jù)中心，w表示數(shù)據(jù)中心內(nèi)可用的虛擬機(jī)數(shù)量。E表示數(shù)據(jù)中心之間的路徑，d表示路徑的長(zhǎng)度、跳數(shù)或最短路徑的延遲。如果用戶請(qǐng)求中包含最多放置虛擬機(jī)個(gè)數(shù)/每個(gè)數(shù)據(jù)中心這一限制條件，頂點(diǎn)的權(quán)重w就設(shè)為給定的最大值。反之，如果請(qǐng)求中包含最小放置虛擬機(jī)個(gè)數(shù)/每個(gè)數(shù)據(jù)中心，將權(quán)值低于最小值的頂點(diǎn)從圖中移除。令m表示用戶請(qǐng)求的虛擬機(jī)個(gè)數(shù)，問題變?yōu)檎业揭粋€(gè)子圖G，它的權(quán)值之和至少是m而且子圖的直徑（即任意兩個(gè)頂點(diǎn)間距離的最大值）最小。

算法1最小直徑子圖(Min Diameter Subgraph(G,m))

算法1描述找到最小直徑子圖的過程，首先對(duì)于每一個(gè)頂點(diǎn)v，找到一個(gè)以v為中心的星型拓?fù)?，加入的?jié)點(diǎn)以到v的長(zhǎng)度遞增排序，直到星型拓?fù)涞臋?quán)值大于m。子圖的邊由拓?fù)渲泄?jié)點(diǎn)的邊得來。該算法同樣計(jì)算生成子圖的直徑(DIA)，當(dāng)一個(gè)節(jié)點(diǎn)加入時(shí)，當(dāng)且僅當(dāng)引入該節(jié)點(diǎn)導(dǎo)致邊的長(zhǎng)度大于當(dāng)前的直徑時(shí)，子圖的直徑才會(huì)更新。然后，對(duì)于找到的每一個(gè)子圖，算法選擇具有最小直徑(L)的子圖。

算法1的時(shí)間復(fù)雜度估計(jì)如下：第6行是將G中所有節(jié)點(diǎn)到v的距離按長(zhǎng)度遞增排序，得到d(v,ki)≤d(v,ki+1)，其中ki表示距離，共有n-1個(gè)節(jié)點(diǎn)，需要O(n log n)，n表示數(shù)據(jù)中心的個(gè)數(shù)。另外，每個(gè)節(jié)點(diǎn)執(zhí)行一次repeat循環(huán)，加上計(jì)算直徑需要n2（有n2條邊）。因此，最差情況下算法1的時(shí)間復(fù)雜度是O(n2)。

2 內(nèi)部機(jī)器選擇

算法2最小高度子樹(Min Height Tree(T,s,m))

機(jī)器選擇的目標(biāo)是找到可以降低機(jī)架間通信路徑的機(jī)器，可以將數(shù)據(jù)中心內(nèi)部結(jié)構(gòu)看作一顆樹，根節(jié)點(diǎn)代表核心交換機(jī)，子節(jié)點(diǎn)代表頂層交換機(jī)，孫子節(jié)點(diǎn)代表第二層聚合交換機(jī)，以此類推，最終葉子節(jié)點(diǎn)代表機(jī)架或者刀片服務(wù)器。在這顆樹中，所有的葉子節(jié)點(diǎn)處于同一層，給每個(gè)葉子節(jié)點(diǎn)賦一個(gè)權(quán)值，表示該機(jī)架或刀片服務(wù)器當(dāng)前可用的虛擬機(jī)數(shù)目。對(duì)于機(jī)器選擇問題，主要是最小化任意兩個(gè)虛擬機(jī)之間的通信距離，即找到一顆具有最小高度且葉子節(jié)點(diǎn)權(quán)值之和大于給定虛擬機(jī)請(qǐng)求大小的子樹。與上一節(jié)類似，我們可以加入一些限制條件，比如，每個(gè)機(jī)架或刀片服務(wù)器內(nèi)至多或至少應(yīng)選擇的虛擬機(jī)數(shù)量，只要改變?nèi)~子節(jié)點(diǎn)的權(quán)值就可以實(shí)現(xiàn)。

用m表示一個(gè)數(shù)據(jù)中心內(nèi)需要放置的虛擬機(jī)數(shù)量，T是樹，代表數(shù)據(jù)中心的計(jì)算和網(wǎng)絡(luò)資源，對(duì) T中的每個(gè)節(jié)點(diǎn)都設(shè)置兩個(gè)變量：w(v)，表示從根節(jié)點(diǎn)到節(jié)點(diǎn)v的可用虛擬機(jī)數(shù)量，和h(v)，表示節(jié)點(diǎn)的高度。算法執(zhí)行之前，只有葉子節(jié)點(diǎn)設(shè)置權(quán)值變量。算法2找到一顆根為s，葉子節(jié)點(diǎn)累積權(quán)值為m且高度最小的子樹。算法執(zhí)行后續(xù)遍歷法，并為每個(gè)節(jié)點(diǎn)維護(hù)一顆具有m權(quán)值和的最小高度子樹。算法2的時(shí)間復(fù)雜度是O(n)。

3 虛擬機(jī)放置

分配虛擬機(jī)給數(shù)據(jù)中心及其內(nèi)部CPU問題屬于圖劃分和k-切割問題，將用戶請(qǐng)求表示成圖G=(V,E)，頂點(diǎn)V表示任務(wù)或待放置的虛擬機(jī)，邊E表示虛擬機(jī)之間的通信需求。這里的目標(biāo)是將V劃分成不相交的集合S1，S2，…Sk，使得不同分割集的頂點(diǎn)之間的通信代價(jià)最小。圖的每一個(gè)分割集代表需要調(diào)度的虛擬機(jī)集合，這些虛擬機(jī)集合處于相同的數(shù)據(jù)中心（全局或云調(diào)度）或相同的機(jī)架（數(shù)據(jù)中心內(nèi)部調(diào)度）。每個(gè)分割的大小受限于對(duì)應(yīng)的數(shù)據(jù)中心或機(jī)架的可用虛擬機(jī)個(gè)數(shù)。與傳統(tǒng)的圖劃分不同，這里可能不會(huì)指定每個(gè)分割集確切的節(jié)點(diǎn)數(shù)目，只要求每個(gè)劃分的最大節(jié)點(diǎn)數(shù)，因?yàn)橄到y(tǒng)中可用的虛擬機(jī)往往比請(qǐng)求的要多。

算法3最大分割子圖（Partition(G,M)）

算法3給出了一種圖分割問題的啟發(fā)式方法，輸入是用戶請(qǐng)求圖G和每個(gè)分割集的最大節(jié)點(diǎn)數(shù)目M=m1,m2,…mk，集合M可以由算法1得到。算法3首先將可用容量m1,m2,…mk降序排列，然后利用for循環(huán)盡可能填充這些數(shù)據(jù)中心或機(jī)架。for循環(huán)每次選擇一個(gè)虛擬機(jī)滿足最大輸入/輸出帶寬或鄰居個(gè)數(shù)，并將其放置在數(shù)據(jù)中心或機(jī)架中。該虛擬機(jī)加入被調(diào)度的虛擬機(jī)集合Si，接著算法考慮Si中所有節(jié)點(diǎn)的鄰居，找到擁有最大輸入/輸出通信量Comm(u)的節(jié)點(diǎn)u，并將節(jié)點(diǎn)u加入Si。整個(gè)算法一直重復(fù)，直到數(shù)據(jù)中心或機(jī)架中可用的虛擬機(jī)資源耗盡或者沒有可調(diào)用的虛擬機(jī)。

可以利用Meng[4]提出的貪婪算法進(jìn)一步提高查找分割集的效率，主要是研究不同分割子集中的任意一對(duì)節(jié)點(diǎn)，檢查如果互換這一對(duì)節(jié)點(diǎn)是否可以降低帶寬使用?；蛘呖紤]將一個(gè)節(jié)點(diǎn)從一個(gè)集合移到另一個(gè)集合，看是否能夠提高可用的容量。該算法找到所有移動(dòng)的可能性，并找出最好的策略。整個(gè)過程一直重復(fù)，直到達(dá)到給定的移動(dòng)次數(shù)或者算法沒有進(jìn)一步提高為止。

算法3中每個(gè)節(jié)點(diǎn) （虛擬機(jī)）執(zhí)行一次 repeat循環(huán)，Comm變量可以用堆棧維護(hù)，對(duì)于每個(gè)節(jié)點(diǎn)，該變量為每個(gè)鄰居至多更新一次，因此，算法3的時(shí)間復(fù)雜度是O(n2log n)。

4 實(shí)驗(yàn)分析

將提出的最短通信距離的虛擬機(jī)分配算法（Virtual Machine Allocation with Minimal Communication Distance,簡(jiǎn)稱MCD）,與貪婪算法（Greedy[5]和隨機(jī)選擇/放置方法(Random)[6]進(jìn)行比較。隨機(jī)方法任意選擇一個(gè)數(shù)據(jù)中心，并將請(qǐng)求的虛擬機(jī)盡可能多的放置在該數(shù)據(jù)中心內(nèi)。如果一個(gè)數(shù)據(jù)中心無(wú)法容納用戶所有請(qǐng)求的虛擬機(jī)，可選擇下一個(gè)數(shù)據(jù)中心，以此類推。貪婪算法每次都選擇擁有最大可用虛擬機(jī)的數(shù)據(jù)中心，并將請(qǐng)求的虛擬機(jī)盡可能多的放置在該數(shù)據(jù)中心內(nèi)。

圖1 不同數(shù)據(jù)中心的平均通信距離Fig.1 Average communication distance under different number of data centers

為了評(píng)估上述算法的性能，隨機(jī)生成網(wǎng)絡(luò)拓?fù)浜陀脩粽?qǐng)求，并衡量這些算法放置虛擬機(jī)后任意兩個(gè)虛擬機(jī)之間的最大距離（直徑）。實(shí)驗(yàn)設(shè)置如下：數(shù)據(jù)中心的位置從800×800的網(wǎng)格內(nèi)隨機(jī)選擇，這些數(shù)據(jù)中心之間的距離是網(wǎng)格上點(diǎn)之間的歐幾里得距離。每個(gè)分布式云包含的數(shù)據(jù)中心可以是100,300,500,700，到900，但是每個(gè)云包含的物理機(jī)器是相同的，也就是說一個(gè)數(shù)據(jù)中心的物理機(jī)器數(shù)量與其數(shù)據(jù)中心大小成反比。比如100個(gè)數(shù)據(jù)中心，每個(gè)數(shù)據(jù)中心包含50～100個(gè)物理機(jī)器。與500個(gè)數(shù)據(jù)中心，每個(gè)數(shù)據(jù)中心包含10～20個(gè)物理機(jī)器。這兩個(gè)云的物理機(jī)器總數(shù)是一樣的。

首先，將用戶請(qǐng)求的虛擬機(jī)個(gè)數(shù)固定為1 000個(gè)，圖1給出了虛擬機(jī)放置距離與數(shù)據(jù)中心個(gè)數(shù)之間的關(guān)系，可以看到，隨著數(shù)據(jù)中心個(gè)數(shù)的增大，任意兩個(gè)虛擬機(jī)的平均距離也增大。這是因?yàn)殡S著數(shù)據(jù)中心的增大，內(nèi)部可用的物理機(jī)器數(shù)量減少，因此，同一個(gè)計(jì)算任務(wù)的資源被分散到多個(gè)數(shù)據(jù)中心中，使得通信距離變大。另外，MCD方法比貪婪算法和隨機(jī)方法至少降低了80%的通信距離。

圖2 指定用戶限制條件的通信距離Fig.2 Communication distance given user requirement

接著，考慮用戶指定額外限制條件下的通信距離。實(shí)驗(yàn)條件變?yōu)?00個(gè)用戶請(qǐng)求，每個(gè)用戶需要10~20個(gè)虛擬機(jī)，由100個(gè)數(shù)據(jù)中心構(gòu)成的云系統(tǒng)。限制條件是每個(gè)數(shù)據(jù)中心最多可放置的虛擬機(jī)個(gè)數(shù)，即分配的虛擬機(jī)個(gè)數(shù)占該數(shù)據(jù)中心總的虛擬機(jī)個(gè)數(shù)的比例，用r表示。圖2給出了3個(gè)比較方案與限制條件r的關(guān)系。顯然，隨著r的增大，虛擬機(jī)之間的平均距離縮短，這是因?yàn)橥粩?shù)據(jù)中心要求放置的虛擬機(jī)數(shù)量增大，大部分虛擬機(jī)之間的通信限制在數(shù)據(jù)中心內(nèi)部。當(dāng)r分別為0.1和0.9時(shí)，MCD的通信距離是貪婪算法的1/5和1/3，是隨機(jī)方法的1/7和1/4。從圖2可以還看出，通信距離可以通過參數(shù)r動(dòng)態(tài)調(diào)整。

圖3 系統(tǒng)通信總量比較Fig.3 Comparison of total system communication

圖3給出了3個(gè)算法的通信總量與虛擬機(jī)請(qǐng)求數(shù)量的關(guān)系，實(shí)驗(yàn)中給定虛擬機(jī)之間的通信需求和每個(gè)數(shù)據(jù)中心的可用容量，其中，虛擬機(jī)的帶寬需求從0~1 Mbps之間任意選擇，數(shù)據(jù)中心個(gè)數(shù)設(shè)為500，每個(gè)實(shí)驗(yàn)重復(fù)20次，并取平均值。對(duì)每個(gè)虛擬機(jī)請(qǐng)求，隨機(jī)算法任意指派一個(gè)數(shù)據(jù)中心，貪婪算法按照數(shù)據(jù)中心的可用容量降序排列，并盡可能將虛擬機(jī)放置在最大可用空間的數(shù)據(jù)中心內(nèi)。當(dāng)選擇虛擬機(jī)時(shí)，總是選擇擁有總通信量最大的虛擬機(jī)。從圖3可以看出，隨著請(qǐng)求虛擬機(jī)的增大，系統(tǒng)總通信量升高。在同樣的虛擬機(jī)請(qǐng)求大小條件下，貪婪算法比隨機(jī)算法大約降低22%的通信量，而MCD比貪婪算法大約降低18%

5 結(jié)束語(yǔ)

文中首先介紹了分布式云的作用和運(yùn)行機(jī)制，重點(diǎn)闡述了基于虛擬化技術(shù)的資源管理方法。然后將虛擬機(jī)整合問題劃分為4個(gè)步驟，即數(shù)據(jù)中心選擇、任務(wù)分割方法、內(nèi)部機(jī)器選擇和虛擬機(jī)放置。為降低虛擬機(jī)之間的通信延遲，提出了一種最小直徑子圖的數(shù)據(jù)中心選擇算法，基于最小高度子樹的內(nèi)部機(jī)器選擇算法，以及最大分割子圖的虛擬機(jī)放置算法。實(shí)驗(yàn)結(jié)果表明，本文提出的虛擬機(jī)整合算法MCD能夠大大降低虛擬機(jī)之間的通信距離（延遲）。

雖然本文的虛擬機(jī)整合算法能夠降低虛擬機(jī)的通信延遲，但由于系統(tǒng)的負(fù)載不斷發(fā)生變化，虛擬機(jī)整合還需要綜合考慮CPU的利用率、內(nèi)存占用情況、以及網(wǎng)絡(luò)帶寬資源，下一步工作將研究虛擬機(jī)動(dòng)態(tài)遷移的方法，使得系統(tǒng)的負(fù)載均衡化，從而降低系統(tǒng)總能耗。

[1]Alicherry M,Lakshman T.V.Network aware resource allocation in distributed clouds[C]//Proceedings of 31th IEEE International Conference on Computer Communications,INFOCOM 2012,2012:963-970.

[2]Eisenschmidt E,Haus U.A polynomial time approximation algorithm for the two-commodity splittable flow problem[J].Mathematical Methods of Operations Research.2013,77(3): 381-391.

[3]Ravia R and Sinhab A.Approximating k-cuts using network strength as a Lagrangean relaxation[J].European Journal of Operational Research,2008,186(1):77-90.

[4]Meng X,Pappas V,and Zhang L.Improving the scalability of data center networks with traffic-aware virtual machine placement[C]//Proceedings of 29th IEEE International Conference on Computer Communications,INFOCOM 2010, 2010:1-9.

[5]裴養(yǎng),吳杰,王鑫.基于粒子群優(yōu)化算法的虛擬機(jī)放置策略[J].計(jì)算機(jī)工程,2012,38(16):291-293.PEI Yang,WU Jie,WANG Xin.Virtual machine placement strategy based on particle swarm optimization algorithm[J].Computer Engineering,2012,38(16):291-293.

[6]TANG Zhuo,MO Yan-qing,LI Ken-li,et al.Dynamic forecast scheduling algorithm for virtual machine placement in cloud computing environment[J].The Journal of Supercomputing, 2014,70(3):1279-1296.

A virtual machine allocation algorithm with m inimal communication distance

RUAN Zhi-qiang1,CHEN Zhi-de2
（1.Minjiang University,Fuzhou 350108,China；2.Fujian Normal University,Fuzhou 350108，China)

Traditional resource allocation algorithm of cloud computing does not consider the communication distance of virtual machines,which may increase the complete time of user task.To address this problem,we propose an efficient virtual machine algorithm that includes data center selection algorithm and internal infrastructure assignment algorithm.Users can specify their requirements when requesting virtual machines,the resource allocator can partition this request into a few suitable data centers and their internal servers,so that the distance between any pairs of virtual machines is shortest.The results show that the proposed algorithms outperform greedy-based approach and random selection method in communication traffic and executing time.

Cloud computing；resource allocation；virtual machine；delay

TN91

A

1674－6236（2015）10-0001-04

2014-11-23 稿件編號(hào)：201411196

國(guó)家自然科學(xué)基金項(xiàng)目(61202462);福建省自然科學(xué)基金項(xiàng)目(2014J05079);福建省資助省屬高?？蒲袑ｍ?xiàng)(JK2013043);福建省教育廳重點(diǎn)項(xiàng)目(JA13248);閩江學(xué)院科研啟動(dòng)項(xiàng)目(YKQ13003);教育部互聯(lián)網(wǎng)創(chuàng)新平臺(tái)開放基金項(xiàng)目(KJRP1301)

阮志強(qiáng)(1982—)，男，福建莆田人，博士，講師。研究方向：云計(jì)算、分布式存儲(chǔ)。