彭利民

(華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院，廣東 廣州 510642)

?

高效節(jié)能的虛擬網(wǎng)絡(luò)重構(gòu)算法*

彭利民

(華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院，廣東 廣州 510642)

針對(duì)虛擬網(wǎng)絡(luò)映射中的能耗問(wèn)題，根據(jù)虛擬網(wǎng)絡(luò)重構(gòu)特征以及節(jié)點(diǎn)和鏈路的能耗特性，建立虛擬網(wǎng)絡(luò)重構(gòu)優(yōu)化模型。通過(guò)設(shè)置底層物理網(wǎng)絡(luò)的資源利用率閾值，周期性地將資源利用率大于高閾值和小于低閾值物理節(jié)點(diǎn)和物理鏈路上映射的虛擬節(jié)點(diǎn)和虛擬鏈路遷移到能耗增幅較小的物理節(jié)點(diǎn)和物理鏈路上，并采用節(jié)點(diǎn)、鏈路休眠和喚醒機(jī)制，動(dòng)態(tài)地調(diào)整網(wǎng)絡(luò)中活動(dòng)物理節(jié)點(diǎn)和物理鏈路數(shù)量。模擬結(jié)果表明：EE-VNR算法有效地均衡了底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的負(fù)載水平，提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率，大大地降低了虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。

網(wǎng)絡(luò)虛擬化；網(wǎng)絡(luò)虛擬映射；重構(gòu)；高效節(jié)能；雙閾值

網(wǎng)絡(luò)虛擬化是指通過(guò)整合網(wǎng)絡(luò)的硬件和軟件資源，向用戶提供虛擬網(wǎng)絡(luò)連接的技術(shù)。網(wǎng)絡(luò)虛擬化技術(shù)被公認(rèn)為是解決目前互聯(lián)網(wǎng)僵化問(wèn)題的有效手段。通過(guò)對(duì)公用的底層基礎(chǔ)網(wǎng)絡(luò)設(shè)施采用網(wǎng)絡(luò)虛擬化技術(shù)進(jìn)行抽象并提供統(tǒng)一的可編程接口，可將多個(gè)彼此隔離且具有不同拓?fù)浣Y(jié)構(gòu)的虛擬網(wǎng)絡(luò)映射到同一個(gè)底層物理網(wǎng)絡(luò)上，從而為用戶提供差異化的網(wǎng)絡(luò)服務(wù)。虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化中的一個(gè)關(guān)鍵技術(shù)，它是指將虛擬網(wǎng)絡(luò)(virtual network，VN)映射到底層物理網(wǎng)絡(luò)(substrate network，SN)上，并根據(jù)虛擬網(wǎng)絡(luò)的資源約束條件，將底層物理網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路資源分配給虛擬網(wǎng)絡(luò)請(qǐng)求[1]。目前，大部分的虛擬網(wǎng)絡(luò)映射算法都是以最小化網(wǎng)絡(luò)資源代價(jià)映射虛擬網(wǎng)絡(luò)，以此提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率與系統(tǒng)收益[2]。然而，美國(guó)環(huán)保署公布的一項(xiàng)數(shù)據(jù)表明：當(dāng)前美國(guó)數(shù)據(jù)中心所消耗的電力已占到美國(guó)全部電力使用量的2%，并且其電力需求正在以12%的速度遞增，2008年服務(wù)于互聯(lián)網(wǎng)的路由器、服務(wù)器、交換機(jī)、冷卻設(shè)施和數(shù)據(jù)中心等各種設(shè)施消耗電量達(dá)8 680億度電，占全球總耗電量的5.3%[3]。因此，如何有效地降低網(wǎng)絡(luò)設(shè)備和計(jì)算設(shè)備的能耗，已成為一個(gè)亟待解決的研究課題。

