時間和能量感知的貝葉斯虛擬網映射

胡穎，莊雷，陳鴻昶，馬丁,3

?

時間和能量感知的貝葉斯虛擬網映射

胡穎1，莊雷1，陳鴻昶2，馬丁1,3

（1. 鄭州大學信息工程學院，河南鄭州 450000； 2. 國家數字交換系統工程技術研究中心，河南鄭州 450002； 3. 河南工業大學信息科學與工程學院，河南鄭州 450000）

針對虛擬網的節能映射問題，建立了結合時間和能量感知的虛擬網映射算法。在對節點和路徑的評價標準中加入了時間因素，綜合考慮了物理資源的運行時間等因素，用概率理論輔助分析了每個虛擬節點的多個可用物理節點被選中的概率。在節點選擇階段，綜合考慮底層節點的剩余資源量、CPU資源利用率增量、節點開啟情況和是否延長使用時間等因素，并使用條件概率理論輔助分析得到各可用節點的重要性；在鏈路選擇階段，綜合考慮鏈路開啟情況、延長使用時間和鏈路長度等因素。不僅使虛擬網請求映射在當前較小的節點和鏈路集合中，而且映射到了延長時間較短的設備上。實驗結果表明，與未考慮時間因素的方法相比，該方法能帶來更好的性能和更低的能耗。

虛擬網映射；節能；貝葉斯；條件概率；時間感知

1 引言

隨著電力成本的不斷上漲，網絡運營商已經認識到能耗管理問題的重要性。據有關研究顯示[1,2]，在數據中心，能耗開銷已經占數據中心總開銷的12%~20%，占運營開銷的40%~50%。在Internet中，能耗開銷也已經成為Internet服務提供商總開銷的重要組成部分。能耗開銷過大是由于當前網絡為高峰負荷設計，網絡資源超需供給確保了網絡正常運行，卻也導致資源利用率低下。據統計，大型ISP骨干網的平均鏈路利用率為30%~40%[5]。過低的利用率造成能源的極大浪費，使網絡能耗問題成為研究人員關注的熱點問題[6,7]。

網絡虛擬化技術是解決網絡僵化問題的關鍵解決方案，是未來網絡研究中的一種重要技術。在網絡虛擬化環境中，多個服務提供商(SP, service provider)以虛擬網請求的方式請求租用同一個基礎設施提供商(InP, infrastructure provider)提供的物理網絡，從而向端用戶提供服務；InP負責部署和管理底層物理網絡，優化虛擬網映射策略以使利益最大化，即映射更多的虛擬網請求的同時，使占用底層網絡資源量最小化，以減少運行成本。運行成本不僅包括資源的占用，還包括運行的能耗。在網絡虛擬化環境中降低能耗的方式有2種：虛擬網映射時（建立虛擬網時）和虛擬網運行中（建立虛擬網后）。本文關注虛擬網映射時的節能問題，即虛擬網節能映射問題。

在虛擬網節能映射中包括2個問題：1)如何對虛擬網節能映射問題建立模型；2)如何確定虛擬網節能映射算法，即根據模型建立的目標確定節點和鏈路映射的方法，以整合資源開啟較小的節點和鏈路集合，達到減少能耗的目的。

當前已有一些學者對虛擬網節能映射問題進行了有意義的研究。文獻[8]將虛擬網映射問題成功擴展到虛擬網節能映射問題，并建立了混合整數線性規劃模型，將節能映射的目標設置為開啟的節點數量和開啟的鏈路數量之和；文獻[9]從節能和占用資源最小化2個角度對虛擬網映射問題建立了整數線性規劃模型，并分別以其中一個為主要目標，另一個為次要目標進行了解決和分析；文獻[10]從能耗、請求優先級和請求的位置限制等3個條件來限制虛擬網節能映射問題，分析并得到了較優的結果；文獻[11]為數據中心網絡的虛擬網節能映射問題建立了模型，從實際因素出發，在計算資源和網絡資源2個角度對問題進行了分析討論；文獻[12]應用最優化理論為虛擬網節能映射問題建立了模型；文獻[13]為云計算網絡的虛擬網節能映射問題建立了混合整數線性規劃模型；文獻[14]從節能、負載均衡等多個目標設計虛擬網映射模型，并針對云計算網絡中的節點或鏈路故障問題，提出了一個容錯的映射算法。

