文學(xué)敏　韓言妮　于　冰　孫建朋　徐　震

1(信息安全國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院信息工程研究所)　北京　100093)2(山東大學(xué)信息科學(xué)與工程學(xué)院　濟(jì)南　250100)(wenxuemin@iie.ac.cn)

軟件定義數(shù)據(jù)中心內(nèi)一種基于拓?fù)涓兄腣DC映射算法

文學(xué)敏1韓言妮1于冰1孫建朋2徐震1

1(信息安全國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院信息工程研究所)北京100093)2(山東大學(xué)信息科學(xué)與工程學(xué)院濟(jì)南250100)(wenxuemin@iie.ac.cn)

摘要在云計(jì)算中，服務(wù)提供商(service provider, SP)可以向基礎(chǔ)設(shè)施提供商(infrastructure provider, InP)按需租賃資源并部署服務(wù).SP只需專注于自己的服務(wù)即可，無需考慮設(shè)備成本與維護(hù)代價(jià).然而傳統(tǒng)InP僅以虛擬機(jī)的方式提供資源，并不保證網(wǎng)絡(luò)性能與帶寬隔離.隨著網(wǎng)絡(luò)虛擬化技術(shù)的發(fā)展，尤其是軟件定義網(wǎng)絡(luò)(software defined networking, SDN)概念的提出，一些研究人員建議InP以虛擬數(shù)據(jù)中心(virtual data center, VDC)的方式為SP提供資源，以解決傳統(tǒng)數(shù)據(jù)中心的上述問題.盡管以VDC的方式分配資源具有諸多的優(yōu)勢，也帶來了一項(xiàng)新的挑戰(zhàn)，如何滿足SP的多樣化需求，以最小的代價(jià)、最大的收益為VDC分配資源，這是一個(gè)NP-hard問題.為解決VDC映射問題，提出了一種基于拓?fù)鋭莺湍K度的啟發(fā)式映射算法，折衷租戶的可靠性需求與映射代價(jià)，并提高InP收益.最后，基于收益代價(jià)比門限經(jīng)驗(yàn)值，提出一種動(dòng)態(tài)監(jiān)控策略，選擇高收益代價(jià)比的VDC請求，進(jìn)一步最大化InP的利潤.大量的仿真實(shí)驗(yàn)證明該算法可以以最小的代價(jià)接受更多的請求，同時(shí)提高InP收益.

關(guān)鍵詞云計(jì)算；數(shù)據(jù)中心；軟件定義網(wǎng)絡(luò)；網(wǎng)絡(luò)虛擬化；VDC映射

隨著科學(xué)、商業(yè)等各方面的信息化水平不斷提升，各行各業(yè)與互聯(lián)網(wǎng)產(chǎn)業(yè)不斷碰撞與融合.在“互聯(lián)網(wǎng)+”的不斷發(fā)展進(jìn)程中，信息化社會所產(chǎn)生的數(shù)據(jù)也日益龐大.在人們對數(shù)據(jù)的存儲、計(jì)算、傳輸提出更高需求的背景下，云計(jì)算作為一種變革式的計(jì)算模型被提了出來.作為下一代計(jì)算模式，云計(jì)算將成為“互聯(lián)網(wǎng)+”社會的信息中樞，它允許用戶按需付費(fèi)，隨時(shí)隨地使用遠(yuǎn)程的計(jì)算、網(wǎng)絡(luò)、存儲資源.在云計(jì)算中，基礎(chǔ)設(shè)施提供者(infrastructure provider, InP)將基礎(chǔ)網(wǎng)絡(luò)設(shè)施資源抽象化為池.服務(wù)提供者(service provider, SP)向InP租賃一定的資源就可以部署自己的服務(wù)或計(jì)算任務(wù).InP可以實(shí)現(xiàn)統(tǒng)一的資源管理與調(diào)度，提高物理資源的利用率與收益；SP只需專注于業(yè)務(wù)邏輯，無需投入大量基礎(chǔ)設(shè)施成本以及維護(hù)知識和代價(jià).作為一種高效的計(jì)算模型，云計(jì)算吸引著越來越多的企業(yè)和科研機(jī)構(gòu)的關(guān)注.

然而，當(dāng)前的InP，比如亞馬遜EC2，主要以虛擬機(jī)(VM)的形式為用戶提供資源，并不提供網(wǎng)絡(luò)隔離和帶寬保障.建立在TCPIP協(xié)議棧之上的網(wǎng)絡(luò)僅提供盡力而為的服務(wù)模式.這種傳統(tǒng)服務(wù)模式在網(wǎng)絡(luò)隔離、安全、網(wǎng)絡(luò)性能保障、自動(dòng)化管理等諸多方面存在著問題[1].為了解決傳統(tǒng)數(shù)據(jù)中心的這些問題，研究人員建議InP以虛擬數(shù)據(jù)中心(virtual data center, VDC)的形式為租戶分配資源[1-2].所謂虛擬數(shù)據(jù)中心是指建立在物理網(wǎng)絡(luò)切片上的虛擬資源集合，包括虛擬機(jī)、虛擬交換機(jī)、虛擬路由以及連接它們的虛擬鏈路[2].相比于傳統(tǒng)僅提供VM的方式，以VDC的方式分配資源可以做到網(wǎng)絡(luò)隔離和帶寬保障.

VDC的實(shí)現(xiàn)依賴于網(wǎng)絡(luò)虛擬化技術(shù).與發(fā)展快速且成熟的主機(jī)虛擬化技術(shù)相比，網(wǎng)絡(luò)虛擬化發(fā)展相對滯后.軟件定義網(wǎng)絡(luò)(software defined networking, SDN)概念的出現(xiàn)和發(fā)展，加速了網(wǎng)絡(luò)虛擬化的進(jìn)程.簡單來說，SDN將控制平面從數(shù)據(jù)轉(zhuǎn)發(fā)平面分離出來，可以通過控制器來協(xié)同轉(zhuǎn)發(fā)組件的行為、獲取流量統(tǒng)計(jì)數(shù)據(jù)以及監(jiān)控拓?fù)渥兓痆3].SDN具有集中式控制、全網(wǎng)信息獲取和網(wǎng)絡(luò)功能虛擬化等特性，利用這些特性可以有效解決數(shù)據(jù)中心出現(xiàn)的各種問題[4].當(dāng)前數(shù)據(jù)中心內(nèi)SDN應(yīng)用的部署得到極大的發(fā)展，其中性能和節(jié)能是重點(diǎn)考慮的2個(gè)方面[4-5].基于SDN的網(wǎng)絡(luò)虛擬化技術(shù)可以有效方便地在數(shù)據(jù)中心物理網(wǎng)絡(luò)之上建立VDC，可以幫助InP以VDC的形式出租資源，并為多租戶之間提供網(wǎng)絡(luò)隔離與帶寬保障.由于多個(gè)VDC在邏輯上是分離的，SP可以完全控制自己所租賃的VDC，比如引入自定義的網(wǎng)絡(luò)協(xié)議或流量策略.