近幾年，學(xué)者們提出了一些能耗感知的虛擬網(wǎng)絡(luò)映射算法。文獻(xiàn)[4]通過(guò)考慮各個(gè)地區(qū)以及各個(gè)時(shí)間段的電價(jià)格差異，建立電能消耗模型，將虛擬節(jié)點(diǎn)映射到電價(jià)較低的節(jié)點(diǎn)上，以此降低虛擬網(wǎng)絡(luò)映射的能耗成本；文獻(xiàn)[5-6]通過(guò)建立虛擬網(wǎng)絡(luò)映射能耗模型，將虛擬節(jié)點(diǎn)和虛擬鏈路映射到活動(dòng)的物理節(jié)點(diǎn)和物理鏈路上，最大限度地關(guān)閉或休眠物理節(jié)點(diǎn)和物理鏈路，以此降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。文獻(xiàn)[2]通過(guò)對(duì)底層網(wǎng)絡(luò)資源利用率采用模擬訓(xùn)練的方法，得到不同映射狀態(tài)下的虛擬網(wǎng)絡(luò)映射字典庫(kù)，然后以字典庫(kù)為藍(lán)本指導(dǎo)虛擬網(wǎng)絡(luò)映射，以最大限度地關(guān)閉或休眠網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)鏈路。雖然這些方法可以降低虛擬網(wǎng)絡(luò)映射的能耗，但由于虛擬網(wǎng)絡(luò)具有較強(qiáng)的動(dòng)態(tài)特性，當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求隨機(jī)到達(dá)或離開(kāi)時(shí)，底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的負(fù)載隨之發(fā)生變化，有些節(jié)點(diǎn)或鏈路的負(fù)載可能較低，有些節(jié)點(diǎn)或鏈路的負(fù)載可能較高甚至可能成為瓶頸資源，不僅浪費(fèi)了大量的系統(tǒng)能耗，而且降低了后續(xù)的虛擬網(wǎng)絡(luò)請(qǐng)求接受率，因此非常有必要應(yīng)用虛擬網(wǎng)絡(luò)重構(gòu)機(jī)制，均衡節(jié)點(diǎn)和鏈路的負(fù)載水平，以提高底層物理網(wǎng)絡(luò)的資源利用率。文獻(xiàn)[7]以最小代價(jià)為約束條件，將虛擬節(jié)點(diǎn)遷移到負(fù)載較低的物理節(jié)點(diǎn)上，以此均衡物理網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載分布。針對(duì)虛擬網(wǎng)絡(luò)的資源需求動(dòng)態(tài)性問(wèn)題，文獻(xiàn)[8]通過(guò)提出可增進(jìn)式重構(gòu)機(jī)制，降低每次虛擬節(jié)點(diǎn)遷移個(gè)數(shù)，以此降低虛擬網(wǎng)絡(luò)重構(gòu)的系統(tǒng)開(kāi)銷。文獻(xiàn)[9]根據(jù)虛擬網(wǎng)絡(luò)資源需求的歷史信息，提出資源需求預(yù)測(cè)模型，然后基于最小資源代價(jià)的虛擬網(wǎng)絡(luò)映射方法重新映射虛擬網(wǎng)絡(luò)請(qǐng)求，以此提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率；文獻(xiàn)[10]在現(xiàn)有的虛擬網(wǎng)絡(luò)映射算法基礎(chǔ)上，提出最小能耗鏈路重構(gòu)算法，減少活動(dòng)物理鏈路使用數(shù)量，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。

綜上所述，現(xiàn)有的虛擬網(wǎng)絡(luò)映射方法大部分是基于最小化網(wǎng)絡(luò)資源代價(jià)映射虛擬網(wǎng)絡(luò)，忽視了虛擬網(wǎng)絡(luò)映射的能耗問(wèn)題；另一方面，雖然已提出的能耗感知虛擬網(wǎng)絡(luò)映射方法可有效地降低虛擬網(wǎng)絡(luò)映射的能耗開(kāi)銷，但由于虛擬網(wǎng)絡(luò)隨機(jī)地到達(dá)和離開(kāi)，底層物理網(wǎng)絡(luò)中容易出現(xiàn)負(fù)載不均衡、系統(tǒng)能耗較高等問(wèn)題。針對(duì)這些問(wèn)題，本文根據(jù)底層物理節(jié)點(diǎn)和鏈路的能耗特性，以及底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的負(fù)載分布狀態(tài)，采用虛擬網(wǎng)絡(luò)重構(gòu)方法，將虛擬節(jié)點(diǎn)和虛擬鏈路動(dòng)態(tài)地遷移到負(fù)載較低、能耗增幅較小的物理節(jié)點(diǎn)和物理鏈路上，均衡物理網(wǎng)絡(luò)的資源分布，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。仿真結(jié)果表明，文中提出的EE-VNR算法有效地均衡了底層物理網(wǎng)絡(luò)的負(fù)載分布狀態(tài)，降低了虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗，提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率。

