基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法

陳磊　章兢　蔡立軍　孟濤　何庭欽

摘要：提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法（NWTP）。首先，針對現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性（樹形、服務(wù)器和光纖混合），根據(jù)交互對象的不同，將虛擬機(jī)的帶寬請求分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種。其次，將虛擬機(jī)的分配過程分解成帶寬區(qū)域劃分和物理主機(jī)分配兩個彼此連續(xù)的階段，建立網(wǎng)絡(luò)感知模型。然后，利用流水線技術(shù)將帶寬區(qū)域劃分和物理主機(jī)分配看作兩個連續(xù)的工序，并發(fā)進(jìn)行分配處理。在帶寬區(qū)域劃分環(huán)節(jié)，利用節(jié)點介數(shù)和聚集系數(shù)動態(tài)感知物理主機(jī)的穩(wěn)定性，通過差異化的分配策略為虛擬機(jī)子集選擇合適的物理主機(jī)區(qū)域。在物理主機(jī)分配環(huán)節(jié)，將更多的虛擬機(jī)分配到負(fù)載方差最大的物理主機(jī)上，提高虛擬機(jī)網(wǎng)內(nèi)帶寬的節(jié)約度，均衡物理主機(jī)的資源負(fù)載。最后，對NWTP，遺傳GA，模擬退火SA，貪婪GR四種算法進(jìn)行大量的仿真實驗，從分配時間、延遲、吞吐率、CPU利用率、帶寬利用率和物理主機(jī)使用情況六個方面驗證了NWTP算法的性能。

關(guān)鍵詞：流水線技術(shù)；數(shù)據(jù)中心；云計算；網(wǎng)絡(luò)感知；虛擬機(jī)分配

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A

數(shù)據(jù)中心是成百上千臺物理主機(jī)、存儲通過網(wǎng)絡(luò)設(shè)備彼此互連，利用互聯(lián)網(wǎng)向社會提供計算和服務(wù)的場所。傳統(tǒng)的數(shù)據(jù)中心存在租用成本高、地域限制等缺陷，僅能為大型企業(yè)和政府機(jī)構(gòu)提供計算或存儲服務(wù)。隨著云計算的不斷發(fā)展和演變，按需付費的商業(yè)模式和虛擬機(jī)技術(shù)給傳統(tǒng)數(shù)據(jù)中心帶來了前所未有的機(jī)遇。傳統(tǒng)數(shù)據(jù)中心與云計算結(jié)合的“云數(shù)據(jù)中心”應(yīng)運而生。用戶能夠通過按需付費的模式，利用Internet輕松租用各種不同類型的虛擬機(jī)，進(jìn)行復(fù)雜計算，并支付相應(yīng)的費用。“云數(shù)據(jù)中心”已經(jīng)由奢侈服務(wù)轉(zhuǎn)向了大眾服務(wù)，給社會發(fā)展提供了強(qiáng)大的動力。

云數(shù)據(jù)中心內(nèi)，虛擬機(jī)的分配和調(diào)度是一個長期的挑戰(zhàn)，是影響數(shù)據(jù)中心性能的關(guān)鍵。好的虛擬機(jī)分配策略能夠提高底層物理資源的利用率，降低成本，增加收益，給用戶帶來良好的體驗和幫助。反之，則可能增加數(shù)據(jù)中心運營成本，甚至導(dǎo)致整個數(shù)據(jù)中心的崩潰。在云數(shù)據(jù)中心中，所有的虛擬機(jī)共享底層物理主機(jī)資源。因此，虛擬機(jī)分配的核心目標(biāo)就是提高底層物理資源的利用率，增加收益，利用有限的資源向更多用戶提供高效穩(wěn)定的服務(wù)。在各種服務(wù)中，無論是計算服務(wù)、存儲服務(wù)、容災(zāi)備份服務(wù)，都需要充足的網(wǎng)絡(luò)帶寬的保障。網(wǎng)絡(luò)是云數(shù)據(jù)中心的核心資源，是連接用戶和其他資源的橋梁。在云數(shù)據(jù)中心內(nèi)，所有的物理資源（物理主機(jī)、存儲等）通過網(wǎng)絡(luò)設(shè)備彼此相連，共同組成了網(wǎng)絡(luò)拓?fù)洹Ｔ诰W(wǎng)絡(luò)拓?fù)渲校慌_物理主機(jī)通過網(wǎng)絡(luò)鏈路與多臺設(shè)備進(jìn)行連接。網(wǎng)絡(luò)帶寬是衡量物理設(shè)備間鏈路能力強(qiáng)弱的標(biāo)準(zhǔn)，是物理設(shè)備通信能力的表示。數(shù)據(jù)中心內(nèi)，網(wǎng)絡(luò)帶寬大小非常有限。因此，充分利用網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)帶寬利用率，是虛擬機(jī)分配的重中之重。

近年來數(shù)據(jù)中心的虛擬機(jī)分配問題已經(jīng)被廣泛研究，并取得了較好的成果。成果主要分為物理資源優(yōu)化、能耗優(yōu)化和帶寬優(yōu)化三個方面。①大多數(shù)學(xué)者將研究重點集中于物理資源（CPU、內(nèi)存和存儲）的分配，通過提高物理資源的利用率，增加數(shù)據(jù)中心的收益。Sindelar等人根據(jù)多個虛擬機(jī)共享底層物理主機(jī)內(nèi)存資源的特性，提出了一種內(nèi)存共享感知的虛擬機(jī)分配算法，通過建立層次樹和聚類樹結(jié)構(gòu)存儲虛擬機(jī)間相同的內(nèi)存內(nèi)容，避免相同內(nèi)容的反復(fù)存儲，提升內(nèi)存資源的利用率。文獻(xiàn)中提出了Best-fit和Worst-fit兩種分配策略，最大化底層物理資源的利用率。文獻(xiàn)利用多目標(biāo)思想同時考慮資源利用率和多維資源負(fù)載，進(jìn)一步優(yōu)化了物理資源的分配。以上工作都將目標(biāo)著眼于物理主機(jī)資源，對網(wǎng)絡(luò)帶寬的研究較少。②部分學(xué)者試圖在虛擬機(jī)分配過程中進(jìn)行能源優(yōu)化。文獻(xiàn)通過遺傳算法和啟發(fā)式算法，在考慮能源優(yōu)化的同時進(jìn)行虛擬機(jī)的分配，降低了底層物理主機(jī)的使用數(shù)量，節(jié)約了能耗。然而，能耗優(yōu)化工作大多嘗試著減少物理主機(jī)的使用數(shù)量，并未考慮網(wǎng)絡(luò)帶寬的性能。③此外，也有部分學(xué)者開始考慮網(wǎng)絡(luò)帶寬資源的分配。RWang等人通過觀察網(wǎng)絡(luò)帶寬的峰值變化，提出了一種基于帶寬估計的網(wǎng)絡(luò)感知虛擬機(jī)分配算法，利用經(jīng)驗估計優(yōu)化帶寬分配。Y Zhao等人將網(wǎng)絡(luò)拓?fù)浜吞摂M機(jī)分配結(jié)合，建立混合整數(shù)規(guī)劃模型，利用拉格朗日松弛分解進(jìn)行虛擬機(jī)和帶寬分配，提升了帶寬的利用率。然而，這些工作僅僅考慮了網(wǎng)絡(luò)帶寬的分配，并未對物理資源的分配做過多的研究。

針對目前帶寬分配研究不夠深入的現(xiàn)狀，結(jié)合網(wǎng)絡(luò)帶寬在虛擬機(jī)分配中的關(guān)鍵作用，同時優(yōu)化帶寬分配和物理資源分配成為了本文的動機(jī)。首先，本文根據(jù)數(shù)據(jù)中心帶寬作用對象，將網(wǎng)絡(luò)帶寬分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種。其次，介紹了網(wǎng)絡(luò)感知的相關(guān)知識，分析了云數(shù)據(jù)中心內(nèi)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的隨機(jī)特性，利用節(jié)點介數(shù)和聚集系數(shù)來感知網(wǎng)絡(luò)拓?fù)渲芯W(wǎng)絡(luò)元素的重要性。然后，通過分配資源的不同將整個分配過程分解為帶寬區(qū)域劃分和物理主機(jī)分配兩個彼此連續(xù)的階段，建立相應(yīng)的網(wǎng)絡(luò)感知模型。再次，提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法NWTP。利用流水線技術(shù)模擬整個資源分配過程，將帶寬區(qū)域劃分和物理主機(jī)分配看作流水線上的兩個連續(xù)環(huán)節(jié)，配合錯誤處理，實現(xiàn)并發(fā)資源的分配。最后，在cloudsim平臺進(jìn)行大量實驗，將NWTP算法與貪婪（GR）、模擬退火（SA）、遺傳（GA）等算法進(jìn)行對比，體現(xiàn)了算法性能。本文的主要貢獻(xiàn)如下：

