云數(shù)據(jù)中心的虛擬機放置問題

樊勇兵，陳 天，陳 楠，黃志蘭，呂翠娥

（1.中國電信股份有限公司廣州研究院 廣州 510630；2.浪潮集團有限公司 濟南 250101）

1 虛擬機放置問題的來源

在云數(shù)據(jù)中心（cloud data center，CDC），計算資源和網(wǎng)絡(luò)資源被多個租戶動態(tài)共享，其中計算資源共享方式主要是虛擬化，即物理服務(wù)器（又稱物理機）被虛擬化為多臺虛擬服務(wù)器（又稱虛擬機）。當(dāng)一個或多個租戶的資源請求動態(tài)到達并動態(tài)變化時，如何有效地為其分配（或調(diào)整）虛擬機和網(wǎng)絡(luò)連接且滿足一定的服務(wù)等級協(xié)議（service level agreement，SLA）和資源約束，稱為虛擬機放置（virtual machine placement，VMP）問題。

與VMP問題很類似的一個問題是虛擬網(wǎng)絡(luò)映射（virtual network mapping，VNM）問題：在一個物理網(wǎng)絡(luò)（又稱為基礎(chǔ)網(wǎng)絡(luò)）上有多個虛擬網(wǎng)絡(luò)（virtual network，VN），這些VN在一定的SLA和資源約束下動態(tài)共享物理網(wǎng)絡(luò)中的物理節(jié)點（即物理網(wǎng)絡(luò)設(shè)備）資源、物理鏈路資源。

如果將VNM中的節(jié)點理解為（物理的或虛擬的）服務(wù)器，并且將節(jié)點限定為接入節(jié)點（即直接接入通信終端設(shè)備的節(jié)點），那么VMP問題可以理解為帶位置約束的VNM問題。本文的討論對象是VMP。因為VNM的算法大多都可以直接或間接應(yīng)用于VMP，所以在不會引起歧義的情況下，以下將不加區(qū)分地使用VMP和VNM。

VMP問題是云IDC的核心問題之一，在數(shù)學(xué)上它是一個NP難的問題[1]，這使得VMP研究既具實用價值又具學(xué)術(shù)價值，從而成為云IDC的研究熱點。

2 VMP問題分析

大部分虛擬機放置算法都包含節(jié)點映射和鏈路映射兩個階段，二者都是組合最優(yōu)化問題，也都是NP難的問題，所以虛擬機放置面臨的首要問題是算法。此外還有優(yōu)化目標(biāo)的綜合權(quán)衡、算法評估、算法比較、模擬與仿真等。

在規(guī)模足夠大時求解NP難問題只能采用啟發(fā)式算法。所謂啟發(fā)式算法，是相對于最優(yōu)算法提出的，可以這樣定義[2]：一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的成本下給出待解決問題每一個實例的一個可行解，該解與最優(yōu)解的偏離程度不一定可以事先預(yù)計。啟發(fā)式算法有諸多好處，但也有明顯不足：不能保證求得最優(yōu)解；表現(xiàn)不穩(wěn)定；算法的好壞依賴于實際問題和設(shè)計者的經(jīng)驗，很難總結(jié)規(guī)律，同時使不同算法之間難以比較。啟發(fā)式算法可以大致分為如下幾類：一步法；迭代法；數(shù)學(xué)規(guī)劃法；解空間松弛法；現(xiàn)代優(yōu)化算法，如模擬退火、遺傳算法等，它們的共同目標(biāo)是求NP難問題的全局最優(yōu)解，但NP難問題的特性又使它們只能以啟發(fā)式的算法去求解；其他方法，一類算法是根據(jù)實際問題而產(chǎn)生的，另一類算法是集成諸多啟發(fā)式算法的算法。在虛擬機放置問題中，算法的選擇、集成、改進或適配、算法的并行化、新算法的研究、經(jīng)驗的整理和應(yīng)用都是重要內(nèi)容。

在不同場合，虛擬機放置問題有不同優(yōu)化目標(biāo)，如資源利用率、資源利用均衡性、SLA保障（節(jié)點保障、鏈路保障、服務(wù)保障、容災(zāi)備份、SLA違規(guī)成本等）、節(jié)能、收益成本比、使用節(jié)點最少（可能要求更多虛擬機遷移）、降低虛擬機遷移代價（可能增加物理服務(wù)器數(shù)量）等。其中，有些目標(biāo)是互斥的，如追求資源利用的均衡性則不能保證節(jié)能，追求資源利用率可能導(dǎo)致大量的SLA違規(guī)，即使是相容的目標(biāo)也需要考慮如何轉(zhuǎn)換為綜合的單一目標(biāo)。因此，優(yōu)化目標(biāo)的綜合權(quán)衡也是虛擬機放置問題不容忽視的方面。