1 問(wèn)題描述與優(yōu)化模型

高效節(jié)能的虛擬網(wǎng)絡(luò)重構(gòu)是指在保證虛擬網(wǎng)絡(luò)資源約束的前提下，根據(jù)物理節(jié)點(diǎn)和物理鏈路的負(fù)載狀態(tài)，周期地調(diào)整虛擬節(jié)點(diǎn)和虛擬鏈路在底層物理網(wǎng)絡(luò)中的分布位置，并采用休眠和喚醒機(jī)制調(diào)整活動(dòng)節(jié)點(diǎn)和鏈路數(shù)量，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。本節(jié)首先描述虛擬網(wǎng)絡(luò)映射問(wèn)題和底層物理網(wǎng)絡(luò)能耗模型，然后提出虛擬網(wǎng)絡(luò)重構(gòu)優(yōu)化模型。

1.1 虛擬網(wǎng)絡(luò)映射問(wèn)題

圖1 虛擬網(wǎng)絡(luò)映射實(shí)例Fig.1 An example of virtual network embedding

1.2 底層物理網(wǎng)絡(luò)能耗模型

底層物理網(wǎng)絡(luò)的能耗主要包括物理節(jié)點(diǎn)能耗和物理鏈路能耗兩個(gè)部分。物理節(jié)點(diǎn)主要是指服務(wù)器，其能耗主要包括處理器、內(nèi)存、磁盤I/O以及用于冷卻的風(fēng)扇等，其中處理器和內(nèi)存的能耗占節(jié)點(diǎn)能耗的主要部分，目前大部分的處理器，如Intel公司的Speenstep和AMD公司的PowerNow技術(shù)能夠根據(jù)負(fù)載動(dòng)態(tài)地調(diào)節(jié)性能[2]。與文獻(xiàn)[2,4-7]類似，物理節(jié)點(diǎn)的能耗可定義為

(1)

式(1)中Pb是服務(wù)器的基準(zhǔn)能耗，Pm是服務(wù)器最大負(fù)荷下的總能耗，Pa=Pm-Pb是服務(wù)器與負(fù)載相關(guān)的能耗。底層物理網(wǎng)絡(luò)中物理鏈路的能耗主要是鏈路兩端網(wǎng)絡(luò)設(shè)備的能耗Pl，它可以分為靜態(tài)能耗ps和動(dòng)態(tài)能耗pd兩部分，其中，動(dòng)態(tài)能耗與網(wǎng)絡(luò)設(shè)備實(shí)際業(yè)務(wù)負(fù)載量相關(guān)，靜態(tài)能耗獨(dú)立于業(yè)務(wù)負(fù)載量，它取決于網(wǎng)絡(luò)設(shè)備的狀態(tài)，當(dāng)網(wǎng)絡(luò)設(shè)備處于開(kāi)啟狀態(tài)時(shí)靜態(tài)能耗為常量[11]。因此，物理鏈路的能耗可定義為

(2)

式(2)中，η為業(yè)務(wù)負(fù)載量因子，它取決于網(wǎng)絡(luò)設(shè)備的業(yè)務(wù)負(fù)載量，如通過(guò)鏈路的數(shù)據(jù)量。

1.3 虛擬網(wǎng)絡(luò)重構(gòu)優(yōu)化模型

(3)

一個(gè)虛擬網(wǎng)絡(luò)映射的總能耗可表示為

(4)

為了刻畫(huà)底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路負(fù)載的分布狀態(tài)，文中使用資源利用率表示節(jié)點(diǎn)和鏈路的資源狀態(tài)。物理節(jié)點(diǎn)的資源利用率是指物理節(jié)點(diǎn)上已被分配的CPU資源量與節(jié)點(diǎn)CPU資源總量之比，物理鏈路的資源利用率是指分配給虛擬鏈路的帶寬量之和與物理鏈路帶寬總量之比，它們可以定義為

