基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法*

蔡立軍,何庭欽?,孟濤,陳磊

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082; 2.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙 410082)

基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法*

蔡立軍1,何庭欽1?,孟濤1,陳磊2

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082; 2.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙 410082)

為了均衡分布式數(shù)據(jù)中心物理主機(jī)多維資源的利用率，減少物理主機(jī)使用數(shù)量，節(jié)約能耗，提出了一種基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法HTES(hierarchicaltopologyenergysaving)，此算法可以有效提升虛擬機(jī)分配效率.利用Laplacian矩陣，對(duì)大規(guī)模網(wǎng)絡(luò)拓?fù)浞指?，建立了層次拓?fù)錁淠Ｐ?基于層次拓?fù)淠Ｐ?，根?jù)虛擬機(jī)請(qǐng)求中IP地址與數(shù)據(jù)中心的距離，將虛擬機(jī)請(qǐng)求分組，從層次拓?fù)錁淠Ｐ椭胁樵兒线m的物理主機(jī)區(qū)域，按虛擬機(jī)請(qǐng)求與物理主機(jī)的資源匹配度進(jìn)行虛擬機(jī)的分配.將HTES與其他3種算法進(jìn)行模擬仿真實(shí)驗(yàn)，從虛擬機(jī)分配時(shí)間、資源均衡率、能耗和物理主機(jī)使用情況等方面驗(yàn)證了HTES算法能夠有效加快物理主機(jī)搜索速度，增加底層占用物理主機(jī)的集中度，降低底層物理主機(jī)的使用數(shù)量，達(dá)到節(jié)約能耗的目的.

數(shù)據(jù)中心；虛擬機(jī)分配；層次拓?fù)錁?；能源利用?/p>

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

目前已有很多學(xué)者對(duì)數(shù)據(jù)中心虛擬機(jī)的分配進(jìn)行研究，取得了較多的優(yōu)秀成果.一些研究成果集中在優(yōu)化分布式數(shù)據(jù)中心的資源分配上[1-6].文獻(xiàn)[1]從服務(wù)供應(yīng)商的角度，研究了分布式數(shù)據(jù)中心的收益最大化問題，提出了一種結(jié)合虛擬機(jī)分配的動(dòng)態(tài)調(diào)價(jià)算法.文獻(xiàn)[2-3]同樣著眼于分布式數(shù)據(jù)中心的成本優(yōu)化問題，從數(shù)據(jù)傳輸和資源分配兩個(gè)角度設(shè)計(jì)了相應(yīng)的數(shù)據(jù)管理系統(tǒng)和資源調(diào)度算法，最小化數(shù)據(jù)、成本低的同時(shí)，優(yōu)化了數(shù)據(jù)的傳輸時(shí)間、提升了底層物理資源的利用率.文獻(xiàn)[4]提出了一種基于溫度感知的資源管理系統(tǒng)，通過動(dòng)態(tài)調(diào)整服務(wù)器的功率，實(shí)現(xiàn)虛擬機(jī)分配和服務(wù)器負(fù)載間的優(yōu)化.文獻(xiàn)[5]在分布式數(shù)據(jù)中心內(nèi)，對(duì)虛擬機(jī)的分配請(qǐng)求建立G/G/1/PS隊(duì)列，通過優(yōu)化隊(duì)列處理實(shí)現(xiàn)服務(wù)器負(fù)載和虛擬機(jī)分配的均衡，節(jié)約了數(shù)據(jù)中心能耗.文獻(xiàn)[6]為提升高性能數(shù)據(jù)中心資源使用率，設(shè)計(jì)了CAE集成平臺(tái)架構(gòu)，實(shí)現(xiàn)了一種基于Web方式的高性能計(jì)算中心資源的解決方案.有些研究工作使用數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)鋪韮?yōu)化虛擬機(jī)的分配，提升底層物理資源的利用率[7-10].在portland網(wǎng)絡(luò)拓?fù)渖希墨I(xiàn)[7]提出了2種啟發(fā)式算法，通過分配虛擬機(jī)到最大鏈路能力和鄰近的物理主機(jī)上，降低了網(wǎng)絡(luò)開銷，增加了底層資源利用率.文獻(xiàn)[8]根據(jù)網(wǎng)絡(luò)拓?fù)浣⒘薓NT指標(biāo)，優(yōu)化資源分配.文獻(xiàn)[9]在網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上，通過虛擬機(jī)和鏈路的合并，增加了拓?fù)渲锌臻e網(wǎng)絡(luò)設(shè)備數(shù)量，節(jié)約了能源.同樣，在實(shí)際數(shù)據(jù)中心拓?fù)渖希墨I(xiàn)[10]通過對(duì)帶寬過載的虛擬機(jī)進(jìn)行合并，優(yōu)化了網(wǎng)絡(luò)傳輸消耗.此外，還有較多學(xué)者研究數(shù)據(jù)中心的能耗問題[11-14]，通過各種模型和方法減少數(shù)據(jù)中心的能源消耗.文獻(xiàn)[11]同時(shí)考慮了虛擬機(jī)的分配和網(wǎng)絡(luò)流的傳輸，通過建立線性規(guī)劃模型，并行處理虛擬機(jī)的分配，節(jié)約能源消耗.文獻(xiàn)[12]中將虛擬機(jī)的分配問題看做多商品流的成本最小化問題，通過Benders分解算法進(jìn)行求解，減少了底層物理主機(jī)的使用數(shù)量，節(jié)約了能源消耗.文獻(xiàn)[15]分析了云數(shù)據(jù)中心下資源分配和能源消耗問題，設(shè)計(jì)了一種節(jié)能框架，在減少成本的同時(shí)節(jié)約能耗.文獻(xiàn)[16]研究了分布式數(shù)據(jù)中心內(nèi)的能源節(jié)約問題，建立了最大化整數(shù)規(guī)劃模型，通過虛擬機(jī)的合并，減少了物理主機(jī)的使用，從而實(shí)現(xiàn)能耗的節(jié)約.

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