啟發(fā)式算法有諸多缺陷，虛擬機放置問題的場景、輸入、約束、優(yōu)化目標(biāo)復(fù)雜多樣，所以對算法的評估成為虛擬機放置問題的重要內(nèi)容，評估參數(shù)主要包括：算法的收斂速度、算法適用的問題規(guī)模、優(yōu)化目標(biāo)的滿足程度以及對多優(yōu)化目標(biāo)的適用性、映射成功率、對不同請求模型和物理網(wǎng)絡(luò)拓?fù)涞倪m用性。

與算法評估緊密相關(guān)的是基準(zhǔn)模型。為了比較不同算法的特點和優(yōu)劣勢，必須建立各種算法可以共享的比較基準(zhǔn)。參考文獻[3]提出了一個標(biāo)準(zhǔn)輸入和評估度量，以對不同算法進行客觀比較。

設(shè)計完成的算法最終是需要在生產(chǎn)環(huán)境中使用的，但在此之前該算法必須要得到驗證，云計算模擬和仿真工具應(yīng)運而生。

CloudSim是云計算環(huán)境下的現(xiàn)代模擬框架和工具套件。相比于其他工具套件（如SimGrid、GangSim），CloudSim允許虛擬化環(huán)境的建模，支持按需資源指配和管理，并擴展到支持能源感知的模擬，還集成了動態(tài)負(fù)載下的業(yè)務(wù)應(yīng)用模擬能力。其他如面向能耗感知的GreenCloud、面向應(yīng)用性價比建模的iCanCloud、面向社交網(wǎng)絡(luò)工具評估的CloudAnalyst等都是各具特色的云環(huán)境模擬工具。

此外，還有用于網(wǎng)格計算和VNM環(huán)境的平臺，如GridSim[4]、GangSim[5]、Netbed[6]、PlanetLab[7]等。

3 VMP算法概述

表1是對VNM相關(guān)算法的一個分類[8]，這些算法基本都可以直接或間接地應(yīng)用于VMP問題。表1的一個明顯缺陷是分類維度不一致。

關(guān)于VMP算法或VNM算法的參考文獻很多，下面補充介紹幾個具有顯著特色的算法。

[18]利用了云IDC歸屬于單一管理實體的特點，提出了在多租戶的云中以虛擬數(shù)據(jù)中心（virtual data center，VDC）為資源分配單位的方法，設(shè)計了一種數(shù)據(jù)中心網(wǎng)絡(luò)虛擬化架構(gòu)，稱之為SecondNet，將虛擬機到物理機的映射、路由、帶寬預(yù)留狀態(tài)等功能都分布在服務(wù)器的虛擬機管理器（virtual machine manager，VMM）上，從而達到可擴展性；其基于源路由的端口交換（port-switching based source routing，PSSR）特性進一步使SecondNet適用于任意網(wǎng)絡(luò)拓?fù)?；定義了3種服務(wù)模型；虛擬機分配采用啟發(fā)式算法。為此，參考文獻[18]將相鄰的服務(wù)器組合成一個集群，如ToR集群、Pod集群或n-hop集群，一個服務(wù)器可以同時屬于一個ToR集群和一個Pod集群，甚至整個物理服務(wù)器集群。當(dāng)分配一個VDC時，僅需要搜索集群而不是整個物理網(wǎng)絡(luò)。使用單路徑的最小成本流算法將虛擬機映射到物理機上，然后通過最短路徑算法為虛擬機對分配路徑。

表1 虛擬網(wǎng)絡(luò)映射算法分類

仿真結(jié)果顯示，在一個10萬物理服務(wù)器的數(shù)據(jù)中心里，該方法可以在平均493 s的時間內(nèi)分配5 000個虛擬機，速度非?？?；缺點是不能處理多路徑問題（可能導(dǎo)致亂序）、不能處理特殊情況（如某些虛擬機要單獨部署）、不能處理服務(wù)器失效等。