盡管以VDC的形式提供資源可以解決數(shù)據(jù)中心中的性能、安全等問題，但同時(shí)也帶來了一項(xiàng)新的挑戰(zhàn)，這就是VDC映射問題.所謂VDC映射問題，是指在數(shù)據(jù)中心內(nèi)如何靈活、高效地為VDC請求分配合適的物理資源.一個(gè)優(yōu)秀的VDC映射算法可以幫助InP達(dá)到多種優(yōu)化目標(biāo)，比如最大化資源利用率、最大化收益、最小化維護(hù)代價(jià).VDC映射問題雖然與被廣泛研究的虛擬網(wǎng)(VN)映射問題[6]很相似，但還是存在著一些區(qū)別:1)VN映射問題主要面向于廣域網(wǎng)，而VDC映射問題主要面向于數(shù)據(jù)中心內(nèi)的資源分配；2)VN中的節(jié)點(diǎn)考慮的是廣域網(wǎng)中的轉(zhuǎn)發(fā)設(shè)備，而在VDC中可以包含多種節(jié)點(diǎn)，比如主機(jī)、路由、交換機(jī)、存儲節(jié)點(diǎn)等[1]；3)對同一個(gè)請求，VN映射問題中一個(gè)物理節(jié)點(diǎn)只能映射一個(gè)虛擬節(jié)點(diǎn)[6]，然而在云計(jì)算環(huán)境中同一VDC的多臺VM可以分配到一臺物理主機(jī)中.

本文主要探討了軟件定義數(shù)據(jù)中心中的VDC映射問題.主要貢獻(xiàn)如下：1)提出了基于SDN的數(shù)據(jù)中心資源管理框架；2)對VDC映射問題進(jìn)行了建模，并分析了VDC映射過程中影響InP收益的因素；3)考慮多種資源需求(CPU、內(nèi)存、帶寬)以及VDC可靠性需求，提出了一種新的資源分配算法；4)通過大量的仿真實(shí)驗(yàn)驗(yàn)證該算法能夠以較低的代價(jià)獲取較高的收益，最后提出基于一種動(dòng)態(tài)監(jiān)控策略選擇高收益代價(jià)比的VDC請求，進(jìn)一步優(yōu)化算法.

1問題描述

1.1VDC映射問題與數(shù)據(jù)中心資源管理框架

InP擁有物理基礎(chǔ)設(shè)施，通過向SP出租資源獲取收益.SP需要一定的基礎(chǔ)設(shè)施部署自己的服務(wù)或任務(wù).為了節(jié)約設(shè)備成本和維護(hù)代價(jià)，SP可以向InP以VDC的形式租賃資源.首先，當(dāng)SP需要租賃資源時(shí)，它需要向InP提交VDC請求說明，包括VDC的拓?fù)洹⒚總€(gè)虛擬節(jié)點(diǎn)的vCPU數(shù)量和內(nèi)存需求量、每條虛擬鏈路的最小帶寬.InP收到請求后，根據(jù)底層網(wǎng)絡(luò)的狀態(tài)，為VDC分配滿足需求的物理資源.InP會在不同的時(shí)間收到來自不同SP的不同VDC請求.但I(xiàn)nP無法預(yù)知VDC請求的到達(dá)時(shí)間，也無法預(yù)知VDC請求的具體內(nèi)容.所以，本文所考慮的VDC映射問題是一個(gè)在線映射問題.

InP可以在底層網(wǎng)絡(luò)之上建立多個(gè)網(wǎng)絡(luò)切片，并為不同網(wǎng)絡(luò)切片提供隔離.每個(gè)網(wǎng)絡(luò)切片擁有自己的IP地址空間，互不干涉.從SP的角度看，它可以像控制真實(shí)網(wǎng)絡(luò)一樣控制自己的網(wǎng)絡(luò)切片，底層網(wǎng)絡(luò)對它來說是透明的.SP不僅僅可以直接使用虛擬網(wǎng)絡(luò)切片，它也可以通過自己的SDN控制器來控制虛擬網(wǎng)絡(luò)的轉(zhuǎn)發(fā)行為.本文提出了一個(gè)基于SDN的數(shù)據(jù)中心資源管理框架，如圖1所示.類似于傳統(tǒng)的主機(jī)操作系統(tǒng)，框架分為5層：基礎(chǔ)物理網(wǎng)絡(luò)設(shè)施、控制接口層、網(wǎng)絡(luò)操作系統(tǒng)(NOS)、系統(tǒng)控制層和用戶控制層.下面分別介紹各層的功能特點(diǎn)：

1) 基礎(chǔ)物理網(wǎng)絡(luò)設(shè)施.該層是InP所擁有的底層網(wǎng)絡(luò)設(shè)施.本文主要考慮的是單個(gè)數(shù)據(jù)中心網(wǎng)絡(luò)，而實(shí)際中既可以是單個(gè)數(shù)據(jù)中心，也可以是通過骨干網(wǎng)互聯(lián)的多個(gè)數(shù)據(jù)中心.

2) 控制接口層.該層主要由SDN控制接口和主機(jī)控制接口組成，為上層網(wǎng)絡(luò)操作系統(tǒng)提供接口.SDN控制接口可以控制物理交換機(jī)和虛擬交換機(jī)的轉(zhuǎn)發(fā)行為、查詢交換機(jī)中的流表信息、統(tǒng)計(jì)信息以及監(jiān)控物理網(wǎng)絡(luò)拓?fù)渥兓?主機(jī)控制接口可以控制虛擬機(jī)的創(chuàng)建、刪除、修改和遷移、查詢物理主機(jī)、虛擬機(jī)的使用狀態(tài)和統(tǒng)計(jì)數(shù)據(jù).

Fig. 1　The framework of resource management in SDN-enabled datacenter.圖1　基于SDN的數(shù)據(jù)中心資源管理框架

3) 網(wǎng)絡(luò)操作系統(tǒng)(NOS).①NOS通過控制層的北向接口，對底層物理資源進(jìn)行統(tǒng)一的管理和調(diào)度，可以利用SDN控制器下發(fā)流表策略，利用Server控制器操作物理主機(jī)和虛擬機(jī)；②NOS內(nèi)部會維護(hù)底層網(wǎng)絡(luò)的全局拓?fù)湟晥D以及各個(gè)節(jié)點(diǎn)和鏈路的分配、使用狀態(tài)；③NOS抽象化底層物理資源的使用方式，為上層應(yīng)用程序(系統(tǒng)控制程序和用戶控制程序)提供統(tǒng)一的接口，并且為不同的應(yīng)用程序提供隔離并分配權(quán)限；④NOS負(fù)責(zé)事件的分發(fā)：當(dāng)NOS收到底層網(wǎng)絡(luò)產(chǎn)生的事件時(shí)，它會根據(jù)事件的源、類型、優(yōu)先級(系統(tǒng)級或用戶級)以及訂閱者信息，將事件分發(fā)給相應(yīng)的應(yīng)用程序.