1）根據(jù)作用對象，將用戶帶寬需求分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種。網(wǎng)內(nèi)帶寬是指多個虛擬機(jī)間相互進(jìn)行數(shù)據(jù)通信所造成的帶寬。網(wǎng)間帶寬是指用戶通過internet與虛擬機(jī)進(jìn)行數(shù)據(jù)通信所需要的帶寬。

2）根據(jù)分配資源的不同，將虛擬機(jī)的分配過程分解為帶寬區(qū)劃劃分和物理主機(jī)分配兩個彼此連續(xù)的階段，將復(fù)雜的虛擬機(jī)分配問題簡單化。

3）提出了一種基于網(wǎng)絡(luò)感知的兩階段分配算法NWTP。利用流水線技術(shù)模擬虛擬機(jī)的分配過程，將帶寬區(qū)域劃分和物理主機(jī)分配看作流水線中兩個彼此連續(xù)的環(huán)節(jié)。在整個流水線中，不同環(huán)節(jié)采用不同的分配策略，配合錯誤處理，實現(xiàn)虛擬機(jī)請求的并行分配。

4）在帶寬區(qū)域劃分環(huán)節(jié)，利用節(jié)點介數(shù)和聚集系統(tǒng)感知網(wǎng)絡(luò)元素在網(wǎng)絡(luò)拓?fù)涞闹朽従佑H密性和網(wǎng)絡(luò)樞紐性。將不同的虛擬機(jī)請求按照帶寬類型進(jìn)行分組，不同分組采用不同的分配策略。高網(wǎng)間帶寬虛擬機(jī)組將分配到網(wǎng)絡(luò)拓?fù)渲兄匾臉屑~節(jié)點上，保證用戶交互快速性和可靠性；高網(wǎng)內(nèi)帶寬的虛擬機(jī)組將分配到邊界網(wǎng)絡(luò)區(qū)域中，保證彼此交互的虛擬機(jī)間擁有區(qū)域集中性，減少通信距離，降低網(wǎng)絡(luò)突發(fā)流造成的擁塞和影響；均衡的虛擬機(jī)組將結(jié)合前兩種的優(yōu)點，區(qū)域化的分配到網(wǎng)絡(luò)拓?fù)渲休^重要的節(jié)點上，保證對外通信和對內(nèi)通信的快速性。

5）在物理主機(jī)分配環(huán)節(jié)，針對固定的虛擬機(jī)組和物理主機(jī)區(qū)域，以節(jié)約網(wǎng)內(nèi)帶寬通信、均衡區(qū)域內(nèi)物理主機(jī)帶寬負(fù)載為目標(biāo)，進(jìn)行虛擬機(jī)到物理主機(jī)的映射，盡可能多地將虛擬機(jī)分配到同一物理主機(jī)。

本文后續(xù)工作的組織如下：第1節(jié)進(jìn)行網(wǎng)絡(luò)感知的介紹，對整個分配過程進(jìn)行建模；基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法（NWTP）在第2節(jié)被設(shè)計；第3節(jié)進(jìn)行實驗對比，驗證NWTP算法的性能；第4節(jié)總結(jié)全文。

1 基于網(wǎng)絡(luò)感知的分配模型

首先，本節(jié)介紹了網(wǎng)絡(luò)感知的定義和核心知識；然后，對網(wǎng)絡(luò)感知的虛擬機(jī)分配過程進(jìn)行了公式化描述；最后，將整個分配過程分解成帶寬區(qū)劃劃分和物理主機(jī)分配兩個彼此連續(xù)的階段，并進(jìn)行相應(yīng)的建模。

1.1 網(wǎng)絡(luò)感知

網(wǎng)絡(luò)感知是對整個網(wǎng)絡(luò)所有元素（網(wǎng)絡(luò)拓?fù)洹⒙酚蓞f(xié)議、網(wǎng)絡(luò)設(shè)備等）使用情況的實時監(jiān)控，對網(wǎng)絡(luò)流量動態(tài)變化的預(yù)防和處理。簡單而言，網(wǎng)絡(luò)感知就是恰當(dāng)?shù)姆峙渚W(wǎng)絡(luò)元素的剩余能力，合理的應(yīng)對和處理網(wǎng)絡(luò)突發(fā)情況。本文的網(wǎng)絡(luò)感知主要監(jiān)控兩個重點和應(yīng)對一種突發(fā)情況。

1）網(wǎng)絡(luò)拓?fù)洹＞W(wǎng)絡(luò)拓?fù)涫蔷W(wǎng)絡(luò)感知監(jiān)控的第一個重點，所有的虛擬機(jī)分配請求都將映射到網(wǎng)絡(luò)拓?fù)渲械囊粋€物理主機(jī)上，共享物理主機(jī)的底層資源，向用戶提供服務(wù)。因此，網(wǎng)絡(luò)拓?fù)涫呛侠矸峙涮摂M機(jī)，充分利用網(wǎng)絡(luò)帶寬資源和底層物理資源的重要參考。傳統(tǒng)數(shù)據(jù)中心都采用樹形的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1所示。樹形網(wǎng)絡(luò)拓?fù)湟话惴譃槿龑樱汉诵膶樱╟ore）、聚合層（aggregation）和接入層（access）。大量的服務(wù)器則為整個網(wǎng)絡(luò)拓?fù)涞娜~子節(jié)點，通過接入層交換機(jī)彼此相連。在三層網(wǎng)絡(luò)拓?fù)渲校诵膶拥哪芰ψ顝?qiáng)，聚合層次之，接入層最弱。常用的樹形網(wǎng)絡(luò)拓?fù)溆蠪at-Tree，portland，VL2。圖2為典型的以服務(wù)器中心的網(wǎng)絡(luò)拓?fù)洌渌Ｒ姷姆?wù)器為中心的網(wǎng)絡(luò)拓?fù)溆蠦cube，Dcell，F(xiàn)iconn。

2）網(wǎng)絡(luò)元素的重要性。數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)溆稍S多的網(wǎng)絡(luò)設(shè)備（交換機(jī)、路由器等）將大量物理服務(wù)器連接而成。每個網(wǎng)絡(luò)元素（交換機(jī)、路由器和服務(wù)器）在拓?fù)渲衅鹬煌淖饔茫瑩碛胁煌闹匾浴８鶕?jù)網(wǎng)絡(luò)元素的重要性和能力，動態(tài)地進(jìn)行資源分配，保證核心元素的強(qiáng)大服務(wù)能力，提升普通元素的平均利用率，對虛擬機(jī)的分配過程至關(guān)重要。例如，在三層樹形結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)渲校尤雽咏粨Q機(jī)重要性最差，聚合層次之，核心層最大。在進(jìn)行資源分配時，必須保證核心層交換機(jī)的強(qiáng)大服務(wù)能力和擴(kuò)展性，盡量少地占用其帶寬。因為，核心層交換機(jī)出現(xiàn)故障或擁塞，必然導(dǎo)致整個數(shù)據(jù)中心的癱瘓和崩潰。相反，接入層交換機(jī)僅僅影響部分物理主機(jī)，所以應(yīng)該更加充分地利用接入層的網(wǎng)絡(luò)帶寬，提升網(wǎng)絡(luò)帶寬的利用率。