參考文獻[19]提出的服務(wù)器整合方法充分利用了虛擬機間的通信關(guān)系和應(yīng)用特征的相容性。服務(wù)器整合時需要遷移虛擬機，可能使本來距離很近的需要相互通信的虛擬機變得很遠(yuǎn)。大部分研究者都是基于CPU利用率進行虛擬機遷移的，這可能導(dǎo)致同一物理服務(wù)器上運行多臺有同樣資源需求的虛擬機，使該服務(wù)器的某類資源（如CPU或內(nèi)存）迅速耗盡，最終結(jié)果是需要開啟更多的服務(wù)器以容納其他虛擬機，從而提高了總體能耗和流量成本。該參考文獻給一對虛擬機定義了一個流量權(quán)、一個通信成本（如跳數(shù)），并對所有虛擬機及其通信關(guān)系建模得到一個圖。頂點是虛擬機，邊是通信關(guān)系，邊的權(quán)值是流量權(quán)。對邊的權(quán)值從小到大排序，將權(quán)值最小的邊刪除，得到若干子圖。如此遞歸，最終所有子圖都只包含一個頂點。整個過程可以用樹型結(jié)構(gòu)描述，最終同一層次的兄弟葉子節(jié)點部署在靠近的物理機上（但不是同一臺物理機）。

參考文獻[20]將商業(yè)運營的云IDC因SLA違規(guī)導(dǎo)致的成本作為算法的重要考慮因素，并得到很多富于啟發(fā)意義的結(jié)論。提出一種基于歷史數(shù)據(jù)以自適應(yīng)預(yù)測過載主機的算法，然后根據(jù)3種策略選擇被遷移虛擬機：策略1——根據(jù)所使用內(nèi)存決定遷移時間最小的虛擬機；策略2——隨機選擇；策略3——選擇和其他虛擬機的CPU利用率有最大相關(guān)性的虛擬機進行遷移。用Power Aware Best Fit Decreasing方法[21]找到目的主機：將虛擬機按CPU利用率降序排列，目的主機應(yīng)提供最小的能耗增加；將所有過載主機處理完之后，選擇負(fù)載最低的主機，將其上虛擬機遷移到其他主機且使目的主機不過載。若該主機上所有虛擬機被遷移，則關(guān)閉該主機。如此循環(huán)，遍歷所有主機。

參考文獻[20]得出的結(jié)論是：動態(tài)整合算法顯著優(yōu)于靜態(tài)分配策略；啟發(fā)式動態(tài)整合算法顯著優(yōu)于優(yōu)化在線確定性算法；上述虛擬機遷移策略的策略1顯著優(yōu)于策略2和策略3；基于本地回歸的動態(tài)整合優(yōu)于基于閾值和自適應(yīng)閾值的算法，因為前者更好地預(yù)見了過載，從而降低了SLA違規(guī)和遷移次數(shù)；基于本地回歸的算法優(yōu)于頑健的本地回歸算法，這可以解釋為對于實驗中的模擬負(fù)載，響應(yīng)峰值負(fù)載比平滑這些峰值更重要。

4 骨干互聯(lián)網(wǎng)的“虛擬機”放置問題

直觀上看，骨干互聯(lián)網(wǎng)也存在VMP問題。數(shù)以億計的接入用戶（如寬帶用戶、專線用戶、移動用戶、IDC用戶、它網(wǎng)用戶）通過互聯(lián)網(wǎng)進行通信，猶如數(shù)以億計的虛擬機通過云IDC的網(wǎng)絡(luò)進行通信。無論是從規(guī)模還是從復(fù)雜性，似乎骨干互聯(lián)網(wǎng)的問題嚴(yán)重性都遠(yuǎn)大于云IDC網(wǎng)絡(luò)，但從實踐上看前者解決VMP問題的方法是粗糙而有效的，不需要非常精致：以歷史流量流向為基礎(chǔ)，結(jié)合宏觀規(guī)劃或預(yù)測（如GDP、城市規(guī)劃、大的技術(shù)升級或新的應(yīng)用部署），通過簡單的擬合外推等手段，輔以仿真和局部調(diào)整，總是能得到基本滿意的網(wǎng)絡(luò)方案。但這并不意味著看似規(guī)模和復(fù)雜性都更小的云IDC的VMP問題也同樣如此。

骨干互聯(lián)網(wǎng)的VMP具有以下幾個特點。

·只需要考慮單個“虛擬機”的出口帶寬，不需要考慮多個虛擬機承載在一個物理機上的情況，也不需要考慮“虛擬機”的CPU、內(nèi)存等其他節(jié)點約束。

