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

阮志強,陳志德

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

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

阮志強1,陳志德2

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

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

云計算；資源分配；虛擬機；延遲

資源分配是云計算自動化管理軟件的核心功能之一，用戶通常請求云為其分配虛擬機以完成計算任務。由于傳統的數據中心由于距離較大，需要經過多個服務運營商，延遲會有很大的差異，而分布式數據中心[1]可以降低訪問延遲。但是，云自動化軟件的資源分配算法對用戶程序的性能有直接的影響，因為有時需要將同一個計算任務的資源分配到多個相對較小的數據中心。即使一個數據中心能夠滿足用戶請求，從容錯性角度考慮，用戶也不希望將所有的虛擬機設置在同一個數據中心內部。

數據中心內部可以看作分層結構，每個機架有一些固定的刀片服務器，每個刀片服務器由一些處理器組成(單核、雙核或多核)。同一刀片上不同處理機上的虛擬機可以直接通信，而同一機架上的不同刀片服務器上的機器需借助機架頂部交換機實現通信，兩個機架之間則使用聚合交換機。如果機架位置相隔較遠，可能需要多層的聚合交換機。可見，某個應用程序的虛擬機之間的通信延遲取決于調度的物理機器的位置。

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

文中的目標是減少數據中心之間以及數據中心內部的通信量，同時最小化數據包傳遞的路徑長度，以提高服務性能。整個資源分配過程可分為以下4步：

1)數據中心選擇：確定放置用戶虛擬機的數據中心。根據用戶請求條件和系統可用性，用戶虛擬機可能會被放置在多個數據中心。如何找到一個數據中心子集，滿足資源需求的同時最小化數據中心之間的路徑長度，是本文要解決的第一個問題。這是因為虛擬機之間通信延遲越大，任務完成時間越滯后，從而影響用戶總體完成時間。

2)任務分割：一旦確定好滿足用戶請求的候選數據中心，需要為每個虛擬機指派一個數據中心。這一步的目標是最小化數據中心之間的通信量。

3)機架、刀片和處理器選擇：為每一個選中的數據中心確定物理計算資源，同樣的，優先選擇機架間通信量的最低的物理機器。

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

1 數據中心選擇

數據中心選擇問題可用看作子圖選擇問題，給定一個完全圖G=(V,E,w,l)，頂點V表示數據中心，w表示數據中心內可用的虛擬機數量。E表示數據中心之間的路徑，d表示路徑的長度、跳數或最短路徑的延遲。如果用戶請求中包含最多放置虛擬機個數/每個數據中心這一限制條件，頂點的權重w就設為給定的最大值。反之，如果請求中包含最小放置虛擬機個數/每個數據中心，將權值低于最小值的頂點從圖中移除。令m表示用戶請求的虛擬機個數，問題變為找到一個子圖G，它的權值之和至少是m而且子圖的直徑（即任意兩個頂點間距離的最大值）最小。

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

算法1描述找到最小直徑子圖的過程，首先對于每一個頂點v，找到一個以v為中心的星型拓撲，加入的節點以到v的長度遞增排序，直到星型拓撲的權值大于m。子圖的邊由拓撲中節點的邊得來。該算法同樣計算生成子圖的直徑(DIA)，當一個節點加入時，當且僅當引入該節點導致邊的長度大于當前的直徑時，子圖的直徑才會更新。然后，對于找到的每一個子圖，算法選擇具有最小直徑(L)的子圖。

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

2 內部機器選擇

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

機器選擇的目標是找到可以降低機架間通信路徑的機器，可以將數據中心內部結構看作一顆樹，根節點代表核心交換機，子節點代表頂層交換機，孫子節點代表第二層聚合交換機，以此類推，最終葉子節點代表機架或者刀片服務器。在這顆樹中，所有的葉子節點處于同一層，給每個葉子節點賦一個權值，表示該機架或刀片服務器當前可用的虛擬機數目。對于機器選擇問題，主要是最小化任意兩個虛擬機之間的通信距離，即找到一顆具有最小高度且葉子節點權值之和大于給定虛擬機請求大小的子樹。與上一節類似，我們可以加入一些限制條件，比如，每個機架或刀片服務器內至多或至少應選擇的虛擬機數量，只要改變葉子節點的權值就可以實現。

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