以上虛擬網節能映射算法的主要節能方式是盡可能地將節點鏈路映射到活動的底層節點鏈路上，達到了較好的節能效果，但都沒有考慮延長運行時間對映射效果的影響。本文在對節點和鏈路評價標準的設計中考慮時間因素，加入了對物理資源的延長運行時間這一要素，設計了基于時間和能量感知的虛擬網映射算法(TEAVNE, time and energyaware virtual network embedding)。算法中，用傳統概率理論輔助分析，并確定了每個虛擬節點的多個可用物理節點將被選中的概率，并通過仿真實驗對該算法進行了驗證與分析。

2 虛擬網節能映射模型

底層網絡能耗包括物理節點能耗和物理鏈路2個部分，對其分析前，首先對符號定義如表1所示。

表1 符號表示

2.1 物理節點功耗

同文獻[15]，設置物理節點的功耗（ECN, energy consumption in node）為

2.2 物理鏈路功耗

同文獻[15]，定義底層網絡物理鏈路l的功耗（ECL, energy consumption in link）為

其中，物理鏈路的功耗n是常量。

2.3 底層網絡總能耗

為方便分析描述，首先做如下定義。

定義1 如果在某個時間段內，底層網絡上沒有發生虛擬網請求的到達或離開事件，稱此時段的底層網絡處于穩定狀態。

定義2 如果在某時刻發生了虛擬網請求的映射或離開事件（這里認為映射和離開事件的發生時間忽略不計），稱該時刻為分裂點。

定義3 相鄰2個分裂點間的時間段，稱為有效時間片。

由以上定義可知，在有效時間片內，底層網絡處于穩定狀態；在不同的有效時間片間，底層網絡單位能耗量不同。于是，計算底層網絡總能耗前應先確定所有分裂點，由各分裂點將運行時間分為多個有效時間片，在各個有效時間片內分別計算底層網絡的能耗，底層網絡的總能耗即各有效時間片的能耗總和為

其中，為分裂點劃分出的有效時間片總個數，E為有效時間片內底層網絡的單位能耗，T為有效時間片的時長。

在有效時間片內，物理網絡設備穩定運行，底層網絡能耗即物理節點和物理鏈路的能耗之和。由式(1)和式(2)，得到底層網絡的單位能耗E為

2.4 虛擬網節能映射問題模型

根據式(4)，設置虛擬網節能映射問題的目標如下。

目標函數為

和虛擬網映射問題一樣，虛擬網節能映射問題的約束條件包括以下幾項。

1) 容量約束

2) 傳輸約束

(7)

一個虛擬節點只能映射到一個底層節點的約束

3) 相同虛擬網請求的虛擬節點不能映射到同一個底層節點的約束

(9)

4) 變量約束

以上基于混合整數規劃設計得到虛擬網節能映射模型，下面針對該問題設計節點和鏈路的節能評價標準以及節能映射的貪婪算法，找到虛擬網節能映射的較優解。

3 時間和能量感知的虛擬網映射算法

與傳統的虛擬網節能映射算法相比，TEAVNE算法最主要的不同點在于：在為虛擬節點選取映射目標時，將會把占用設備的時間納入其評價要素，并應用傳統概率論方法分析可用節點的選中概率，使虛擬網請求優先映射在已開啟、延長資源占用時間較短且增加資源利用率較少的物理節點上；在為虛擬鏈路選取物理路徑時，兼顧了路徑的長度、路徑中物理鏈路的開啟量和物理鏈路的延長使用時間等3個因素。下面首先給出節點和鏈路的評價要素和評價標準。

3.1 節點和鏈路的評價要素

由虛擬網映射的基本指標——占用資源量和請求接收率等，可知評價要素中應包括如資源剩余量、物理路徑的長度等要素。由虛擬網節能映射的目標式(5)，應將物理節點和物理鏈路的開關狀態以及增加的CPU資源利用率作為評價要素。加入時間因素后，還應將當前的虛擬網請求是否延長設備運行時間以及延長運行時間的大小加入評價要素，否則將可能造成較差的節能效果。一個虛擬網映射的例子如圖1所示。

圖1中，六邊形節點構成的拓撲代表虛擬網，圓形節點構成的拓撲代表底層物理網絡，正方形框中的數字代表虛擬網的運行時間，矩形框中的數字表示底層網絡節點或鏈路還要被占用的時間。

設圖1中的底層網絡的帶寬和CPU剩余資源足夠多，各物理節點或鏈路均可滿足虛擬網請求的資源量，并設物理節點的CPU資源總量都相等。這里忽略執行映射操作的時間。