·只需要考慮獨立“虛擬機”的出口帶寬，不需要考慮有組網(wǎng)關(guān)系和通信需求的多個“虛擬機”的通信約束，其根本原因并不在于“虛擬機”間真的沒有通信約束，而是由于骨干互聯(lián)網(wǎng)以B/S架構(gòu)為主的通信模式、分層匯聚結(jié)構(gòu)、巨大的網(wǎng)絡(luò)容量和“虛擬機”數(shù)量、可預(yù)知的單“虛擬機”出口帶寬和相對穩(wěn)定的通信需求、內(nèi)置的負(fù)載均衡、粗顆粒的調(diào)度、“盡力而為”的通信保障機制，共同導(dǎo)致了流量模型的統(tǒng)計穩(wěn)定性，使得“虛擬機”間的通信約束湮沒其中，可以忽略不計。

·“虛擬機”數(shù)量和總?cè)萘渴穷A(yù)知且有限的，不需要考慮未知且無限的請求序列；“虛擬機”的位置分布是幾乎固定的（除了極少量的移動用戶），不需要考慮因節(jié)點容量、SLA等因素的約束而導(dǎo)致的位置選擇和遷移，因而簡化了鏈路映射。

總之，不管從實踐上還是從理論上看，相對云IDC來說，骨干互聯(lián)網(wǎng)的VMP問題都是經(jīng)過高度簡化的，簡化主要來源于以下3個方面。

·問題特性，如不需要考慮過多的節(jié)點約束、鏈路約束。

·技術(shù)上的“不作為”，如不考慮多個“虛擬機”間的通信約束（事實上也難以考慮）、不大規(guī)模地部署細(xì)顆粒度的流量工程。

·技術(shù)上的“作為”，如網(wǎng)絡(luò)架構(gòu)、內(nèi)置的負(fù)載均衡、分布式處理、粗顆粒的QoS機制等。這種簡化一方面帶來了操作上的便利性、有效性；另一方面也間接地說明了在大型公眾互聯(lián)網(wǎng)上，細(xì)顆粒度、多目標(biāo)、逐跳預(yù)留的流量工程沒有被大規(guī)模成功部署的原因。

骨干互聯(lián)網(wǎng)的VMP問題為云IDC的工程實踐提供了重要借鑒。

·業(yè)務(wù)特性決定網(wǎng)絡(luò)特性。云IDC網(wǎng)絡(luò)與骨干互聯(lián)網(wǎng)本質(zhì)上是兩種不同的網(wǎng)絡(luò)，這使得前者既存在創(chuàng)新的可能和必要，也存在借鑒和甄別傳統(tǒng)技術(shù)的可能和必要。

·虛擬機通信是云IDC網(wǎng)絡(luò)承載的基本業(yè)務(wù)，可以考慮將VMP問題的復(fù)雜性部分卸載到網(wǎng)絡(luò)層或商業(yè)層解決（緩解），而不是僅由算法層承擔(dān)。

·看似完美但已經(jīng)證明是徒勞無功的做法（如上述“理想的”流量工程）不應(yīng)再次成為新網(wǎng)絡(luò)的負(fù)擔(dān)。

5 VMP算法和骨干互聯(lián)網(wǎng)規(guī)劃為云IDC帶來的工程啟示

VMP問題是NP難問題，一定規(guī)模下只能采用啟發(fā)式算法，而啟發(fā)式算法的有效性高度依賴于算法設(shè)計者的經(jīng)驗——既包括工程經(jīng)驗（對具體問題的理解）也包括算法經(jīng)驗（基于對算法的理解，將工程經(jīng)驗轉(zhuǎn)化為算法設(shè)計）。一方面，工程經(jīng)驗可以指導(dǎo)云IDC的規(guī)劃設(shè)計，并轉(zhuǎn)化為算法經(jīng)驗內(nèi)置在運營平臺中；另一方面，一個既有的平臺可以為算法設(shè)計者和云IDC設(shè)計者反饋經(jīng)驗。因此，經(jīng)驗的獲取、積累、應(yīng)用、反饋、改進以及工程經(jīng)驗和算法經(jīng)驗的互相轉(zhuǎn)化，成為一個重要問題。顯然，算法和工程是一種相互適配、相得益彰的關(guān)系。

5.1 監(jiān)控和計量

