時(shí)間和能量感知的貝葉斯虛擬網(wǎng)映射

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

?

時(shí)間和能量感知的貝葉斯虛擬網(wǎng)映射

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

（1. 鄭州大學(xué)信息工程學(xué)院，河南鄭州 450000； 2. 國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州 450002； 3. 河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，河南鄭州 450000）

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

虛擬網(wǎng)映射；節(jié)能；貝葉斯；條件概率；時(shí)間感知

1 引言

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

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

在虛擬網(wǎng)節(jié)能映射中包括2個(gè)問題：1)如何對(duì)虛擬網(wǎng)節(jié)能映射問題建立模型；2)如何確定虛擬網(wǎng)節(jié)能映射算法，即根據(jù)模型建立的目標(biāo)確定節(jié)點(diǎn)和鏈路映射的方法，以整合資源開啟較小的節(jié)點(diǎn)和鏈路集合，達(dá)到減少能耗的目的。

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

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

2 虛擬網(wǎng)節(jié)能映射模型

底層網(wǎng)絡(luò)能耗包括物理節(jié)點(diǎn)能耗和物理鏈路2個(gè)部分，對(duì)其分析前，首先對(duì)符號(hào)定義如表1所示。

表1 符號(hào)表示

2.1 物理節(jié)點(diǎn)功耗

同文獻(xiàn)[15]，設(shè)置物理節(jié)點(diǎn)的功耗（ECN, energy consumption in node）為

2.2 物理鏈路功耗

同文獻(xiàn)[15]，定義底層網(wǎng)絡(luò)物理鏈路l的功耗（ECL, energy consumption in link）為

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

2.3 底層網(wǎng)絡(luò)總能耗

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

定義1 如果在某個(gè)時(shí)間段內(nèi)，底層網(wǎng)絡(luò)上沒有發(fā)生虛擬網(wǎng)請(qǐng)求的到達(dá)或離開事件，稱此時(shí)段的底層網(wǎng)絡(luò)處于穩(wěn)定狀態(tài)。

定義2 如果在某時(shí)刻發(fā)生了虛擬網(wǎng)請(qǐng)求的映射或離開事件（這里認(rèn)為映射和離開事件的發(fā)生時(shí)間忽略不計(jì)），稱該時(shí)刻為分裂點(diǎn)。

定義3 相鄰2個(gè)分裂點(diǎn)間的時(shí)間段，稱為有效時(shí)間片。

由以上定義可知，在有效時(shí)間片內(nèi)，底層網(wǎng)絡(luò)處于穩(wěn)定狀態(tài)；在不同的有效時(shí)間片間，底層網(wǎng)絡(luò)單位能耗量不同。于是，計(jì)算底層網(wǎng)絡(luò)總能耗前應(yīng)先確定所有分裂點(diǎn)，由各分裂點(diǎn)將運(yùn)行時(shí)間分為多個(gè)有效時(shí)間片，在各個(gè)有效時(shí)間片內(nèi)分別計(jì)算底層網(wǎng)絡(luò)的能耗，底層網(wǎng)絡(luò)的總能耗即各有效時(shí)間片的能耗總和為

其中，為分裂點(diǎn)劃分出的有效時(shí)間片總個(gè)數(shù)，E為有效時(shí)間片內(nèi)底層網(wǎng)絡(luò)的單位能耗，T為有效時(shí)間片的時(shí)長(zhǎng)。

在有效時(shí)間片內(nèi)，物理網(wǎng)絡(luò)設(shè)備穩(wěn)定運(yùn)行，底層網(wǎng)絡(luò)能耗即物理節(jié)點(diǎn)和物理鏈路的能耗之和。由式(1)和式(2)，得到底層網(wǎng)絡(luò)的單位能耗E為

2.4 虛擬網(wǎng)節(jié)能映射問題模型

根據(jù)式(4)，設(shè)置虛擬網(wǎng)節(jié)能映射問題的目標(biāo)如下。

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

和虛擬網(wǎng)映射問題一樣，虛擬網(wǎng)節(jié)能映射問題的約束條件包括以下幾項(xiàng)。

