軟件定義數據中心內一種基于拓撲感知的VDC映射算法

文學敏　韓言妮　于　冰　孫建朋　徐　震

1(信息安全國家重點實驗室(中國科學院信息工程研究所)　北京　100093)2(山東大學信息科學與工程學院　濟南　250100)(wenxuemin@iie.ac.cn)

軟件定義數據中心內一種基于拓撲感知的VDC映射算法

文學敏1韓言妮1于冰1孫建朋2徐震1

1(信息安全國家重點實驗室(中國科學院信息工程研究所)北京100093)2(山東大學信息科學與工程學院濟南250100)(wenxuemin@iie.ac.cn)

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

關鍵詞云計算；數據中心；軟件定義網絡；網絡虛擬化；VDC映射

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

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

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

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

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

1問題描述

1.1VDC映射問題與數據中心資源管理框架

InP擁有物理基礎設施，通過向SP出租資源獲取收益.SP需要一定的基礎設施部署自己的服務或任務.為了節約設備成本和維護代價，SP可以向InP以VDC的形式租賃資源.首先，當SP需要租賃資源時，它需要向InP提交VDC請求說明，包括VDC的拓撲、每個虛擬節點的vCPU數量和內存需求量、每條虛擬鏈路的最小帶寬.InP收到請求后，根據底層網絡的狀態，為VDC分配滿足需求的物理資源.InP會在不同的時間收到來自不同SP的不同VDC請求.但InP無法預知VDC請求的到達時間，也無法預知VDC請求的具體內容.所以，本文所考慮的VDC映射問題是一個在線映射問題.

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

1) 基礎物理網絡設施.該層是InP所擁有的底層網絡設施.本文主要考慮的是單個數據中心網絡，而實際中既可以是單個數據中心，也可以是通過骨干網互聯的多個數據中心.

2) 控制接口層.該層主要由SDN控制接口和主機控制接口組成，為上層網絡操作系統提供接口.SDN控制接口可以控制物理交換機和虛擬交換機的轉發行為、查詢交換機中的流表信息、統計信息以及監控物理網絡拓撲變化.主機控制接口可以控制虛擬機的創建、刪除、修改和遷移、查詢物理主機、虛擬機的使用狀態和統計數據.

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

3) 網絡操作系統(NOS).①NOS通過控制層的北向接口，對底層物理資源進行統一的管理和調度，可以利用SDN控制器下發流表策略，利用Server控制器操作物理主機和虛擬機；②NOS內部會維護底層網絡的全局拓撲視圖以及各個節點和鏈路的分配、使用狀態；③NOS抽象化底層物理資源的使用方式，為上層應用程序(系統控制程序和用戶控制程序)提供統一的接口，并且為不同的應用程序提供隔離并分配權限；④NOS負責事件的分發：當NOS收到底層網絡產生的事件時，它會根據事件的源、類型、優先級(系統級或用戶級)以及訂閱者信息，將事件分發給相應的應用程序.

4) 系統控制層.系統控制層包含運行在NOS之上協助InP實現數據中心自動化管理的應用程序，比如路由程序、VDC映射程序、資源監控程序等.

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

1.2資源利用率與可靠性

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

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

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

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

2問題建模

2.1網絡建模

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

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

(1)

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

(2)

2.2VDC映射過程

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

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

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

(10)

(11)

4) 滿足可靠性需求：

(12)

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

(13)

2.3收益模型

對每個被接受的VDC請求，SP根據服務需求按照使用時間長短付費，而單位時間的價格由VDC所請求的資源量決定，定義如下：

(14)

(15)

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

(16)

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

2.4目標函數

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

(17)

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

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

3基于拓撲勢的VDC映射算法

為了滿足VDC需求，以最小代價為VDC分配資源，提高算法的VDC接受率和收益，本文提出一種啟發式算法解決VDC的映射問題.算法的理論基礎是利用拓撲勢來評價網絡中節點的重要性，在考慮VDC可靠性需求的基礎上對虛擬機節點聚類，盡量將節點間流量較多的VM映射到相同的主機上，節點間流量較少的VM分散到不同的主機上.由于算法利用拓撲勢實現節點映射(nodes mapping based on topological potential)，因此我們將本文的算法命名為NMP.本節首先介紹拓撲勢的含義以及計算方法，然后詳細描述本文的算法設計.

3.1拓撲勢

在物理學中，“勢場”可以描述沒有直接接觸的節點之間所產生的相互作用，比如電磁場和重力場.拓撲勢[13]就是受此啟發，將類似的方法應用到網絡中，評價網絡節點的拓撲重要性.在網絡中，我們定義2個節點之間的相互作用與它們的資源容量和它們之間的距離有關.本文使用高斯函數的形式描述2個節點的相互作用.一個節點的拓撲勢等于網絡中所有節點對它作用的疊加，節點n的拓撲勢通過以下方式計算：