3）網(wǎng)絡(luò)突發(fā)流。網(wǎng)絡(luò)突發(fā)流是指網(wǎng)絡(luò)中突然出現(xiàn)超過正常大小的帶寬請求，造成網(wǎng)絡(luò)擁塞和延遲的現(xiàn)象。在數(shù)據(jù)中心中，經(jīng)常出現(xiàn)網(wǎng)絡(luò)突發(fā)流情況。如何預(yù)防網(wǎng)絡(luò)突發(fā)流，減少網(wǎng)絡(luò)突發(fā)流對整個數(shù)據(jù)中心的影響，縮小擁塞范圍，是虛擬機(jī)分配的關(guān)鍵問題。

隨著數(shù)據(jù)中心規(guī)模的不斷擴(kuò)大，地理位置的不斷分散，各種數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)不斷涌現(xiàn)。傳統(tǒng)數(shù)據(jù)中心的樹形拓?fù)洌鐖D1，已經(jīng)不能滿足需求。以服務(wù)器為中心、以光纖為中心的網(wǎng)絡(luò)拓?fù)湓絹碓蕉啵鐖D2。因此，目前數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)錇椴煌耆?guī)則的半隨機(jī)拓?fù)浣Y(jié)構(gòu)，集合了樹形、服務(wù)器、光纖等多種拓?fù)浣Y(jié)構(gòu)，是一種混合的拓?fù)浣Y(jié)構(gòu)，給虛擬機(jī)的分配帶來了新的困難。

1.1.1 節(jié)點介數(shù)和聚集系數(shù)

在現(xiàn)代的拓?fù)浣Y(jié)構(gòu)中，網(wǎng)絡(luò)元素在拓?fù)渲械闹匾愿用黠@，本文引入了聚集系數(shù)和節(jié)點介數(shù)兩個參數(shù)來衡量網(wǎng)絡(luò)元素的重要性。

網(wǎng)絡(luò)拓?fù)淇煽醋饕粋€無向圖G=，所有的網(wǎng)絡(luò)元素（交換機(jī)、服務(wù)器）可看作節(jié)點。假設(shè)節(jié)點數(shù)量為N，邊數(shù)量為M。e_ij表示節(jié)點i與節(jié)點j之間的連接邊。V={i|i∈N}是所有節(jié)點的集合，E={e_ij|i，l∈N且i≠j}是所有邊的集合。

定義1 節(jié)點鄰居和節(jié)點度：節(jié)點鄰居是指與網(wǎng)絡(luò)節(jié)點i直接相連的節(jié)點集合。定義如下：

N_i={j|j∈N且e_ij∈E） （1）

節(jié)點i的度k_i就是節(jié)點的鄰居個數(shù)。

定義2 聚集系數(shù)：聚集系數(shù)是網(wǎng)絡(luò)聚集特性的度量指標(biāo)，表示節(jié)點與鄰居間的親疏程度。在網(wǎng)絡(luò)拓?fù)渲校趇個網(wǎng)絡(luò)節(jié)點的聚集系數(shù)C_i定義如下：

在公式（2）中，節(jié)點的度為K_i，表示有K_o個鄰居，E_i表示節(jié)點i與K_i個鄰居間的實際連接邊的數(shù)量，T_i表示節(jié)點i與K_i個鄰居間可能形成的最大連接邊的數(shù)量。當(dāng)C_i=1時，表示節(jié)點i與所有鄰居節(jié)點互相連接，形成全局耦合網(wǎng)絡(luò)，連接非常緊密。

定義3 節(jié)點介數(shù)（node betweenness）：節(jié)點介數(shù)是網(wǎng)絡(luò)拓?fù)涞囊粋€重要度量。節(jié)點介數(shù)是衡量網(wǎng)絡(luò)拓?fù)渲型ㄟ^該網(wǎng)絡(luò)節(jié)點的最短路徑數(shù)量，反應(yīng)了節(jié)點在網(wǎng)絡(luò)流通中的樞紐性。節(jié)點介數(shù)B_i的定義如下：

在公式（3）中，d_st表示節(jié)點s與節(jié)點t間的最短路徑數(shù)量，d_sit表示過節(jié)點i的節(jié)點s與節(jié)點t間的最短路徑數(shù)量，N（N-1）/2表示節(jié)點s與節(jié)點t的所有可能組合數(shù)。節(jié)點介數(shù)越大說明節(jié)點在網(wǎng)絡(luò)中的樞紐性越強(qiáng)，刪除節(jié)點（節(jié)點故障）會造成大量節(jié)點對間的最短路徑變長，從而增加整個網(wǎng)絡(luò)的壓力，造成網(wǎng)絡(luò)擁塞，甚至是網(wǎng)絡(luò)崩潰。

節(jié)點聚集系數(shù)和節(jié)點介數(shù)能夠很好地反應(yīng)網(wǎng)絡(luò)元素在整個網(wǎng)絡(luò)拓?fù)渲械闹匾潭龋奂禂?shù)體現(xiàn)了節(jié)點與鄰居間的親密程度，介數(shù)反應(yīng)了節(jié)點對整個網(wǎng)絡(luò)流的樞紐性。通過聚集系數(shù)和節(jié)點介數(shù)，能夠輕松感知整個網(wǎng)絡(luò)的資源情況和動態(tài)變化，為虛擬機(jī)的分配提供了強(qiáng)有力的支撐。

1.1.2 網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬

通過仔細(xì)分析數(shù)據(jù)中心的網(wǎng)絡(luò)帶寬使用情況，根據(jù)使用對象的不同，可以將網(wǎng)絡(luò)帶寬分成兩種：網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬。

1）網(wǎng)間帶寬。網(wǎng)間帶寬是指數(shù)據(jù)中心的外部用戶通過互聯(lián)網(wǎng)獲取虛擬機(jī)中計算數(shù)據(jù)所造成的帶寬，也就是用戶與虛擬機(jī)間的通信所產(chǎn)生的網(wǎng)絡(luò)流量。網(wǎng)間帶寬必須通過核心交換機(jī)與外界用戶進(jìn)行交互，需要占用整個網(wǎng)絡(luò)拓?fù)涞墓歉删W(wǎng)絡(luò)資源。網(wǎng)間帶寬是用戶服務(wù)的基礎(chǔ)，是保證服務(wù)SLA等級的關(guān)鍵。因此，網(wǎng)間帶寬應(yīng)該盡量接近核心交換機(jī)，更快速地與用戶進(jìn)行交互。

2）網(wǎng)內(nèi)帶寬。網(wǎng)內(nèi)帶寬是指用戶的多臺虛擬機(jī)間進(jìn)行數(shù)據(jù)通信所造成的帶寬。當(dāng)用戶的多臺虛擬機(jī)為流量密集型虛擬機(jī)時，則虛擬機(jī)間需要頻繁快速地進(jìn)行數(shù)據(jù)交互，保證虛擬機(jī)間的及時通信和運行。網(wǎng)內(nèi)帶寬可能占用過多網(wǎng)絡(luò)資源，造成網(wǎng)絡(luò)突發(fā)流的現(xiàn)象，導(dǎo)致整個數(shù)據(jù)中心網(wǎng)絡(luò)的崩潰。根據(jù)網(wǎng)內(nèi)帶寬的內(nèi)部通信特性，多個相互通信的虛擬機(jī)應(yīng)該盡快靠近，保證較小的通信距離。此外，為了避免網(wǎng)內(nèi)帶寬造成的網(wǎng)絡(luò)突發(fā)流問題，應(yīng)該將流量密集型虛擬機(jī)分配到邊界節(jié)點上，避免核心節(jié)點和骨干網(wǎng)絡(luò)受到影響，約束網(wǎng)絡(luò)突發(fā)流造成的破壞。

網(wǎng)間帶寬與網(wǎng)內(nèi)帶寬的分解使得網(wǎng)絡(luò)感知能夠更加精確地進(jìn)行虛擬機(jī)分配，保證整個數(shù)據(jù)中心網(wǎng)絡(luò)的可靠和穩(wěn)定，減少網(wǎng)絡(luò)突發(fā)流的產(chǎn)生和嚴(yán)重的破壞。

1.2 分配模型