1) 容量約束

2) 傳輸約束

(7)

一個(gè)虛擬節(jié)點(diǎn)只能映射到一個(gè)底層節(jié)點(diǎn)的約束

3) 相同虛擬網(wǎng)請(qǐng)求的虛擬節(jié)點(diǎn)不能映射到同一個(gè)底層節(jié)點(diǎn)的約束

(9)

4) 變量約束

以上基于混合整數(shù)規(guī)劃設(shè)計(jì)得到虛擬網(wǎng)節(jié)能映射模型，下面針對(duì)該問題設(shè)計(jì)節(jié)點(diǎn)和鏈路的節(jié)能評(píng)價(jià)標(biāo)準(zhǔn)以及節(jié)能映射的貪婪算法，找到虛擬網(wǎng)節(jié)能映射的較優(yōu)解。

3 時(shí)間和能量感知的虛擬網(wǎng)映射算法

與傳統(tǒng)的虛擬網(wǎng)節(jié)能映射算法相比，TEAVNE算法最主要的不同點(diǎn)在于：在為虛擬節(jié)點(diǎn)選取映射目標(biāo)時(shí)，將會(huì)把占用設(shè)備的時(shí)間納入其評(píng)價(jià)要素，并應(yīng)用傳統(tǒng)概率論方法分析可用節(jié)點(diǎn)的選中概率，使虛擬網(wǎng)請(qǐng)求優(yōu)先映射在已開啟、延長(zhǎng)資源占用時(shí)間較短且增加資源利用率較少的物理節(jié)點(diǎn)上；在為虛擬鏈路選取物理路徑時(shí)，兼顧了路徑的長(zhǎng)度、路徑中物理鏈路的開啟量和物理鏈路的延長(zhǎng)使用時(shí)間等3個(gè)因素。下面首先給出節(jié)點(diǎn)和鏈路的評(píng)價(jià)要素和評(píng)價(jià)標(biāo)準(zhǔn)。

3.1 節(jié)點(diǎn)和鏈路的評(píng)價(jià)要素

由虛擬網(wǎng)映射的基本指標(biāo)——占用資源量和請(qǐng)求接收率等，可知評(píng)價(jià)要素中應(yīng)包括如資源剩余量、物理路徑的長(zhǎng)度等要素。由虛擬網(wǎng)節(jié)能映射的目標(biāo)式(5)，應(yīng)將物理節(jié)點(diǎn)和物理鏈路的開關(guān)狀態(tài)以及增加的CPU資源利用率作為評(píng)價(jià)要素。加入時(shí)間因素后，還應(yīng)將當(dāng)前的虛擬網(wǎng)請(qǐng)求是否延長(zhǎng)設(shè)備運(yùn)行時(shí)間以及延長(zhǎng)運(yùn)行時(shí)間的大小加入評(píng)價(jià)要素，否則將可能造成較差的節(jié)能效果。一個(gè)虛擬網(wǎng)映射的例子如圖1所示。

圖1中，六邊形節(jié)點(diǎn)構(gòu)成的拓?fù)浯硖摂M網(wǎng)，圓形節(jié)點(diǎn)構(gòu)成的拓?fù)浯淼讓游锢砭W(wǎng)絡(luò)，正方形框中的數(shù)字代表虛擬網(wǎng)的運(yùn)行時(shí)間，矩形框中的數(shù)字表示底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路還要被占用的時(shí)間。

設(shè)圖1中的底層網(wǎng)絡(luò)的帶寬和CPU剩余資源足夠多，各物理節(jié)點(diǎn)或鏈路均可滿足虛擬網(wǎng)請(qǐng)求的資源量，并設(shè)物理節(jié)點(diǎn)的CPU資源總量都相等。這里忽略執(zhí)行映射操作的時(shí)間。