如果按照傳統的節能映射目標和節點鏈路的評價因素，在節能映射時不考慮延長節點或鏈路的運行時間等因素，那么將、、映射到、、或將其映射到、、的這2種方案的節點或鏈路開啟量都是零，CPU資源上增加的總的資源利用率也相等。也就是說，2種映射方案得到的當時的映射目標值是相等的。而在5個時間單位后，映射到、、的方案下釋放的節點和鏈路量較多。也就是說，不納入時間因素的評價標準可能會增加長期的系統能耗。因此，在虛擬網節能映射中，為節點和鏈路設計評價標準時，應考慮時間因素，即將延長節點或鏈路的使用時間這一因素納入評價要素。

綜上，在對虛擬網節能映射時，對節點的評價要素包括設備是否已開啟、增加的CPU資源利用率之和、是否延長設備運行時間以及延長運行時間的大小、資源剩余量等要素；對物理路徑的評價要素包括需要開啟的設備量、延長設備使用的時間和物理路徑的長度等要素。

3.2 節點的評價標準

在為虛擬節點選取映射目標時，需要建立一種針對候選底層節點的評價標準，該標準對底層物理節點是否適合承載該虛擬節點進行評價，從而確定每個可用節點的重要性。

節點評價要素中有關節能的2個布爾型變量是物理節點是否已被開啟和是否延長了物理節點的使用時間，用這2個布爾變量將可用節點集劃分為3個節點集合：令1表示已開啟且使用時間不會被延長的節點集；2表示已開啟且使用時間會被延長的節點集；3表示未開啟的節點集。這樣，3個節點集1、2和3是所有可選節點樣本空間的一個劃分。

令A表示選中節點集S的事件，若N表示選中可用節點的事件，那么(NA)是聯合概率，表示節點集S中的被選中的概率。由條件概率公式，聯合概率(NA)可由條件概率與邊緣概率之積得到

其中，S是節點所隸屬的節點集；(N|A)表示已選中子節點集S的條件下選擇節點的概率；(A)表示選擇子節點集S的概率。

3.2.1 對邊緣概率(A)的計算

為達到較好的節能效果，應優先選擇已開啟且未延長使用時間的節點，其次選擇已開啟且使用時間將被延長的節點，即3個節點集中元素的選中次序為1→2→3，因此，應保證隸屬于3個節點集的節點聯合概率的平均值滿足如下關系

于是，定義(A)為

其中，常數1、2和3分別為節點集1、2和3的經驗權重系數。為滿足式(12)，應設置權重系數大小滿足1>2>3。這里令1+2+3=1。由式(13)，。

3.2.2 對條件概率(N|A)的計算

1) 節點集1

節點集1中的節點都已被開啟，且使用時間未被延長，那么，節點集內節點間的相對重要性只與CPU資源利用率的增量和資源剩余量有關。

定義節點CPU資源剩余量如下

(18)

其中，1和2為經驗權重常系數。表示其該節點集中資源剩余量最小的節點，則表示該節點集中最小的資源剩余量。表示該節點集中資源剩余量最大的節點，則表示該節點集中最大的資源剩余量。表示該節點集中CPU資源總量最小的節點，則表示該節點集中最小的CPU資源總量。表示該節點集中CPU資源總量最大的節點，則表示該節點集中最大的CPU資源總量。1和2為2個相近的極小正數，1<2<<1，2用來避免2個最值相等時，使分母為0的情況；1用來避免分子為0的情況；當所有節點延長時間相等時，1和2的比值決定了對這種情況的評價值。

定義節點集1中節點被選擇的條件概率

2) 節點集2

節點集2中的節點已被開啟且將被延長使用時間，延長使用時間的長短對節能效果是有影響的，應優先選擇延長時間較短的節點。另外，加入節點集1中的2個評價要素，可定義節點集2中節點的相對重要性為

其中，1、2和3為經驗權重系數，表示節點集2中節點的最長延長時間，表示該節點集中節點的最短延長時間，表示節點將被延長的時間。

類似地，定義節點集2中節點被選擇的條件概率為

3) 節點集3

節點集3中的節點尚未被開啟，延長的使用時間為零，其評價要素由節點的CPU資源總量以及映射虛擬節點后CPU資源利用率增量決定。

首先定義資源量

在節點集3中，對CPU資源利用率增量的分析和節點集1中是一致的。類似于對條件概率(N|1)的定義，定義節點集3中節點的相對重要性如下

定義3中節點被選擇的條件概率

(24)

以上從節點的開關狀態和節點是否被延長了使用時間2個角度將底層節點分類，根據經驗傾向和各節點集中元素的數量確定選擇各集合的概率，即確定邊緣概率；在各節點集中，從剩余資源量、CPU資源利用率增量以及所延長的節點使用時間這3個方面，綜合評價隸屬各節點集中物理節點的相對重要性，從而確定條件概率。