4) 系統(tǒng)控制層.系統(tǒng)控制層包含運(yùn)行在NOS之上協(xié)助InP實(shí)現(xiàn)數(shù)據(jù)中心自動(dòng)化管理的應(yīng)用程序，比如路由程序、VDC映射程序、資源監(jiān)控程序等.

5) 用戶控制層.對SP來說，它只能看到自己所擁有的VDC，并且可以像使用真實(shí)的SDN網(wǎng)絡(luò)一樣來控制它，底層物理網(wǎng)絡(luò)對SP來說是透明的.SP可以通過自己的控制器vSDN對自己的VDC進(jìn)行完全控制.舉例來說，SP在VDC上部署了一個(gè)Web服務(wù)，其中有面向Web用戶的即時(shí)流量，也有數(shù)據(jù)庫節(jié)點(diǎn)之間的備份流量.為了能給用戶提供更優(yōu)質(zhì)的服務(wù)，SP可以為不同流量定義不同的優(yōu)先級：面向用戶的高優(yōu)先級流量、后端數(shù)據(jù)庫的低優(yōu)先級備份流量.SP可以通過vSDN控制器將優(yōu)先級轉(zhuǎn)發(fā)策略發(fā)送給NOS，NOS將該策略轉(zhuǎn)化為合法流表項(xiàng)下發(fā)到底層交換機(jī)中.SP僅有操作自己擁有的VDC的權(quán)限，沒有操作其他VDC和物理資源的權(quán)限.

1.2資源利用率與可靠性

VDC映射問題不僅可以幫助InP實(shí)現(xiàn)數(shù)據(jù)中心的自動(dòng)化管理和資源的靈活分配，而且可以達(dá)到多方面的目標(biāo)，比如提高資源利用率、提高VDC請求的接受率、最大化收益.但是目前為止，考慮VDC的可靠性問題，折衷可靠性需求與映射代價(jià)進(jìn)行資源映射問題卻沒有被很好地解決.VDC的可靠性在云計(jì)算環(huán)境中是一個(gè)非常重要的問題.對SP來說，服務(wù)的中斷，雖然只有幾秒，可能會帶來巨大的損失，嚴(yán)重影響SP的聲譽(yù)[7].同時(shí)，由于服務(wù)不可達(dá)，InP也需要向SP賠償一定的罰金，比如亞馬遜EC2承諾1個(gè)月內(nèi)服務(wù)的在線率高于99%，但低于99.95%會賠償所付總額的10%[8].

Fig. 2　Different VDC embedding schemes.圖2　不同映射策略的對比

在數(shù)據(jù)中心中，一臺主機(jī)可以放置多臺虛擬機(jī).如果2臺虛擬機(jī)被分配到同一臺物理主機(jī)中，那么就無需為它們之間的虛擬鏈路分配資源；如果2臺虛擬機(jī)被分配到了不同的物理主機(jī)中，那么就需要為它們之間的虛擬鏈路分配物理鏈路資源.圖2(a)表示一個(gè)VDC請求，其中?～?代表虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)之間的實(shí)線表示虛擬鏈路，實(shí)線上的數(shù)字表示虛擬鏈路的帶寬需求。圖2(b)(c)表示2種映射方案，其中數(shù)字表示虛擬鏈路所占用的帶寬.為了提高映射后VDC的可靠性，VDC中的虛擬機(jī)應(yīng)該分散到多個(gè)故障域，如圖2(b)所示.但這種情況下，VDC會占用更多的鏈路資源，資源利用率較低.另一方面，如果為了提高資源利用率，VDC中的虛擬機(jī)應(yīng)該盡量放置在一臺物理主機(jī)或者一臺機(jī)架內(nèi).圖2(c)的VDC映射方案占用較少的鏈路資源，具有較高的資源利用率，但如果一臺物理主機(jī)出現(xiàn)故障，就有可能導(dǎo)致大量VM失效.在實(shí)際中，數(shù)據(jù)中心中存在多種類型的故障，比如物理主機(jī)故障、ToR(top of rack)交換機(jī)故障、電力故障等.本文只考慮物理主機(jī)故障.

目前已經(jīng)有大量針對VN映射問題的研究.文獻(xiàn)[9]采用了一種top-k支配模型，通過平衡多種資源因素對節(jié)點(diǎn)排序.NodeRank[10]同時(shí)考慮節(jié)點(diǎn)資源容量、鏈路帶寬容量以及VN的拓?fù)鋵?jié)點(diǎn)排序，實(shí)現(xiàn)拓?fù)涓兄墓?jié)點(diǎn)映射.然而，只有少量針對虛擬數(shù)據(jù)中心映射問題的研究.Zhani等人[11]提出了VDC planner的映射框架，可以通過虛擬節(jié)點(diǎn)的遷移提高VDC的接受率，但它并沒有考慮VDC的可靠性問題.SecondNet[12]采用一種貪心算法映射VDC，但它限制了一臺物理主機(jī)最多只能映射一個(gè)VM.Greenhead[2]研究了分布在不同地理位置的多數(shù)據(jù)中心中的VDC映射問題，它根據(jù)VDC拓?fù)湟约癡M的位置限制條件將VDC劃分為多個(gè)組，使用貪心算法將各個(gè)組分配到不同數(shù)據(jù)中心中.

2問題建模

2.1網(wǎng)絡(luò)建模

本文中，我們將底層數(shù)據(jù)中心網(wǎng)絡(luò)通過無向圖G(N∪X,E)表示，其中N表示數(shù)據(jù)中心中的主機(jī)集合，X表示數(shù)據(jù)中心中的交換機(jī)集合，E表示物理節(jié)點(diǎn)(主機(jī)和交換機(jī))之間的鏈路集合.每臺主機(jī)都包含一系列的資源屬性(比如CPU、內(nèi)存等)，本文使用A={ai,a2,…,ak}表示，其中ai表示主機(jī)的第i種屬性.ci(n,t)表示在時(shí)刻t主機(jī)n(n∈N)中資源ai(0

對VDC請求j，本文使用無向圖Gj(Nj,Ej)表示.我們用tj表示它的到達(dá)時(shí)間，用Tj表示它在數(shù)據(jù)中心內(nèi)的生命時(shí)長，用rj表示VDC的可靠性需求.在只考慮主機(jī)故障的情況下，VDC的可靠性定義為在最壞情況下的VM的存活率或可達(dá)率.VDCj映射后的實(shí)際可靠性應(yīng)該不小于rj，具體為

(1)

其中,Pj(n)表示VDCj分配到主機(jī)n中的VM數(shù)量.根據(jù)式(1)，對于VDCj，一臺主機(jī)上允許放置的最大VM數(shù)目K可以計(jì)算為

(2)

2.2VDC映射過程

為了方便問題描述，本文定義了3個(gè)二元決策變量xj,yi(n′,n)和zj(e′,l).xj表示VDCj是否被接受：

(3)

yi(n′,n)表示VDCj中的VMn′(n′∈Nj)是否被分配到物理主機(jī)n(n∈N)中：

(4)

zj(e′,l)表示VDCj中的虛擬鏈路e′(e′∈Ej)是否被分配到物理路徑l中(l∈P，P表示數(shù)據(jù)中心內(nèi)的所有無向無環(huán)路徑)：

(5)

在給出映射過程需要滿足的限制條件之前，為了方便描述，本文使用πj(t)表示VDCj在時(shí)刻t是否有效：

(6)

1) 如果VDCj被拒絕，即xj=0，那么對任意VM和虛擬鏈路來說，yi(n′,n)和zj(e′,l)只能為0：