如果按照傳統(tǒng)的節(jié)能映射目標(biāo)和節(jié)點(diǎn)鏈路的評(píng)價(jià)因素，在節(jié)能映射時(shí)不考慮延長(zhǎng)節(jié)點(diǎn)或鏈路的運(yùn)行時(shí)間等因素，那么將、、映射到、、或?qū)⑵溆成涞健ⅰ⒌倪@2種方案的節(jié)點(diǎn)或鏈路開啟量都是零，CPU資源上增加的總的資源利用率也相等。也就是說，2種映射方案得到的當(dāng)時(shí)的映射目標(biāo)值是相等的。而在5個(gè)時(shí)間單位后，映射到、、的方案下釋放的節(jié)點(diǎn)和鏈路量較多。也就是說，不納入時(shí)間因素的評(píng)價(jià)標(biāo)準(zhǔn)可能會(huì)增加長(zhǎng)期的系統(tǒng)能耗。因此，在虛擬網(wǎng)節(jié)能映射中，為節(jié)點(diǎn)和鏈路設(shè)計(jì)評(píng)價(jià)標(biāo)準(zhǔn)時(shí)，應(yīng)考慮時(shí)間因素，即將延長(zhǎng)節(jié)點(diǎn)或鏈路的使用時(shí)間這一因素納入評(píng)價(jià)要素。

綜上，在對(duì)虛擬網(wǎng)節(jié)能映射時(shí)，對(duì)節(jié)點(diǎn)的評(píng)價(jià)要素包括設(shè)備是否已開啟、增加的CPU資源利用率之和、是否延長(zhǎng)設(shè)備運(yùn)行時(shí)間以及延長(zhǎng)運(yùn)行時(shí)間的大小、資源剩余量等要素；對(duì)物理路徑的評(píng)價(jià)要素包括需要開啟的設(shè)備量、延長(zhǎng)設(shè)備使用的時(shí)間和物理路徑的長(zhǎng)度等要素。

3.2 節(jié)點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)

在為虛擬節(jié)點(diǎn)選取映射目標(biāo)時(shí)，需要建立一種針對(duì)候選底層節(jié)點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)對(duì)底層物理節(jié)點(diǎn)是否適合承載該虛擬節(jié)點(diǎn)進(jìn)行評(píng)價(jià)，從而確定每個(gè)可用節(jié)點(diǎn)的重要性。

節(jié)點(diǎn)評(píng)價(jià)要素中有關(guān)節(jié)能的2個(gè)布爾型變量是物理節(jié)點(diǎn)是否已被開啟和是否延長(zhǎng)了物理節(jié)點(diǎn)的使用時(shí)間，用這2個(gè)布爾變量將可用節(jié)點(diǎn)集劃分為3個(gè)節(jié)點(diǎn)集合：令1表示已開啟且使用時(shí)間不會(huì)被延長(zhǎng)的節(jié)點(diǎn)集；2表示已開啟且使用時(shí)間會(huì)被延長(zhǎng)的節(jié)點(diǎn)集；3表示未開啟的節(jié)點(diǎn)集。這樣，3個(gè)節(jié)點(diǎn)集1、2和3是所有可選節(jié)點(diǎn)樣本空間的一個(gè)劃分。

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

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

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

為達(dá)到較好的節(jié)能效果，應(yīng)優(yōu)先選擇已開啟且未延長(zhǎng)使用時(shí)間的節(jié)點(diǎn)，其次選擇已開啟且使用時(shí)間將被延長(zhǎng)的節(jié)點(diǎn)，即3個(gè)節(jié)點(diǎn)集中元素的選中次序?yàn)?→2→3，因此，應(yīng)保證隸屬于3個(gè)節(jié)點(diǎn)集的節(jié)點(diǎn)聯(lián)合概率的平均值滿足如下關(guān)系

于是，定義(A)為

其中，常數(shù)1、2和3分別為節(jié)點(diǎn)集1、2和3的經(jīng)驗(yàn)權(quán)重系數(shù)。為滿足式(12)，應(yīng)設(shè)置權(quán)重系數(shù)大小滿足1>2>3。這里令1+2+3=1。由式(13)，。

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

1) 節(jié)點(diǎn)集1