(18)

選擇一個合適的σ對拓撲勢來說十分重要.如果σ太大，每個節點的影響范圍就很大，那么網絡中所有節點的拓撲勢就會非常接近，難以區別節點的重要性；相反，如果σ太小，一個節點的拓撲勢只由自身的資源容量決定，鄰居節點的影響近乎消失.根據信息熵的理論，如果所有節點的拓撲勢幾乎一樣，那么所提供的信息量就最小，拓撲勢的熵最大.因此我們可以通過計算拓撲勢的最小熵獲取合適的影響因子σ.拓撲勢的熵計算為

(19)

3.2算法設計

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

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

步驟2. 通過虛擬機節點聚類的方式搜索一簇VM節點.首先選擇拓撲勢最大的VM節點作為簇心.由式(18)對拓撲勢的定義可知，網絡節點拓撲勢的大小由該節點與其鄰居節點共同決定，反映了一個節點在網絡中的重要性.拓撲勢最大的節點可以作為簇心實現網絡節點聚類，所以在每次迭代過程中使用未分配的VM集合中拓撲勢最大的節點作為簇心搜索VM簇.

步驟3. 從未分配的VM集合中選擇可以使網絡模塊度最大化的VM，加入到VM簇中，重復執行直到VM簇的大小到達K.模塊度可以評價網絡社區劃分結果的好壞.模塊度將社區內鏈路密度與社區間鏈路密度做比較.一個優秀的社區劃分結果在社區內相比于社區之間具有更緊密的鏈路，所以本文利用模塊度來選擇VM加入到VM簇，以使簇內具有更高的鏈路密度.有關模塊度的計算以及虛擬機節點聚類的方法將在3.2.2節詳述.

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

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

步驟6. 如果仍有未映射的VM，回到步驟2重復執行.

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

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

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

輸出：是否映射成功.

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

①U←Nj;

②C←?;

③ 根據可靠性需求計算K；

④ 計算U中所有VM的拓撲勢；

⑤ whileU≠? do

⑥v←U中拓撲勢最大的VM;

⑦C←{v};

⑧stack←[v];

⑨ fori←0 toK-1 do

⑩ 計算UC中所有VM對應的模塊度增量ΔQ;

且stack≠? do

NMP算法包含2個最關鍵的步驟：虛擬機節點聚類和物理主機的選擇.接下來本文對這2部分進行詳盡的描述.

3.2.1虛擬機節點聚類

在網絡中，拓撲勢最大的節點可以說明以這個節點為中心的范圍內擁有更多的資源，所以本文將拓撲勢最大的節點作為搜索VM簇的核心.模塊度用來評價網絡社區劃分算法的結果.模塊度的定義為[14]

(20)

(21)

這表示模塊度等于社區內鏈路所占比例減去隨機情況下社區內鏈路所占比例.

在算法1中，每次迭代過程利用拓撲勢最大的VM節點作為核心搜索一簇VM集合.最開始，C中只有核心VM節點；接下來，從UC中選擇一個VM加入到C中并可以最大化網絡整體模塊度，重復添加VM直到C的大小達到K.為了提高算法的效率，本文只計算將一臺VM從集合U中移到C中的模塊度增量ΔQ.如果將一個節點v從類簇j中移到類簇i中，ΔQ可以計算為

(22)

3.2.2物理主機選擇方法

搜索到一簇VM節點后，我們需要選擇一臺物理主機來映射VM簇.為了減少簇間虛擬鏈路的跳數，選擇物理主機時應該同時考慮主機的剩余資源容量以及到已映射VM的距離.本文提出了2種選擇物理的方法：1)通過節點聚類(clustering)的方法將VDC的映射限定在一簇資源容量較多的主機集合中，本文將這種方法命名為NMPC；2)根據主機的拓撲勢和到已映射VM的距離(distance)對主機進行評分，并選擇評分最高的主機，這種方法被命名為NMPD.下面詳細說明這2種方法：

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

2) NMPD.與NMPC先搜索一簇候選主機集合，再從其中選擇主機的方式不同，NMPD根據主機的拓撲勢和到已映射VM的距離對所有未考慮的主機進行評分，并選擇評分最高的主機.本文通過式(23)計算每臺物理主機的評分.

(23)

其中,tpn表示物理主機n的拓撲勢，us表示已映射的VM所在的物理主機集合，dn n′表示2臺物理主機的距離，λ是主機拓撲勢和到已選擇主機平均距離的平衡因子.被評價的主機拓撲勢越大，到已選擇主機的平均距離越近，評分越高.