(7)

2) 主機(jī)資源和鏈路帶寬的容量限制條件：

(8)

(9)

其中δe,l表示物理鏈路e是否為物理路徑l的一部分.

3) 保證被接受VDC的所有元素都被映射：

(10)

(11)

4) 滿足可靠性需求：

(12)

5) 端點(diǎn)條件.如果虛擬鏈路e′被分配到物理路徑l中，那么e′的2個(gè)端點(diǎn)應(yīng)該分別分配到l的2個(gè)端點(diǎn)上.如果用u(·)和v(·)表示一條鏈路或路徑的2個(gè)端點(diǎn)，那么需要滿足條件：

(13)

2.3收益模型

對每個(gè)被接受的VDC請求，SP根據(jù)服務(wù)需求按照使用時(shí)間長短付費(fèi)，而單位時(shí)間的價(jià)格由VDC所請求的資源量決定，定義如下：

(14)

(15)

將式(6)代入式(15)中：

(16)

R(t)可以表示時(shí)刻0～t已接受的VDC在它們生命時(shí)長到達(dá)后所產(chǎn)生的總收益減去當(dāng)前存活的VDC還可以再產(chǎn)生的收益.

2.4目標(biāo)函數(shù)

本文的目標(biāo)是幫助InP提高長期的單位時(shí)間平均收益，其定義如下：

(17)

可以看出這個(gè)優(yōu)化函數(shù)是一個(gè)非線性整數(shù)優(yōu)化問題，該NP-hard問題的求解空間龐大，因此本文將提出一種啟發(fā)式映射算法，最大化InP收益.

影響長期單位時(shí)間平均收益的因素主要有2個(gè)：VDC接受率和收益代價(jià)比.VDC接受率是指一段時(shí)間內(nèi)InP接受的VDC請求數(shù)目占收到VDC請求的總數(shù)目的比例.一般來說，VDC接受率越高，InP就能獲得更高的收益.收益代價(jià)比是指VDC請求的資源量與VDC實(shí)際占用資源量的比值，反映了物理資源的利用率.低收益代價(jià)比的VDC表示VDC占用了更多的物理鏈路資源，使物理網(wǎng)絡(luò)產(chǎn)生更多的碎片資源.這會進(jìn)一步影響后續(xù)VDC的收益代價(jià)比，降低InP的接受率.

3基于拓?fù)鋭莸腣DC映射算法

為了滿足VDC需求，以最小代價(jià)為VDC分配資源，提高算法的VDC接受率和收益，本文提出一種啟發(fā)式算法解決VDC的映射問題.算法的理論基礎(chǔ)是利用拓?fù)鋭輥碓u價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，在考慮VDC可靠性需求的基礎(chǔ)上對虛擬機(jī)節(jié)點(diǎn)聚類，盡量將節(jié)點(diǎn)間流量較多的VM映射到相同的主機(jī)上，節(jié)點(diǎn)間流量較少的VM分散到不同的主機(jī)上.由于算法利用拓?fù)鋭輰?shí)現(xiàn)節(jié)點(diǎn)映射(nodes mapping based on topological potential)，因此我們將本文的算法命名為NMP.本節(jié)首先介紹拓?fù)鋭莸暮x以及計(jì)算方法，然后詳細(xì)描述本文的算法設(shè)計(jì).

3.1拓?fù)鋭?/p>

在物理學(xué)中，“勢場”可以描述沒有直接接觸的節(jié)點(diǎn)之間所產(chǎn)生的相互作用，比如電磁場和重力場.拓?fù)鋭輀13]就是受此啟發(fā)，將類似的方法應(yīng)用到網(wǎng)絡(luò)中，評價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)渲匾?在網(wǎng)絡(luò)中，我們定義2個(gè)節(jié)點(diǎn)之間的相互作用與它們的資源容量和它們之間的距離有關(guān).本文使用高斯函數(shù)的形式描述2個(gè)節(jié)點(diǎn)的相互作用.一個(gè)節(jié)點(diǎn)的拓?fù)鋭莸扔诰W(wǎng)絡(luò)中所有節(jié)點(diǎn)對它作用的疊加，節(jié)點(diǎn)n的拓?fù)鋭萃ㄟ^以下方式計(jì)算：

(18)

選擇一個(gè)合適的σ對拓?fù)鋭輥碚f十分重要.如果σ太大，每個(gè)節(jié)點(diǎn)的影響范圍就很大，那么網(wǎng)絡(luò)中所有節(jié)點(diǎn)的拓?fù)鋭菥蜁浅＝咏y以區(qū)別節(jié)點(diǎn)的重要性；相反，如果σ太小，一個(gè)節(jié)點(diǎn)的拓?fù)鋭葜挥勺陨淼馁Y源容量決定，鄰居節(jié)點(diǎn)的影響近乎消失.根據(jù)信息熵的理論，如果所有節(jié)點(diǎn)的拓?fù)鋭輲缀跻粯?，那么所提供的信息量就最小，拓?fù)鋭莸撵刈畲?因此我們可以通過計(jì)算拓?fù)鋭莸淖钚§孬@取合適的影響因子σ.拓?fù)鋭莸撵赜?jì)算為

(19)

3.2算法設(shè)計(jì)

在本節(jié)中，我們會詳細(xì)描述NMP算法的具體細(xì)節(jié).NMP算法的主要思想是采用一種迭代的方式，每次搜索一簇VM節(jié)點(diǎn)，使簇內(nèi)VM相互之間具有更密集的鏈路帶寬，在滿足VDC可靠性需求的條件上，將這簇VM集合映射到一臺主機(jī)中.這可以有效地減少虛擬鏈路占用的資源.算法的具體步驟如下：

步驟1. 根據(jù)VDC的可靠性需求，計(jì)算單臺物理主機(jī)所允許的最大VM數(shù)量K.