節(jié)點(diǎn)集1中的節(jié)點(diǎn)都已被開啟，且使用時(shí)間未被延長(zhǎng)，那么，節(jié)點(diǎn)集內(nèi)節(jié)點(diǎn)間的相對(duì)重要性只與CPU資源利用率的增量和資源剩余量有關(guān)。

定義節(jié)點(diǎn)CPU資源剩余量如下

(18)

其中，1和2為經(jīng)驗(yàn)權(quán)重常系數(shù)。表示其該節(jié)點(diǎn)集中資源剩余量最小的節(jié)點(diǎn)，則表示該節(jié)點(diǎn)集中最小的資源剩余量。表示該節(jié)點(diǎn)集中資源剩余量最大的節(jié)點(diǎn)，則表示該節(jié)點(diǎn)集中最大的資源剩余量。表示該節(jié)點(diǎn)集中CPU資源總量最小的節(jié)點(diǎn)，則表示該節(jié)點(diǎn)集中最小的CPU資源總量。表示該節(jié)點(diǎn)集中CPU資源總量最大的節(jié)點(diǎn)，則表示該節(jié)點(diǎn)集中最大的CPU資源總量。1和2為2個(gè)相近的極小正數(shù)，1<2<<1，2用來避免2個(gè)最值相等時(shí)，使分母為0的情況；1用來避免分子為0的情況；當(dāng)所有節(jié)點(diǎn)延長(zhǎng)時(shí)間相等時(shí)，1和2的比值決定了對(duì)這種情況的評(píng)價(jià)值。

定義節(jié)點(diǎn)集1中節(jié)點(diǎn)被選擇的條件概率

2) 節(jié)點(diǎn)集2

節(jié)點(diǎn)集2中的節(jié)點(diǎn)已被開啟且將被延長(zhǎng)使用時(shí)間，延長(zhǎng)使用時(shí)間的長(zhǎng)短對(duì)節(jié)能效果是有影響的，應(yīng)優(yōu)先選擇延長(zhǎng)時(shí)間較短的節(jié)點(diǎn)。另外，加入節(jié)點(diǎn)集1中的2個(gè)評(píng)價(jià)要素，可定義節(jié)點(diǎn)集2中節(jié)點(diǎn)的相對(duì)重要性為

其中，1、2和3為經(jīng)驗(yàn)權(quán)重系數(shù)，表示節(jié)點(diǎn)集2中節(jié)點(diǎn)的最長(zhǎng)延長(zhǎng)時(shí)間，表示該節(jié)點(diǎn)集中節(jié)點(diǎn)的最短延長(zhǎng)時(shí)間，表示節(jié)點(diǎn)將被延長(zhǎng)的時(shí)間。

類似地，定義節(jié)點(diǎn)集2中節(jié)點(diǎn)被選擇的條件概率為

3) 節(jié)點(diǎn)集3

節(jié)點(diǎn)集3中的節(jié)點(diǎn)尚未被開啟，延長(zhǎng)的使用時(shí)間為零，其評(píng)價(jià)要素由節(jié)點(diǎn)的CPU資源總量以及映射虛擬節(jié)點(diǎn)后CPU資源利用率增量決定。

首先定義資源量

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

定義3中節(jié)點(diǎn)被選擇的條件概率

(24)

以上從節(jié)點(diǎn)的開關(guān)狀態(tài)和節(jié)點(diǎn)是否被延長(zhǎng)了使用時(shí)間2個(gè)角度將底層節(jié)點(diǎn)分類，根據(jù)經(jīng)驗(yàn)傾向和各節(jié)點(diǎn)集中元素的數(shù)量確定選擇各集合的概率，即確定邊緣概率；在各節(jié)點(diǎn)集中，從剩余資源量、CPU資源利用率增量以及所延長(zhǎng)的節(jié)點(diǎn)使用時(shí)間這3個(gè)方面，綜合評(píng)價(jià)隸屬各節(jié)點(diǎn)集中物理節(jié)點(diǎn)的相對(duì)重要性，從而確定條件概率。