因此，本文提出了一種基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法.首先，將分布式數(shù)據(jù)中心的大規(guī)模網(wǎng)絡(luò)隨機(jī)拓?fù)溥M(jìn)行拓?fù)浞指?，建立層次拓?fù)錁?其次，在考慮底層物理主機(jī)多維資源均衡的前提下，掃描層次拓?fù)錁?，將虛擬機(jī)集中分配網(wǎng)絡(luò)拓?fù)渲械募袇^(qū)域，降低底層物理主機(jī)的使用.通過關(guān)閉空閑物理主機(jī)達(dá)到節(jié)約能源的目的.最后，通過大量實(shí)驗(yàn)驗(yàn)證了算法的性能.基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法優(yōu)化了虛擬機(jī)的分配，提高了底層資源利用率，降低了能源消耗.

1 模型建立

1.1 預(yù)備知識(shí)

1.1.1 分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?/p>

在虛擬機(jī)的分配過程中，網(wǎng)絡(luò)拓?fù)淦鹬匾淖饔?所有的虛擬機(jī)必須映射到網(wǎng)絡(luò)拓?fù)渲械奈锢碇鳈C(jī)上，占用物理主機(jī)的CPU，MEM資源，占用網(wǎng)絡(luò)拓?fù)渲卸鄠€(gè)物理主機(jī)間的鏈路帶寬資源，甚至占用拓?fù)渲写鎯?chǔ)節(jié)點(diǎn)的部分存儲(chǔ)資源.一個(gè)虛擬機(jī)在分配過程中，需要掃描網(wǎng)絡(luò)拓?fù)渲械目臻e物理主機(jī)，進(jìn)行最終的資源分配.網(wǎng)絡(luò)拓?fù)淇梢暂p松反映虛擬機(jī)的分配情況和運(yùn)行情況，能夠方便監(jiān)控物理主機(jī)的負(fù)載和運(yùn)行，便于物理主機(jī)的資源調(diào)優(yōu)和能源節(jié)約.當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，說明底層物理設(shè)備出現(xiàn)了故障，需要進(jìn)行虛擬機(jī)的遷移和重新分配.

分布式數(shù)據(jù)中心由多個(gè)地理位置分散的小型數(shù)據(jù)中心組成.小型數(shù)據(jù)中心之間通過高速網(wǎng)絡(luò)進(jìn)行互連.每個(gè)小型數(shù)據(jù)中心彼此獨(dú)立，可以擁有不同類型的網(wǎng)絡(luò)拓?fù)浜臀锢碇鳈C(jī).通常，分布式數(shù)據(jù)中心的整體網(wǎng)絡(luò)拓?fù)涫请S機(jī)的，底層物理主機(jī)資源是異構(gòu)的.圖1為分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)鋱D.

圖1 分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)鋱D

在圖1中，分布式數(shù)據(jù)中心由K個(gè)小型數(shù)據(jù)中心組成.每個(gè)數(shù)據(jù)中心擁有不同的網(wǎng)絡(luò)拓?fù)浜臀锢碇鳈C(jī)類型.分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)涑尸F(xiàn)隨機(jī)性和大規(guī)模性，物理主機(jī)擁有異構(gòu)特性.網(wǎng)絡(luò)拓?fù)涞拇笠?guī)模性和隨機(jī)性導(dǎo)致虛擬機(jī)分配時(shí)掃描的物理主機(jī)范圍龐大，增加了虛擬機(jī)的搜索時(shí)間，降低了虛擬機(jī)的分配效率.此外，網(wǎng)絡(luò)拓?fù)涞拇笠?guī)模性必然存在大量物理主機(jī)和網(wǎng)絡(luò)設(shè)備空閑的情況，帶來龐大的能源開銷，增加數(shù)據(jù)中心的成本；物理主機(jī)的異構(gòu)性增加了虛擬機(jī)分配后物理主機(jī)多維資源間的不均衡分配，造成資源浪費(fèi)；數(shù)據(jù)中心的分散性增加了額外的網(wǎng)絡(luò)開銷，浪費(fèi)了網(wǎng)絡(luò)帶寬資源.

1.1.2 單機(jī)多維資源的不均衡分配