(5)

(6)

式(5)中vi→vs表示虛擬節(jié)點(diǎn)vi被映射到物理節(jié)點(diǎn)vs上，式(6)中l(wèi)uv→lmn表示虛擬鏈路luv被映射到物理鏈路lmn上。

雖然重構(gòu)虛擬網(wǎng)絡(luò)可以提高網(wǎng)絡(luò)性能，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗，但是虛擬網(wǎng)絡(luò)重構(gòu)也需要付出額外的代價(jià)，如虛擬網(wǎng)絡(luò)提供的網(wǎng)絡(luò)服務(wù)可能暫時(shí)中斷等。令RC表示重新映射虛擬網(wǎng)絡(luò)Gv的重構(gòu)代價(jià)，它主要包含遷移虛擬節(jié)點(diǎn)和虛擬鏈路的代價(jià)之和，它可以定義為

(7)

高效節(jié)能的虛擬網(wǎng)絡(luò)重構(gòu)方法的主要目標(biāo)是降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗，同時(shí)減少虛擬網(wǎng)絡(luò)重構(gòu)對(duì)網(wǎng)絡(luò)服務(wù)帶來(lái)的負(fù)面影響，因此虛擬網(wǎng)絡(luò)重構(gòu)的優(yōu)化目標(biāo)可定義為

(8)

式(8)中μ和λ分別表示系統(tǒng)能耗因子P和重構(gòu)代價(jià)因子RC的相應(yīng)權(quán)重。

2 高效節(jié)能的虛擬網(wǎng)絡(luò)重構(gòu)算法

虛擬網(wǎng)絡(luò)重構(gòu)算法分為兩個(gè)階段：① 在物理網(wǎng)絡(luò)中查找最適合遷移的虛擬節(jié)點(diǎn)和虛擬鏈路；② 根據(jù)物理網(wǎng)絡(luò)資源的分布狀態(tài)，將需要遷移的虛擬節(jié)點(diǎn)和虛擬鏈路映射到最合適的物理節(jié)點(diǎn)和物理鏈路上。重構(gòu)算法的核心思想可歸納為：① 根據(jù)底層物理網(wǎng)絡(luò)的資源分布特性，設(shè)置物理節(jié)點(diǎn)和物理鏈路的資源利用率最高閾值和最低閾值；② 根據(jù)底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的負(fù)載狀態(tài)，動(dòng)態(tài)地將資源利用率大于最高閾值以及小于最低閾值的物理節(jié)點(diǎn)(和物理鏈路)上的虛擬節(jié)點(diǎn)(和虛擬鏈路)遷移到能耗增幅較小、資源可用的物理節(jié)點(diǎn)(和物理路徑)上，均衡底層物理網(wǎng)絡(luò)的負(fù)載強(qiáng)度，減少底層物理網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)和活動(dòng)鏈路數(shù)量，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗；③ 根據(jù)虛擬網(wǎng)絡(luò)請(qǐng)求的剩余生存時(shí)間長(zhǎng)短，在重構(gòu)隊(duì)列中優(yōu)先選擇生存時(shí)間較多的虛擬節(jié)點(diǎn)和虛擬鏈路進(jìn)行重構(gòu)，提高虛擬網(wǎng)絡(luò)重構(gòu)對(duì)網(wǎng)絡(luò)性能的改善能力，降低重構(gòu)對(duì)網(wǎng)絡(luò)性能帶來(lái)的負(fù)面影響，優(yōu)化底層物理網(wǎng)絡(luò)的資源分布水平。

算法1：查找遷移虛擬節(jié)點(diǎn)算法

1: Procedure of getting virtual node migrationList

2:for each substrate node sn in snList do {

3:vnList←sn.getVnList()

4:vnList.sortDecreasingLifetime ()

5:snUtil←sn.getUtil()

6:bestFitUtil←Max}∥end for

7:for each snUtil

8:migrationList.add(sn.getVnList())