為了積累、復(fù)用基礎(chǔ)數(shù)據(jù)和經(jīng)驗，并將其用于驗證或修正已有方法，必須對運營平臺進行實時、連續(xù)、全面的監(jiān)控和計量，包括客戶請求信息和到達情況、平臺和算法運行情況、資源占用情況、SLA違規(guī)情況、流量流向數(shù)據(jù)、能耗數(shù)據(jù)等。運營者宜事先籌劃并不斷完善監(jiān)控和計量的對象、參數(shù)、工具。例如，算法的歷史數(shù)據(jù)既可以作為比對和改進的基礎(chǔ)，也可以留待將來有類似需求時參照使用。參考文獻[22]針對中心輻射拓?fù)浣Y(jié)構(gòu)的虛擬網(wǎng)絡(luò)請求，提出了一種個性化的節(jié)點映射算法。推而廣之，如果能根據(jù)歷史數(shù)據(jù)總結(jié)各種請求模型并分別得到較優(yōu)化的算法，可以極大提高運營效率和效益。

5.2 業(yè)務(wù)模型、SLA和資費設(shè)計

通過完善的業(yè)務(wù)模型、SLA和資費設(shè)計，既可以有效發(fā)掘和引導(dǎo)用戶需求，提供差異化增值服務(wù)，又可以使得用戶請求的內(nèi)在關(guān)聯(lián)顯性化，量化程度和可預(yù)見性也大大增強，從而有利于部分卸載算法層的復(fù)雜性和運營管理的迭代改善。例如，現(xiàn)在絕大部分公有云平臺所能接受的用戶請求參數(shù)基本限于虛擬機規(guī)格和數(shù)量，并不涉及虛擬機間的通信拓?fù)浜蛶挕r延等參數(shù)，僅有的幾個SLA指標(biāo)也是由云服務(wù)提供商單方面強加給用戶的，這顯然不利于業(yè)務(wù)的精細(xì)開展和資源的高效使用。一種可供借鑒的選擇是以VDC為分配單位（或者考慮虛擬機之間的通信密度），并盡量將有通信需求的虛擬機分配在鄰近的節(jié)點，不僅能節(jié)省資源，還能改善SLA。參考文獻[19]提出的算法可以部分滿足要求，前提是要通過某種手段（技術(shù)手段或非技術(shù)手段）獲取用戶的通信模型。但從激勵用戶或提供增值服務(wù)的角度看，非技術(shù)手段（完善的業(yè)務(wù)模型、SLA和資費設(shè)計）才是用戶可以直接感知的，因此顯然是更合適的。

5.3 云資源池的設(shè)計

資源池設(shè)計的根本依據(jù)是業(yè)務(wù)和技術(shù)要求。設(shè)計一旦確定，它對算法的效能將起到?jīng)Q定性作用。所以，從算法出發(fā)反推，可以給出另一個審視資源池設(shè)計的角度，期望設(shè)計既不違反通用原則，又有利于算法高效運行。事實上，既存在通用設(shè)計原則，也存在針對性設(shè)計原則，可以使資源池與算法更為匹配，從而在一定程度上卸載算法復(fù)雜性，提高總體效能。

5.3.1 資源池規(guī)模和架構(gòu)

如果資源池中存在明顯的稀缺資源，容易導(dǎo)致映射失敗[23]。骨干互聯(lián)網(wǎng)的“虛擬機”放置問題之所以簡單，一個重要原因是規(guī)模帶來的流量流向的統(tǒng)計穩(wěn)定性。而傳統(tǒng)IDC網(wǎng)絡(luò)的分層匯聚架構(gòu)恰好在骨干鏈路形成瓶頸，因此需要規(guī)模更大的、稠密的扁平網(wǎng)絡(luò)。這里的“規(guī)?！笔窍鄬τ谫Y源池中典型的單用戶虛擬機通信容量而言的，規(guī)模越大，則資源越豐富，流量流向的統(tǒng)計穩(wěn)定性越強，有利于消除啟發(fā)式算法內(nèi)在的不穩(wěn)定性；“稠密”指的是網(wǎng)絡(luò)節(jié)點的“度”（degree）數(shù)要達到一定水平，也就是網(wǎng)絡(luò)的鏈路數(shù)量要足夠多；“扁平”意指去掉不必要的匯聚層次，并使網(wǎng)絡(luò)在一定范圍內(nèi)（以下稱為“域”）形成對稱結(jié)構(gòu)，消除局部的資源稀缺。當(dāng)某些情況下只能采用特殊的網(wǎng)絡(luò)架構(gòu)，則算法改變成為必然。