3 虛擬機放置

分配虛擬機給數據中心及其內部CPU問題屬于圖劃分和k-切割問題，將用戶請求表示成圖G=(V,E)，頂點V表示任務或待放置的虛擬機，邊E表示虛擬機之間的通信需求。這里的目標是將V劃分成不相交的集合S1，S2，…Sk，使得不同分割集的頂點之間的通信代價最小。圖的每一個分割集代表需要調度的虛擬機集合，這些虛擬機集合處于相同的數據中心（全局或云調度）或相同的機架（數據中心內部調度）。每個分割的大小受限于對應的數據中心或機架的可用虛擬機個數。與傳統的圖劃分不同，這里可能不會指定每個分割集確切的節點數目，只要求每個劃分的最大節點數，因為系統中可用的虛擬機往往比請求的要多。

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

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

可以利用Meng[4]提出的貪婪算法進一步提高查找分割集的效率，主要是研究不同分割子集中的任意一對節點，檢查如果互換這一對節點是否可以降低帶寬使用。或者考慮將一個節點從一個集合移到另一個集合，看是否能夠提高可用的容量。該算法找到所有移動的可能性，并找出最好的策略。整個過程一直重復，直到達到給定的移動次數或者算法沒有進一步提高為止。

算法3中每個節點 （虛擬機）執行一次 repeat循環，Comm變量可以用堆棧維護，對于每個節點，該變量為每個鄰居至多更新一次，因此，算法3的時間復雜度是O(n2log n)。

4 實驗分析

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

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

為了評估上述算法的性能，隨機生成網絡拓撲和用戶請求，并衡量這些算法放置虛擬機后任意兩個虛擬機之間的最大距離（直徑）。實驗設置如下：數據中心的位置從800×800的網格內隨機選擇，這些數據中心之間的距離是網格上點之間的歐幾里得距離。每個分布式云包含的數據中心可以是100,300,500,700，到900，但是每個云包含的物理機器是相同的，也就是說一個數據中心的物理機器數量與其數據中心大小成反比。比如100個數據中心，每個數據中心包含50～100個物理機器。與500個數據中心，每個數據中心包含10～20個物理機器。這兩個云的物理機器總數是一樣的。

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

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

接著，考慮用戶指定額外限制條件下的通信距離。實驗條件變為500個用戶請求，每個用戶需要10~20個虛擬機，由100個數據中心構成的云系統。限制條件是每個數據中心最多可放置的虛擬機個數，即分配的虛擬機個數占該數據中心總的虛擬機個數的比例，用r表示。圖2給出了3個比較方案與限制條件r的關系。顯然，隨著r的增大，虛擬機之間的平均距離縮短，這是因為同一數據中心要求放置的虛擬機數量增大，大部分虛擬機之間的通信限制在數據中心內部。當r分別為0.1和0.9時，MCD的通信距離是貪婪算法的1/5和1/3，是隨機方法的1/7和1/4。從圖2可以還看出，通信距離可以通過參數r動態調整。

圖3 系統通信總量比較Fig.3 Comparison of total system communication

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

5 結束語

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

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

[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]裴養,吳杰,王鑫.基于粒子群優化算法的虛擬機放置策略[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 稿件編號：201411196

國家自然科學基金項目(61202462);福建省自然科學基金項目(2014J05079);福建省資助省屬高校科研專項(JK2013043);福建省教育廳重點項目(JA13248);閩江學院科研啟動項目(YKQ13003);教育部互聯網創新平臺開放基金項目(KJRP1301)

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