基于層次拓撲樹的虛擬機節能分配算法

蔡立軍+何庭欽+孟濤+陳磊

摘 要：為了均衡分布式數據中心物理主機多維資源的利用率，減少物理主機使用數量，節約能耗，提出了一種基于層次拓撲樹的虛擬機節能分配算法HTES（hierarchical topology energy saving），此算法可以有效提升虛擬機分配效率.利用Laplacian矩陣，對大規模網絡拓撲分割，建立了層次拓撲樹模型.基于層次拓撲模型，根據虛擬機請求中IP地址與數據中心的距離，將虛擬機請求分組，從層次拓撲樹模型中查詢合適的物理主機區域，按虛擬機請求與物理主機的資源匹配度進行虛擬機的分配.將HTES與其他3種算法進行模擬仿真實驗，從虛擬機分配時間、資源均衡率、能耗和物理主機使用情況等方面驗證了HTES算法能夠有效加快物理主機搜索速度，增加底層占用物理主機的集中度，降低底層物理主機的使用數量，達到節約能耗的目的.

關鍵詞：數據中心；虛擬機分配；層次拓撲樹；能源利用率

中圖分類號：TP391 文獻標志碼：A

Energy Saving Allocation Algorithm

of a Virtual Machine Based on Hierarchical Topology Tree

CAI Lijun1，HE Tingqin1，MENG Tao1，CHEN Lei2

（ 1. College of Information Science and Engineering，Hunan University，Changsha 410082，China；

2. College of Electrical and Information Engineering， Hunan University，Changsha 410082，China）

Abstract：In order to balance the utilization of multi-dimensional physical host resources and reduce usage number， a virtual machine allocation energy saving algorithm was proposed based on hierarchical topology tree （HTES） in the environments of distributed data center， which enhances allocation efficiency of the virtual machines. Laplacian matrix was then used to split large-scale network topology and to build hierarchical topology tree model. Furthermore， according to the distance between request IP address and the data center， HTES divided the virtual machines into groups， and searched the appropriate physical host region from hierarchical topology tree for allocation， which is based on the match degree between virtual machine requests and physical hosts. Simulation experiments were performed on HTES algorithms and other three algorithms， considering the virtual machine allocation time， resource balancing rate， energy consumption and physical host usage， and other aspects. The results shows that the HTES is able to balance multi-dimensional resources physical hosts， reduce physical host usage， and save energy consumption.

Key words：data centers；virtual machine allocation；hierarchical topology tree；energy utilization

隨著信息科技的不斷發展，數據中心作為一種基礎設施，已經被各行各業普遍使用.然而當前數據中心的發展也面臨新的問題，數據中心的規模不斷擴張，地理位置愈趨分散.多個分散的數據中心通過高速網絡互聯，共同組成了大型的分布式數據中心.在分布式數據中心內，用戶通過按需付費的模式，向數據中心提交需求.數據中心根據用戶地理位置，從較近的基礎設施庫分配資源并構建虛擬機為用戶服務.然而，大規模分布式數據中心環境的虛擬機的分配問題面臨新的挑戰，主要表現為主機地理位置更為分散、底層資源規模更為龐大、多維異構資源、較高的能源消耗等.因此，合理的虛擬機（資源）分配策略是數據中心收益的保障，研究虛擬機分配算法具有重要意義.

目前已有很多學者對數據中心虛擬機的分配進行研究，取得了較多的優秀成果.一些研究成果集中在優化分布式數據中心的資源分配上[1-6].文獻[1]從服務供應商的角度，研究了分布式數據中心的收益最大化問題，提出了一種結合虛擬機分配的動態調價算法.文獻[2-3]同樣著眼于分布式數據中心的成本優化問題，從數據傳輸和資源分配兩個角度設計了相應的數據管理系統和資源調度算法，最小化數據、成本低的同時，優化了數據的傳輸時間、提升了底層物理資源的利用率.文獻[4]提出了一種基于溫度感知的資源管理系統，通過動態調整服務器的功率，實現虛擬機分配和服務器負載間的優化.文獻[5]在分布式數據中心內，對虛擬機的分配請求建立G/G/1/PS隊列，通過優化隊列處理實現服務器負載和虛擬機分配的均衡，節約了數據中心能耗.文獻[6]為提升高性能數據中心資源使用率，設計了CAE集成平臺架構，實現了一種基于Web方式的高性能計算中心資源的解決方案.有些研究工作使用數據中心網絡拓撲來優化虛擬機的分配，提升底層物理資源的利用率[7-10].在portland網絡拓撲上，文獻[7]提出了2種啟發式算法，通過分配虛擬機到最大鏈路能力和鄰近的物理主機上，降低了網絡開銷，增加了底層資源利用率.文獻[8]根據網絡拓撲建立了MNT指標，優化資源分配.文獻[9]在網絡拓撲的基礎上，通過虛擬機和鏈路的合并，增加了拓撲中空閑網絡設備數量，節約了能源.同樣，在實際數據中心拓撲上，文獻[10]通過對帶寬過載的虛擬機進行合并，優化了網絡傳輸消耗.此外，還有較多學者研究數據中心的能耗問題[11-14]，通過各種模型和方法減少數據中心的能源消耗.文獻[11]同時考慮了虛擬機的分配和網絡流的傳輸，通過建立線性規劃模型，并行處理虛擬機的分配，節約能源消耗.文獻[12]中將虛擬機的分配問題看做多商品流的成本最小化問題，通過Benders分解算法進行求解，減少了底層物理主機的使用數量，節約了能源消耗.文獻[15]分析了云數據中心下資源分配和能源消耗問題，設計了一種節能框架，在減少成本的同時節約能耗.文獻[16]研究了分布式數據中心內的能源節約問題，建立了最大化整數規劃模型，通過虛擬機的合并，減少了物理主機的使用，從而實現能耗的節約.