9:vnList.remove(sn.getVnList())

10: snList.remove(sn)}∥end for

11: if each snUtil>Up_threshhold{

12: wake up a hibermating substrate node sn

13: snList.add(sn)}

14: for each sn in snList do{

15: while snUtil>Up_Threshhold do{

16: for each vn in vnList do {

17:if vn.getUtil()>snUtil-Up_Threshhold{

18: temp←vn.getUtil()-snUtil+Up_Threshhold

19: if temp

20: bestFitUtil←temp

21: bestFitVn←vn}∥end if

22:else if bestFitUtil==MAX then

23: bestFitVn←vn}∥end if

24:break }}∥end while

25: snUtil←snUtil-bestFitVn.getUtil()

26: migrationList.add(bestFitVn)

27: vnList.remove(bestFitVn)

28: return migrationList}∥end for

算法1根據(jù)虛擬節(jié)點(diǎn)的剩余生存時(shí)間進(jìn)行降序排列，優(yōu)先選擇剩余生存時(shí)間較多的虛擬節(jié)點(diǎn)進(jìn)行重構(gòu)(步驟4)；步驟7-10用于將資源利用率小于低閾值物理節(jié)點(diǎn)上映射的虛擬節(jié)點(diǎn)直接加入遷移隊(duì)列中，以便休眠這些節(jié)點(diǎn)，從而降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗；如果底層物理網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)的資源利用率均大于高閾值，則喚醒一個(gè)物理節(jié)點(diǎn)(步驟11-13)；步驟14-27用于將資源利用率大于高閾值的物理節(jié)點(diǎn)上映射的虛擬節(jié)點(diǎn)自適應(yīng)地遷出，均衡底層物理網(wǎng)絡(luò)中的資源分布，提高虛擬網(wǎng)絡(luò)映射請(qǐng)求接受率。算法1的時(shí)間復(fù)雜度為O(|Ns|·|Nv|)，其中，|Ns|和|Nv|分別為物理節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的個(gè)數(shù)。

查找遷移虛擬鏈路算法與算法1基本相同，唯一的差別是每次喚醒物理鏈路的個(gè)數(shù)設(shè)為5，其時(shí)間復(fù)雜度為O(|Ls|·|Lv|)，其中|Ls|和|Lv|分別為物理鏈路和虛擬鏈路的個(gè)數(shù)。

算法2：虛擬節(jié)點(diǎn)和虛擬鏈路重映射算法

1: Procedure of re-mapping virtual nodes and links

2: for each vn in vnList do{

3:minEnergyCons←MAX

4:mappedSn←NULL

5:for all adjacent virtual link vl connected with vn

6:vlList.add(vl)

7:for each sn in snList do{

8:if sn has enough resource for vn then{

9:energyCons←estimateEnergyCons(sn,vn)

10: if energyCons< minEnergyCons then{

11:mappedSn←sn

12:minEnergyCons←energyCons}}}∥end for

13: if mappedSn≠NULL then

14:map vn onto the mappedSn

15: for each vl in vlList do

16:map vl using the minimum energy consumption algorithm

17: for each sn in snList and vl in slList{

18:if sn.getVnList()=NULL or sl.getVlList()=NULL

19:hibernate sn or sl }

20: return mapped result }

算法2首先將與虛擬節(jié)點(diǎn)鄰接的虛擬鏈路加入遷移虛擬鏈路隊(duì)列中，然后將虛擬節(jié)點(diǎn)依次映射到能耗增加最小、資源可用的物理節(jié)點(diǎn)上。這里的資源可用包含兩層含義，其一是指該物理節(jié)點(diǎn)上的可用CPU資源量滿足虛擬節(jié)點(diǎn)的CPU資源需求，并且映射后不會(huì)導(dǎo)致該節(jié)點(diǎn)的資源利用率大于設(shè)置的最高閾值；其二是指物理節(jié)點(diǎn)鄰接鏈路的可用累積鏈路帶寬量大于虛擬節(jié)點(diǎn)鄰接鏈路的累積鏈路帶寬需求量，并且映射后不會(huì)導(dǎo)致物理節(jié)點(diǎn)的鄰接鏈路帶寬利用率大于設(shè)置的最高閾值。步驟15-16是使用最小能耗路由算法將虛擬鏈路映射到能耗最小的物理路徑上。算法2的時(shí)間復(fù)雜度為O(|Nv|·|Ns|+|Lv|·|Ns|2)，其中|Nv|和|Lv|分別為虛擬網(wǎng)絡(luò)中和虛擬節(jié)點(diǎn)和虛假鏈路的個(gè)數(shù)，|Ls|為底層物理網(wǎng)絡(luò)中物理鏈路的個(gè)數(shù)。