在節(jié)能目標(biāo)下，為某個(gè)虛擬節(jié)點(diǎn)選擇映射節(jié)點(diǎn)時(shí)，應(yīng)首先為所有可用物理節(jié)點(diǎn)計(jì)算聯(lián)合概率。聯(lián)合概率值越大，說明節(jié)點(diǎn)的重要性越高，節(jié)點(diǎn)越適宜承載該虛擬節(jié)點(diǎn)。

3.3 物理路徑的評(píng)價(jià)標(biāo)準(zhǔn)

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

最后，通過定義節(jié)能路徑長(zhǎng)度來對(duì)虛擬鏈路的多個(gè)可用物理路徑進(jìn)行評(píng)價(jià)。

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

3.4 映射算法

現(xiàn)已設(shè)計(jì)了加入時(shí)間因素的節(jié)點(diǎn)和鏈路節(jié)能評(píng)價(jià)標(biāo)準(zhǔn)，為了便于突出該評(píng)價(jià)標(biāo)準(zhǔn)的優(yōu)勢(shì)，采用較為簡(jiǎn)單的算法——貪婪算法。算法中，在多個(gè)可用節(jié)點(diǎn)中，選擇概率值最高的作為映射節(jié)點(diǎn)；在最短路徑算法[16]得到的多條最短路徑中，選擇值最小的作為映射路徑。

下面對(duì)該算法描述如下。

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

輸入 虛擬網(wǎng)請(qǐng)求拓?fù)?i>G(N,L)，底層網(wǎng)絡(luò)拓?fù)鋱DG(N,L)；

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

1) 將虛擬節(jié)點(diǎn)按照請(qǐng)求資源量的大小降序排序，得到虛擬節(jié)點(diǎn)映射序列：

4) 如果集合中元素個(gè)數(shù)為0，返回NODE_MAP_FAILED；

6) End for

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

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

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

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

13) End for

14) Return MAP_SUCCESS;

最短路徑算法[16]的時(shí)間復(fù)雜度為(|N|log|N|+|N|+|L|)，其中，|N|和|L|分別為底層網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)和鏈路個(gè)數(shù)。由上述流程可知，TEAVNE算法的時(shí)間復(fù)雜度為(|L||N|log|N|+|N||L|+|L||L|+ |N||N|)，其中，|N|和|L|分別為虛擬網(wǎng)請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)和鏈路個(gè)數(shù)。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

同文獻(xiàn)[17]，這里設(shè)置3種不同的實(shí)驗(yàn)場(chǎng)景分別測(cè)試算法的節(jié)能效果。實(shí)驗(yàn)在雙核CPU 3.4 GHz，4 GB內(nèi)存的PC機(jī)上運(yùn)行。底層網(wǎng)絡(luò)拓?fù)浜吞摂M網(wǎng)請(qǐng)求拓?fù)溆蒅T-ITM[18]工具生成。

1) 實(shí)驗(yàn)場(chǎng)景1

將該實(shí)驗(yàn)環(huán)境標(biāo)識(shí)為中等規(guī)模—低集中（medium-sized &low-concentration），實(shí)驗(yàn)設(shè)置同文獻(xiàn)[19]。

底層物理網(wǎng)絡(luò)拓?fù)洌旱讓泳W(wǎng)絡(luò)共包含100個(gè)節(jié)點(diǎn)，每?jī)晒?jié)點(diǎn)間連接的概率為0.5，底層節(jié)點(diǎn)的CPU資源量和底層鏈路的帶寬資源量取值在[50,100]內(nèi)均勻分布。

虛擬網(wǎng)請(qǐng)求拓?fù)洌禾摂M網(wǎng)請(qǐng)求的到達(dá)時(shí)刻服從平均100個(gè)時(shí)間單元到達(dá)5個(gè)請(qǐng)求的泊松過程，持續(xù)時(shí)間服從均值為1 000的指數(shù)分布。每個(gè)請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)在[2,10]內(nèi)均勻分布，節(jié)點(diǎn)連接率為0.5，虛擬節(jié)點(diǎn)請(qǐng)求的CPU資源取值在[0,20]，虛擬鏈路請(qǐng)求的帶寬資源取值在[0, 25]之間均勻分布，虛擬網(wǎng)請(qǐng)求共計(jì)2 500個(gè)，實(shí)驗(yàn)共運(yùn)行50 000個(gè)左右的時(shí)間單元。