在節能目標下，為某個虛擬節點選擇映射節點時，應首先為所有可用物理節點計算聯合概率。聯合概率值越大，說明節點的重要性越高，節點越適宜承載該虛擬節點。

3.3 物理路徑的評價標準

在虛擬網映射中，節點映射成功后，通常是使用最短路徑算法得到多條較短的物理路徑。物理路徑越長，消耗的底層鏈路帶寬資源越多，所以從占用資源量的角度應選擇最短物理路徑。然而，在虛擬網節能映射中，最短路徑上可能需要開啟較多的物理鏈路，因此不一定是最節能的路徑。為達到較好的節能效果，在選擇物理路徑時，要兼顧路徑的長度、物理鏈路的開啟量和物理鏈路的延長使用時間等多個因素。

最后，通過定義節能路徑長度來對虛擬鏈路的多個可用物理路徑進行評價。

由式(26)可以看出，從物理鏈路的延長運行時間、物理鏈路的開啟量以及物理路徑的長度這3個方面對底層物理路徑做出綜合評價。值越大，說明路徑長度較長、需要開啟的物理鏈路較多或延時較長，越不適于承載虛擬鏈路；值越小，評價結果越好，因此，取多個較短路徑中值最小的作為承載路徑。

3.4 映射算法

現已設計了加入時間因素的節點和鏈路節能評價標準，為了便于突出該評價標準的優勢，采用較為簡單的算法——貪婪算法。算法中，在多個可用節點中，選擇概率值最高的作為映射節點；在最短路徑算法[16]得到的多條最短路徑中，選擇值最小的作為映射路徑。

下面對該算法描述如下。

算法1 TEAVNE(time and energy aware virtual network embedding)

輸入 虛擬網請求拓撲G(N,L)，底層網絡拓撲圖G(N,L)；

輸出 映射結果(E,E)。

1) 將虛擬節點按照請求資源量的大小降序排序，得到虛擬節點映射序列：

4) 如果集合中元素個數為0，返回NODE_MAP_FAILED；

6) End for

7) 將虛擬鏈路按照請求資源的多少降序排序，得到虛擬鏈路映射序列：；

10) 利用最短路徑算法求出前條從E()到E()的最短路徑；

11) 由式(26)計算每條路徑的值，將映射到值最小的一條路徑min上，即E()=min；

12) 如果最短路徑不存在，返回EDGE_ MAP_FAILED；

13) End for

14) Return MAP_SUCCESS;

最短路徑算法[16]的時間復雜度為(|N|log|N|+|N|+|L|)，其中，|N|和|L|分別為底層網絡的節點個數和鏈路個數。由上述流程可知，TEAVNE算法的時間復雜度為(|L||N|log|N|+|N||L|+|L||L|+ |N||N|)，其中，|N|和|L|分別為虛擬網請求的節點個數和鏈路個數。

4 實驗

4.1 實驗環境

同文獻[17]，這里設置3種不同的實驗場景分別測試算法的節能效果。實驗在雙核CPU 3.4 GHz，4 GB內存的PC機上運行。底層網絡拓撲和虛擬網請求拓撲由GT-ITM[18]工具生成。

1) 實驗場景1

將該實驗環境標識為中等規模—低集中（medium-sized &low-concentration），實驗設置同文獻[19]。

底層物理網絡拓撲：底層網絡共包含100個節點，每兩節點間連接的概率為0.5，底層節點的CPU資源量和底層鏈路的帶寬資源量取值在[50,100]內均勻分布。

虛擬網請求拓撲：虛擬網請求的到達時刻服從平均100個時間單元到達5個請求的泊松過程，持續時間服從均值為1 000的指數分布。每個請求的節點個數在[2,10]內均勻分布，節點連接率為0.5，虛擬節點請求的CPU資源取值在[0,20]，虛擬鏈路請求的帶寬資源取值在[0, 25]之間均勻分布，虛擬網請求共計2 500個，實驗共運行50 000個左右的時間單元。

2) 實驗場景2

將該實驗環境標識為中等規模—中度集中（medium-sized &moderate-concentration），實驗設置同文獻[17,20~23]。

底層物理網絡拓撲：網絡設置同實驗場景1的物理網絡設置。

虛擬網請求拓撲：虛擬網請求的到達時刻服從平均100個時間單元到達5個請求的泊松過程，持續時間服從均值為1 000的指數分布，每個請求的節點個數在[2,20]內均勻分布，節點連接率為0.5，虛擬節點請求的CPU資源取值在[0,50]，虛擬鏈路請求的帶寬資源取值在[0, 50]之間均勻分布，虛擬網請求共計2 500個，實驗共運行50 000個左右的時間單元。