在數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲?，物理主機(jī)本身由多種資源組成(CPU，MEM和存儲(chǔ))，可看作多維資源向量.如果某維資源(CPU)過度分配，必然造成其他維資源(MEM和存儲(chǔ))的浪費(fèi).只有均衡利用各維資源，才能更充分地發(fā)揮資源效率，提升底層資源的利用率，減少數(shù)據(jù)中心物理主機(jī)的使用數(shù)量，降低能源開銷.在傳統(tǒng)虛擬機(jī)分配過程中，虛擬機(jī)的隨機(jī)分配往往導(dǎo)致單機(jī)多維資源的不均衡分配.

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

圖2 單機(jī)多維資源不合理分配圖

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

1.2 問題描述

在虛擬機(jī)的分配過程中，每個(gè)虛擬機(jī)vmi只能分配到一臺(tái)物理主機(jī)上hostj.物理主機(jī)hostj的剩余資源能力必須滿足虛擬機(jī)的請(qǐng)求.一個(gè)用戶可以提交多個(gè)虛擬機(jī)請(qǐng)求，同一用戶的多個(gè)虛擬機(jī)應(yīng)該分配在同一地理位置的物理主機(jī)上.此外，分布式數(shù)據(jù)中心內(nèi)，多個(gè)數(shù)據(jù)中心的物理主機(jī)通常為異構(gòu)主機(jī)，擁有不同的CPU，MEM大小.在分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲?，所有網(wǎng)絡(luò)設(shè)備和存儲(chǔ)設(shè)備不能獨(dú)立承載虛擬機(jī)，不具備相應(yīng)的計(jì)算和處理能力.

1.3 分配模型

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

分布式數(shù)據(jù)中心內(nèi)，虛擬機(jī)的分配過程是連續(xù)的，分配過程不斷循環(huán)，一次分配過程完成后另一次分配過程準(zhǔn)備開始.在多次虛擬機(jī)分配過程中，物理主機(jī)負(fù)載狀態(tài)前后一致.單個(gè)物理主機(jī)可以在不同輪次的分配過程中承載多個(gè)虛擬機(jī)請(qǐng)求.為了均衡單個(gè)物理主機(jī)多維資源的均衡分配，必須在物理主機(jī)歷史負(fù)載狀態(tài)下考慮本輪分配，實(shí)現(xiàn)虛擬機(jī)分配后物理主機(jī)各維資源的剩余率均衡.

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

(1)

Is_Newj=

(2)

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

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

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

在虛擬機(jī)分配過程中，虛擬機(jī)請(qǐng)求數(shù)量與底層物理主機(jī)數(shù)量不同，本文定義0-1變量xij表示虛擬機(jī)vmi與物理主機(jī)hostj間的映射關(guān)系，見式(3).

(3)

在式(3)中，虛擬機(jī)vmi分配到物理主機(jī)hostj上，則xij為1;否則，xij為0.因此，分布式數(shù)據(jù)中心虛擬機(jī)分配的目標(biāo)函數(shù)可以表示如下：

(4)

st.

for each vmi, hostj: 0≤HMatchij<2

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

表1 符號(hào)術(shù)語表

2 基于層次拓?fù)錁涞墓?jié)能分配算法

針對(duì)分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)涮攸c(diǎn)，結(jié)合分配模型，本節(jié)提出了一種基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法，簡(jiǎn)稱HTES.首先，HTES將分布式數(shù)據(jù)中心的大規(guī)模網(wǎng)絡(luò)拓?fù)溥M(jìn)行分配，建立了層次拓?fù)錁?，詳?xì)描述見2.1節(jié)；其次，在層次拓?fù)錁涞幕A(chǔ)上，根據(jù)用戶的地理位置，將虛擬機(jī)分配到網(wǎng)絡(luò)拓?fù)渲械哪硞€(gè)區(qū)域，保證占用的物理主機(jī)相對(duì)集中，均衡物理主機(jī)多維資源分配，減少物理主機(jī)使用數(shù)量，節(jié)約能耗，詳細(xì)的分配算法見2.2節(jié).

2.1 拓?fù)浞指罱哟瓮負(fù)錁?/p>

分布式數(shù)據(jù)中心由多個(gè)地理位置分散的小型數(shù)據(jù)中心組成，整個(gè)網(wǎng)絡(luò)拓?fù)渚哂忻黠@的大規(guī)模性和隨機(jī)性.在虛擬機(jī)的分配過程中，需要為每個(gè)虛擬機(jī)尋找合適的物理主機(jī)，從而必須搜索網(wǎng)絡(luò)拓?fù)涞乃形锢碇鳈C(jī).網(wǎng)絡(luò)拓?fù)涞拇笠?guī)模給虛擬機(jī)的分配過程帶來了兩個(gè)難點(diǎn)：①增加了底層物理主機(jī)的搜索時(shí)間，降低了虛擬機(jī)的分配效率.②擴(kuò)散了底層物理主機(jī)的占用分布.例如，同一用戶的多個(gè)虛擬機(jī)請(qǐng)求可能分配到不同地理位置的物理主機(jī)上，也可能分配到同一地理位置內(nèi)的距離位置較遠(yuǎn)的多臺(tái)物理主機(jī)上.這種分散性給底層物理主機(jī)的管理和維護(hù)帶來了巨大困難，增加了節(jié)能策略的監(jiān)控難度.