2) 實(shí)驗(yàn)場(chǎng)景2

將該實(shí)驗(yàn)環(huán)境標(biāo)識(shí)為中等規(guī)模—中度集中（medium-sized &moderate-concentration），實(shí)驗(yàn)設(shè)置同文獻(xiàn)[17,20~23]。

底層物理網(wǎng)絡(luò)拓?fù)洌壕W(wǎng)絡(luò)設(shè)置同實(shí)驗(yàn)場(chǎng)景1的物理網(wǎng)絡(luò)設(shè)置。

虛擬網(wǎng)請(qǐng)求拓?fù)洌禾摂M網(wǎng)請(qǐng)求的到達(dá)時(shí)刻服從平均100個(gè)時(shí)間單元到達(dá)5個(gè)請(qǐng)求的泊松過程，持續(xù)時(shí)間服從均值為1 000的指數(shù)分布，每個(gè)請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)在[2,20]內(nèi)均勻分布，節(jié)點(diǎn)連接率為0.5，虛擬節(jié)點(diǎn)請(qǐng)求的CPU資源取值在[0,50]，虛擬鏈路請(qǐng)求的帶寬資源取值在[0, 50]之間均勻分布，虛擬網(wǎng)請(qǐng)求共計(jì)2 500個(gè)，實(shí)驗(yàn)共運(yùn)行50 000個(gè)左右的時(shí)間單元。

3) 實(shí)驗(yàn)場(chǎng)景3

將該實(shí)驗(yàn)環(huán)境標(biāo)識(shí)為小規(guī)模—高集中（small- sized & high-concentration），設(shè)置同文獻(xiàn)[17,22~24]。

底層物理網(wǎng)絡(luò)拓?fù)洌旱讓泳W(wǎng)絡(luò)共包含50個(gè)節(jié)點(diǎn)，每?jī)晒?jié)點(diǎn)間連接的概率為0.5，底層節(jié)點(diǎn)的計(jì)算資源和底層鏈路的帶寬資源取值在[50,100]內(nèi)均勻分布。

虛擬網(wǎng)請(qǐng)求拓?fù)洌禾摂M網(wǎng)請(qǐng)求的到達(dá)時(shí)刻服從平均100個(gè)時(shí)間單元到達(dá)4個(gè)請(qǐng)求的泊松過程，持續(xù)時(shí)間服從均值為1 000的指數(shù)分布。每個(gè)請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)在[2,10]內(nèi)均勻分布，節(jié)點(diǎn)連接率為0.5，虛擬節(jié)點(diǎn)請(qǐng)求的CPU資源取值在[0,20]，虛擬鏈路請(qǐng)求的帶寬資源取值在[0, 50]之間均勻分布。虛擬網(wǎng)請(qǐng)求共計(jì)2 000個(gè)，實(shí)驗(yàn)共運(yùn)行50 000個(gè)左右的時(shí)間單元。

4) 其他參數(shù)設(shè)置

在參數(shù)設(shè)置上，同文獻(xiàn)[25~28]中的設(shè)置，得到節(jié)點(diǎn)和鏈路能耗中常數(shù)的值為：為150 W，為300 W，為15 W。其他參數(shù)設(shè)置為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算法是以節(jié)能為目標(biāo)分兩階段映射的貪婪算法，為檢驗(yàn)加入時(shí)間因素的節(jié)點(diǎn)和鏈路評(píng)價(jià)標(biāo)準(zhǔn)的節(jié)能效果，并保證比較的公平性，實(shí)驗(yàn)選取2個(gè)較經(jīng)典的同為兩階段映射的貪婪算法作為比較對(duì)象，即以最大化收益成本比為目標(biāo)的貪婪映射算法SP[20]和同樣以節(jié)能為目標(biāo)的貪婪映射算法EAVNE[8]。

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