4實驗結果與分析

4.1仿真環境

我們基于Python開發了一個離散事件仿真器來模擬數據中心中的VDC映射過程.數據中心網絡采用6端口的FatTree拓撲，包含45個交換機、54臺物理主機.每臺主機包含16個vCPU和8 096 MB內存,交換機的每個端口的帶寬容量為1 000 Mbps.VDC請求使用BRITE[15]拓撲生成器生成.VDC請求的VM數量均勻分布在10～50之間，每臺VM請求的vCPU均勻分布在1～4之間，內存容量均勻分布在512～2 048 MB，每條虛擬鏈路請求的帶寬容量均勻分布在100～200 Mbps.VDC請求的到達服從均值為0.03的泊松分布，VDC的生命時長服從均值為500單位時間的指數分布.本文選擇基于節點排序的NodeRank[10]作為對比算法，并擴展到VDC場景，允許一臺物理主機可以映射VDC的多個VM，并滿足可靠性需求，該對比算法在后文中均以Baseline標記.

4.2評價指標

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

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

(24)

其中,|·|表示集合中的元素數目.只有接受率并不能完全反映算法的性能.如果一種算法只接受小規模請求、拒絕大請求，可能會產生較高的接受率，收益反而會減小.這是因為接受率是由接受的VDC數目決定的，而收益是由VDC規模大小和接受的VDC數目共同決定的.

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

(25)

其中,代價Cj由其實際所占用的資源量決定：

(26)

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

(27)

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

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

(28)

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

4.3NMPD中平衡因子的選擇

在3.2節中，NMPD算法同時考慮主機的拓撲勢和到已選擇主機的距離，對每臺主機評分并選擇評分最高的主機.其中，λ表示拓撲勢與距離因素之間的平衡因子.λ越大，距離因素影響越小，會導致虛擬鏈路占用更多的帶寬資源；相反，λ越小，距離因素的權重越大，距離已映射VM稍微遠一點的主機就會被忽略掉.圖3反映了接受率隨平衡因子λ的變化關系.從圖3可以看到,λ太大或太小，接受率都比較小，當λ=1.5時，映射算法的接受率最高.因此接受率隨λ的變化并不是很大：當λ從1增加到4，接受率變化范圍只有0.03.本文在NMPD算法中默認使用λ=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　累積收益代價比與核心鏈路平均占用率隨時間的變化

4.4不同算法的比較

首先，本文將VDC的可靠性需求設為0.2～0.9，對比了3種算法在不同評價指標下的表現.

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

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

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

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

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

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

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

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

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

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

2) 不同VDC請求到達率對算法的影響.由圖7(a)(b)可見，隨著請求到達率的增加，各種算法的接受率會不斷下降，然而單位時間的平均收益具有上升趨勢且會趨于平衡.很顯然，隨著請求到達率不斷增加，雖然更多的請求被拒絕，但底層網絡接受的請求數也在增加，所以單位時間的平均收益也會增加.由于底層網絡資源的固有容量限制，單位時間的平均收益不可能無限增長下去，所以會趨于平衡.從圖7(c)可以發現，VDC平均收益代價比會隨著到達率的增加而下降.這是因為算法接受了更多數目的VDC請求，此時底層網絡剩余資源有限，只能以更大的代價接受新到的VDC請求.

4.6利用收益代價比門限進一步優化算法

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

為了更方便地評價收益代價比門限對算法的影響，本文定義了一個新指標——單位時間內的平均利潤，具體如下：

(29)

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

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

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

5結束語

本文提出了一種基于SDN的數據中心資源管理框架；同時以提高InP收益為目標，折衷VDC可靠性需求與映射代價，提出了基于拓撲勢的VDC映射算法.為了減少鏈路資源的占用，本文通過虛擬機節點聚類的方式，將鏈路密集的虛擬機集合分配到同一臺主機中，將鏈路稀疏的虛擬機節點分散到不同主機中.本文提出了2種不同的主機選擇方法，進一步提高了物理資源的利用率.通過仿真實驗，我們發現本文所提的算法可以達到較高的接受率與收益.最后，我們提出一種動態監控策略，選擇收益代價比高的VDC請求，通過選擇合適的收益代價比門限，可以進一步優化算法.在將來的研究中，我們會考慮分布式數據中心中的VDC映射問題.

參考文獻

[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)(張朝昆, 崔勇, 唐翯祎, 等. 軟件定義網絡(SDN)研究進展[J]. 軟件學報, 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)(董仕, 李瑞軒, 李曉林. 基于軟件定義數據中心網絡的節能路由算法[J]. 計算機研究與發展, 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

基金項目：國家自然科學基金項目(61303252，61303250)；中國科學院戰略性先導科技專項基金項目(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).