5.3.2 業(yè)務(wù)分區(qū)和遷移控制的設(shè)計

嚴(yán)格說，業(yè)務(wù)分區(qū)和遷移控制（尤其是遷移網(wǎng)絡(luò)）的設(shè)計也是資源池架構(gòu)的一部分。

與上述“扁平”所強調(diào)的“連通性”不同，“分區(qū)”強調(diào)的是“隔離”，即按照一定分類標(biāo)準(zhǔn)（如用戶類型、業(yè)務(wù)類型、生命周期等），每個類別形成一個獨立的域，域之間往往通過3層進行隔離。分區(qū)對算法的意義在于：降低計算復(fù)雜度，有利于算法的并行化和隔離，將域特定的經(jīng)驗應(yīng)用于算法，從而形成定制算法，算法的不穩(wěn)定性或非全局最優(yōu)性不會無限累加，也不會在域間互相滲透。此外，參考文獻[18]認(rèn)為，VDC分配過程中能否為VDC選擇到合適的集群比在確定的集群中能否找到一個好的分配對算法的影響更大（這里的“集群”可以粗略理解為“分區(qū)”）。

對于高頻率使用的大規(guī)模單一應(yīng)用（如Hadoop計算），可使用物理上獨立的業(yè)務(wù)分區(qū)。該應(yīng)用如果必須與其他應(yīng)用共享物理基礎(chǔ)設(shè)施，算法上則可將該應(yīng)用處理為已經(jīng)成功映射的虛擬機放置請求。

關(guān)于云IDC網(wǎng)絡(luò)業(yè)務(wù)分區(qū)的設(shè)計，可以借鑒參考文獻[24]提出的方法。

云IDC區(qū)別于傳統(tǒng)IDC的一個重要特點就是虛擬機遷移。在手工管理或小規(guī)模自動化管理的情況下，虛擬機遷移也許不是大事，但在大規(guī)模自動化管理環(huán)境中，系統(tǒng)往往借助它完成優(yōu)化部署任務(wù)。由于虛擬機遷移對環(huán)境敏感，所受限制較多，資源占用厲害，所以規(guī)模越大，自動化程度越高，遷移網(wǎng)絡(luò)相對于業(yè)務(wù)網(wǎng)絡(luò)的隔離越重要，遷移的啟動控制和實施控制也應(yīng)該越精細(xì)。參考文獻[20]提出了具體的遷移控制建議，包括遷移決策方法、遷移依據(jù)、遷移與SLA違規(guī)的關(guān)系等。

5.3.3 資源池的資源均衡性

包括同質(zhì)資源的均衡性（如扁平對稱網(wǎng)絡(luò)、鏈路帶寬和成本、物理服務(wù)器的配置和功能）、異質(zhì)資源之間的均衡性（如網(wǎng)絡(luò)容量和計算容量之間的均衡性、CPU和I/O之間的均衡性）。這種均衡性本質(zhì)上是以規(guī)模為基礎(chǔ)，消除某些資源類別的稀缺性（從資源配比的角度），從而達到物理資源消耗的統(tǒng)計穩(wěn)定性。

5.3.4 邏輯網(wǎng)絡(luò)和物理網(wǎng)絡(luò)基礎(chǔ)功能的設(shè)計