在虛擬機(jī)的分配過程中，每個虛擬機(jī)r_i需要映射到數(shù)據(jù)中心的一臺物理主機(jī)s_i上。物理主機(jī)s_i的CPU，MEM和BW剩余資源必須大于虛擬機(jī)r_i的請求大小。一個虛擬機(jī)只能映射到一臺物理主機(jī)上。同一物理主機(jī)上的多個虛擬機(jī)共享物理主機(jī)資源（CPU，MEM和BW）。每個用戶可能有多個彼此通信的虛擬機(jī)。數(shù)據(jù)中心的物理主機(jī)是異構(gòu)的，存在不同CPU、MEM和BW大小的物理主機(jī)。網(wǎng)絡(luò)拓?fù)鋱DG中的所有交換機(jī)、路由器等網(wǎng)絡(luò)設(shè)備不具有計算能力，只有通信能力，不能將虛擬機(jī)映射到網(wǎng)絡(luò)設(shè)備上。

1.3 兩階段分配目標(biāo)

基于網(wǎng)絡(luò)感知的虛擬機(jī)分配過程同時考慮帶寬資源和物理資源。當(dāng)多個用戶提交一組虛擬機(jī)請求時，其分配過程就是在網(wǎng)絡(luò)拓?fù)渲羞x擇物理主機(jī)進(jìn)行映射的過程。整個過程可以簡單地分為兩個連續(xù)的階段。第一個階段，根據(jù)一組虛擬機(jī)的總體請求帶寬大小，在網(wǎng)絡(luò)拓?fù)渲羞x擇滿足帶寬要求一塊合適的區(qū)域，保證選擇區(qū)域的穩(wěn)定性和可靠性，降低網(wǎng)絡(luò)突發(fā)流的產(chǎn)生概率。第二個階段，在選擇的區(qū)域中，根據(jù)用戶需求尋找最合適的物理主機(jī)進(jìn)行分配，保證物理主機(jī)的資源利用率和負(fù)載。因此，本文將整個網(wǎng)絡(luò)感知的虛擬機(jī)分配過程分解成帶寬區(qū)域劃分和物理主機(jī)分配兩個階段。

1.3.1 帶寬區(qū)域劃分

帶寬區(qū)域劃分階段主要目標(biāo)是為一組虛擬機(jī)集合RS={r_i，i∈P}中的P臺虛擬機(jī)，根據(jù)虛擬機(jī)類型的不同，選擇多個物理主機(jī)區(qū)域，保證每個區(qū)域內(nèi)的虛擬機(jī)擁有較好的網(wǎng)絡(luò)性能，避免和減少網(wǎng)絡(luò)突發(fā)流的產(chǎn)生和帶來的影響。

在帶寬區(qū)域劃分階段，首先需要按類型對虛擬機(jī)進(jìn)行分組。虛擬機(jī)類型Type_BW是指虛擬機(jī)r_i的帶寬請求對鄰居依賴性和網(wǎng)絡(luò)樞紐性的側(cè)重程度，其具體定義如下：

在公式（4）中，虛擬機(jī)類型由虛擬機(jī)的網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬需求大小決定。本文將虛擬機(jī)分成了網(wǎng)間虛擬機(jī)（1）、網(wǎng)內(nèi)虛擬機(jī)（3）和均衡虛擬機(jī)（2）三種。其中，α和β是兩個常數(shù)，表示網(wǎng)間帶寬與網(wǎng)內(nèi)帶寬大小的比值。根據(jù)3.2節(jié)實驗測試，本文默認(rèn)為（1/2和2）。

在虛擬機(jī)類型確定以后，不同類型虛擬機(jī)分配到不同物理主機(jī)，將對整個網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性造成不同程度的影響。例如，當(dāng)網(wǎng)內(nèi)流量高的多個虛擬機(jī)分配到核心網(wǎng)絡(luò)節(jié)點上，必然占用核心節(jié)點帶寬資源，導(dǎo)致其他節(jié)點的通信延遲，甚至發(fā)生網(wǎng)絡(luò)突發(fā)流。當(dāng)網(wǎng)間流量高的虛擬機(jī)分配到邊緣網(wǎng)絡(luò)節(jié)點時，則增加了通信距離，降低了響應(yīng)時間（QOS），導(dǎo)致整個網(wǎng)絡(luò)的不穩(wěn)定。因此，本文使用穩(wěn)定系數(shù)R_C（reliablecoefficient）來描述網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定，定義如下：

從公式（5）中可以看出，不同類型虛擬機(jī)映射到不同的物理主機(jī)上，其穩(wěn)定系數(shù)的產(chǎn)生方式不同。對于網(wǎng)間虛擬機(jī)而言，帶寬和QOS需求較高，應(yīng)映射到靠近核心的樞紐節(jié)點，且周圍鄰居應(yīng)越稀疏，從而保證經(jīng)過的路徑越短，交互速度越快，對鄰居的影響越小；對于網(wǎng)內(nèi)虛擬機(jī)而言，主要是虛擬機(jī)間的彼此通信，應(yīng)該映射到邊界節(jié)點上，使得多個通信虛擬機(jī)彼此靠近。同時，遠(yuǎn)離核心節(jié)點，減少對整個網(wǎng)絡(luò)的過多影響；對于均衡虛擬機(jī)而言，應(yīng)該選擇網(wǎng)絡(luò)拓?fù)涞闹虚g區(qū)域，平衡節(jié)點樞紐性和鄰居依賴性，約束網(wǎng)絡(luò)突發(fā)流的影響，保證整個網(wǎng)絡(luò)的穩(wěn)定性。

因此，帶寬區(qū)域劃分階段的目標(biāo)就是將P臺虛擬機(jī)映射到M臺物理主機(jī)構(gòu)成的多個區(qū)域內(nèi)，實現(xiàn)網(wǎng)絡(luò)穩(wěn)定性的最大化，其目標(biāo)模型如下：

在目標(biāo)模型（6）中，x_ij是一個二進(jìn)制變量，表示虛擬機(jī)i是否分配到物理主機(jī)j上。每個虛擬機(jī)只能映射到一臺物理主機(jī)。

1.3.2 物理主機(jī)分配

通過帶寬區(qū)域劃分階段后，P個虛擬機(jī)集合RS={r_i，i∈P}將被映射到M臺物理主機(jī)組成的區(qū)域KS中。物理主機(jī)分配的核心目標(biāo)就是降低虛擬機(jī)的網(wǎng)內(nèi)帶寬的消耗，均衡KS區(qū)域內(nèi)所有物理主機(jī)的帶寬負(fù)載。

在P個虛擬機(jī)集合RS中，同一用戶的多個虛擬機(jī)屬于相同的類型，且多個虛擬機(jī)間通常彼此通信，需要較大的網(wǎng)內(nèi)帶寬。若將多個虛擬機(jī)映射到同一物理主機(jī)，可大大節(jié)約數(shù)據(jù)中心帶寬的使用。因為，同一物理主機(jī)內(nèi)，多個虛擬機(jī)的通信不需要占用帶寬。為了描述這種網(wǎng)內(nèi)帶寬的節(jié)約度，本文定義了同用戶同物理主機(jī)的虛擬機(jī)分配集，表示分配到同一物理主機(jī)上的相同用戶的虛擬機(jī)請求集合，定義如下：

根據(jù)公式（7），u表示虛擬機(jī)i的用戶屬性，U表示RS中的用戶屬性數(shù)量。x_ij表示虛擬機(jī)i是否分配到物理主機(jī)j。根據(jù)公式（7）可得，物理主機(jī)j的網(wǎng)內(nèi)帶寬節(jié)約度為：