3 仿真實(shí)驗(yàn)

為了測(cè)試EE-VNR算法的網(wǎng)絡(luò)性能，本文通過(guò)設(shè)計(jì)一個(gè)離散事件仿真實(shí)驗(yàn)，從資源利用率方差、系統(tǒng)能耗和虛擬網(wǎng)絡(luò)請(qǐng)求接受率等三個(gè)方面對(duì)EE-VNR算法進(jìn)行性能測(cè)試。文中選擇文獻(xiàn)[12]中的虛擬網(wǎng)絡(luò)映射算法映射虛擬網(wǎng)絡(luò)，并用TA-VNM表示文獻(xiàn)[12]中的虛擬網(wǎng)絡(luò)映射算法。用TA-VNM+LC-VNR表示在文獻(xiàn)[12]的基礎(chǔ)上采用文獻(xiàn)[7]中LC-VNR算法重構(gòu)后的映射過(guò)程，用TA-VNM+EE-VNR表示在文獻(xiàn)[12]的基礎(chǔ)上采用本文EE-VNR算法重構(gòu)后的映射過(guò)程。

3.1 仿真環(huán)境

與文獻(xiàn)[12]類似，仿真實(shí)驗(yàn)采用GT-ITM工具[13]隨機(jī)生成一個(gè)由100個(gè)物理節(jié)點(diǎn)、560條鏈路組成的底層物理網(wǎng)絡(luò)拓?fù)?，每個(gè)物理節(jié)點(diǎn)的初始狀態(tài)為關(guān)閉狀態(tài)，物理節(jié)點(diǎn)的CPU資源量和物理鏈路的帶寬量服從50-100的均勻分布。虛擬網(wǎng)絡(luò)請(qǐng)求過(guò)程模擬泊松過(guò)程，每100個(gè)時(shí)間單元內(nèi)虛擬網(wǎng)絡(luò)請(qǐng)求個(gè)數(shù)服從均值為20的泊松分布，每個(gè)虛擬網(wǎng)絡(luò)的生存時(shí)間服從均值為500個(gè)時(shí)間單元的指數(shù)分布，每個(gè)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)服從2-10的均勻分布，每對(duì)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)以0.5的概率隨機(jī)相連，虛擬網(wǎng)絡(luò)節(jié)點(diǎn)CPU資源需求量與虛擬鏈路的帶寬需求量服從1-20的均勻分布。仿真期間內(nèi)隨機(jī)選擇10%的虛擬網(wǎng)絡(luò)，并使其節(jié)點(diǎn)和鏈路的資源需求量在1-20隨機(jī)動(dòng)態(tài)變化。物理節(jié)點(diǎn)的基準(zhǔn)能耗均設(shè)置為150W，最大能耗為300W，物理鏈路的靜態(tài)能耗設(shè)置為10W，動(dòng)態(tài)能耗設(shè)置為5W。1.3節(jié)式(7)中參數(shù)α和β分別設(shè)置為0.5、式(8)中參數(shù)μ和λ分別設(shè)置為1和10，重構(gòu)周期T設(shè)置為1000個(gè)時(shí)間單元，節(jié)點(diǎn)資源利用率的最高閾值設(shè)置為75%，最低閾值設(shè)置為25%。每次模擬實(shí)驗(yàn)運(yùn)行約為50 000個(gè)時(shí)間單元，包含10 000個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，共進(jìn)行10次仿真實(shí)驗(yàn)，然后取10次實(shí)驗(yàn)的平均值為實(shí)驗(yàn)最終結(jié)果。

