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

（1.中國(guó)電信股份有限公司廣州研究院 廣州 510630；2.浪潮集團(tuán)有限公司 濟(jì)南 250101）

1 虛擬機(jī)放置問題的來(lái)源

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

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

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

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

2 VMP問題分析

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

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

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

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

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

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

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

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

3 VMP算法概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 監(jiān)控和計(jì)量

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3.3 資源池的資源均衡性

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

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

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

其次是QoS功能，它同樣可以有效卸載算法復(fù)雜性，并提供增值服務(wù)。云IDC網(wǎng)絡(luò)在數(shù)學(xué)模型上是一個(gè)比骨干互聯(lián)網(wǎng)復(fù)雜得多的網(wǎng)絡(luò)，如果連后者都從來(lái)沒有大規(guī)模成功部署過細(xì)顆粒度、多目標(biāo)、逐跳預(yù)留的流量工程，那在設(shè)計(jì)云IDC的VMP算法時(shí)更應(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ì)不同，并且云資源池大多歸屬于單一管理實(shí)體，這為相關(guān)的創(chuàng)新提供了廣闊空間。例如，參考文獻(xiàn)[18]提出的基于VMM的源路由，在公共互聯(lián)網(wǎng)上就很難實(shí)現(xiàn)，因?yàn)榫W(wǎng)絡(luò)運(yùn)營(yíng)商不能控制通信終端，所以路由不能由終端決定，只能由網(wǎng)絡(luò)決定；Google提出的B4網(wǎng)絡(luò)[25]是云IDC網(wǎng)絡(luò)整體架構(gòu)上的創(chuàng)新，這種短時(shí)間內(nèi)整體架構(gòu)的創(chuàng)新在公共互聯(lián)網(wǎng)上是難以想象的，而其技術(shù)上的成功又是因?yàn)樵摷軜?gòu)與Google新型業(yè)務(wù)模型的高度適配。

6 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)

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)化計(jì)算方法.北京:清華大學(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é)報(bào),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ù)交換機(jī)的大規(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