步驟2. 通過虛擬機(jī)節(jié)點(diǎn)聚類的方式搜索一簇VM節(jié)點(diǎn).首先選擇拓?fù)鋭葑畲蟮腣M節(jié)點(diǎn)作為簇心.由式(18)對拓?fù)鋭莸亩x可知，網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)鋭莸拇笮∮稍摴?jié)點(diǎn)與其鄰居節(jié)點(diǎn)共同決定，反映了一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性.拓?fù)鋭葑畲蟮墓?jié)點(diǎn)可以作為簇心實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)聚類，所以在每次迭代過程中使用未分配的VM集合中拓?fù)鋭葑畲蟮墓?jié)點(diǎn)作為簇心搜索VM簇.

步驟3. 從未分配的VM集合中選擇可以使網(wǎng)絡(luò)模塊度最大化的VM，加入到VM簇中，重復(fù)執(zhí)行直到VM簇的大小到達(dá)K.模塊度可以評價(jià)網(wǎng)絡(luò)社區(qū)劃分結(jié)果的好壞.模塊度將社區(qū)內(nèi)鏈路密度與社區(qū)間鏈路密度做比較.一個(gè)優(yōu)秀的社區(qū)劃分結(jié)果在社區(qū)內(nèi)相比于社區(qū)之間具有更緊密的鏈路，所以本文利用模塊度來選擇VM加入到VM簇，以使簇內(nèi)具有更高的鏈路密度.有關(guān)模塊度的計(jì)算以及虛擬機(jī)節(jié)點(diǎn)聚類的方法將在3.2.2節(jié)詳述.

步驟4. 為了映射當(dāng)前搜索到的VM簇，需要選擇一臺物理主機(jī).為了減少VDC請求所占用的鏈路資源，本文提出了2種主機(jī)選擇方法：1)主機(jī)的選擇限定在一簇物理主機(jī)集合中，而不是數(shù)據(jù)中心內(nèi)的所有主機(jī).本文通過網(wǎng)絡(luò)節(jié)點(diǎn)聚類，搜索一簇相鄰且剩余資源容量較高的物理主機(jī)集合.2)根據(jù)主機(jī)的剩余資源容量與到已映射VM的距離對所有主機(jī)評分，選擇評分最高的主機(jī).具體的主機(jī)選擇算法在3.2.2節(jié)描述.

步驟5. 如果選擇的主機(jī)不滿足當(dāng)前VM簇的需求，則需要減小當(dāng)前VM簇的大小.本文以添加到VM簇的相反順序刪除VM，直到VM簇可以被映射到主機(jī)中.

步驟6. 如果仍有未映射的VM，回到步驟2重復(fù)執(zhí)行.

下面的算法1給出了NMP算法的具體步驟.

算法1. NMP算法的具體步驟.

輸入：G(N∪X,E)，Gj(Nj∪Xj,Ej)；

輸出：是否映射成功.

符號說明：U表示未映射的VM集合，C表示當(dāng)前VM簇集合.

①U←Nj;

②C←?;

③ 根據(jù)可靠性需求計(jì)算K；

④ 計(jì)算U中所有VM的拓?fù)鋭荩?/p>

⑤ whileU≠? do

⑥v←U中拓?fù)鋭葑畲蟮腣M;

⑦C←{v};

⑧stack←[v];

⑨ fori←0 toK-1 do

⑩ 計(jì)算UC中所有VM對應(yīng)的模塊度增量ΔQ;

且stack≠? do

NMP算法包含2個(gè)最關(guān)鍵的步驟：虛擬機(jī)節(jié)點(diǎn)聚類和物理主機(jī)的選擇.接下來本文對這2部分進(jìn)行詳盡的描述.

3.2.1虛擬機(jī)節(jié)點(diǎn)聚類

在網(wǎng)絡(luò)中，拓?fù)鋭葑畲蟮墓?jié)點(diǎn)可以說明以這個(gè)節(jié)點(diǎn)為中心的范圍內(nèi)擁有更多的資源，所以本文將拓?fù)鋭葑畲蟮墓?jié)點(diǎn)作為搜索VM簇的核心.模塊度用來評價(jià)網(wǎng)絡(luò)社區(qū)劃分算法的結(jié)果.模塊度的定義為[14]

(20)

(21)

這表示模塊度等于社區(qū)內(nèi)鏈路所占比例減去隨機(jī)情況下社區(qū)內(nèi)鏈路所占比例.

在算法1中，每次迭代過程利用拓?fù)鋭葑畲蟮腣M節(jié)點(diǎn)作為核心搜索一簇VM集合.最開始，C中只有核心VM節(jié)點(diǎn)；接下來，從UC中選擇一個(gè)VM加入到C中并可以最大化網(wǎng)絡(luò)整體模塊度，重復(fù)添加VM直到C的大小達(dá)到K.為了提高算法的效率，本文只計(jì)算將一臺VM從集合U中移到C中的模塊度增量ΔQ.如果將一個(gè)節(jié)點(diǎn)v從類簇j中移到類簇i中，ΔQ可以計(jì)算為

(22)

3.2.2物理主機(jī)選擇方法

搜索到一簇VM節(jié)點(diǎn)后，我們需要選擇一臺物理主機(jī)來映射VM簇.為了減少簇間虛擬鏈路的跳數(shù)，選擇物理主機(jī)時(shí)應(yīng)該同時(shí)考慮主機(jī)的剩余資源容量以及到已映射VM的距離.本文提出了2種選擇物理的方法：1)通過節(jié)點(diǎn)聚類(clustering)的方法將VDC的映射限定在一簇資源容量較多的主機(jī)集合中，本文將這種方法命名為NMPC；2)根據(jù)主機(jī)的拓?fù)鋭莺偷揭延成銿M的距離(distance)對主機(jī)進(jìn)行評分，并選擇評分最高的主機(jī)，這種方法被命名為NMPD.下面詳細(xì)說明這2種方法：

1) NMPC.為了方便描述，我們用CS表示正在搜索的一簇候選主機(jī)集合.初始時(shí)刻CS=?.首先，計(jì)算所有物理主機(jī)的拓?fù)鋭?；接下來，將拓?fù)鋭葑畲蟮闹鳈C(jī)移入到CS中；然后通過迭代的方式，每次從剩余主機(jī)中選擇與CS中主機(jī)最近且拓?fù)鋭葑畲蟮闹鳈C(jī)，將其移入到CS中，直到CS集合的大小和資源容量足夠映射VDC.當(dāng)每次搜索到一簇VM集合后，選擇CS中拓?fù)鋭葑畲蟮闹鳈C(jī)來映射這簇VM集合.

2) NMPD.與NMPC先搜索一簇候選主機(jī)集合，再從其中選擇主機(jī)的方式不同，NMPD根據(jù)主機(jī)的拓?fù)鋭莺偷揭延成銿M的距離對所有未考慮的主機(jī)進(jìn)行評分，并選擇評分最高的主機(jī).本文通過式(23)計(jì)算每臺物理主機(jī)的評分.

(23)