以上的研究工作在處理大規模非樹型隨機網絡拓撲[17]的虛擬機分配問題上，無法有效減少數據中心物理主機的使用數量，仍面臨能耗較高的缺陷.網絡拓撲的大規模性和隨機性導致虛擬機分配時掃描的物理主機范圍更為龐大，使用傳統的算法效率較低，一方面表現在底層物理主機的搜索時間過長，降低了虛擬機的分配效率；另一方面底層物理主機分配后集中度較低，過高的分散性不利于物理主機的管理和維護.如DCEERS算法[18]通過Benders分解進行虛擬機分配，利用最小數量的物理主機承載虛擬機請求，雖然減少了物理主機的數量，在一定程度上降低了能耗，但并未考慮資源的均衡率，可能引起局部負載及單位時間功耗過大；ANT算法[19]利用蟻群策略求解多目標虛擬機的分配問題，但卻需要大量的迭代尋找最優，分配時間上較差.

因此，本文提出了一種基于層次拓撲樹的虛擬機節能分配算法.首先，將分布式數據中心的大規模網絡隨機拓撲進行拓撲分割，建立層次拓撲樹.其次，在考慮底層物理主機多維資源均衡的前提下，掃描層次拓撲樹，將虛擬機集中分配網絡拓撲中的集中區域，降低底層物理主機的使用.通過關閉空閑物理主機達到節約能源的目的.最后，通過大量實驗驗證了算法的性能.基于層次拓撲樹的虛擬機節能分配算法優化了虛擬機的分配，提高了底層資源利用率，降低了能源消耗.

1 模型建立

1.1 預備知識

1.1.1 分布式數據中心網絡拓撲

網絡拓撲是數據中心整體結構的一種表示和體現.數據中心所有物理主機、存儲設備、網絡設備通過網絡鏈路彼此互連，共同組成網絡拓撲.通常情況下，網絡拓撲用圖G=V，E表示.其中，V為節點集合，表示數據中心內所有的物理設備；E為邊的集合，表示兩兩物理設備間的網絡鏈路能力，即網絡帶寬.

在虛擬機的分配過程中，網絡拓撲起著重要的作用.所有的虛擬機必須映射到網絡拓撲中的物理主機上，占用物理主機的CPU，MEM資源，占用網絡拓撲中多個物理主機間的鏈路帶寬資源，甚至占用拓撲中存儲節點的部分存儲資源.一個虛擬機在分配過程中，需要掃描網絡拓撲中的空閑物理主機，進行最終的資源分配.網絡拓撲可以輕松反映虛擬機的分配情況和運行情況，能夠方便監控物理主機的負載和運行，便于物理主機的資源調優和能源節約.當網絡拓撲發生變化時，說明底層物理設備出現了故障，需要進行虛擬機的遷移和重新分配.

分布式數據中心由多個地理位置分散的小型數據中心組成.小型數據中心之間通過高速網絡進行互連.每個小型數據中心彼此獨立，可以擁有不同類型的網絡拓撲和物理主機.通常，分布式數據中心的整體網絡拓撲是隨機的，底層物理主機資源是異構的.圖1為分布式數據中心網絡拓撲圖.

在圖1中，分布式數據中心由K個小型數據中心組成.每個數據中心擁有不同的網絡拓撲和物理主機類型.分布式數據中心的網絡拓撲呈現隨機性和大規模性，物理主機擁有異構特性.網絡拓撲的大規模性和隨機性導致虛擬機分配時掃描的物理主機范圍龐大，增加了虛擬機的搜索時間，降低了虛擬機的分配效率.此外，網絡拓撲的大規模性必然存在大量物理主機和網絡設備空閑的情況，帶來龐大的能源開銷，增加數據中心的成本；物理主機的異構性增加了虛擬機分配后物理主機多維資源間的不均衡分配，造成資源浪費；數據中心的分散性增加了額外的網絡開銷，浪費了網絡帶寬資源.

1.1.2 單機多維資源的不均衡分配

在數據中心網絡拓撲中，物理主機本身由多種資源組成（CPU，MEM和存儲），可看作多維資源向量.如果某維資源（CPU）過度分配，必然造成其他維資源（MEM和存儲）的浪費.只有均衡利用各維資源，才能更充分地發揮資源效率，提升底層資源的利用率，減少數據中心物理主機的使用數量，降低能源開銷.在傳統虛擬機分配過程中，虛擬機的隨機分配往往導致單機多維資源的不均衡分配.

圖2（a）為單機多維物理資源的不合理分配情況.由圖2（a）可知，僅考慮了CPU和MEM兩維資源，3個虛擬機分配到了物理主機上，造成了物理主機CPU資源的利用率達到了90%（40%+20%+30%）.然而，物理主機的內存資源才使用25%（15%+8%+2%）.當新的虛擬機訪問物理主機時，雖然剩余較多的內存資源，但是由于CPU資源的高利用率，導致物理主機無法承載新的虛擬機，從而造成了內存資源的大量浪費，出現單機多維資源的不均衡分配.圖2（b）中，描述了物理主機的均衡分配情況.同樣是3個虛擬機，但是物理主機的CPU和MEM資源利用率相對均衡，都達到了90%，不會出現單維資源的空閑浪費，能夠更加充分地利用底層資源.

單機多維資源的均衡分配能夠提升底層物理資源的利用率，降低數據中心成本.此外，多維資源的均衡分配，可以在一定程度上減少底層物理主機的使用數量，達到降低數據中心能耗的目的.

1.2 問題描述