3.2 實(shí)驗(yàn)結(jié)果

1) EE-VNR算法均衡了底層物理網(wǎng)絡(luò)的負(fù)載水平

如圖2和圖3可以看出，通過(guò)在TA-VNM算法的基礎(chǔ)上使用EE-VNR算法后，底層物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的資源利用率方差比TA-VNM算法的方差大大地減少。其主要原因是由于EE-VNR算法通過(guò)利用資源利用率最低閾值，在虛擬網(wǎng)絡(luò)重構(gòu)時(shí)能有效地休眠資源利用率較低的物理節(jié)點(diǎn)和鏈路。特別是在模擬開(kāi)始階段虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)目較小、網(wǎng)絡(luò)資源充足時(shí)，節(jié)點(diǎn)和鏈路的資源利用率方差比LC-VNR算法的資源利用率方差大大降低。實(shí)驗(yàn)結(jié)果表明，EE-VNR算法能有效地均衡底層物理網(wǎng)絡(luò)中的負(fù)載水平。

圖2 節(jié)點(diǎn)資源利用率Fig.2 Node resource utilization ratio

圖3 鏈路資源利用率Fig.3 Link resource utilization ratio

2) EE-VNR算法降低了虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗

如圖4所示，通過(guò)在TA-VNM算法的基礎(chǔ)上使用EE-VNR重構(gòu)算法，虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗比其它兩個(gè)算法大大地減少。實(shí)驗(yàn)結(jié)果表明：EE-VNR算法能有效地利用設(shè)定的資源利用率閾值，動(dòng)態(tài)地休眠資源利用率較低的物理節(jié)點(diǎn)和鏈路；在虛擬節(jié)點(diǎn)和虛擬鏈路遷移時(shí)，EE-VNR算法有效地將虛擬節(jié)點(diǎn)和虛擬鏈路合理地遷移到能耗增幅較小的物理節(jié)點(diǎn)和鏈路上，有效地降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。

圖4 虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗Fig.4 The system energy consumption of mapping virtual networks

3) EE-VNR算法提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率

如圖5所示，通過(guò)在TA-VNM算法的基礎(chǔ)上使用LC-VNR和EE-VNR重構(gòu)算法，虛擬網(wǎng)絡(luò)請(qǐng)求接受率都呈現(xiàn)較大幅度的提升。實(shí)驗(yàn)結(jié)果表明：EE-VNR算法能有效地均衡底層物理網(wǎng)絡(luò)中的負(fù)載水平。特別是在模擬階段后期網(wǎng)絡(luò)資源相對(duì)緊張時(shí)，EE-VNR算法可有效地緩解了資源瓶頸問(wèn)題，從而顯著地提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率。

圖5 虛擬網(wǎng)絡(luò)請(qǐng)求接受率Fig.5 The acceptance ratio of virtual network requests

4 結(jié) 語(yǔ)

針對(duì)網(wǎng)絡(luò)虛擬化環(huán)境下的系統(tǒng)能耗問(wèn)題，本文通過(guò)分析底層物理網(wǎng)絡(luò)中負(fù)載動(dòng)態(tài)變化的主要原因，通過(guò)應(yīng)用資源利用率雙閾值方法，周期性地根據(jù)節(jié)點(diǎn)和鏈路的負(fù)載水平，動(dòng)態(tài)地調(diào)整底層物理網(wǎng)絡(luò)中網(wǎng)絡(luò)資源的分布狀態(tài)，并通過(guò)采用節(jié)點(diǎn)、鏈路休眠和喚醒機(jī)制，自適應(yīng)地控制底層物理網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)和活動(dòng)鏈路數(shù)量。仿真結(jié)果表明：文中提出的EE-VNR算法可有效地均衡底層物理網(wǎng)絡(luò)中的負(fù)載水平，提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率，降低虛擬網(wǎng)絡(luò)映射的系統(tǒng)能耗。

[1] 李小玲，王懷民，丁博，等. 虛擬網(wǎng)絡(luò)映射問(wèn)題及其進(jìn)展[J]. 軟件學(xué)報(bào), 2012, 23(11): 3009-3028.