3) 實驗場景3

將該實驗環境標識為小規模—高集中（small- sized & high-concentration），設置同文獻[17,22~24]。

底層物理網絡拓撲：底層網絡共包含50個節點，每兩節點間連接的概率為0.5，底層節點的計算資源和底層鏈路的帶寬資源取值在[50,100]內均勻分布。

虛擬網請求拓撲：虛擬網請求的到達時刻服從平均100個時間單元到達4個請求的泊松過程，持續時間服從均值為1 000的指數分布。每個請求的節點個數在[2,10]內均勻分布，節點連接率為0.5，虛擬節點請求的CPU資源取值在[0,20]，虛擬鏈路請求的帶寬資源取值在[0, 50]之間均勻分布。虛擬網請求共計2 000個，實驗共運行50 000個左右的時間單元。

4) 其他參數設置

在參數設置上，同文獻[25~28]中的設置，得到節點和鏈路能耗中常數的值為：為150 W，為300 W，為15 W。其他參數設置為1=10?6、2=10?9，1=0.5，2=0.3，3=0.2，1=0.6，2=0.4，1=0.4，2=0.4，3=0.2，=0.2，=7。

5) 比較算法

TEAVNE算法是以節能為目標分兩階段映射的貪婪算法，為檢驗加入時間因素的節點和鏈路評價標準的節能效果，并保證比較的公平性，實驗選取2個較經典的同為兩階段映射的貪婪算法作為比較對象，即以最大化收益成本比為目標的貪婪映射算法SP[20]和同樣以節能為目標的貪婪映射算法EAVNE[8]。

4.2 實驗結果分析

4.2.1 對度量指標的定義

1) 能耗度量指標

在能耗度量指標上做如下5個定義。

定義平均節點開啟量（ANON, average number of open nodes）為

定義平均鏈路開啟量（ANOL, average number of open links）為

定義平均節點資源利用率（AUCPU, average utilization of CPU）為

定義平均鏈路資源利用率（AUBW, average utilization of BW）為

定義平均能耗量（AAEC, average amount of energy consumption）為

從以上定義可以看出，每次平均值的計算都是從起始時刻開始的。

2) 資源使用情況的度量指標

虛擬網映射算法一方面要滿足服務提供商的構建需求，另一方面需要高效地使用基礎設施提供商的物理網絡資源，因此可用虛擬網映射的請求接受率和收益成本比來衡量映射算法的資源使用情況。請求接受率用來衡量虛擬網請求的映射成功率，收益成本比用來衡量已映射虛擬網的資源占用情況。請求接受率和收益成本比從不同角度反映算法對資源的使用情況，其值越高，映射算法對資源的使用越充分。這里用收益成本比來衡量資源的使用情況。

對平均收益成本比（ARRC, average ratio of revenue and cost）定義如下

(33)

由上式可以看出，在映射某個虛擬網請求時，收益成本比只和物理路徑的長度有關，映射的物理路徑越短，收益成本比越高。

3) 映射時間長度的度量指標

定義平均映射時間(AMT, average mapping time)為

4.2.2 對實驗場景1的結果分析

在實驗場景1（medium-sized & low- concentration）中，各算法的請求接受率均為100%，此時只需要比較各算法的節能情況。圖2給出了在該場景下TEAVNE算法、EAVNE算法和SP算法的映射結果。

本文的TEAVNE算法降低了底層網絡節點和鏈路的開啟數量，很大程度地減少了底層網絡能耗。圖2(a)~2(c)展示了節點和鏈路的平均開啟量以及底層網絡的平均能耗量隨時間變化的情況。圖中表明了在開啟的節點數量和能耗量上，TEAVNE算法較SP和EAVNE有較為明顯的優勢。這是由于TEAVNE算法在每次映射時不僅考慮本次映射的節能效果，在節點和路徑的選擇標準中，還加入了延長節點（或鏈路）的時長等因素，考慮了對后續映射的節能效果，從而使總體的節能效果更好。

TEAVNE算法提高了節點和鏈路的資源利用率。圖2(d)、圖2(e)展示了節點的CPU資源利用率和鏈路的帶寬資源利用率隨時間變化的情況。圖中表明了在提高資源利用率方面，TEAVNE算法較SP和EAVNE有較明顯的優勢。在該場景下，各算法所接受的請求完全相同，節能算法的目標是開啟盡可能少的節點和鏈路，即要在更少的節點和鏈路集合上滿足相同的虛擬網請求，從而使節能效果越好，資源利用率越高。