分布式數據中心內虛擬機的調度過程可描述為：位置各異的多個用戶向數據中心提交一批虛擬機請求Vms={vm1，vm2，…}.每個虛擬機擁有4種屬性，用vmi={req_cpui，req_memi，req_bwi，ipi，lifetimei}表示，其中req_cpui，req_memi，req_bwi分別表示CPU，MEM和帶寬請求大小，ipi表示用戶的地理位置信息，lifetimei表示當前虛擬機的生命周期.分布式數據中心由網絡拓撲圖G=V，E表示.其中，V為物理資源的集合，E為物理資源間網絡鏈路帶寬的集合.在分布式數據中心內，用戶提交的虛擬機請求將根據用戶位置分配到較近的物理主機上，占用物理主機資源和網絡帶寬.每個物理主機hostj={cab_cpuj，cab_memj，cab_bwj，DC}擁有3種資源CPU，MEM和帶寬.DC（Data Center）是物理主機所屬子數據中心的標識，代表物理主機的位置信息.

在虛擬機的分配過程中，每個虛擬機vmi只能分配到一臺物理主機上hostj.物理主機hostj的剩余資源能力必須滿足虛擬機的請求.一個用戶可以提交多個虛擬機請求，同一用戶的多個虛擬機應該分配在同一地理位置的物理主機上.此外，分布式數據中心內，多個數據中心的物理主機通常為異構主機，擁有不同的CPU，MEM大小.在分布式數據中心網絡拓撲中，所有網絡設備和存儲設備不能獨立承載虛擬機，不具備相應的計算和處理能力.

1.3 分配模型

根據分布式數據中心的虛擬機分配過程描述，本文的虛擬機分配目標是：均衡物理主機多維資源的分配，減少底層物理主機的使用數量，提升底層資源的利用率，節約數據中心的能源消耗.

分布式數據中心內，虛擬機的分配過程是連續的，分配過程不斷循環，一次分配過程完成后另一次分配過程準備開始.在多次虛擬機分配過程中，物理主機負載狀態前后一致.單個物理主機可以在不同輪次的分配過程中承載多個虛擬機請求.為了均衡單個物理主機多維資源的均衡分配，必須在物理主機歷史負載狀態下考慮本輪分配，實現虛擬機分配后物理主機各維資源的剩余率均衡.

為了更好地描述物理主機多維資源的均衡情況，文中定義了請求匹配度HMatch的概念，描述當前虛擬機分配到物理主機后各維資源的使用情況.

1， （sur_cpu

公式（1）描述了虛擬機vmi分配到物理主機hostj后，物理主機剩余資源的均衡程度.其中，req_cpui，req_memi表示虛擬機vmi對CPU和MEM資源的請求大小.sur_cpuj，sur_memj表示物理主機hostj經過多輪虛擬機分配后剩余的CPU和MEM資源大小.cab_cpuj，cab_memj表示物理主機hostj的原始CPU和MEM資源大小.本文僅考慮物理主機的CPU和MEM資源的分配均衡程度，暫未考慮存儲和I/O等資源.

此外，從式（1）可知，請求匹配度0≤HMatchij<2.當虛擬機vmi分配到物理主機hostj后，CPU和MEM的剩余資源占總資源的比值相同，則匹配度為0.否則，匹配度值大于0.剩余資源間越均衡，則匹配度值越小.通過匹配度的計算，可以快速獲取虛擬機分配對物理主機資源使用的影響，越小的資源匹配度，則說明物理主機資源的利用率越高，越能減少底層物理主機的數量，實現節約能耗的目的.

在式（2）中，Is_Newj描述了物理主機是否在歷史分配過程中承載了虛擬機.若當前物理主機是空閑物理主機，為承載任何虛擬機，則主機的剩余CPU和MEM能力與總資源能力相同.否則，剩余能力小于總資源能力.為了限制虛擬機隨意分配到新的空閑虛擬機，本文用整數1和2來分別描述當前物理主機的狀態.

在虛擬機分配過程中，虛擬機請求數量與底層物理主機數量不同，本文定義0-1變量xij表示虛擬機vmi與物理主機hostj間的映射關系，見式（3）.

xij=1 ， vmi is maped to hostj 0 ，vmi is not maped to hostj（3）

在式（3）中，虛擬機vmi分配到物理主機hostj上，則xij為1；否則，xij為0.因此，分布式數據中心虛擬機分配的目標函數可以表示如下：

min ∑j∈Hosts∑i∈Vmsxij×HMatchij （4）

st.

for each vmi： ∑j∈Hostsxij≤1

for each hostj： ∑i∈Vmsxij×req_cpui≤cab_cpuj

∑i∈Vmsxij×req_memi≤cab_memj∑i∈Vmsxij×req_bwi≤cab_bwj

for each vmi ， hostj： 0≤HMatchij<2

在式（4）中，最小的物理主機匹配度表示所有虛擬機分配到物理主機后，物理主機剩余資源的均衡性最好，則其可以承載的虛擬機數量就越多，分配過程中使用的物理主機數量將減少，此外，當已使用的物理主機分配完之后，再將虛擬機分配到其他的空閑物理主機上，從而節約了數據中心能耗.表1為分布式數據中心虛擬機分配過程中的符號及相關術語.

2 基于層次拓撲樹的節能分配算法

針對分布式數據中心的網絡拓撲特點，結合分配模型，本節提出了一種基于層次拓撲樹的虛擬機節能分配算法，簡稱HTES.首先，HTES將分布式數據中心的大規模網絡拓撲進行分配，建立了層次拓撲樹，詳細描述見2.1節；其次，在層次拓撲樹的基礎上，根據用戶的地理位置，將虛擬機分配到網絡拓撲中的某個區域，保證占用的物理主機相對集中，均衡物理主機多維資源分配，減少物理主機使用數量，節約能耗，詳細的分配算法見2.2節.

2.1 拓撲分割建立層次拓撲樹

分布式數據中心由多個地理位置分散的小型數據中心組成，整個網絡拓撲具有明顯的大規模性和隨機性.在虛擬機的分配過程中，需要為每個虛擬機尋找合適的物理主機，從而必須搜索網絡拓撲的所有物理主機.網絡拓撲的大規模給虛擬機的分配過程帶來了兩個難點：①增加了底層物理主機的搜索時間，降低了虛擬機的分配效率.②擴散了底層物理主機的占用分布.例如，同一用戶的多個虛擬機請求可能分配到不同地理位置的物理主機上，也可能分配到同一地理位置內的距離位置較遠的多臺物理主機上.這種分散性給底層物理主機的管理和維護帶來了巨大困難，增加了節能策略的監控難度.