其中,tpn表示物理主機(jī)n的拓?fù)鋭?，us表示已映射的VM所在的物理主機(jī)集合，dn n′表示2臺物理主機(jī)的距離，λ是主機(jī)拓?fù)鋭莺偷揭堰x擇主機(jī)平均距離的平衡因子.被評價(jià)的主機(jī)拓?fù)鋭菰酱?，到已選擇主機(jī)的平均距離越近，評分越高.

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

4.1仿真環(huán)境

我們基于Python開發(fā)了一個(gè)離散事件仿真器來模擬數(shù)據(jù)中心中的VDC映射過程.數(shù)據(jù)中心網(wǎng)絡(luò)采用6端口的FatTree拓?fù)洌?5個(gè)交換機(jī)、54臺物理主機(jī).每臺主機(jī)包含16個(gè)vCPU和8 096 MB內(nèi)存,交換機(jī)的每個(gè)端口的帶寬容量為1 000 Mbps.VDC請求使用BRITE[15]拓?fù)渖善魃?VDC請求的VM數(shù)量均勻分布在10～50之間，每臺VM請求的vCPU均勻分布在1～4之間，內(nèi)存容量均勻分布在512～2 048 MB，每條虛擬鏈路請求的帶寬容量均勻分布在100～200 Mbps.VDC請求的到達(dá)服從均值為0.03的泊松分布，VDC的生命時(shí)長服從均值為500單位時(shí)間的指數(shù)分布.本文選擇基于節(jié)點(diǎn)排序的NodeRank[10]作為對比算法，并擴(kuò)展到VDC場景，允許一臺物理主機(jī)可以映射VDC的多個(gè)VM，并滿足可靠性需求，該對比算法在后文中均以Baseline標(biāo)記.

4.2評價(jià)指標(biāo)

本文的主要目標(biāo)是提高InP的長期單位時(shí)間平均收益.影響單位時(shí)間平均收益的因素主要有2個(gè)：接受率和收益代價(jià)比.除了接受率、收益代價(jià)比外，本文還提出了核心鏈路利用率的指標(biāo)來比較各種算法的性能.下面對各種評價(jià)指標(biāo)進(jìn)行詳細(xì)說明.

1) 接受率.時(shí)刻t的接受率定義為在時(shí)刻t被接受的VDC數(shù)目占收到的VDC請求總數(shù)的比例：

(24)

其中,|·|表示集合中的元素?cái)?shù)目.只有接受率并不能完全反映算法的性能.如果一種算法只接受小規(guī)模請求、拒絕大請求，可能會產(chǎn)生較高的接受率，收益反而會減小.這是因?yàn)榻邮苈适怯山邮艿腣DC數(shù)目決定的，而收益是由VDC規(guī)模大小和接受的VDC數(shù)目共同決定的.

2) VDC收益代價(jià)比.對VDCj來說，收益代價(jià)比表示VDC的請求資源量與實(shí)際占用資源量的比值：

(25)

其中,代價(jià)Cj由其實(shí)際所占用的資源量決定：

(26)

3) 累積收益代價(jià)比.對數(shù)據(jù)中心來說，數(shù)據(jù)中心在時(shí)刻t的收益代價(jià)比為數(shù)據(jù)中心在時(shí)刻0～t獲得的累積收益與產(chǎn)生的代價(jià)的比值，反映了數(shù)據(jù)中心的資源利用率.具體定義如下：

(27)

低的收益代價(jià)比一般由2方面的因素導(dǎo)致：①不合理的映射算法所導(dǎo)致的資源浪費(fèi)；②數(shù)據(jù)中心內(nèi)剩余資源有限或資源碎片較多.低收益代價(jià)比的VDC會占用更多的鏈路帶寬資源，進(jìn)一步造成更多的資源碎片，這會影響將來VDC的資源分配與收益代價(jià)比，會降低將來時(shí)刻的接受率，最終影響InP的長期收益.

4) 核心鏈路占用率.核心鏈路是指由核心層交換機(jī)所連接的鏈路.核心鏈路不僅承載著數(shù)據(jù)中心內(nèi)日益加劇的東西向流量，也負(fù)責(zé)通往外部的南北向流量.實(shí)際研究[16]發(fā)現(xiàn)核心層交換機(jī)的鏈路負(fù)載相當(dāng)高，這會導(dǎo)致數(shù)據(jù)中心網(wǎng)絡(luò)擁塞甚至丟包.式(28)定義了核心鏈路平均占用率來評價(jià)VDC映射算法的表現(xiàn).

(28)

其中,Ec∈E表示核心鏈路集合，BW(l)表示物理鏈路l的總帶寬容量.

4.3NMPD中平衡因子的選擇

在3.2節(jié)中，NMPD算法同時(shí)考慮主機(jī)的拓?fù)鋭莺偷揭堰x擇主機(jī)的距離，對每臺主機(jī)評分并選擇評分最高的主機(jī).其中，λ表示拓?fù)鋭菖c距離因素之間的平衡因子.λ越大，距離因素影響越小，會導(dǎo)致虛擬鏈路占用更多的帶寬資源；相反，λ越小，距離因素的權(quán)重越大，距離已映射VM稍微遠(yuǎn)一點(diǎn)的主機(jī)就會被忽略掉.圖3反映了接受率隨平衡因子λ的變化關(guān)系.從圖3可以看到,λ太大或太小，接受率都比較小，當(dāng)λ=1.5時(shí)，映射算法的接受率最高.因此接受率隨λ的變化并不是很大：當(dāng)λ從1增加到4，接受率變化范圍只有0.03.本文在NMPD算法中默認(rèn)使用λ=1.5.

Fig. 3　Acceptance ratio with different λ.圖3　接受率隨λ的變化

Fig. 5　Cumulative revenuecost ratio over time and average utilization of core links over time.圖5　累積收益代價(jià)比與核心鏈路平均占用率隨時(shí)間的變化

4.4不同算法的比較

首先，本文將VDC的可靠性需求設(shè)為0.2～0.9，對比了3種算法在不同評價(jià)指標(biāo)下的表現(xiàn).

1) NMPC接受最多的VDC請求.從圖4可以看到，NMPC和NMPD算法具有較高的VDC接受率和收益，而且NMPC的表現(xiàn)優(yōu)于NMPD.這表明NMPC算法可以接受最多的VDC請求，也獲得最高的收益.舉例來說，在20 000單位時(shí)間時(shí)，NMPC和NMPD的VDC接受率分別為0.58和0.55，比Baseline算法的0.46高10%以上.

Fig. 4　Acceptance ratio and revenue over time.圖4　接受率與收益隨時(shí)間的變化