在公式（8）中，網(wǎng)內(nèi)帶寬節(jié)約度就是相同用戶的網(wǎng)內(nèi)帶寬節(jié)約均值之和與總物理主機(jī)消耗帶寬的比值，其值域為[0，1）。

此外，在節(jié)約網(wǎng)內(nèi)帶寬的同時，需要盡量均衡各個物理主機(jī)的帶寬負(fù)載，保證網(wǎng)絡(luò)突發(fā)流情況下所有物理主機(jī)擁有相同的抵御程度和擴(kuò)展性，從而提升數(shù)據(jù)中心網(wǎng)絡(luò)的可靠性。因此，本文定義了帶寬負(fù)載方差，衡量主機(jī)區(qū)域的各物理主機(jī)的帶寬負(fù)載情況，物理主機(jī)j的帶寬負(fù)載方差如下：

在公式（9）中，物理主機(jī)負(fù)載方差的值域同樣為[0，1）。

因此，物理主機(jī)分配階段的目標(biāo)模型是最大化網(wǎng)內(nèi)帶寬節(jié)約度和最小化負(fù)載方差，定義如下：

2 基于網(wǎng)絡(luò)感知的兩階段分配算法

根據(jù)上節(jié)的分配模型，本節(jié)提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法，簡稱NWTP算法。NWTP算法將網(wǎng)絡(luò)感知的虛擬機(jī)分配過程看作一個流水線作業(yè)過程。虛擬機(jī)請求集合為流水線的加工原料，帶寬區(qū)域劃分和物理主機(jī)分配為流水線的兩個連續(xù)工序（環(huán)節(jié)）。2.1節(jié)將詳細(xì)介紹帶寬區(qū)域劃分的流程和策略，為虛擬機(jī)子集選擇物理主機(jī)區(qū)域。2.2節(jié)將介紹物理主機(jī)分配的流程和相應(yīng)策略，更多地節(jié)約網(wǎng)內(nèi)帶寬和均衡區(qū)域主機(jī)帶寬負(fù)載。2.3節(jié)將整體介紹NWTP算法的詳細(xì)流程。

2.1 帶寬區(qū)域劃分

在多個用戶提交的虛擬機(jī)請求集合RS中，根據(jù)虛擬機(jī)類型和用戶屬性，可將RS分解成多個虛擬機(jī)子集。帶寬區(qū)域劃分的目標(biāo)就是根據(jù)每個虛擬機(jī)子集的虛擬機(jī)類型，在網(wǎng)絡(luò)拓?fù)渲羞x擇合適的物理主機(jī)區(qū)域。在虛擬機(jī)子集中，所有虛擬機(jī)都擁有相同的類型和相同的用戶屬性。一次帶寬區(qū)域劃分只為一個虛擬機(jī)子集進(jìn)行主機(jī)區(qū)域選擇。此外，為了保證物理主機(jī)分配的成功率，帶寬區(qū)域劃分中的物理主機(jī)數(shù)量將會多于虛擬機(jī)子集的虛擬機(jī)數(shù)量。本文默認(rèn)物理主機(jī)數(shù)量為虛擬機(jī)數(shù)量的1.2倍，可根據(jù)需要進(jìn)行調(diào)整。

根據(jù)虛擬機(jī)子集內(nèi)虛擬機(jī)的類型，可將虛擬機(jī)子集分成網(wǎng)內(nèi)子集、網(wǎng)間子集和均衡子集三類。三類不同的子集，其區(qū)域選擇的目標(biāo)是不同的、動態(tài)變化的。

1）網(wǎng)間子集。網(wǎng)間子集內(nèi)的虛擬機(jī)都是網(wǎng)間帶寬遠(yuǎn)大于網(wǎng)內(nèi)帶寬的虛擬機(jī)集合。這類虛擬機(jī)的目標(biāo)是對外與用戶交互，保證交互質(zhì)量，提升交互速度是虛擬機(jī)分配的要點。在NWTP算法中，網(wǎng)間子集虛擬機(jī)將映射到具有核心樞紐性的物理主機(jī)上。根據(jù)節(jié)點介數(shù)的定義，核心物理主機(jī)必然在通往外網(wǎng)的核心路徑上。這種分配方式，能夠大大減少用戶與物理主機(jī)交互的通信距離，降低網(wǎng)絡(luò)成本，增加網(wǎng)絡(luò)帶寬的資源利用率。當(dāng)網(wǎng)間流量虛擬機(jī)出現(xiàn)突發(fā)流時，會造成核心節(jié)點的延遲和擁塞。但是，由于網(wǎng)內(nèi)流量的邊界化分配策略，核心節(jié)點的帶寬能力將會最大化，擴(kuò)展性較強(qiáng)，受到突發(fā)流的影響也會越小。同樣，網(wǎng)內(nèi)流量虛擬機(jī)被分配到邊界區(qū)域的節(jié)點和鏈路，且節(jié)點間交互彼此靠近，核心節(jié)點的突發(fā)流不會過多影響網(wǎng)內(nèi)流量的虛擬機(jī)。

2）網(wǎng)內(nèi)子集。網(wǎng)內(nèi)子集的所有虛擬機(jī)網(wǎng)內(nèi)交互帶寬遠(yuǎn)大于網(wǎng)間通信。這類虛擬機(jī)分配的目標(biāo)就是彼此盡量靠近，減少通信距離。在NWTP算法中，網(wǎng)內(nèi)子集的分配策略為：將虛擬機(jī)集合分配到網(wǎng)絡(luò)拓?fù)涞倪吔绻?jié)點區(qū)域，增加邊界節(jié)點的資源利用率，減少虛擬機(jī)對網(wǎng)絡(luò)拓?fù)渲袠屑~節(jié)點的消耗。此外，通過區(qū)域性的分配，能充分保證虛擬機(jī)間的通信距離，減少通信跳數(shù)，提高通信速率。

當(dāng)網(wǎng)內(nèi)子集出現(xiàn)突發(fā)流時，由于分配策略的邊界化，網(wǎng)間虛擬機(jī)受到的影響較少。因為，突發(fā)流發(fā)生在網(wǎng)絡(luò)拓?fù)涞倪吔纾渎拥姆秶邢蓿粫^多蔓延到網(wǎng)絡(luò)拓?fù)渲械暮诵臉屑~節(jié)點。邊界區(qū)域化分配方式增加了數(shù)據(jù)中心網(wǎng)絡(luò)的擴(kuò)展性。此外，對于網(wǎng)內(nèi)虛擬機(jī)而言，由于其分配策略的區(qū)域化，網(wǎng)絡(luò)突發(fā)流的發(fā)生將被限制在固定區(qū)域內(nèi)，造成區(qū)域內(nèi)的延遲和擁塞，影響區(qū)域較小，不會受到其他虛擬機(jī)的干擾，突發(fā)流的消亡周期會大大縮減。此外，通過邊界區(qū)域化的虛擬機(jī)分配，能夠很好地平衡整個網(wǎng)絡(luò)的負(fù)載，增加網(wǎng)絡(luò)的穩(wěn)定性。

3）均衡子集。均衡子集內(nèi)的虛擬機(jī)其網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬相對均衡。這類虛擬機(jī)應(yīng)該同時兼顧網(wǎng)內(nèi)子集和網(wǎng)間子集的分配策略。在NWTP算法中，均衡子集的虛擬機(jī)將被區(qū)域化地分配到網(wǎng)絡(luò)拓?fù)涞闹虚g區(qū)域。在保證用戶對外交互的同時，區(qū)域化地捆綁多個虛擬機(jī)節(jié)點，減少虛擬機(jī)間的通信距離。

圖3展示了不同虛擬機(jī)子集的不同帶寬區(qū)域的選擇策略。整個網(wǎng)絡(luò)拓?fù)淇煽醋饕粋€圓，圓的中心點為網(wǎng)絡(luò)中的核心樞紐點。整個拓?fù)鋱A以核心點為中心，可分為3個圈：核心圈、中間圈和邊界圈，圖中用藍(lán)色虛線劃分。不同的虛擬機(jī)子集將劃分到不同的拓?fù)淙?nèi)，從而均衡整個網(wǎng)絡(luò)拓?fù)涞呢?fù)載，保證網(wǎng)絡(luò)的穩(wěn)定性和可靠性。在圖3中，網(wǎng)內(nèi)子集將被分配到最外層邊界圈內(nèi)。網(wǎng)內(nèi)子集的虛擬機(jī)將分配到彼此鄰居的物理主機(jī)上，縮小虛擬機(jī)間的通信距離；網(wǎng)間子集的虛擬機(jī)將被分配到最內(nèi)層的核心圈內(nèi)，以最快的速度與外界用戶進(jìn)行交互；均衡子集的虛擬機(jī)則映射到中間圈內(nèi)，結(jié)合前兩種策略的優(yōu)點，保證網(wǎng)絡(luò)的擴(kuò)展性。當(dāng)某類型虛擬機(jī)出現(xiàn)突發(fā)流時，區(qū)域化的分配策略必然降低突發(fā)流的破壞性，減少虛擬機(jī)間的干擾性，保障網(wǎng)絡(luò)的穩(wěn)定性。