針對以上兩個難點，本文對分布式數據中心的網絡拓撲進行逐級分割，建立層次拓撲樹.將整個拓撲轉化為層次結構，保證每一層的節點數目逐層遞減.當進行虛擬機分配時，根據虛擬機的分配數量，找到相應層級的拓撲子樹尋找物理主機，不用再掃描整個網絡拓撲，減少了物理主機的掃描時間，增加了虛擬機占用物理主機的集中度，便于虛擬機的快速分配和能耗節約.

為了進行網絡拓撲的分割，本文引入了規范割Normalized-cut（Ncut）和Laplacian矩陣，證明了Laplacian矩陣的第二特征值是2分Ncut的最優解.

定義1 規范割Normalized-cut（Ncut）是衡量網絡拓撲中兩個節點子集間相似度的標準，公式如下：

NcutA，=cut（A，）vol（A，V）+cut（A，）vol（，V）

A∈V and ∈V（5）

cut（A，）=∑i∈A，j∈wij （6）

vol（A，V）=∑i∈A，j∈Vwij （7）

式中：V為網絡拓撲G中的節點集合；wij為網絡拓撲的鄰接矩陣W中的值，表示節點i與節點j間的權值.鄰接矩陣W為對稱矩陣，其中wij=wji0.使用規范割Ncut進行拓撲分割度量，能夠較好地避免小區域的產生.

定義2 Laplacian 矩陣是網絡拓撲圖的一種有效表示方式，一個Laplacian矩陣對應一個非負權重的無向有權圖.Laplacian矩陣的常用表示如下：

Lsym=D-1/2LD-1/2=I-D-1/2WD-1/2（8）

式中：I為單位矩陣；D為網絡拓撲中節點的度矩陣；W為鄰接矩陣.每個節點的度di=∑njwij，表示與該節點相連的所有邊的權值和.

Laplacian矩陣具有如下特性：

1）任意n維向量f∈R，有：fΤLf=12∑ni，j=1wij×（fi-fj）2.

2）L為半正定矩陣.

3）L的最小特征值為0，對應的最小特征向量為值1的常向量A.

4）L有n個非負實特征值0=λ1≤λ2≤…≤λn.

5）如果網絡拓撲G是C的連通部件，那么L有C個等于0的特征值.

根據Ncut和Laplacian矩陣的定義和性質，可得Laplacian矩陣的第二特征值是2分Ncut的最優解，證明過程如下：

證明 設劃分向量f如下：

f（vi）=vol（，V）vol（A，V） ， if vi∈A -vol（A，V）vol（，V） ， if vi∈

根據L的性質1 ，得

fTLf=12∑ni，j=1wij（fi-fj）2=

12∑i∈A，j∈wij（fi-fj）2+12∑i∈A，j∈Awij（fi-fj）2+

12∑i∈，j∈Awij（fi-fj）2+12∑i∈，j∈wij（fi-fj）2=

12∑i∈A，j∈wij（fi-fj）2+12∑i∈，j∈Awij（fi-fj）2=

12cut（A，）vol（，V）vol（A，V） +vol（A，V）vol（，V） 2+

12cut（A，）-vol（，V）vol（A，V） -vol（A，V）vol（，V） 2=

cut（A，）vol（V，V）vol（A，V）+vol（V，V）vol（，V）=

vol（V，V）Ncut（A，）

此外：

fTDf=∑i∈Avol（，V）vol（A，V）divol（，V）vol（A，V）+

∑i∈-vol（A，V）vol（，V）di-vol（A，V）vol（，V）=

vol（，V）vol（A，V）∑i∈Adi+vol（A，V）vol（，V）∑i∈di=

vol（，V）vol（A，V）vol（A，V）+vol（A，V）vol（，V）vol（，V）=

vol（V，V）

將上述兩式結合，可得：NcutA，=fTLffTDf

根據L的性質3，可得：

DfTA=∑ni=1difi=∑i∈Adivol（，V）vol（A，V）-

∑i∈divol（A，V）vol（，V）=

vol（A，V）vol（，V）vol（A，V）-

vol（，V）vol（A，V）vol（，V）=

vol（A，V）vol（，v）-

vol（，v）vol（A，V）=0

因此，Ncut的最小化：min f fTLffTDf

st.

fi∈vol（，V）vol（A，V），-vol（A，V）vol（，V）

DfTA=0

由于最小化的Ncut是一個廣義Rayleigh商，根據性質可得λ1=0，D1/2A為其最小特征值，可得fTLf/fTDf的第二小特征值是Ncut的最優解.

根據Laplacian矩陣與Ncut間的特性，本文將分布式數據中心的網絡拓撲轉化為Laplacian矩陣，然后對其求第二特征值，從而將網絡拓撲分割成耦合度最小的兩個子集.再依次對兩個子集進行拓撲分割，最終形成層次拓撲樹.圖3為網絡拓撲分割的過程.

從圖中可以看出，網絡拓撲的分割過程為2分迭代分割，通過多次迭代將網絡拓撲分割成2個子拓撲.在整個分割過程中，必須保持多個數據中心間地位位置的分散特性.因此，分布式數據中心的層次拓撲樹的第一層拓撲樹就是多個地理位置分散數據中心拓撲，不進行過細的劃分.此外，拓撲分割的目標是加快物理主機的搜索速度，減少分配時間，2分迭代分割必然出現最下層子拓撲中節點數量較少的情況.為此，本文設定了拓撲分割門限SplT和拓撲合并門限MerT.根據拓撲分割門限SplT判斷是否繼續進行網絡拓撲的分割.根據拓撲合并門限進行節點數小于MerT的子拓撲的合并.因此，拓撲分割門限SplT必須大于拓撲合并門限MerT.