針對(duì)以上兩個(gè)難點(diǎn)，本文對(duì)分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)溥M(jìn)行逐級(jí)分割，建立層次拓?fù)錁?將整個(gè)拓?fù)滢D(zhuǎn)化為層次結(jié)構(gòu)，保證每一層的節(jié)點(diǎn)數(shù)目逐層遞減.當(dāng)進(jìn)行虛擬機(jī)分配時(shí)，根據(jù)虛擬機(jī)的分配數(shù)量，找到相應(yīng)層級(jí)的拓?fù)渥訕鋵ふ椅锢碇鳈C(jī)，不用再掃描整個(gè)網(wǎng)絡(luò)拓?fù)?，減少了物理主機(jī)的掃描時(shí)間，增加了虛擬機(jī)占用物理主機(jī)的集中度，便于虛擬機(jī)的快速分配和能耗節(jié)約.

為了進(jìn)行網(wǎng)絡(luò)拓?fù)涞姆指?，本文引入了?guī)范割Normalized-cut(Ncut)和Laplacian矩陣，證明了Laplacian矩陣的第二特征值是2分Ncut的最優(yōu)解.

定義1 規(guī)范割Normalized-cut(Ncut)是衡量網(wǎng)絡(luò)拓?fù)渲袃蓚€(gè)節(jié)點(diǎn)子集間相似度的標(biāo)準(zhǔn)，公式如下：

(5)

(6)

(7)

式中：V為網(wǎng)絡(luò)拓?fù)銰中的節(jié)點(diǎn)集合；wij為網(wǎng)絡(luò)拓?fù)涞泥徑泳仃嘩中的值，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j間的權(quán)值.鄰接矩陣W為對(duì)稱矩陣，其中wij=wji≥0.使用規(guī)范割Ncut進(jìn)行拓?fù)浞指疃攘?，能夠較好地避免小區(qū)域的產(chǎn)生.

定義2Laplacian矩陣是網(wǎng)絡(luò)拓?fù)鋱D的一種有效表示方式，一個(gè)Laplacian矩陣對(duì)應(yīng)一個(gè)非負(fù)權(quán)重的無向有權(quán)圖.Laplacian矩陣的常用表示如下：

Lsym=D-1/2LD-1/2=I-D-1/2WD-1/2

(8)

Laplacian矩陣具有如下特性：

2)L為半正定矩陣.

3)L的最小特征值為0，對(duì)應(yīng)的最小特征向量為值1的常向量A.

4)L有n個(gè)非負(fù)實(shí)特征值0=λ1≤λ2≤…≤λn.

5)如果網(wǎng)絡(luò)拓?fù)銰是C的連通部件，那么L有C個(gè)等于0的特征值.

根據(jù)Ncut和Laplacian矩陣的定義和性質(zhì)，可得Laplacian矩陣的第二特征值是2分Ncut的最優(yōu)解，證明過程如下：

證明 設(shè)劃分向量f如下：

根據(jù)L的性質(zhì)1 ，得

此外：

vol(V,V)

根據(jù)L的性質(zhì)3，可得：

st.

由于最小化的Ncut是一個(gè)廣義Rayleigh商，根據(jù)性質(zhì)可得λ1=0,D1/2A為其最小特征值，可得fTLf/fTDf的第二小特征值是Ncut的最優(yōu)解.

根據(jù)Laplacian矩陣與Ncut間的特性，本文將分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)滢D(zhuǎn)化為Laplacian矩陣，然后對(duì)其求第二特征值，從而將網(wǎng)絡(luò)拓?fù)浞指畛神詈隙茸钚〉膬蓚€(gè)子集.再依次對(duì)兩個(gè)子集進(jìn)行拓?fù)浞指?，最終形成層次拓?fù)錁?圖3為網(wǎng)絡(luò)拓?fù)浞指畹倪^程.

圖3 網(wǎng)絡(luò)拓?fù)浞指钸^程圖

從圖中可以看出，網(wǎng)絡(luò)拓?fù)涞姆指钸^程為2分迭代分割，通過多次迭代將網(wǎng)絡(luò)拓?fù)浞指畛?個(gè)子拓?fù)?在整個(gè)分割過程中，必須保持多個(gè)數(shù)據(jù)中心間地位位置的分散特性.因此，分布式數(shù)據(jù)中心的層次拓?fù)錁涞牡谝粚油負(fù)錁渚褪嵌鄠€(gè)地理位置分散數(shù)據(jù)中心拓?fù)?，不進(jìn)行過細(xì)的劃分.此外，拓?fù)浞指畹哪繕?biāo)是加快物理主機(jī)的搜索速度，減少分配時(shí)間，2分迭代分割必然出現(xiàn)最下層子拓?fù)渲泄?jié)點(diǎn)數(shù)量較少的情況.為此，本文設(shè)定了拓?fù)浞指铋T限SplT和拓?fù)浜喜㈤T限MerT.根據(jù)拓?fù)浞指铋T限SplT判斷是否繼續(xù)進(jìn)行網(wǎng)絡(luò)拓?fù)涞姆指?根據(jù)拓?fù)浜喜㈤T限進(jìn)行節(jié)點(diǎn)數(shù)小于MerT的子拓?fù)涞暮喜?因此，拓?fù)浞指铋T限SplT必須大于拓?fù)浜喜㈤T限MerT.