[2] 陳曉華, 李春芝, 陳良育，等.主動(dòng)休眠節(jié)點(diǎn)鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報(bào), 2014, 25(7): 1416-1431.

[3] 張法, ANTA A F, 王林，等. 網(wǎng)絡(luò)能耗系統(tǒng)模型及能效算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(3): 603-615.

[4] AMOKRANE A, ZHANI M F, LANGAR R, et al. Greenhead: Virtual data center embedding across distributed infrastructures [J]. IEEE Transactions on Cloud Computing, 2013, 1(1): 36-49.

[5] CHANG X L, WANG B, LIU J Q, et al. Green cloud virtual network provisioning based ant colony optimization [C]∥Proceeding of the 15th Annual Conference. Companion on Genetic and Evolutionary Computation. New York: ACM Press, 2013:1553-1560.

[6] FISCHER A, BECK M T, MEER H D. An approach to energy-efficient virtual network embeddings [C]∥Proceeding of the 2013 IFIP/IEEE International Symposium on Integrated Network Management. Ghent: IEEE, 2013:1142-1147.

[7] 曲樺，趙季紅，郭爽樂(lè)，等. 基于最小代價(jià)的虛擬網(wǎng)絡(luò)重配置方法[J]. 北京郵電大學(xué)學(xué)報(bào), 2014, 37(5): 114-118.[8] ZHOU Y, YANG X, JIN Y, et al. Incremental re-embedding scheme for evolving virtual network requests [J]. IEEE communications letters, 2013, 17(5): 1016-1019.

[9] XU Z C, LIANG W F, XIA Q F. Efficient virtual network embedding via exploring periodic resource demands[C]∥Proceeding of the 39thAnnual IEEE Conference on Local Computer Networks. Edmonton, Canada: IEEE, 2014: 90-98.

[10] GHAZISAEEDI E, WANG N, TAFAZOLLI R. Link sleeping optimization for green virtual network infrastructures [C]∥The 4thIEEE International Workshop on Management of Emerging Networks and Services. Anaheim, CA: IEEE, 2012: 842-846.[11] 伍元?jiǎng)?，郭兵，沈艷，等. 面向核心網(wǎng)的多層網(wǎng)絡(luò)能耗優(yōu)化方法[J].計(jì)算機(jī)學(xué)報(bào), 2013, 36(7): 1538-1548.

[12] LI X L, WANG H M,GUO C G, et al. Topology awareness algorithm for virtual network mapping [J]. Journal of Zhejiang University-Science C (Computers & Electronic), 2012, 13(3): 178-186.

[13] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an internetwork[C]∥Proceeding of the 15th Annual Joint conference of the IEEE Computer and Communications Society. San Francisco, USA: IEEE, 1996: 594-602.

An Energy Efficient Virtual Network Reconfiguration Algorithm

PENGLimin

(College of Mathematics and Informatics, South China Agricultural University, Guangzhou 510642, China)

Aiming at the problem of energy consumption in the virtual network mapping, according to the characteristics of the virtual network reconfiguration and energy consumption of substrate nodes and links, a reconfiguration optimization model of mapping virtual networks is proposed. By setting resource utilization threshold in the substrate network, virtual nodes that are already mapped onto substrate nodes, which resource utilization is greater than the high threshold or less than low threshold, are remapped onto the substrate nodes consuming smaller energy periodically, the same operation as the virtual links. By using the method of hibernating and waking up substrate nodes and links, the number of active substrate nodes and substrate links in the substrate network are adjusted dynamically. Simulation results show that EE-VNR algorithm balances the substrate nodes and links load effectively, improves the acceptance ratio of virtual network requests and reduces the system energy consumption of mapping virtual networks evidently.

network virtualization; virtual network mapping; reconfiguration; energy efficient; double threshold

10.13471/j.cnki.acta.snus.2015.05.002

2014-12-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61103037)；廣東省自然科學(xué)基金資助項(xiàng)目(S2012040007599)

彭利民(1976年生)，男；研究方向：網(wǎng)絡(luò)虛擬化、分布式計(jì)算;E-mail:penglm86@126.com

TP393

A

0529-6579(2015)05-0005-06