因此，分布式數據中心網絡拓撲分割的具體過程如下：①根據分布式數據中心內小型數據中心的網絡拓撲，建立第1層子拓撲集，保持分布式數據中心網絡拓撲間地理位置的分散特性；②逐個遍歷第1層子拓撲集，形成L矩陣，根據公式（8）進行第二特征值求解.根據求解結果計算相應的特征向量.按照特征向量中得到的節點列表，將網絡拓撲分割成兩個子拓撲；③逐層遍歷所有子拓撲，生成下一層子拓撲集.當某個子拓撲中的節點數量少于最低分割門限SplT，不再進行下一層拓撲分割；④當所有拓撲分割完成后，遍歷最后一層的子拓撲集，將節點數少于MerT的子拓撲與其兄弟節點進行合并；⑤遍歷所有層的子拓撲，統計每層子拓撲中節點數量的范圍，結合層次號和地理位置（IP），建立索引方便查詢.算法1詳細描述了網絡拓撲分割建立拓撲樹的詳細過程.

算法1 網絡拓撲分割過程

輸入：網絡拓撲G，拓撲分割門限值SplT，拓撲合并門限值MerT.

輸出：層次拓撲樹TT.

Step1 初始化.

1）根據網絡拓撲G，生成相應的鄰接矩陣W和度矩陣D.

2）初始化待分割的網絡拓撲集TS和子拓撲集STS為空.

3）初始化層次拓撲樹TT為空，層次序號IN為0.

4）根據網絡拓撲G和多個數據中心的地理位置分散關系，生成第1層子拓撲集，填充到STS，計算總節點數量VN.更新層次拓撲樹的頂層索引，包括層次序號、節點總數、子拓撲集合鏈接等，如下所示.更新完成后進入Step2，開始拓撲分割.insert 〈IN，VN，TS〉 to TTIN.

Step2 更新待分割拓撲集，將STS覆蓋TS，清空STS.更新當前層次拓撲樹的層號IN=IN+1.進入Step3開始拓撲分割.

Step3 判斷TS是否為空.TS為空，則進入Step5合并節點數目過小的子拓撲.否則，進入Step4，分割拓撲.

Step4 遍歷待分割拓撲集TS，生成子拓撲集STS.

1）計算子拓撲中節點數量VN.比較VN與分割門限SplT的大小.若大于，進入2）進行拓撲分割.若小于，則不進行拓撲分割.進行下一個子拓撲的計算.如果TS遍歷完成，進入Step2更新待分割拓撲集.

2）根據子拓撲G、鄰接矩陣W和度矩陣D，按照公式（8）生成L矩陣Lsym=I-D-1/2WD-1/2，其中I是單位矩陣.進入3）計算第二特征值.

3）根據L矩陣特性，計算（D-W）x=λDx的第二小特征值.根據特征值求得想要的特征向量f.按照特性向量中的節點，將子拓撲分割成兩個子集，加入STS中.進入4）更新層次拓撲樹.

4）計算中STS總節點數量VN，更新層次拓撲樹，如下所示.更新完成后重新進行1），分割下一個子拓撲.

insert 〈IN，VN，TS〉 to TTIN.

Step5 遍歷IN層子拓撲，判斷每個子拓撲中節點數量.若節點數量小于MerT，刪除當前子拓撲集和同一父節點的兄弟拓撲集.

2.2 區域性節能分配算法

根據分布式數據中心的網絡拓撲特性，在構建層次拓撲樹的基礎上，本節提出了一種區域性虛擬機節能分配算法HTES.HTES的核心節能策略是減少底層物理主機的使用，通過關閉空閑物理主機實現節能.較傳統的相同策略節能算法[12]而言，HTES關注于分布式數據中心環境；根據用戶IP分組虛擬機請求，就近提供物理主機資源；分割網絡拓撲建立層次拓撲樹，快速尋找合適的物理主機；區域性分配虛擬機到底層集中的物理主機上，緩解了傳統零散分配帶來的難管理、難節能、難糾錯等缺點；考慮物理主機多維資源的均衡分配，提高底層物理主機的資源利用率.

本文采用區域性分配，將虛擬機分配到底層集中的物理主機上，緩解了物理主機分散帶來的節能和管理困難.區域性虛擬機節能算法的主要流程分為：虛擬機請求分組，物理主機搜索和區域性虛擬機均衡分配3個步驟.

虛擬機請求分組：①請求分組，根據虛擬機請求中IP地址屬性，按照層次拓撲中頂層節點的地理位置（IP），將虛擬機請求進行分組.分組完成后，所有虛擬機請求都在距離自己最近的數據中心隊列中.②并發分配，并發對多個虛擬機請求分組進行相應的物理資源分配.

區域性物理主機搜索：①鎖定搜索層次.根據分組完成后的虛擬機請求個數V_size，查詢拓撲層次樹中空閑節點數量（物理主機）充足的子拓撲，保證子拓撲的空閑數量大于虛擬機請求數量α倍，更加均衡地分配虛擬機，均衡物理主機的多維資源.②比較資源能力.比較虛擬機請求大小與空閑物理主機的剩余能力，選擇剩余能力大于請求大小的物理主機.若物理主機搜索成功，數量等于α×V_size，則進行虛擬機分配.否則，遍歷當前子拓撲的父親拓撲，再次搜索合適數量的主機，直到找到α×V_size個物理主機為止.③請求遷移.如果當前頂層拓撲內所有空閑物理主機數量小于V_size，則分配相應數量的虛擬機請求，并將多余的虛擬機請求移動到鄰近的數據中心隊列中，等待分配.如果鄰近數據中心內資源同樣不足，則繼續遷移到其他數據中心.如果整個網絡拓撲資源不足，則返回最近數據中心等待其他虛擬機釋放資源.