2) NMPD具有最好的資源利用率.盡管NMPC算法可以接受最多的VDC請求，然而它的收益代價(jià)比卻低于NMPD.如圖5(a)所示，大部分時(shí)間NMPD的累計(jì)收益代價(jià)比接近90%，大幅高于NMPC的70%和Baseline算法的60%.這表明NMPD以最小的代價(jià)為VDC分配資源，可以提高數(shù)據(jù)中心的資源利用率.當(dāng)數(shù)據(jù)中心剩余資源有限或者碎片資源較多時(shí)，VDC的映射代價(jià)太高，NMPD會拒絕掉新到的VDC請求；相反，NMPC和Baseline算法由于貪婪的本質(zhì)，盡力映射每一個(gè)請求，這樣導(dǎo)致收益代價(jià)比較低.

3) NMPD核心鏈路占用率最小.圖5(b)顯示大部分時(shí)間NMPD算法的核心鏈路平均占用率要低于另外2種算法;大部分時(shí)間內(nèi)，NMPD算法的核心鏈路平均占用率要比NMPC低20%左右;NMPC算法的核心鏈路平均占用率甚至高于Baseline，這是因?yàn)镹MPC算法比Baseline接受了更多的請求.NMPD算法比Baseline接受了更多的VDC請求，但卻占用了更少的核心鏈路帶寬，這表明了NMPD算法可以達(dá)到較高的資源利用率.

Fig. 6　The influence of reliability requirement.圖6　可靠性需求對算法的影響

4.5可靠性需求與請求到達(dá)率對算法的影響

這節(jié)本文分別對比了不同VDC可靠性需求和不同請求到達(dá)率對算法的影響.

Fig. 7　The influence of VDC arrival rate.圖7　請求到達(dá)率對算法的影響

1) 不同VDC可靠性需求對算法的影響.從圖6可以看到，算法的接受率和VDC平均收益代價(jià)比都會隨著VDC可靠性需求的增加而下降.這是因?yàn)榭煽啃孕枨笤酱?，算法需要將VDC分散到更多的物理主機(jī)中，導(dǎo)致VDC會占用更多的鏈路資源.圖6(a)展示了接受率與可靠性需求的變化關(guān)系，可以看到可靠性需求在0.2～0.7之間時(shí)，NMPC和NMPD的接受率幾乎一致，均比Baseline高10%左右;當(dāng)可靠性需求超過0.7后，NMPD算法的接受率迅速下降，而NMPC在超過0.8后才劇烈下降.這是因?yàn)镹MPD更傾向于拒絕占用資源較多的VDC請求.從圖6(b)可以再次印證上面的分析，NMPD算法維持著較高的VDC平均收益代價(jià)比，而且VDC平均收益代價(jià)比隨著可靠性需求的增加而下降.

Fig. 8　Performance with different revenuecost thresholds.圖8　不同收益代價(jià)比門限對算法的影響

2) 不同VDC請求到達(dá)率對算法的影響.由圖7(a)(b)可見，隨著請求到達(dá)率的增加，各種算法的接受率會不斷下降，然而單位時(shí)間的平均收益具有上升趨勢且會趨于平衡.很顯然，隨著請求到達(dá)率不斷增加，雖然更多的請求被拒絕，但底層網(wǎng)絡(luò)接受的請求數(shù)也在增加，所以單位時(shí)間的平均收益也會增加.由于底層網(wǎng)絡(luò)資源的固有容量限制，單位時(shí)間的平均收益不可能無限增長下去，所以會趨于平衡.從圖7(c)可以發(fā)現(xiàn)，VDC平均收益代價(jià)比會隨著到達(dá)率的增加而下降.這是因?yàn)樗惴ń邮芰烁鄶?shù)目的VDC請求，此時(shí)底層網(wǎng)絡(luò)剩余資源有限，只能以更大的代價(jià)接受新到的VDC請求.

4.6利用收益代價(jià)比門限進(jìn)一步優(yōu)化算法

雖然NMPD算法通過一種啟發(fā)式的方法拒絕了一些低收益代價(jià)比的VDC請求，但本文所提到的算法都具有貪婪的本質(zhì)：只要可以發(fā)現(xiàn)滿足VDC請求需求的資源，它就會接受VDC請求.如果VDC請求占用了大量的底層資源，這將會影響后續(xù)VDC的收益代價(jià)比和接受率，形成惡性循環(huán).基于以上分析，本文嘗試基于收益代價(jià)比門限值，在算法中采用一種動(dòng)態(tài)監(jiān)控策略，通過比較門限閾值大小動(dòng)態(tài)接受或拒絕VDC請求：如果VDC請求的收益代價(jià)比低于門限值，則拒絕掉該VDC請求.

為了更方便地評價(jià)收益代價(jià)比門限對算法的影響，本文定義了一個(gè)新指標(biāo)——單位時(shí)間內(nèi)的平均利潤，具體如下：

(29)

其中,β表示收益和代價(jià)的調(diào)節(jié)因子.本文定義收益R(t)與代價(jià)C(t)時(shí)，資源請求量和占用量均做了歸一化處理.在實(shí)際中，這么計(jì)算得到的收益和代價(jià)存在著一定的比例，所以使用β作為調(diào)節(jié)因子.

針對本文所提出的2種算法，我們對比了不同收益代價(jià)比門限情況下2種算法的表現(xiàn)，如圖8所示.圖8(a)顯示了單位時(shí)間的平均收益與收益代價(jià)比門限的變化情況.從圖8(a)可以看到，NMPD的單位時(shí)間平均收益隨門限值的增加先增大后減小.因?yàn)楹线m的門限值可以拒絕掉一些浪費(fèi)較多資源的VDC請求，接受更多高收益代價(jià)比的VDC請求.但如果門限值太高的話，被拒絕掉的請求也會越多，導(dǎo)致接受率下降，單位時(shí)間平均收益減少.對NMPC來說，門限值為0～0.6，其單位時(shí)間平均收益并沒有提高，然而NMPC所映射VDC的平均收益代價(jià)比卻大幅提升，如圖8(b)所示.這表明當(dāng)門限值從0變到0.6時(shí)，NMPC以更少的代價(jià)獲得了相同的收益.

圖8(c)(d)顯示收益代價(jià)比門限與單位時(shí)間平均利潤的關(guān)系.從圖8(c)可以看到，2種算法的單位時(shí)間平均利潤(β=0.25)很接近，均隨門限值的增加先增大后減??；當(dāng)收益代價(jià)比門限值為0.6時(shí)，二者均達(dá)到最優(yōu)的單位時(shí)間平均利潤.圖8(d)顯示了NMPC算法中不同β、門限值與單位時(shí)間平均利潤的關(guān)系.從圖8(d)可以看到，單位時(shí)間的平均利潤均隨門限值的增加先增大后減小.當(dāng)β較大時(shí)，表示VDC占用的物理資源具有較高的成本，所以最優(yōu)的收益代價(jià)比門限也越高；當(dāng)β較小時(shí)，表示物理資源的成本較低，較低的收益代價(jià)比門限就可以獲得最優(yōu)的單位時(shí)間平均利潤.在實(shí)際中，可以根據(jù)資源成本與收益的比例設(shè)置合適的門限值，以獲得最優(yōu)的利潤.

5結(jié)束語