TEAVNE算法較EAVNE算法和SP算法降低了收益成本比。圖2(f)展示了平均收益成本比隨時間變化的情況。圖中表明了在最大化收益成本比這一目標上，TEAVNE算法較SP和EAVNE算法有較差的效果。

根據式(32)~式(34)，對于相同的虛擬網請求，收益成本比的大小只與虛擬鏈路映射到的物理路徑長度（即虛擬鏈路的長度）有關。虛擬鏈路長度越長，收益成本比越小。在節能映射的初始階段，將開啟較小的物理鏈路集合，使部分物理鏈路的資源利用率過高，從而無法繼續承載虛擬鏈路，這樣的物理鏈路越多，虛擬鏈路將越長，甚至無法映射成功。因此，在接受相同虛擬網請求的情況下，算法的節能效果越好，收益成本比越低。

4.2.3 對實驗場景2的結果分析

在實驗場景2（medium-sized & moderate- concentration）中，各算法的請求接受率不再是100%。圖3給出了該場景下TEAVNE算法、EAVNE算法和SP算法的映射結果。

在請求接受率不再為100%的場景下，節能算法TEAVNE依然有較好的節能效果；和另一節能算法EAVNE一樣，其平均收益成本比較低。

從圖3(a)~圖3(e)可以看出，3種算法中，TEAVNE算法有最好的節能效果。

在收益成本比上，從圖2(f)和圖3(f)的對比中可以看出，請求接受率的下降伴隨著收益成本比的下降。其中，SP算法的收益成本比下降幅度較小，TEAVNE和EAVNE算法的收益成本比下降幅度較大。這是由于節能算法集中映射的方式使部分鏈路的利用率過高，平均鏈路利用率越高（對比圖2(e)和圖3(e)），鏈路利用率過高的物理鏈路越多，虛擬鏈路的長度越長，從而使節能算法的收益成本比下降的幅度越大。

3種算法的請求接受率差距越來越小。從圖3(g)中可以看出，SP算法的請求接受率隨時間的變化不大，而節能算法TEAVNE和EAVNE的請求接受率隨時間增長的下降趨勢較為明顯。在運行5 000個左右的時間單元后，三者的平均請求接受率相差無幾。

這是由于集中映射的方式使部分節點或鏈路的資源利用率較高，節點或鏈路的負載越不均衡，請求接受率越低。

4.2.4 對實驗場景3的結果分析

在實驗場景3（small-sized & high-concentration）中，各算法的請求接受率較低。圖4給出了該場景下TEAVNE算法、EAVNE算法和SP算法的映射結果。

兩節能算法TEAVNE和EAVNE較SP算法的節能效果更加明顯，TEAVNE算法較EAVNE算法在后期有更優的節能效果。從圖4(a)~圖4(c)可以看出，TEAVNE算法較EAVNE算法在后期有更優的節能效果。兩節能算法使節點或鏈路的開啟更加集中，節能效果更加顯著。由于TEAVNE算法中加入了時間因素，納入了對后續映射的節能效果的考慮，從而在后期，TEAVNE算法較EAVNE算法有更優的節能效果。

兩節能算法較SP算法的收益成本比更低。從圖2(f)、圖3(f)和圖4(f)可以看出，隨著請求接受率的下降，兩節能算法的收益成本比下降更為顯著。這是由于集中映射的策略使有些鏈路的資源利用率過高，無法承載虛擬鏈路。物理鏈路的平均資源利用率越高（對比圖2(e)、圖3(e)和圖4(e)），鏈路利用率過高的鏈路越多，虛擬鏈路的長度越長，從而降低了收益成本比。

節能算法的請求接受率較低。從圖4(g)可以看出，節能算法較SP算法的請求接受較低。其中，TEAVNE算法的請求接受率最低。這是由于集中映射的策略使有些節點或鏈路的資源利用率過高，無法承載虛擬節點或虛擬鏈路。節點或鏈路的平均資源利用率越高，節點或鏈路的利用率過高的節點或鏈路越多，不均衡的現象越為嚴重，從而降低了請求接受率。

4.2.5 算法映射時間的比較

TEAVNE算法與同為貪婪算法的SP算法和EAVNE算法運行時間相當。

實驗中，底層網絡分別在3種拓撲環境下運行所用的平均映射時間如圖5所示。

可以看出，同為貪婪算法的TEAVNE算法增加了運行時間，這是因為其在節點選擇時增加了對每個節點選擇概率的計算。但從圖中也可以看出，平均運行時間仍保持在毫秒級，且增加量比較小。