因此，分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浞指畹木唧w過程如下：①根據(jù)分布式數(shù)據(jù)中心內(nèi)小型數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)?，建立?層子拓?fù)浼?，保持分布式?shù)據(jù)中心網(wǎng)絡(luò)拓?fù)溟g地理位置的分散特性；②逐個(gè)遍歷第1層子拓?fù)浼?，形成L矩陣，根據(jù)公式(8)進(jìn)行第二特征值求解.根據(jù)求解結(jié)果計(jì)算相應(yīng)的特征向量.按照特征向量中得到的節(jié)點(diǎn)列表，將網(wǎng)絡(luò)拓?fù)浞指畛蓛蓚€(gè)子拓?fù)?；③逐層遍歷所有子拓?fù)洌上乱粚幼油負(fù)浼?當(dāng)某個(gè)子拓?fù)渲械墓?jié)點(diǎn)數(shù)量少于最低分割門限SplT，不再進(jìn)行下一層拓?fù)浞指?④當(dāng)所有拓?fù)浞指钔瓿珊?，遍歷最后一層的子拓?fù)浼?，將?jié)點(diǎn)數(shù)少于MerT的子拓?fù)渑c其兄弟節(jié)點(diǎn)進(jìn)行合并；⑤遍歷所有層的子拓?fù)?，統(tǒng)計(jì)每層子拓?fù)渲泄?jié)點(diǎn)數(shù)量的范圍，結(jié)合層次號(hào)和地理位置(IP)，建立索引方便查詢.算法1詳細(xì)描述了網(wǎng)絡(luò)拓?fù)浞指罱⑼負(fù)錁涞脑敿?xì)過程.

算法1 網(wǎng)絡(luò)拓?fù)浞指钸^程

輸入：網(wǎng)絡(luò)拓?fù)銰,拓?fù)浞指铋T限值SplT,拓?fù)浜喜㈤T限值MerT.

輸出：層次拓?fù)錁銽T.

Step1 初始化.

1)根據(jù)網(wǎng)絡(luò)拓?fù)銰，生成相應(yīng)的鄰接矩陣W和度矩陣D.

2)初始化待分割的網(wǎng)絡(luò)拓?fù)浼疶S和子拓?fù)浼疭TS為空.

3)初始化層次拓?fù)錁銽T為空，層次序號(hào)IN為0.

Step2 更新待分割拓?fù)浼?，將STS覆蓋TS，清空STS.更新當(dāng)前層次拓?fù)錁涞膶犹?hào)IN=IN+1.進(jìn)入Step3開始拓?fù)浞指?

Step3 判斷TS是否為空.TS為空，則進(jìn)入Step5合并節(jié)點(diǎn)數(shù)目過小的子拓?fù)?否則，進(jìn)入Step4，分割拓?fù)?

Step4 遍歷待分割拓?fù)浼疶S，生成子拓?fù)浼疭TS.

1)計(jì)算子拓?fù)渲泄?jié)點(diǎn)數(shù)量VN.比較VN與分割門限SplT的大小.若大于，進(jìn)入2)進(jìn)行拓?fù)浞指?若小于，則不進(jìn)行拓?fù)浞指?進(jìn)行下一個(gè)子拓?fù)涞挠?jì)算.如果TS遍歷完成，進(jìn)入Step2更新待分割拓?fù)浼?

2)根據(jù)子拓?fù)銰、鄰接矩陣W和度矩陣D，按照公式(8)生成L矩陣Lsym=I-D-1/2WD-1/2，其中I是單位矩陣.進(jìn)入3)計(jì)算第二特征值.

3)根據(jù)L矩陣特性，計(jì)算(D-W)x=λDx的第二小特征值.根據(jù)特征值求得想要的特征向量f.按照特性向量中的節(jié)點(diǎn)，將子拓?fù)浞指畛蓛蓚€(gè)子集，加入STS中.進(jìn)入4)更新層次拓?fù)錁?

4)計(jì)算中STS總節(jié)點(diǎn)數(shù)量VN，更新層次拓?fù)錁?，如下所?更新完成后重新進(jìn)行1)，分割下一個(gè)子拓?fù)?

Step5 遍歷IN層子拓?fù)?，判斷每個(gè)子拓?fù)渲泄?jié)點(diǎn)數(shù)量.若節(jié)點(diǎn)數(shù)量小于MerT，刪除當(dāng)前子拓?fù)浼屯桓腹?jié)點(diǎn)的兄弟拓?fù)浼?

2.2 區(qū)域性節(jié)能分配算法

根據(jù)分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)涮匦裕跇?gòu)建層次拓?fù)錁涞幕A(chǔ)上，本節(jié)提出了一種區(qū)域性虛擬機(jī)節(jié)能分配算法HTES.HTES的核心節(jié)能策略是減少底層物理主機(jī)的使用，通過關(guān)閉空閑物理主機(jī)實(shí)現(xiàn)節(jié)能.較傳統(tǒng)的相同策略節(jié)能算法[12]而言，HTES關(guān)注于分布式數(shù)據(jù)中心環(huán)境；根據(jù)用戶IP分組虛擬機(jī)請(qǐng)求，就近提供物理主機(jī)資源；分割網(wǎng)絡(luò)拓?fù)浣哟瓮負(fù)錁?，快速尋找合適的物理主機(jī)；區(qū)域性分配虛擬機(jī)到底層集中的物理主機(jī)上，緩解了傳統(tǒng)零散分配帶來的難管理、難節(jié)能、難糾錯(cuò)等缺點(diǎn)；考慮物理主機(jī)多維資源的均衡分配，提高底層物理主機(jī)的資源利用率.

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