根據(jù)圖3的示意，NWTP中帶寬區(qū)域劃分的基本思想如下：根據(jù)虛擬機(jī)子集的類型（網(wǎng)間子集、網(wǎng)內(nèi)子集和均衡子集），選擇相應(yīng)的劃分策略。網(wǎng)間子集劃分到更加接近核心樞紐節(jié)點的物理主機(jī)上，減少通信距離，增加交互速率；網(wǎng)內(nèi)子集區(qū)域性地分配到邊界網(wǎng)絡(luò)節(jié)點上，充分利用邊界節(jié)點能力，降低核心節(jié)點和帶寬壓力；網(wǎng)間子集劃分到中間區(qū)域，均衡前兩種策略的優(yōu)點。算法1展示了帶寬區(qū)域劃分的主要流程。

算法1帶寬區(qū)域劃分過程

輸入：虛擬機(jī)子集RS_l，網(wǎng)絡(luò)拓?fù)銰，穩(wěn)定系數(shù)矩陣RC_l。

輸出：虛擬機(jī)子集和物理主機(jī)區(qū)域?qū)?rs_l，SSl>。

Step1：初始化。

①初始化區(qū)域物理主機(jī)數(shù)量上限SN，SN是子集中虛擬機(jī)數(shù)量的1.2倍。

②初始化錯誤核心集ES為空集，ES表示鄰居區(qū)域內(nèi)找不到足夠物理主機(jī)數(shù)量（SN）的節(jié)點集合。

③初始化SS_l，鄰居集N，合理鄰居集NR為空集。

④初始化最小資源需求MIN_CPU，MIN_MEM，MIN_BW，最小資源需求是所有虛擬機(jī)的資源請求最小值。

//在初始化過程中，穩(wěn)定系數(shù)矩陣RC_t與虛擬機(jī)子集RS_l相對應(yīng)，穩(wěn)定系數(shù)矩陣是根據(jù)虛擬機(jī)子集類型按照公式（5）計算而來，并已經(jīng)排好序。

Step2：判斷合理性。遍歷穩(wěn)定系數(shù)矩陣RC_l，選擇區(qū)域核心點s_i，判斷核心點的合理性。核心點不合理的判斷標(biāo)準(zhǔn)如下：

如果s_i不滿足標(biāo)準(zhǔn)，將核心點s_i加人物理主機(jī)區(qū)域SS_l和NR集中，進(jìn)入step3。否則，s_i屬于錯誤核心集ES，或s_i的剩余資源小于最小資源需求。將s_i加入錯誤核心集ES。開始下一個核心點的判斷。

Step3：尋找NR的鄰居點N（NR）。根據(jù)公式（11）計算N（NR）中合理的主機(jī)節(jié)點集合，并替換NR。

①如果NR不為空，將所有主機(jī)加入到SS_l中，進(jìn)人step4。

②如果NR為空，則將N（NR）加入錯誤集ES。返回Step2，判斷下一核心點。

Step4：判斷RC_l是否遍歷完成，且SS_l中物理主機(jī)的數(shù)量是否大于SN。

①遍歷未完成，且主機(jī)數(shù)量小于SN。返回step3，尋找更多的物理主機(jī)節(jié)點。

②遍歷未完成，主機(jī)數(shù)量大于或等于SN。終止程序，返回虛擬機(jī)子集和物理區(qū)域?qū)?rs_l，SSl>。

③RCI遍歷完成。終止程序，返回虛擬機(jī)子集和物理區(qū)域?qū)?rs_l，？>。

2.2 物理主機(jī)分配

物理主機(jī)分配環(huán)節(jié)是整個流水線的第二個環(huán)節(jié)，負(fù)責(zé)對帶寬區(qū)域劃分形成的虛擬機(jī)子集和物理區(qū)域?qū)?rs_{l，SSl>進(jìn)行主機(jī)映射。帶寬區(qū)域劃分和物理主機(jī)分配兩個環(huán)節(jié)彼此連續(xù)。}

相對帶寬區(qū)域劃分而言，物理主機(jī)的分配過程較簡單。其核心目標(biāo)就是最大化的虛擬機(jī)網(wǎng)內(nèi)流量的節(jié)約度，均衡物理主機(jī)區(qū)域內(nèi)的帶寬負(fù)載，增加主機(jī)區(qū)域?qū)W(wǎng)絡(luò)突發(fā)流的免疫力，保證數(shù)據(jù)中心的穩(wěn)定性和擴(kuò)展性。物理主機(jī)分配的詳細(xì)流程如算法2所示。

算法2 物理主機(jī)分配過程輸入：虛擬機(jī)子集和物理主機(jī)區(qū)域?qū)?rs_l，SSl>。

輸出：未分配的虛擬機(jī)集合NoRS_l。

Step1：初始化。將RS_l，SS_l按網(wǎng)內(nèi)帶寬和剩余內(nèi)存的大小進(jìn)行降序排列。初始化未分配的虛擬機(jī)集合NoRS_l為空集。

Step2：遍歷RS_l，分配虛擬機(jī)r_i到物理主機(jī)s_i。具體過程如下：

Step3：返回未分配的虛擬機(jī)集合NoRS_l。

在物理主機(jī)的分配過程中，虛擬機(jī)子集將首先分配到剩余資源多的物理主機(jī)，從而保證更多的虛擬機(jī)分配到同一物理主機(jī)上，增加網(wǎng)內(nèi)流量的節(jié)約度公式（8）。此外，剩余資源最多的物理主機(jī)通常就是負(fù)載方差最大的主機(jī)，將更多的虛擬機(jī)分配到物理主機(jī)，可以均衡帶寬負(fù)載公式（9）。

2.3 NWTP算法

帶寬區(qū)域劃分和物理主機(jī)分配是虛擬機(jī)分配過程的兩個連續(xù)階段。NWTP算法將整個分配過程看作流水線處理過程，兩個分配階段就是流水線中兩個連續(xù)的工序（環(huán)節(jié)）。NWTP算法的基本思想就是：根據(jù)公式（4）定義的虛擬機(jī)類型和用戶屬性，將虛擬機(jī)集合RS分解成L個虛擬機(jī)子集。將每個虛擬機(jī)子集看作原材料，在兩個連續(xù)的工序中進(jìn)行加工，最終完成虛擬機(jī)的分配。NWTP算法是一個并行處理算法，帶寬區(qū)域的劃分與物理主機(jī)的分配兩個工序并行工作，加快了虛擬機(jī)分配的速度。圖4為NWTP算法的分配過程示意圖。

從圖4可以看出，NWTP算法的流水線共有三個工序（環(huán)節(jié)），帶寬區(qū)域劃分、物理主機(jī)分配和錯誤處理。三個環(huán)節(jié)間并行進(jìn)行虛擬機(jī)的分配過程。在t₁時刻，虛擬機(jī)子集RS₁開始進(jìn)行帶寬區(qū)域劃分。t₂時刻，虛擬機(jī)子集RS₁進(jìn)行主機(jī)分配的同時，RS₂開始進(jìn)行帶寬區(qū)域劃分。依次類推，直到所有虛擬機(jī)子集分配完成。因此，NWTP算法能夠并行進(jìn)行多個虛擬機(jī)子集的分配處理，加快分配速度。

在NWTP算法的整個流水線中，錯誤處理是非常重要的環(huán)節(jié)。當(dāng)帶寬劃分中虛擬機(jī)子集無法找到合適的物理主機(jī)時，當(dāng)物理主機(jī)分配中某些虛擬機(jī)無法進(jìn)行分配時，都要進(jìn)行錯誤處理。錯誤處理的流程如下：將未分配虛擬機(jī)集合，分割成兩個虛擬機(jī)子集，重新投人流水線進(jìn)程處理。若虛擬機(jī)集合中只有一個虛擬機(jī)，則等待固定周期T，再次進(jìn)行虛擬機(jī)的分配。因此，NWTP的詳細(xì)過程如算法3所示。