本文提出了一種基于SDN的數(shù)據(jù)中心資源管理框架；同時(shí)以提高InP收益為目標(biāo)，折衷VDC可靠性需求與映射代價(jià)，提出了基于拓?fù)鋭莸腣DC映射算法.為了減少鏈路資源的占用，本文通過虛擬機(jī)節(jié)點(diǎn)聚類的方式，將鏈路密集的虛擬機(jī)集合分配到同一臺主機(jī)中，將鏈路稀疏的虛擬機(jī)節(jié)點(diǎn)分散到不同主機(jī)中.本文提出了2種不同的主機(jī)選擇方法，進(jìn)一步提高了物理資源的利用率.通過仿真實(shí)驗(yàn)，我們發(fā)現(xiàn)本文所提的算法可以達(dá)到較高的接受率與收益.最后，我們提出一種動(dòng)態(tài)監(jiān)控策略，選擇收益代價(jià)比高的VDC請求，通過選擇合適的收益代價(jià)比門限，可以進(jìn)一步優(yōu)化算法.在將來的研究中，我們會考慮分布式數(shù)據(jù)中心中的VDC映射問題.

參考文獻(xiàn)

[1]Bari M F, Boutaba R, Esteves R, et al. Data center network virtualization: A survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(2): 909-928

[2]Amokrane A, Zhani M F, Langar R, et al. Greenhead: Virtual data center embedding across distributed infrastructures[J]. IEEE Trans on Cloud Computing, 2013, 1(1): 36-49

[3]Kim H, Feamster N. Improving network management with software defined networking[J]. IEEE Communications Magazine, 2013, 51(2): 114-119

[4]Zhang Chaokun, Cui Yong, Tang Heyi, et al. State-of-the-Art survey on software-defined networking[J]. Journal of Software, 2015, 26(1): 62-81 (in Chinese)(張朝昆, 崔勇, 唐翯祎, 等. 軟件定義網(wǎng)絡(luò)(SDN)研究進(jìn)展[J]. 軟件學(xué)報(bào), 2015, 26(1): 62-81)

[5]Dong shi, Li Ruixuan, Li Xiaolin. Energy efficient routing algorithm based on software defined data center network[J]. Journal of Computer Research and Development, 2015, 52(4): 806-812 (in Chinese)(董仕, 李瑞軒, 李曉林. 基于軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)的節(jié)能路由算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(4): 806-812)

[6]Fischer A, Botero J F, Till Beck M, et al. Virtual network embedding: A survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(4): 1888-1906

[7]Rabbani M G, Zhani M F, Boutaba R. On achieving high survivability in virtualized data centers[J]. IEICE Trans on Communications, 2014, 97(1): 10-18

[8]Amazon. Amazon EC2 service level agreement[EB/OL]. 2013 [2015-12-17]. http://aws.amazon.com/cn/ec2/sla

[9]Li Xiaoling, Wang Huaimin, Ding Bo, et al. Resource allocation with multi-factor node ranking in data center networks[J]. Future Generation Computer Systems, 2014, 32: 1-12

[10]Cheng Xiang, Su Sen, Zhang Zhongbao, et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 38-47

[11]Zhani M F, Zhang Q, Simon G, et al. VDC planner: Dynamic migration-aware virtual data center embedding for clouds[C] //Proc of IFIP/IEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2013: 18-25

[12]Guo C, Lu G, Wang H J, et al. SecondNet: A data center network virtualization architecture with bandwidth guarantees[C] //Proc of the 6th Int Conf. New York: ACM, 2010: 15:1-15:12

[13]Li D, Du Y. Artificial Intelligence with Uncertainty[M]. Boca Raton, FL: CRC, 2007

[14]Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113

[15]Medina A, Lakhina A, Matta I, et al. BRITE: An approach to universal topology generation[C] //Proc of the 9th Int Symp on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE, 2001: 346-353

[16]Benson T, Anand A, Akella A, et al. Understanding data center traffic characteristics[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(1): 92-99

Wen Xuemin, born in 1988. PhD candidate at the Institute of Information Engineering, Chinese Academy of Sciences. His main research interests include data center network, network virtualization and cloud computing.

Han Yanni, born in 1981. PhD and assistant researcher in the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences. Her current research interests include resource management, network virtualization and future Internet.

Yu Bing, born in 1990. PhD candidate at the Institute of Information Engineering, Chinese Academy of Sciences. Her main research interests include service migration and resource management (yubing@iie.ac.cn).

Sun Jianpeng, born in 1989. Master candidate at the School of Information Science and Engineering, Shandong University. His main research interests include virtual machine live migration in cloud computing (sunjianpeng@iie.ac.cn).

Xu Zhen, born in 1976. PhD, professor, PhD supervisor. Member of China Computer Federation. His main research interests include database security, trusted computing and network security (xuzhen@iie.ac.cn).

A Topology-Aware VDC Embedding Algorithm in Software-Defined Datacenter

Wen Xuemin1, Han Yanni1, Yu Bing1, Sun Jianpeng2, and Xu Zhen1

1(StateKeyLaboratoryofInformationSecurity(InstituteofInformationEngineering,ChineseAcademyofSciences),Beijing100093)2(SchoolofInformationScienceandEngineering,ShandongUniversity,Jinan250100)

AbstractIn cloud computing environment, service provider (SP) can pay for the resources from infrastructure provider (InP) on-demand to deploy their services. In the case, SP can focus on service business without considering their physical infrastructures and expertise of maintenance. Only providing resources in term of virtual machines, the traditional InPs do not ensure network performance and bandwidth isolation. As the network virtualization is developed, especially the SDN concept, some researchers advocate InPs to provide resources in term of virtual data center (VDC) to solve these limits. Despite many advantages of VDC, there is also a new challenge that is the VDC embedding problem known as an NP-hard problem. With the goal of minimal cost and maximal revenue, it solves the problem of allocating resources to fulfill the SPs’ requirements. Considering the tradeoff of VDC reliability and embedding cost, a VDC embedding algorithm based on topological potential and modularity is proposed to improve acceptance ratio and the InPs’ revenue. Moreover, we further optimize the algorithm based on a given threshold by selecting high Revenue?Cost ratio VDCs. Extensive simulations show that compared with the existing algorithms, our approach is capable of reducing the core bandwidth consumption in data center. Furthermore, these proposals can accept more VDCs and obtain more revenue.

Key wordscloud computing; data center; software defined networking (SDN); network virtualization; virtual data center (VDC) embedding

收稿日期：2015-12-21；修回日期：2016-02-03

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61303252，61303250)；中國科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(xiàng)基金項(xiàng)目(XDA06010300)

通信作者：韓言妮(hanyanni@iie.ac.cn)

中圖法分類號TP393.01

This work was supported by the National Natural Science Foundation of China (61303252, 61303250) and the Strategic Priority Research Program of the Chinese Academy of Sciences (XDA06010300).