虛擬機(jī)請(qǐng)求分組：①請(qǐng)求分組，根據(jù)虛擬機(jī)請(qǐng)求中IP地址屬性，按照層次拓?fù)渲许攲庸?jié)點(diǎn)的地理位置(IP)，將虛擬機(jī)請(qǐng)求進(jìn)行分組.分組完成后，所有虛擬機(jī)請(qǐng)求都在距離自己最近的數(shù)據(jù)中心隊(duì)列中.②并發(fā)分配，并發(fā)對(duì)多個(gè)虛擬機(jī)請(qǐng)求分組進(jìn)行相應(yīng)的物理資源分配.

區(qū)域性物理主機(jī)搜索：①鎖定搜索層次.根據(jù)分組完成后的虛擬機(jī)請(qǐng)求個(gè)數(shù)V_size，查詢拓?fù)鋵哟螛渲锌臻e節(jié)點(diǎn)數(shù)量(物理主機(jī))充足的子拓?fù)洌ＷC子拓?fù)涞目臻e數(shù)量大于虛擬機(jī)請(qǐng)求數(shù)量α倍，更加均衡地分配虛擬機(jī)，均衡物理主機(jī)的多維資源.②比較資源能力.比較虛擬機(jī)請(qǐng)求大小與空閑物理主機(jī)的剩余能力，選擇剩余能力大于請(qǐng)求大小的物理主機(jī).若物理主機(jī)搜索成功，數(shù)量等于α×V_size，則進(jìn)行虛擬機(jī)分配.否則，遍歷當(dāng)前子拓?fù)涞母赣H拓?fù)?，再次搜索合適數(shù)量的主機(jī)，直到找到α×V_size個(gè)物理主機(jī)為止.③請(qǐng)求遷移.如果當(dāng)前頂層拓?fù)鋬?nèi)所有空閑物理主機(jī)數(shù)量小于V_size，則分配相應(yīng)數(shù)量的虛擬機(jī)請(qǐng)求，并將多余的虛擬機(jī)請(qǐng)求移動(dòng)到鄰近的數(shù)據(jù)中心隊(duì)列中，等待分配.如果鄰近數(shù)據(jù)中心內(nèi)資源同樣不足，則繼續(xù)遷移到其他數(shù)據(jù)中心.如果整個(gè)網(wǎng)絡(luò)拓?fù)滟Y源不足，則返回最近數(shù)據(jù)中心等待其他虛擬機(jī)釋放資源.

均衡分配：根據(jù)虛擬機(jī)請(qǐng)求隊(duì)列和相應(yīng)的物理主機(jī)隊(duì)列，進(jìn)行虛擬機(jī)的最終分配.按照公式(1)的定義，將虛擬機(jī)分配到請(qǐng)求匹配度最好的物理主機(jī)上，完成分配過程.

圖4展示了基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法過程.從圖中可以看出，虛擬機(jī)的分配過程主要分為虛擬機(jī)請(qǐng)求分組、根據(jù)層次拓?fù)錁渌阉魑锢碇鳈C(jī)和虛擬機(jī)分配3個(gè)步驟.分布式數(shù)據(jù)中心由2個(gè)地理位置分散的小型數(shù)據(jù)中心A和B組成.4個(gè)用戶在不同的位置向數(shù)據(jù)中心提交了7個(gè)虛擬機(jī)請(qǐng)求.根據(jù)用戶IP和物理中心的位置，V1-V4虛擬機(jī)請(qǐng)求分配到了A，V5-V7分配到了B.根據(jù)虛擬機(jī)請(qǐng)求的數(shù)量，并發(fā)從A和B中尋找合適數(shù)量的子拓?fù)?，進(jìn)行虛擬機(jī)的分配，正如V1,V3-V7所示.然而，當(dāng)子拓?fù)涞目捎梦锢碇鳈C(jī)數(shù)量小于虛擬機(jī)請(qǐng)求數(shù)量時(shí)，從其父節(jié)點(diǎn)的拓?fù)渲袑ふ移渌锢碇鳈C(jī)進(jìn)行分配，如V2所示.在整個(gè)虛擬機(jī)的分配過程中，根據(jù)虛擬機(jī)請(qǐng)求與物理主機(jī)的匹配度公式(1)，進(jìn)行物理主機(jī)的分配.如圖中V1,V3,V4分配到了原拓?fù)涞奈锢碇鳈C(jī)，V2因其匹配度較差從而分配到了原拓?fù)涞母腹?jié)點(diǎn).整個(gè)節(jié)能分配算法HTES的分配過程如算法2所示.

圖4 區(qū)域性虛擬機(jī)節(jié)能分配過程圖

算法2 基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法

輸入：網(wǎng)絡(luò)拓?fù)銰,虛擬機(jī)請(qǐng)求列表Vms

輸出：虛擬機(jī)分配結(jié)果.