5 結束語

本文研究了網絡虛擬化環境下的系統能耗問題，根據節能運行的實際需要，設計了節能模型，然后借助條件概率理論輔助分析，在對節點和鏈路的節能評價中加入時間因素，最終設計了時間和能量感知的虛擬網映射算法，把虛擬網映射在一個較小的節點和鏈路集合中，提高關閉的節點和鏈路數量，以實現高效節能。實驗結果表明了TEAVNE算法能夠有效降低底層網絡的能量消耗，由于節能算法集中映射的特點，在資源請求量較底層網絡的資源剩余量較多的情況下，節能算法會降低請求接受率。于是，以節能為目標的映射是有一定的適用場景的，在確定的場景下，如何平衡節能和提高請求接受率2個相對矛盾的目標，以最大化商家的總收益，將是下一步有待深入研究的問題。

[1] CHUN B, IANNACCONE G, IANNACCONE G, et al. An energy case for hybrid datacenters [J]. ACMSIGOPS Operating Systems Review, 2010,44 (1): 76-80.

[2] APC American Power Conversion. Determining total cost of ownership for data center and network room infrastructure[EB/OL]. http://www.apcmedia.com/salestools/CMRP-5T9PQGR4EN.pdf, 2003.

[3] QURESHI A, WEBER R, BALAKRISHNAN H, et al. Cutting the electric bill for internet-scale systems[C]//The ACM SIGCOMM 2009 Conference on Data Communication. Barcelona, Spain, c2009: 123-134.

[4] China Mobile Research Institute[EB/OL]. http://v7vjw.greentouch.org/ uploads/documents/Chih-Lin_I%20-%20TIA%20Green%20from%20a% 20Service%20Provider%20Perspective .pdf. 2012.

[5] FISHER W, SUCHARA M, REXFORD J. Greening backbone networks: reducing energy consumption by shutting off cables in bundled links[C]//The 1st ACM SIGCOMM Workshop on Green Networking. New Delhi, India, c2010: 29-34.

[6] 林闖, 田源, 姚敏. 綠色網絡和綠色評價:節能機制、模型和評價[J].計算機學報, 2011,34(4):593-612.

LIN C, TIAN Y, YAO M. Green network and green evaluation: mechanism, modeling and evaluation [J]. Chinese Journal of Computers, 2011,34(4): 593-612.

[7] 葉可江,吳朝暉,姜曉紅,等.虛擬化云計算平臺的能耗管理[J].計算機學報,2012,35(6):1262-1285.

YE K J, WU Z H, JIANG X H, et al. Power management of virtualized cloud computing platform [J]. Chinese Journal of Computers, 2012,35(6): 1262-1285.

[8] BOTERO J F, HESSELBACH X, DUELLI M, et al. Energy efficient virtual network embedding[J]. IEEE Communications Letters, 2012, 16(5): 756-759.

[9] MELO M, SARGENTO S, et al. Optimal virtual network embedding: energy aware formulation[J]. Computer Networks, 2015, 91(C): 184-195.

[10] TRIKI N, KARA N, BARACHI M E, et al. A green energy-aware hybrid virtual network embedding approach[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 91(C):712-737.

[11] GUAN X J, CHOI B Y, SONG S. Energy efficient virtual network embedding for green data centers using data center topology and future migration[J]. Computer Communications, 2015, 69: 50-59.

[12] CHEN X H, LI C Z, JIANG Y L. Optimization model and algorithm for energy efficient virtual node embedding[J]. IEEE Communications Letters, 2015, 19(8): 1327-1330.

[13] NONDE L, EL-GORASHI T E H, ELMIRGHANI J M H. Energy efficient virtual network embedding for cloud networks[J]. Journal of Lightwave Technology, 2015, 33(9): 1828-1849.

[14] HOUIDI I, LOUATI W, ZEGHLACHE D. Exact multi-objective virtual network embedding in cloud environments[J]. Computer Journal, 2015, 58(3): 403-415.

[15] 陳曉華,李春芝, 陳良育, 等.主動休眠節點鏈路的高效節能虛擬網絡映射[J]. 軟件學報, 2014, 25(7): 1416-1431.

CHEN X H, LI C Z, CHEN L Y, et al. Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J]. Journal of Software, 2014, 25(7): 1416-1431.

[16] EPPATEIN D. Finding theshortest paths[J]. SIAM Journal on Computing, 1998,28(2):652-673.

[17] CHANG X L, MI X M, MUPPALA J K. Performance evaluation of artificial intelligence algorithms for virtual network embedding[J]. Engineering Applications of Artificial Intelligence, 2013, 26(10): 2540-2550.