首先是負(fù)載均衡功能，這可以極大緩解因算法內(nèi)在缺陷導(dǎo)致的對資源池的負(fù)面影響，提升資源池對算法的支持能力。通常，網(wǎng)絡(luò)都具備負(fù)載均衡能力。云IDC的特殊之處在于，網(wǎng)絡(luò)已經(jīng)延伸到物理服務(wù)器內(nèi)部，并且為了盡量不改變原有基礎(chǔ)網(wǎng)絡(luò)，當(dāng)前傾向于采用疊加（Overlay）組網(wǎng)方式（在當(dāng)前實現(xiàn)中，基礎(chǔ)網(wǎng)絡(luò)和疊加網(wǎng)絡(luò)幾乎無法相互感知、適配），隧道端點既可以在物理服務(wù)器上，也可以在ToR交換機上。如果是前者，受服務(wù)器處理能力的限制，一般采用TCP/UDP之上的隧道封裝，以便很多協(xié)議處理可以卸載到網(wǎng)卡上，因此對網(wǎng)卡的要求也成為整體網(wǎng)絡(luò)功能設(shè)計的一部分；如果是后者，為了避免“大象流”對網(wǎng)絡(luò)的沖擊，也需要采用TCP/UDP之上的隧道封裝，以便形成足夠細(xì)顆粒度的負(fù)載均衡能力，而不是傳統(tǒng)基于五元組的負(fù)載均衡。另一個特殊之處在于，如果VMP算法使用路徑分割[11]方法，負(fù)載均衡可能導(dǎo)致分組亂序；此外，某些云IDC網(wǎng)絡(luò)拓?fù)湫枰汕先f的等價路徑，而傳統(tǒng)網(wǎng)絡(luò)一般只支持16條或更少等價路徑；最后，業(yè)務(wù)鏈（service chain）的引入破壞了傳統(tǒng)端到端的負(fù)載均衡機制，使原來純粹基于網(wǎng)絡(luò)的負(fù)載均衡與業(yè)務(wù)編排、網(wǎng)絡(luò)服務(wù)節(jié)點的部署緊耦合。關(guān)于路徑分割、海量等價路徑和業(yè)務(wù)鏈導(dǎo)致的負(fù)載均衡問題，目前并無成本可行的、統(tǒng)一的商用解決方案，需要進一步深入研究。

其次是QoS功能，它同樣可以有效卸載算法復(fù)雜性，并提供增值服務(wù)。云IDC網(wǎng)絡(luò)在數(shù)學(xué)模型上是一個比骨干互聯(lián)網(wǎng)復(fù)雜得多的網(wǎng)絡(luò)，如果連后者都從來沒有大規(guī)模成功部署過細(xì)顆粒度、多目標(biāo)、逐跳預(yù)留的流量工程，那在設(shè)計云IDC的VMP算法時更應(yīng)避免淪為繁瑣的流量工程工具，而應(yīng)借鑒骨干互聯(lián)網(wǎng)，在物理承載網(wǎng)絡(luò)上采用區(qū)分服務(wù)QoS模型。

5.4 廣闊的創(chuàng)新空間

云IDC網(wǎng)絡(luò)與骨干互聯(lián)網(wǎng)存在本質(zhì)不同，并且云資源池大多歸屬于單一管理實體，這為相關(guān)的創(chuàng)新提供了廣闊空間。例如，參考文獻[18]提出的基于VMM的源路由，在公共互聯(lián)網(wǎng)上就很難實現(xiàn)，因為網(wǎng)絡(luò)運營商不能控制通信終端，所以路由不能由終端決定，只能由網(wǎng)絡(luò)決定；Google提出的B4網(wǎng)絡(luò)[25]是云IDC網(wǎng)絡(luò)整體架構(gòu)上的創(chuàng)新，這種短時間內(nèi)整體架構(gòu)的創(chuàng)新在公共互聯(lián)網(wǎng)上是難以想象的，而其技術(shù)上的成功又是因為該架構(gòu)與Google新型業(yè)務(wù)模型的高度適配。

6 結(jié)束語

本文總結(jié)了虛擬機放置相關(guān)的算法、目標(biāo)及算法評估等關(guān)鍵問題，概述了虛擬機放置問題的主要算法，深入分析了骨干互聯(lián)網(wǎng)中虛擬機放置問題的特點和對云數(shù)據(jù)中心工程實踐的借鑒意義，并從算法和工程相互適配的角度，提出了云數(shù)據(jù)中心設(shè)計、運營的若干重要原則，對未來云數(shù)據(jù)中心的建設(shè)和發(fā)展具有重大的借鑒價值。

隨著云服務(wù)和軟件定義網(wǎng)絡(luò)的興起與發(fā)展，VMP算法作為云管理平臺核心組件的重要性越來越突出。雖然算法涉及的基礎(chǔ)理論研究大部分都比較成熟，但在該領(lǐng)域的應(yīng)用研究現(xiàn)狀并不盡如人意：沒有完整的通用算法框架；算法經(jīng)驗不豐富，更沒有系統(tǒng)性；欠缺算法與云資源池、需求模型的適配研究；算法評估和基準(zhǔn)比較不完善；有些重要算法（如神經(jīng)網(wǎng)絡(luò)）的應(yīng)用研究還只是非常零星地被發(fā)現(xiàn)。這些問題應(yīng)該是VMP算法下一步的重點研究方向。

參考文獻