Step1 初始化.根據(jù)網(wǎng)絡(luò)拓?fù)銰，利用算法1生成層次拓?fù)錁銽T，監(jiān)控?cái)?shù)據(jù)中心所有物理主機(jī)的使用情況.

Step2 虛擬機(jī)請(qǐng)求分組.

1)根據(jù)虛擬機(jī)的IP和數(shù)據(jù)中心位置，將虛擬機(jī)分配到位置最近的數(shù)據(jù)中心排隊(duì)隊(duì)列中.

2)分配完成后，并發(fā)對(duì)多個(gè)數(shù)據(jù)中心進(jìn)行虛擬機(jī)的分配.

Step3 區(qū)域性搜索物理主機(jī).

1)根據(jù)分組完成后的虛擬機(jī)請(qǐng)求個(gè)數(shù)V_size，查詢拓?fù)鋵哟螛渲锌臻e節(jié)點(diǎn)數(shù)量(物理主機(jī))充足的子拓?fù)?，保證子拓?fù)涞目臻e數(shù)量大于虛擬機(jī)請(qǐng)求數(shù)量α倍.

2)比較虛擬機(jī)請(qǐng)求大小與空閑物理主機(jī)的剩余能力，選擇剩余能力大于請(qǐng)求大小的物理主機(jī).

3)若物理主機(jī)搜素成功，數(shù)量等于α×V_size，進(jìn)入Step5進(jìn)行虛擬機(jī)分配.否則，遍歷當(dāng)前子拓?fù)涞母赣H拓?fù)?，再次搜索合適的數(shù)量主機(jī)，直到找到α×V_size個(gè)物理主機(jī)為止.

4)當(dāng)遍歷到頂層拓?fù)?，搜索完整個(gè)小數(shù)據(jù)中心的所有物理主機(jī)，物理主機(jī)數(shù)量不滿足V_size時(shí)，進(jìn)入Step4進(jìn)行虛擬機(jī)請(qǐng)求的遷移.

Step4 虛擬機(jī)請(qǐng)求的遷移.

1)當(dāng)頂層拓?fù)鋬?nèi)所有空閑物理主機(jī)數(shù)量小于V_size，則分配空閑主機(jī)數(shù)量的虛擬機(jī)請(qǐng)求，并將多余的虛擬機(jī)請(qǐng)求遷移到鄰近的數(shù)據(jù)中心隊(duì)列中，等待分配.

2)如果整個(gè)網(wǎng)絡(luò)拓?fù)滟Y源不足，則返回最近數(shù)據(jù)中心等待其他虛擬機(jī)釋放資源.

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

3 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證HTES算法的性能，本文使用CloudSim3.5[17]作為仿真平臺(tái)，將HTES算法與貪婪算法GRD[18]，蟻群算法ANT[19]和DCEERS[12]算法進(jìn)行比較，從分配時(shí)間、物理主機(jī)數(shù)量、物理主機(jī)異構(gòu)使用情況等方面進(jìn)行了性能驗(yàn)證.

3.1 實(shí)驗(yàn)環(huán)境

在CloudSim平臺(tái)上，利用brite網(wǎng)絡(luò)拓?fù)鋱D生成工具，隨機(jī)生成10個(gè)地理位置分散的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌負(fù)渲邪? 000個(gè)物理主機(jī)和200個(gè)網(wǎng)絡(luò)設(shè)備.表2為物理主機(jī)參數(shù)表.

表2 物理主機(jī)參數(shù)表

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

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

本節(jié)對(duì)實(shí)驗(yàn)中的參數(shù)值拓?fù)浞指铋T限值SplT，拓?fù)浜喜㈤T限值MerT和虛擬機(jī)分配算法中的α參數(shù)進(jìn)行討論及測(cè)試.在網(wǎng)絡(luò)拓?fù)浞指畹倪^程中，本文通過設(shè)定拓?fù)浞指铋T限SplT和拓?fù)浜喜㈤T限MerT來處理2分迭代分割出現(xiàn)的最下層子拓?fù)渲泄?jié)點(diǎn)數(shù)量較少的情況.本文通過固定合并門限，變動(dòng)分割門限，或者固定分割門限，變動(dòng)合并門限，通過不同的門限取值，觀察不同設(shè)置下平均虛擬機(jī)分配時(shí)間.在網(wǎng)絡(luò)拓?fù)渲?，?duì)物理主機(jī)的搜尋速度越快，則相應(yīng)的虛擬機(jī)分配時(shí)速會(huì)更快.因此實(shí)驗(yàn)測(cè)試中，測(cè)試100個(gè)虛擬機(jī)請(qǐng)求的分配，設(shè)置拓?fù)浞指铋T限值SplT(10～20)，合并門限值MerT(0～5)時(shí)，從表3中可以看出，拓?fù)浞指铋T限值SplT(15～16)，拓?fù)浜喜㈤T限值MerT(2～3)時(shí)，此時(shí)拓?fù)浣Y(jié)構(gòu)下物理主機(jī)的搜尋速度最快，虛擬機(jī)平均分配時(shí)間最少，顯示出良好的分配性能.

表3 100個(gè)虛擬機(jī)下門限參數(shù)性能對(duì)比表