[18] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an Internet work[C]//IEEE INFOCOM ‘96. Conference on Computer Communications. San Francisco, CA, USA, c1996: 594-602.

[19] 江逸茗,蘭巨龍, 程東年,等. 網絡虛擬化環境中面向服務聚合的映射算法[J]. 軟件學報, 2014, 25(6): 1328-1338.

JIANG Y M, LAN J L, CHENG D N, et al. Mapping algorithm for service aggregation in network virtualization [J]. Journal of Software, 2014,25(6): 1328-1338.

[20] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):19-29.

[21] CHENG X, SU S, ZHANG Z B, et al. Virtual network embedding through topology awareness and optimization [J]. Computer Networks, 2012, 56(6): 1797-1813.

[22] CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping [J]. IEEE/ACM Transactions on Networking, 2012, 20(1): 206-219.

[23] MI X M, CHANG X L, LIU J Q, et al. Embedding virtual infrastructure based on genetic algorithm[C]//2012 13th International Conference on Parallel and Distributed Computing Applications and Technologies(PDCAT). Beijing, China, c2012: 239-244.

[24] MOSHARAF N M, CHOWDHURY K, RAHMAN M R, et al. Virtual network embedding with coordinated node and link mapping[C]//28th Conference on Computer Communications(IEEE INFOCOM 2009). Rio de Janeiro, Brazil, c2009: 783-791.

[25] LU G, GUO C, LI YL, et al. Serverswitch: a programmable and high performance platform for datacenter networks[C]//The 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley: USENIX Association, c2011: 1-14.

[26] SIVARAMANV, VISHWANATH A, ZHAO Z, et al. Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]//2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS 2011). Shanghai, China, c2011: 331-336.

[27] UNNIKRISHNAN D, VADLAMANI R, LIAO Y, et al. Scalable network virtualization using FPGAs[C]//18th ACMSIGDA International Symposium on Field-Programmable Gate Arrays(FPGA’10). c2010: 219-228.

[28] BARROSO L A, HOLZLE U. The datacenter as a computer: an introduction to the design of warehouse-scale machines[J]. Synthesis Lectures on Computer Architecture, 2009, 6: 1-107.

Time and energy aware virtual network embedding using Bayesian theory analysis

HU Ying1, ZHUANG Lei1, CHEN Hong-chang2, MA Ding1,3

(1. School of Information Engineering, Zhengzhou University, Zhengzhou 450000, China; 2. National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China; 3. College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450000, China)

Aiming at the energy consumption problem in virtual network embedding, a virtual-network-embedding algorithm was proposed by combining the time and energy aware. Taking the running time during the evaluation of physical nodes and physical paths into account, it considered multiple factors which included the processing time of physical devices, and used probability theory to help analyze the selected probability of each available physical node for a virtual node. During the selection of substrate nodes, the factors of remaining resources, the increment of CPU utilization, the switch state and the amount of extended time of physical nodes were considered. The theory of conditional probability was further used to analyze the importance of available nodes. The factors of the switch state, the amount of extended time and the length of physical paths were also considered. The proposed approach could effectively map the current virtual network request onto a smaller set of nodes and links which are switched on, and also the devices which have less amount of extended time. Experimental results show that the proposed approach has better performance, and can effectively decrease energy consumption comparing with the methods without taking the time factor into consideration.

virtual network embedding, energy-saving, Bayesian, conditional probability, time aware

TP393

A

10.11959/j.issn.1000-436x.2016105

2015-08-06；

2016-03-10

莊雷，ielzhuang@zzu.edn.cn

國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2012CB315901）；國家自然科學基金資助項目（No.61379079）；河南省科技廳攻關基金資助項目（No.122102210042）

The National Basic Research Program of China (973 Program)(No.2012CB315901), The National Natural Science Foundation of China (No.61379079), Science and Technology Key Project of Henan Province (No.122102210042)

胡穎（1982-），女，河南商丘人，鄭州大學博士生，主要研究方向為未來網絡、網絡虛擬化、虛擬網映射等。

莊雷（1963-），女，山東日照人，鄭州大學教授、博士生導師，主要研究方向為未來網絡、網絡虛擬化等。

陳鴻昶（1964-），男，河南鄭州人，國家數字交換系統工程技術研究中心教授、博士生導師，主要研究方向為未來網絡、網絡安全等。

馬丁（1978-），男，河南鄭州人，鄭州大學博士生，河南工業大學講師，主要研究方向為未來網絡、網絡功能虛擬化等。