1 Andersen D G.Theoretical approaches to node assignment(unpublished manuscript).http://nms.lcs.mit.edu/papers/andersenassign.ps,2002

2 邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計算方法.北京:清華大學(xué)出版社,1999 Xing W X,Xie J X.Modern Optimization Computing Method.Beijing:Tsinghua University Press,1999

3 Zhu J.Benchmarking virtual network mapping algorithms.University of Massachusetts,2012

4 Buyya R,Murshed M.GridSim:a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing.Journal of Concurrency and Computation:Practice and Experience,2002,14(13～15):1175～1220

5 GangSim:a simulator for grid scheduling studies with support for uSLAs.http://people.cs.uchicago.edu/～cldumitr/GangSim,2006

6 White B,Lepreau J,Stoller L,et al.An integrated experimental environment for distributed systems and networks.Proceedings of the 5th Symposium on Operating Systems Design and Implementation,Boston,MA,USA,2002:255～270

7 Peterson L,Anderson T,Culler D,et al.A blueprint for introducing disruptive technology into the internet.Proceedings of HotNets-I,Princeton,NJ,USA,2002

8 程祥,張忠寶,蘇森等.虛擬網(wǎng)絡(luò)映射問題研究綜述.通信學(xué)報,2011,32(10)Cheng X,Zhang Z B,Su S,et al.Survey of virtual network embedding problem.Journal on Communication,2011,32(10)

9 Zhu Y,Ammar M.Algorithms for assigning substrate network resources to virtual network components.Proceedings of IEEE INFOCOM,Barcelona,Spain,2006:1～12

10 Lu J,Turner J.Efficient Mapping of Virtual Networks onto a Shared Substrate.Technical Report WUCSE-2006-35,Washington University,2006

11 Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration.ACM SIGCOMM Computer Communication Review,2008,38(2):17～29

12 Chowdhury N,Rahman M,Boutaba R.Virtual network embedding with coordinated node and link mapping.Proceedings of IEEE INFOCOM,Rio de Janeiro,Brazil,2009:783～791

13 Lischka J,Karl H.A virtual network mapping algorithm based on subgraph isomorphism detection.Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures,Barcelona,Spain,2009:81～88

14 Shamsi J,Brockmeyer M.QoSMap:QoS aware mapping of virtual networks for resiliency and efficiency.Proceedings of IEEE GLOBECOM Workshop,Washington,IX,USA,2007:1～6

15 Houidi I,Louati W,Zeghlache D.A distributed virtual network mapping algorithm.Proceedings of IEEE ICC,Beijing,China,2008:5634～5640

16 He J,Zhang S R,Li Y,et al.Davinci:dynamically adaptive virtual networks for a customized intemet.Proceedings of the ACM CoNEXT Conference,Madrid,Spain,2008:1～12

17 Cheng X,Su S,Zhang Z,et al.Virtual network embedding through topology-aware node ranking.ACM SIGCOMM Computer Communication Review,2011,41(2):39～47

18 Guo C X,Lu G H,Wang H J,et al.SecondNet:a data center network virtualization architecture with bandwidth guarantees.ACM CoNEXT 2010,Philadelphia,USA,2010

19 Vu H T,Hwang S.A traffic and power-aware algorithm for virtual machine placement in cloud data center.International Journal of Grid and Distributed Computing,2014,7(1):21～32

20 Beloglazov A,Buyya R.Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers.Concurrency and Computation:Practice and experience,2012(24):1397～1420

21 Beloglazov A,Abawajy J,Buyya R.Energy-aware resource allocation heuristics for efficient management of datacenters for cloud computing.Future Generation Computer Systems,2011

22 Yu M L,Yi Y,Rexford J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration.ACM SIGCOMM Computer Communication Review,2008,38(2)

23 Ricci R,Alfeld C,Lepreau J.A solver for the network testbed mapping problem.ACMSIGCOMMComputerCommunicationsReview,2003

24 樊勇兵,丁圣勇,陳楠.基于業(yè)務(wù)交換機的大規(guī)模云數(shù)據(jù)中心通用網(wǎng)絡(luò)架構(gòu).電信科學(xué),2013,29(10):1～4 Fan Y B,Ding S Y,Chen N.A general network architecture design of large-scale cloud data center based on service switch.Telecommunications Science,2013,29(10):1～4

25 Jain S,Kumar A,Mandal S,et al.B4:experience with a clobally-deployed software defined WAN.Proceedings of SIGCOMM’13,Hong Kong,China,2013