算法3 NWTP并發(fā)分配過程

輸入：虛擬機(jī)集合RS，網(wǎng)絡(luò)拓?fù)銰。

輸出：NULL。

Step1：初始化。根據(jù)網(wǎng)絡(luò)拓?fù)銰，為每個物理主機(jī)節(jié)點生成穩(wěn)定系數(shù)矩陣RC。在RC中，每個物理主機(jī)將有3種類型的穩(wěn)定系數(shù)，因為不同類型的虛擬機(jī)分配物理主機(jī)上，其穩(wěn)定系數(shù)是不同的。

Step2：根據(jù)公式（4）中虛擬機(jī)的類型和用戶屬性，將RS分解成L個虛擬機(jī)子集集合RSL。

Step3：遍歷RSL，根據(jù)虛擬機(jī)的類型為每個虛擬機(jī)子集RS_l求得相應(yīng)的RC_l。根據(jù)RS_l，G，RC_l，按照算法1進(jìn)行帶寬區(qū)域的劃分，獲得虛擬子集與物理主機(jī)區(qū)域?qū)?rs_{l，SSl>。將虛擬子集與物理主機(jī)區(qū)域?qū)?rsl，SSl>輸入到step4，并開始下一個虛擬機(jī)子集的帶寬區(qū)域劃分。}

Step4：根據(jù)輸入的虛擬子集與物理主機(jī)區(qū)域?qū)?rs_{l，SSl>，按照算法2，進(jìn)行虛擬機(jī)到物理主機(jī)的分配。獲取未分配的虛擬機(jī)集合NoRSl。將NoRSl輸入到step5，等待下一個輸入，繼續(xù)執(zhí)行。}

Step5：判斷NoRS_l的虛擬機(jī)數(shù)量。若大于1，分裂成兩個虛擬機(jī)子集，重新加入RSL中等待分配。否則，等待周期t，重新開始分配。

Step6：當(dāng)RSL中所有虛擬機(jī)分配完成，算法結(jié)束。

在NWTP算法中，通過流水線技術(shù)，并行多個階段的處理，加快了處理效率，減少了算法的時間復(fù)雜度。NWTP算法的時間復(fù)雜度為o（R*S），其中R是虛擬機(jī)集合中虛擬機(jī)數(shù)量，S為網(wǎng)絡(luò)拓?fù)渲形锢碇鳈C(jī)數(shù)量。

3 實驗結(jié)果分析

本文利用云計算仿真平臺CloudSim3.5作為仿真工具，將NWTP算法與遺傳算法GA，貪婪算法GR，模擬退火算法SA進(jìn)行對比，從分配時間、網(wǎng)絡(luò)延遲、吞吐率、CPU利用率、帶寬利用率、主機(jī)使用情況等六個方面對NWTP算法進(jìn)行驗證。

3.1 實驗環(huán)境

在CloudSim平臺中，利用隨機(jī)方式產(chǎn)生物理機(jī)資源和虛擬機(jī)分配請求，通過DataCenter，Host，Vm，DataCenteBoker等多個類，實現(xiàn)底層物理機(jī)和虛擬機(jī)的仿真。利用多線程思想優(yōu)化了CloudSim仿真平臺，實現(xiàn)了流水線式的虛擬機(jī)分配過程。在仿真環(huán)境中隨機(jī)產(chǎn)生了500個物理主機(jī)，包含[<2core-4g>，<4core-6g>，<4core-12g>，<8core-24g>]四種類型，詳細(xì)的物理主機(jī)參數(shù)見表1。為了模擬網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性，使用brite拓?fù)渖善麟S機(jī)生成500個節(jié)點的網(wǎng)絡(luò)拓?fù)洌ㄟ叺膸挻笮『脱舆t幾率等信息。虛擬機(jī)同樣采用隨機(jī)策略生成，數(shù)量范圍為[3～400]。每個虛擬機(jī)的CPU需求從[1～4]隨機(jī)生成，內(nèi)存需求從[1～10]*512M隨機(jī)生成，網(wǎng)間和網(wǎng)內(nèi)帶寬需求從[1～10]M隨機(jī)生成。

3.2 虛擬機(jī)類型門限參數(shù)測試

虛擬機(jī)類型是整個網(wǎng)絡(luò)感知分配算法的基礎(chǔ)，是虛擬機(jī)帶寬請求對鄰居依賴性和網(wǎng)絡(luò)樞紐性的偏好。在公式（4）中，α和β是兩個虛擬機(jī)類型的門限參數(shù)，表示虛擬機(jī)網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬需求的比值大小。在不同的門限參數(shù)下，同一虛擬機(jī)將被視作不同的類型，從而采用不同的分配策略，占用網(wǎng)絡(luò)拓?fù)渲胁煌巧木W(wǎng)絡(luò)節(jié)點，對整個網(wǎng)絡(luò)產(chǎn)生不同程度的影響。

本文對決定虛擬機(jī)類型的兩個門限參數(shù)<α，β>進(jìn)行仿真測試。在不同虛擬機(jī)數(shù)量（10～300）下，采用不同的<α，β>值（α從0.1到1，β從1到10）進(jìn)行實驗，對比網(wǎng)絡(luò)感知分配算法在分配時間和網(wǎng)絡(luò)穩(wěn)定性上的差異。表2描述了在100個虛擬機(jī)請求下7種不同<α，β>值對網(wǎng)絡(luò)延遲率、網(wǎng)絡(luò)吞吐率和分配時間的影響。從表中可以看出，隨著α的不斷增加（0.1～0.5），β的不斷減少（10～2），網(wǎng)絡(luò)感知算法的延遲率、吞吐率和分配時間逐漸減少；當(dāng)α和β在<0.5，2>時，算法的性能較好；隨著α的繼續(xù)增加（0.5～1），β的繼續(xù)減少（2～1），算法的延遲率、吞吐率和分配時間又逐漸增加。同樣，表3展示了7種不同<α，β>值在200個虛擬機(jī)請求下對算法的延遲率、吞吐率和分配時間的影響。從圖中可以得到表2相似的結(jié)論，隨著α的不斷增加，β的不斷減少，算法的性能先提升后降低。

通過表2和表3的分析，虛擬機(jī)類型的門限參數(shù)值<α，β>在<0.5，2>時，整個算法的延遲率、吞吐率和分配時間的性能最佳，算法擁有較好的網(wǎng)絡(luò)穩(wěn)定性和分配效率。因此，在后續(xù)的實驗對比中，基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法內(nèi)虛擬機(jī)類型的門限參數(shù)值，公式（4），默認(rèn)設(shè)置為<0.5，2>。

3.3實驗結(jié)果

本次實驗從分配時間、延遲率、吞吐率、CPU利用率、帶寬利用率、主機(jī)使用情況等六個方面對NWTP算法進(jìn)行驗證，體現(xiàn)了NWTP算法的性能。

圖5為4種算法的分配時間對比。從圖中可以看出，隨著虛擬機(jī)請求數(shù)量的不斷增加，分配時間不斷增大。在虛擬機(jī)數(shù)量較小時（10～30），4種算法的分配時間相近。但是，隨著虛擬機(jī)數(shù)據(jù)的不斷增加（30～300），NWTP算法的分配時間明顯優(yōu)于SA和GA算法，僅次于GR算法。因為，GR算法采用隨機(jī)分配策略，不要考慮其他的分配指標(biāo)，尋求局部解，分配時間很快。NWTP，SA和GA算法都在尋找較優(yōu)解，同時考慮負(fù)載均衡等其他目標(biāo)，需要不斷迭代，分配時間較多。然而，在不斷迭代中，NWTP算法采用流水線技術(shù)，并發(fā)進(jìn)行多個階段的分配，提升了分配效率。