均衡分配：根據虛擬機請求隊列和相應的物理主機隊列，進行虛擬機的最終分配.按照公式（1）的定義，將虛擬機分配到請求匹配度最好的物理主機上，完成分配過程.

圖4展示了基于層次拓撲樹的虛擬機節能分配算法過程.從圖中可以看出，虛擬機的分配過程主要分為虛擬機請求分組、根據層次拓撲樹搜索物理主機和虛擬機分配3個步驟.分布式數據中心由2個地理位置分散的小型數據中心A和B組成.4個用戶在不同的位置向數據中心提交了7個虛擬機請求.根據用戶IP和物理中心的位置，V1-V4虛擬機請求分配到了A，V5-V7分配到了B.根據虛擬機請求的數量，并發從A和B中尋找合適數量的子拓撲，進行虛擬機的分配，正如V1，V3-V7所示.然而，當子拓撲的可用物理主機數量小于虛擬機請求數量時，從其父節點的拓撲中尋找其他物理主機進行分配，如V2所示.在整個虛擬機的分配過程中，根據虛擬機請求與物理主機的匹配度公式（1），進行物理主機的分配.如圖中V1，V3，V4分配到了原拓撲的物理主機，V2因其匹配度較差從而分配到了原拓撲的父節點.整個節能分配算法HTES的分配過程如算法2所示.

算法2 基于層次拓撲樹的虛擬機節能分配算法

輸入：網絡拓撲G，虛擬機請求列表Vms

輸出：虛擬機分配結果.

Step1 初始化.根據網絡拓撲G，利用算法1生成層次拓撲樹TT，監控數據中心所有物理主機的使用情況.

Step2 虛擬機請求分組.

1）根據虛擬機的IP和數據中心位置，將虛擬機分配到位置最近的數據中心排隊隊列中.

2）分配完成后，并發對多個數據中心進行虛擬機的分配.

Step3 區域性搜索物理主機.

1）根據分組完成后的虛擬機請求個數V_size，查詢拓撲層次樹中空閑節點數量（物理主機）充足的子拓撲，保證子拓撲的空閑數量大于虛擬機請求數量α倍.

2）比較虛擬機請求大小與空閑物理主機的剩余能力，選擇剩余能力大于請求大小的物理主機.

3）若物理主機搜素成功，數量等于α×V_size，進入Step5進行虛擬機分配.否則，遍歷當前子拓撲的父親拓撲，再次搜索合適的數量主機，直到找到α×V_size個物理主機為止.

4）當遍歷到頂層拓撲，搜索完整個小數據中心的所有物理主機，物理主機數量不滿足V_size時，進入Step4進行虛擬機請求的遷移.

Step4 虛擬機請求的遷移.

1）當頂層拓撲內所有空閑物理主機數量小于V_size，則分配空閑主機數量的虛擬機請求，并將多余的虛擬機請求遷移到鄰近的數據中心隊列中，等待分配.

2）如果整個網絡拓撲資源不足，則返回最近數據中心等待其他虛擬機釋放資源.

Step5 均衡分配虛擬機.按照公式（1）的定義，根據請求匹配度的大小，將虛擬機分配到最好的物理主機上，均衡物理主機的多維資源，完成分配過程.

3 實驗結果分析

為了驗證HTES算法的性能，本文使用CloudSim3.5[17]作為仿真平臺，將HTES算法與貪婪算法GRD[18]，蟻群算法ANT[19]和DCEERS[12]算法進行比較，從分配時間、物理主機數量、物理主機異構使用情況等方面進行了性能驗證.

3.1 實驗環境

在CloudSim平臺上，利用brite網絡拓撲圖生成工具，隨機生成10個地理位置分散的數據中心網絡拓撲，拓撲中包括1 000個物理主機和200個網絡設備.表2為物理主機參數表.

此外，利用Cloudsim平臺中的DataCenter，Host，Vm，DataCenteBoker等多個類，構建相應的1 000個物理主機屬性信息和模擬對應的虛擬機請求信息.仿真了4種類型的物理主機模擬數據中心的異構特性：[〈4core-8g〉，〈8core-8g〉，〈8core-16g〉，〈16core-24g〉].同樣利用隨機的方式，模擬不同用戶在不同IP下的虛擬機請求，虛擬機請求數量從10～500隨機波動.每個虛擬機的資源請求大小為CPU[1～4]，內存為[1～10]×512 M.

3.2 參數設置

本節對實驗中的參數值拓撲分割門限值SplT，拓撲合并門限值MerT和虛擬機分配算法中的α參數進行討論及測試.在網絡拓撲分割的過程中，本文通過設定拓撲分割門限SplT和拓撲合并門限MerT來處理2分迭代分割出現的最下層子拓撲中節點數量較少的情況.本文通過固定合并門限，變動分割門限，或者固定分割門限，變動合并門限，通過不同的門限取值，觀察不同設置下平均虛擬機分配時間.在網絡拓撲中，對物理主機的搜尋速度越快，則相應的虛擬機分配時速會更快.因此實驗測試中，測試100個虛擬機請求的分配，設置拓撲分割門限值SplT（10～20），合并門限值MerT（0～5）時，從表3中可以看出，拓撲分割門限值SplT（15～16），拓撲合并門限值MerT（2～3）時，此時拓撲結構下物理主機的搜尋速度最快，虛擬機平均分配時間最少，顯示出良好的分配性能.

參數α是從子拓撲空閑物理主機數與虛擬機請求數量的比值.如果從子拓撲空閑物理主機中等同于虛擬機請求數量，則虛擬機的分配情況唯一，這種分配并非最優.因此從子拓撲空間選擇空閑物理主機數量是要大于虛擬機的請求數量.本文在仿真實驗中，設置固定虛擬機數為100，變動α取值為1.0～2.0，從網絡拓撲中，搜尋虛擬機請求數量α倍的物理主機，表4給出了部分實驗數據，可以看出，α取值為1.2～1.5時，物理主機的平均利用率較高，浪費率較低.