參數(shù)α是從子拓?fù)淇臻e物理主機(jī)數(shù)與虛擬機(jī)請(qǐng)求數(shù)量的比值.如果從子拓?fù)淇臻e物理主機(jī)中等同于虛擬機(jī)請(qǐng)求數(shù)量，則虛擬機(jī)的分配情況唯一，這種分配并非最優(yōu).因此從子拓?fù)淇臻g選擇空閑物理主機(jī)數(shù)量是要大于虛擬機(jī)的請(qǐng)求數(shù)量.本文在仿真實(shí)驗(yàn)中，設(shè)置固定虛擬機(jī)數(shù)為100，變動(dòng)α取值為1.0～2.0，從網(wǎng)絡(luò)拓?fù)渲?，搜尋虛擬機(jī)請(qǐng)求數(shù)量α倍的物理主機(jī)，表4給出了部分實(shí)驗(yàn)數(shù)據(jù)，可以看出，α取值為1.2～1.5時(shí)，物理主機(jī)的平均利用率較高，浪費(fèi)率較低.

表 4 α參數(shù)性能對(duì)比表

通過對(duì)表3和表4的分析可知，當(dāng)拓?fù)浞指铋T限值SplT(15～16)且拓?fù)浜喜㈤T限值MerT(2～3)時(shí)，算法擁有較快的物理主機(jī)搜尋速度；當(dāng)α取值為1.2～1.5時(shí)，物理主機(jī)的平均利用率較高，浪費(fèi)率較低.

3.3 實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)從虛擬機(jī)分配時(shí)間、資源均衡度、資源浪費(fèi)度、能耗和物理主機(jī)數(shù)量等5個(gè)方面對(duì)HTES算法進(jìn)行驗(yàn)證.

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

虛擬機(jī)數(shù)量/個(gè)

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

虛擬機(jī)數(shù)量/個(gè)

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

虛擬機(jī)數(shù)量/個(gè)

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

虛擬機(jī)數(shù)量/個(gè)

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

虛擬機(jī)數(shù)量-算法

4 結(jié) 論

針對(duì)虛擬機(jī)分配中物理主機(jī)多維資源的浪費(fèi)問題，結(jié)合分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涞拇笠?guī)模性和地理位置的不同，本文提出了一種基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法.首先，將大規(guī)模網(wǎng)絡(luò)拓?fù)浒凑盏乩砦恢玫牟煌?，劃分成多個(gè)頂層子拓?fù)?其次，利用Laplacian矩陣和Ncut的特性，進(jìn)行迭代二分切割，建立層次拓?fù)錁?然后，根據(jù)虛擬機(jī)請(qǐng)求IP地址與數(shù)據(jù)中心位置的遠(yuǎn)近，將虛擬機(jī)請(qǐng)求分組，根據(jù)分組中虛擬機(jī)數(shù)量檢索層次拓?fù)錁?，快速查詢合適的區(qū)域性物理主機(jī)集合.最后，根據(jù)虛擬機(jī)請(qǐng)求與物理主機(jī)間的匹配度均衡分配物理主機(jī)的多維資源，提高了資源利用率，減少底層物理主機(jī)使用數(shù)量，通過關(guān)閉空閑物理主機(jī)實(shí)現(xiàn)了數(shù)據(jù)中心的節(jié)能.文中將HTES算法與GRD算法、DCEERS算法和ANT算法進(jìn)行比較，從虛擬機(jī)分配時(shí)間、資源均衡率、能耗和物理主機(jī)使用情況等方面驗(yàn)證了HTES算法的性能，表明HTES算法適合于分布式數(shù)據(jù)中心.

[1]ZHAOJ,LIH,WUC,etal. 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,etal. 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,etal. 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] 鄧子云,章兢,白樹仁,等.基于超級(jí)計(jì)算的 CAE 集成平臺(tái)架構(gòu)設(shè)計(jì)[J].湖南大學(xué)學(xué)報(bào):自然科學(xué)版,2013,40(7): 80-85.

DENG Ziyun, ZHANG Jing, BAI Shuren,etal.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,etal. 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,etal. 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,etal.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,etal. 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,etal.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,etal. 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.

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)

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.

data centers;virtual machine allocation;hierarchical topology tree;energy utilization

1674-2974(2017)02-0137-12

10.16339/j.cnki.hdxbzkb.2017.02.020

2016-02-02

國家自然科學(xué)基金資助項(xiàng)目(61174140, 61472127, 61272395),NationalNaturalScienceFoundationofChina(61174140, 61472127, 61272395)；中國博士后科學(xué)基金資助項(xiàng)目(2013M540628,2014T70767)，ChinaPostdoctoralScienceFoundation(2013M540628,2014T70767)；湖南省自然科學(xué)基金資助項(xiàng)目(14JJ3107)，NaturalScienceFoundationofHunanProvinceofChina(14JJ3107)；湖南省教育廳科研優(yōu)秀青年資助項(xiàng)目(15B087)，ScienceFoundationfortheExcellentYouthScholarsofHunanProvinceofChina(15B087)

蔡立軍(1964-)，男，湖南常德人，湖南大學(xué)教授，博士

?通訊聯(lián)系人，E-mail:hetingqin@hnu.edu.cn

TP391

A