圖6展示了4種算法在不同虛擬機(jī)請求下平均延遲率的對比。延遲率是指通信中延遲時間與正常通信時間的比值。從圖中可以看出，隨著虛擬機(jī)數(shù)量的不斷增加，4種算法的延遲率呈上升趨勢，GR算法的延遲率最大，GA和SA的延遲率相近，NWTP算法延遲率最優(yōu)。當(dāng)虛擬機(jī)請求數(shù)量較小時（0～100），4種算法的延遲率都較小且頻繁波動。其中，GR延遲率最大，波動最劇烈。SA的延遲率其次，波動比較頻繁。GA延遲率與SA近似，但是波動最小。NWTP的延遲率最小，波動與SA近似。因為，當(dāng)虛擬機(jī)請求較小時，整個網(wǎng)絡(luò)的吞吐量較小，虛擬機(jī)間的通信彼此不會過多干擾，延遲率較小。但是，GR算法的貪婪分配原則，會將虛擬機(jī)快速分配到高性能物理主機(jī)上，造成虛擬機(jī)的地理位置較分散，延遲率的波動最大。SA和GA算法都通過反復(fù)迭代尋求較優(yōu)的分配位置，其延遲率優(yōu)于GR，波動程度也較小。NWTP則將虛擬機(jī)按照帶寬請求進(jìn)行分類，然后區(qū)域性地進(jìn)行不同類型的虛擬機(jī)分配，保證虛擬機(jī)分配到底層彼此靠近的某幾臺物理主機(jī)上，減少了通信距離。但是，由于底層占用的物理主機(jī)位置比較集中，虛擬機(jī)間的沖突將增大，導(dǎo)致延遲率有所波動。隨著虛擬機(jī)請求數(shù)量的增加（100～300），4種算法的延遲率逐漸增加，波動程度逐漸趨于平緩。其中，NWTP和GA的延遲率最小，NWTP和SA波動最均衡。因為，隨著虛擬機(jī)數(shù)量的增加，4種算法占用的物理主機(jī)數(shù)量快速增加，虛擬機(jī)間的通信可能跨越多個節(jié)點，增加了網(wǎng)絡(luò)的平均延遲率，降低了四種算法對應(yīng)的延遲波動。但是，GR，SA和GA算法的物理主機(jī)分散性，必然導(dǎo)致通信的延遲率加大，其性能差于NWTP算法。

圖7為4種算法在不同虛擬機(jī)請求下平均吞吐率的對比圖。從圖中可以看出，隨著虛擬機(jī)請求數(shù)量的不斷增加，4種算法的平均吞吐率逐漸上升。其中，NWTP算法的吞吐率最大，其次是GA和SA，GR的吞吐率最小。當(dāng)虛擬機(jī)請求數(shù)量較小時（0～40），NWTP算法的吞吐率明顯高于其他3種算法。因為，NWTP將虛擬機(jī)分配到相對集中的物理主機(jī)區(qū)域，減少了虛擬機(jī)間的通信距離，降低了虛擬機(jī)的通信延遲，增加了吞吐量。GR算法隨機(jī)選擇高性能主機(jī)進(jìn)行分配，虛擬機(jī)位置比較分散。SA和GA通過迭代選擇較優(yōu)物理主機(jī)，虛擬機(jī)的位置同樣較分散，通信距離較長，延遲較大，吞吐率較差。隨著虛擬機(jī)數(shù)量的增加（50～300），其他3種算法的吞吐率逐漸逼近NWTP算法。其中，SA和GA比較接近，GR吞吐率最差。因為，隨著虛擬機(jī)數(shù)量增加，占用底層物理主機(jī)資源數(shù)量增大，網(wǎng)絡(luò)的通信負(fù)載加大，虛擬機(jī)間的相互干擾增加，平均的通信延遲加大，4種算法間的吞吐量彼此靠近。較其他3種算法，NWTP算法的區(qū)域性集中分配策略，能夠減少通信距離，降低延遲，提升吞吐率。

圖8展示了4種算法占用底層物理主機(jī)的平均CPU利用率。從圖中可以看出，不同數(shù)量的虛擬機(jī)請求下（10～300），4種算法占用底層物理主機(jī)的平均CPU利用率波動較大。NWTP算法和SA算法的波動情況相對均衡，GA算法次之，GR算法最差。NWTP算法通過區(qū)域化的分配物理主機(jī)，使得區(qū)域內(nèi)物理主機(jī)的CPU使用相對均衡，從而提升了整體網(wǎng)絡(luò)中物理主機(jī)的平均CPU利用率。GR算法的隨機(jī)分配策略，必然造成高性能的物理主機(jī)優(yōu)先分配，隨著虛擬數(shù)據(jù)的不斷增加，浪費的虛擬機(jī)資源不斷增加，平均CPU利用率的波動變化明顯。

圖9是4種算法平均帶寬利用率的對比圖，展示了承載虛擬機(jī)的物理主機(jī)在多次實驗過程中平均帶寬利用率。從圖中可以看出，隨著虛擬機(jī)數(shù)量的不斷變化（從10～300），4種算法占用底層物理主機(jī)的帶寬資源快速變化。GR算法變化最快，GA算法次之，NWTP算法穩(wěn)定性最好。此外，從圖中還可知，較GR和GA兩種算法，NWTP算法在整個分配過程中，具有較高的帶寬利用率，符合提高底層資源利用率的目標(biāo)。因為，GR算法的隨機(jī)分配策略，未考慮任務(wù)資源的負(fù)載情況，很容易造成資源負(fù)載的不均衡。GA算法的不斷迭代，選擇不同類型的物理主機(jī)組合，造成主機(jī)間帶寬通信較頻繁，從而造成帶寬負(fù)載的巨大波動。NWTP算法將帶寬分解成網(wǎng)間帶寬、網(wǎng)內(nèi)帶寬，并根據(jù)虛擬機(jī)的帶寬類型，分配到網(wǎng)絡(luò)拓?fù)渲械牟煌瑓^(qū)域，減少網(wǎng)內(nèi)帶寬的同時，均衡了區(qū)域物理主機(jī)的帶寬負(fù)載，增加了區(qū)域帶寬的利用率，提升了數(shù)據(jù)中心的穩(wěn)定性，對網(wǎng)絡(luò)突發(fā)流有較強(qiáng)的擴(kuò)展性和適應(yīng)性。

圖10展示了4種算法使用底層物理主機(jī)的情況對比。相同的虛擬機(jī)請求使用不同的分配算法，其占用的底層物理主機(jī)不同。從圖10中可以看出，GA算法占用了較多的高性能物理主機(jī)，SA和GA算法對高性能物理主機(jī)的占用情況都明顯高于NWTP算法。在數(shù)據(jù)中心中，高性能的物理主機(jī)往往起著非常核心的作用，是網(wǎng)絡(luò)拓?fù)涞臉屑~，成本較高。較差性能的物理主機(jī)則屬于邊界節(jié)點，樞紐性差，成本低。NWTP算法的邊界區(qū)域分配策略很好地迎合了這種特性，能夠更加適應(yīng)數(shù)據(jù)中心的現(xiàn)實狀況。

4 結(jié)論

針對云數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性，結(jié)合虛擬機(jī)分配很少同時考慮帶寬資源和物理主機(jī)資源的現(xiàn)狀，本文提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機(jī)分配算法，NWTP。首先，根據(jù)交互對象的不同，將虛擬機(jī)的帶寬請求分解為網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬兩種。利用節(jié)點介數(shù)和聚集系數(shù)感知節(jié)點在網(wǎng)絡(luò)拓?fù)渲械泥従右蕾囆院途W(wǎng)絡(luò)樞紐性；其次，將整個虛擬機(jī)分配過程分解為帶寬區(qū)域劃分和物理主機(jī)分配兩個彼此連續(xù)的階段，分別建立網(wǎng)絡(luò)感知模型；然后，利用流水線技術(shù)，將帶寬區(qū)域劃分、物理主機(jī)分配和錯誤處理看作彼此連續(xù)的三個工序（環(huán)節(jié)），并為每個環(huán)節(jié)設(shè)計了相應(yīng)的處理算法，并發(fā)進(jìn)行虛擬機(jī)分配。最后，將NWTP算法與遺傳GA，模擬退火SA，貪婪GR算法進(jìn)行對比，驗證了NWTP算法在分配時間、網(wǎng)絡(luò)延遲、吞吐率、帶寬利用率、CPU利用率和占用主機(jī)均衡度等方面的優(yōu)勢。