通過對表3和表4的分析可知，當拓撲分割門限值SplT（15～16）且拓撲合并門限值MerT（2～3）時，算法擁有較快的物理主機搜尋速度；當α取值為1.2～1.5時，物理主機的平均利用率較高，浪費率較低.

3.3 實驗結果

本次實驗從虛擬機分配時間、資源均衡度、資源浪費度、能耗和物理主機數量等5個方面對HTES算法進行驗證.

圖5為4種算法在不同虛擬機數量下的分配時間對比.從圖4可以看出，隨著虛擬機數量的不斷增加（10～200），分配時間快速增大.在4種算法中，GRD算法的分配時間最少，其次是HTES算法，ANT算法時間最多.在4種算法中，GRD算法隨機分配虛擬機，將虛擬機分配到空閑資源最大的物理主機上，不考慮其他目標，其分配速度最快.HTES、DCEERS和ANT以節能和提升底層資源利用率為虛擬機分配的目標，通過不同的分配策略實現節能，分配時間較GRD算法而言有所增加.HTES算法在3種算法中分配時間最快.因為，HTES算法將分布式數據中心網絡拓撲進行分割，建立層次拓撲樹，生成索引.根據用戶IP將虛擬機請求分組，快速掃描層次拓撲，查詢物理主機，將虛擬機請求集中的分配到底層物理主機，加快了分配效率，減少了物理主機的使用數量，節約了能耗；DCEERS算法將虛擬機分配問題看做最小商品流問題，通過Benders分解進行虛擬機分配，利用最小數量的物理主機承載虛擬機請求，同樣減少了物理主機的數量，節約了能耗；ANT算法利用蟻群策略求解多目標虛擬機的分配問題，同時優化底層資源的利用和能耗.然而ANT算法需要大量的迭代尋找最優，分配時間上較差.

物理主機內CPU和內存資源的均衡率對比如圖6所示.從圖6可以看出，隨著虛擬機請求數量的不斷增加（10～200），4種算法的資源均衡程度不斷變化.其中，HTES算法均衡率最好，ANT和DCEERS較差，GRD最差.當虛擬機請求數為10～50時，GRD和ANT的資源均衡逐級下降，HTES和DCEERS兩種算法圍繞0.65和0.6兩條水平線上下波動.當虛擬機請求數超過50時，ANT和GRD的均衡率稍微回升，DCEERS則開始下降，HTES相對平穩且有所提升.在各種虛擬機請求數量下，HTES都擁有較好的資源均衡率.因為，HTES在進行虛擬機分配時，需要根據公式（1）計算虛擬機與物理主機間的匹配度，將虛擬機分配到合適的物理主機上，均衡物理主機多維資源的利用率；DCEERS和ANT算法在嘗試用最小的物理主機分配最多的虛擬機，隨著虛擬機數量的增加，造成物理主機間資源的不均衡；GRD算法隨機分配虛擬機，當虛擬機數量較小時，占用底層高性能的物理主機，造成物理主機內的資源分配不均衡.隨著虛擬機數量增加，高性能物理主機的資源利用率提升，各維資源的均衡度相應增加.

圖7展示了4種算法的資源浪費情況.圖中資源的浪費率是指CPU和內存浪費率的均值，從圖7可以看出，在不同虛擬機請求數量下（10～200），4種算法的資源浪費率不斷變化，HTES算法浪費率最小，其次是DCEERS和ANT，GRD算法最大.在虛擬機數量較小時（10～30），HTES，DCEERS和ANT 3種算法的資源浪費率相近，HTES略差于DCEERS和ANT算法.隨著虛擬機數量的不斷增加，HTES算法的浪費率明顯優于其他3種算法.因為，GRD算法的隨機分配策略，并未考慮任何資源均衡目標，其分配時間快，資源浪費率高.DCEERS和ANT通過蟻群和Benders分解，在優化虛擬機分配的同時，提高了資源利用率，節約了能耗；但是兩者并未考慮物理主機多維資源的均衡分配問題.HTES算法利用公式（1），在區域性分配虛擬機的同時，均衡地分配物理主機的多維資源（CPU和MEM），在提升底層資源利用率的同時，降低了各維資源的浪費率.

圖8為4種算法在不同數量虛擬機下占用物理主機的單位時間能耗情況，物理主機單位時間能耗是指虛擬機占用的所有物理主機功耗之和.從圖8可以看出，隨著虛擬機數據的不斷增加（10～350），單位時間的功耗快速加大.4種算法中GRD算法功耗增加最快，ANT和DCEERS的功耗比較接近，HTES算法的功耗最小.當虛擬機的數量為10～150時，其功耗增加速率相對較慢，4條趨勢線的坡度比較緩，HTES算法功耗增加速度最慢.然而，隨著虛擬機數量的不斷增加，4種算法的功耗急速增加，坡度加大，HTES算法的功耗逐漸接近ANT和DCEERS算法.因為HTES算法、ANT和DCEERS算法都是通過提供資源利用率，減少底層物理主機使用數量來節約能耗.HTES算法額外考慮了物理主機多維資源均衡分配問題，進一步提升了物理主機的資源利用率.然而，隨著虛擬機數量的不斷增加，底層物理主機的空閑數量不斷減少，單位時間產生的功效必然增加，最終變為一致（所有物理主機都在使用）.