4.2.1 對(duì)度量指標(biāo)的定義

1) 能耗度量指標(biāo)

在能耗度量指標(biāo)上做如下5個(gè)定義。

定義平均節(jié)點(diǎn)開啟量（ANON, average number of open nodes）為

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

定義平均節(jié)點(diǎn)資源利用率（AUCPU, average utilization of CPU）為

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

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

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

2) 資源使用情況的度量指標(biāo)

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

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

(33)

由上式可以看出，在映射某個(gè)虛擬網(wǎng)請(qǐng)求時(shí)，收益成本比只和物理路徑的長(zhǎng)度有關(guān)，映射的物理路徑越短，收益成本比越高。

3) 映射時(shí)間長(zhǎng)度的度量指標(biāo)

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

圖2 實(shí)驗(yàn)場(chǎng)景1的映射結(jié)果

4.2.2 對(duì)實(shí)驗(yàn)場(chǎng)景1的結(jié)果分析

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

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

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

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

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

4.2.3 對(duì)實(shí)驗(yàn)場(chǎng)景2的結(jié)果分析

在實(shí)驗(yàn)場(chǎng)景2（medium-sized & moderate- concentration）中，各算法的請(qǐng)求接受率不再是100%。圖3給出了該場(chǎng)景下TEAVNE算法、EAVNE算法和SP算法的映射結(jié)果。

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

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

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

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

這是由于集中映射的方式使部分節(jié)點(diǎn)或鏈路的資源利用率較高，節(jié)點(diǎn)或鏈路的負(fù)載越不均衡，請(qǐng)求接受率越低。

4.2.4 對(duì)實(shí)驗(yàn)場(chǎng)景3的結(jié)果分析

在實(shí)驗(yàn)場(chǎng)景3（small-sized & high-concentration）中，各算法的請(qǐng)求接受率較低。圖4給出了該場(chǎng)景下TEAVNE算法、EAVNE算法和SP算法的映射結(jié)果。

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

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

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

4.2.5 算法映射時(shí)間的比較

TEAVNE算法與同為貪婪算法的SP算法和EAVNE算法運(yùn)行時(shí)間相當(dāng)。

實(shí)驗(yàn)中，底層網(wǎng)絡(luò)分別在3種拓?fù)洵h(huán)境下運(yùn)行所用的平均映射時(shí)間如圖5所示。

可以看出，同為貪婪算法的TEAVNE算法增加了運(yùn)行時(shí)間，這是因?yàn)槠湓诠?jié)點(diǎn)選擇時(shí)增加了對(duì)每個(gè)節(jié)點(diǎn)選擇概率的計(jì)算。但從圖中也可以看出，平均運(yùn)行時(shí)間仍保持在毫秒級(jí)，且增加量比較小。

5 結(jié)束語

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

[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] 林闖, 田源, 姚敏. 綠色網(wǎng)絡(luò)和綠色評(píng)價(jià):節(jié)能機(jī)制、模型和評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào), 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ì)算平臺(tái)的能耗管理[J].計(jì)算機(jī)學(xué)報(bào),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] 陳曉華,李春芝, 陳良育, 等.主動(dòng)休眠節(jié)點(diǎn)鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J]. 軟件學(xué)報(bào), 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] 江逸茗,蘭巨龍, 程?hào)|年,等. 網(wǎng)絡(luò)虛擬化環(huán)境中面向服務(wù)聚合的映射算法[J]. 軟件學(xué)報(bào), 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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2012CB315901）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379079）；河南省科技廳攻關(guān)基金資助項(xiàng)目（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-），女，河南商丘人，鄭州大學(xué)博士生，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化、虛擬網(wǎng)映射等。

莊雷（1963-），女，山東日照人，鄭州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化等。

陳鴻昶（1964-），男，河南鄭州人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)、網(wǎng)絡(luò)安全等。

馬丁（1978-），男，河南鄭州人，鄭州大學(xué)博士生，河南工業(yè)大學(xué)講師，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化等。