圖9為4種算法對底層異構物理主機的使用情況.從圖9可以看出，4種算法在相同虛擬機數量下占用的物理主機類型和數量各不相同.在4種算法中，GRD算法偏向于占用高性能物理主機.在虛擬機數量較小（80～150）時，G4[16c，24g]類型的物理主機被全部占用.隨著虛擬機數量的增加（150～300），G3[8c，16g]類型的物理主機被快速占用；相反，HTES算法偏向于使用低性能的物理主機.在虛擬機數量較小（80～150）時，G1[4c，8g]和G2[8c，8g]類型的物理主機被占用.隨著虛擬機數量的增加（150～300），G3[8c，16g]和G4[16c，24g]類型的物理主機少量被占用；ANT和DCEERS算法則相對比較均衡，在各種虛擬機數量下，均衡占用G1[4c，8g]，G2[8c，8g]，G3[8c，16g]和G4[16c，24g]類型的物理主機.HTES算法喜好占用低性能物理主機特性更方便進行分布式數據中心的節能.

4 結 論

針對虛擬機分配中物理主機多維資源的浪費問題，結合分布式數據中心網絡拓撲的大規模性和地理位置的不同，本文提出了一種基于層次拓撲樹的虛擬機節能分配算法.首先，將大規模網絡拓撲按照地理位置的不同，劃分成多個頂層子拓撲.其次，利用Laplacian矩陣和Ncut的特性，進行迭代二分切割，建立層次拓撲樹.然后，根據虛擬機請求IP地址與數據中心位置的遠近，將虛擬機請求分組，根據分組中虛擬機數量檢索層次拓撲樹，快速查詢合適的區域性物理主機集合.最后，根據虛擬機請求與物理主機間的匹配度均衡分配物理主機的多維資源，提高了資源利用率，減少底層物理主機使用數量，通過關閉空閑物理主機實現了數據中心的節能.文中將HTES算法與GRD算法、DCEERS算法和ANT算法進行比較，從虛擬機分配時間、資源均衡率、能耗和物理主機使用情況等方面驗證了HTES算法的性能，表明HTES算法適合于分布式數據中心.

參考文獻

[1] ZHAO J， LI H， WU C， et al. Dynamic pricing and profit maximization for the cloud with geo-distributed data centers[C]//Conference on Computer Communications.Toronto： IEEE， 2014： 118-126.

[2] TUDORAN R， COSTAN A， WANG R， et al. Bridging data in the clouds： an environment-aware system for geographically distributed data transfers[C]//Cluster， Cloud and Grid Computing （CCGrid）， 2014 14th IEEE/ACM International Symposium on. Chicago：IEEE，2014： 92-101.

[3] ALICHERRY M， LAKSHMAN T V. Network aware resource allocation in distributed clouds[C]//INFOCOM.Orlando： IEEE，2012： 963-971.

[4] ISLAM M A， REN S， PISSINOU N， et al. Distributed temperature-aware resource management in virtualized data center[J].Sustainable Computing： Informatics and Systems， 2015（6）： 3-16.

[5] KO Y M， CHO Y. A distributed speed scaling and load balancing algorithm for energy efficient data centers[J]. Performance Evaluation， 2014， 79： 120-133.

[6] 鄧子云，章兢，白樹仁，等.基于超級計算的 CAE 集成平臺架構設計[J].湖南大學學報：自然科學版，2013，40（7）： 80-85.

DENG Ziyun， ZHANG Jing， BAI Shuren，et al.Architectural design of CAE integration platform based on super computation[J]. Journal of Hunan University： Natural Sciences，2013， 40（7）： 80-85.（In Chinese）

[7] GEORGIOU S， TSAKALOZOS K， DELIS A. Exploiting network-topology awareness for VM placement in IAAS clouds[C]//Cloud and Green Computing （CGC）， 2013 Third International Conference on. Karlsruhe： IEEE， 2013： 151-158.

[8] PENG Y， YUAN Y， HUANG X， et al. Research on maintainability of network topology for data centers[C]//2014 Sixth International Conference on Ubiquitous and Future Networks （ICUFN）. Shanghai： IEEE， 2014： 317-321.

[9] SHIRAYANAGI H， YAMADA H， KENJI K. Honeyguide： a VM migration-aware network topology for saving energy consumption in data center networks[J]. IEICE Transactions on Information and Systems， 2013， 96（9）： 2055-2064.

[10]JAIN N， MENACHE I， NAOR J S，et al. Topology-aware VM migration in bandwidth oversubscribed datacenter networks[M].Berlin Heidelberg： Springer Berlin Heidelberg，2012：586-597.

[11]JIN H， CHEOCHERNAGNGARN T，LEVY D，et al.Joint host-network optimization for energy-efficient data center networking[C]// Parallel & Distributed Processing （IPDPS）， 2013 IEEE 27th International Symposium on. Boston ： IEEE， 2013： 623-634.

[12]SHUJA J， BILAL K， MADANI S A， et al. Data center energy efficient resource scheduling[J]. Cluster Computing， 2014， 17（4）： 1265-1277.

[13]HAMMADI A， MHAMDI L. A survey on architectures and energy efficiency in data center networks[J]. Computer Communications， 2014， 40： 1-21.

[14]MOGHADDAM F A， LAGO P， GROSSO P. Energy-efficient networking solutions in cloud-based environments： a systematic literature review[J]. ACM Computing Surveys （CSUR）， 2015， 47（4）：1-32.

[15]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（5）： 755-768.

[16]GU L， ZENG D， GUO S，et al.Joint optimization of VM placement and request distribution for electricity cost cut in geo-distributed data centers[C]//Computing， Networking and Communications （ICNC）， 2015 International Conference on. Garden Grove： IEEE， 2015： 717-721.

[17]BUYYA R， RANJAN R， CALHEIROS R N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit： challenges and opportunities[C]// High Performance Computing & Simulation，HPCS'09，International Conference on. Leipzig： IEEE， 2009： 1-11.

[18]MILLS K， FILLIBEN J， DABROWSKI C. Comparing VM-placement algorithms for on-demand clouds[C]// Cloud Computing Technology and Science （CloudCom）， IEEE Third International Conference on. Athens ： IEEE， 2011： 91-98.

[19]GAO Y， GUAN H， QI Z， et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J]. Journal of Computer and System Sciences， 2013， 79（8）： 1230-1242.