基于可分割流的虛擬網(wǎng)絡(luò)映射節(jié)能算法

劉認(rèn)倫，孫冬冬

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

基于可分割流的虛擬網(wǎng)絡(luò)映射節(jié)能算法

劉認(rèn)倫，孫冬冬

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

據(jù)統(tǒng)計(jì)，工業(yè)國(guó)家中，信息與通信技術(shù)的能量消耗占所有產(chǎn)業(yè)能耗的10%左右。為了解決通信中網(wǎng)絡(luò)設(shè)備的能耗問題，節(jié)能技術(shù)應(yīng)運(yùn)而生。虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化的關(guān)鍵技術(shù)之一，越來越多的場(chǎng)合下都能夠見到虛擬網(wǎng)絡(luò)映射的應(yīng)用。虛擬網(wǎng)絡(luò)映射過程中，可能由于物理資源利用不充分，從而導(dǎo)致資源和能量利用得不合理。盡管對(duì)有關(guān)虛擬網(wǎng)絡(luò)映射節(jié)能的算法與方案已進(jìn)行了較為充分的研究，但虛擬網(wǎng)絡(luò)映射的節(jié)能算法仍有研究的價(jià)值。為節(jié)省物理網(wǎng)絡(luò)資源，提出了一種基于可分割流的虛擬網(wǎng)絡(luò)映射節(jié)能算法，并給出了算法所用的網(wǎng)絡(luò)模型和公式以及基于可分割流的能量感知虛擬網(wǎng)絡(luò)映射混合整數(shù)規(guī)劃公式。仿真結(jié)果表明，提出算法在網(wǎng)絡(luò)節(jié)能上具有較顯著的效果。

虛擬網(wǎng)絡(luò)映射；可分割流；能量感知；節(jié)能

0 引 言

網(wǎng)絡(luò)虛擬化技術(shù)能夠使多個(gè)異構(gòu)網(wǎng)絡(luò)共存于同一個(gè)物理實(shí)體中，這種技術(shù)可以克服互聯(lián)網(wǎng)技術(shù)發(fā)展中的一些關(guān)鍵性難題。虛擬網(wǎng)絡(luò)映射(Virtual Network Embedding)是一種將虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò)的技術(shù)，近年來有關(guān)虛擬網(wǎng)絡(luò)映射的研究已經(jīng)相當(dāng)充分，國(guó)內(nèi)的相關(guān)研究也得到了一定發(fā)展[1-2]。能量感知的虛擬網(wǎng)絡(luò)映射(見圖1)是近年來在虛擬網(wǎng)絡(luò)映射課題研究中出現(xiàn)的新方向，這個(gè)方向?qū)⒅攸c(diǎn)從傳統(tǒng)的注重網(wǎng)絡(luò)收益轉(zhuǎn)移到注重網(wǎng)絡(luò)能耗上來。據(jù)統(tǒng)計(jì)，大型骨干網(wǎng)中的鏈路平均利用率約為30%～40%[3]，這一現(xiàn)狀使得虛擬網(wǎng)絡(luò)映射在節(jié)能方面的研究有了充分可能。

網(wǎng)絡(luò)虛擬化的關(guān)鍵性問題是資源分配，節(jié)能的虛擬網(wǎng)絡(luò)映射算法的基本思想是將盡可能多的虛擬網(wǎng)絡(luò)請(qǐng)求映射到相同的物理資源上，同時(shí)關(guān)閉未被映射到的資源。當(dāng)物理網(wǎng)絡(luò)中越多的節(jié)點(diǎn)與鏈路處于開啟狀態(tài)，網(wǎng)絡(luò)能耗越高，節(jié)能的算法使網(wǎng)絡(luò)中的能量消耗集中在很少的物理實(shí)體上。

假設(shè)虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬鏈路是可分割的，提出了一種基于可分割流的虛擬網(wǎng)絡(luò)映射節(jié)能算法，并在文獻(xiàn)[4]提出算法的基礎(chǔ)上進(jìn)行了改進(jìn)，同時(shí)參考了文獻(xiàn)[5-9]中的方法，提出了基于可分割流的混合整數(shù)規(guī)劃(Mixed Integer Program based on Flow Splitting)解決該問題。仿真結(jié)果表明，該算法能夠節(jié)省較多的鏈路能耗，提高了網(wǎng)絡(luò)接收率。

圖1 能量感知虛擬網(wǎng)絡(luò)映射(左)與基于可分割

1 網(wǎng)絡(luò)模型

首先介紹算法中使用的網(wǎng)絡(luò)模型，給出算法的基本輸入和變量，然后給出基于可分割流的能量感知虛擬網(wǎng)絡(luò)映射混合整數(shù)規(guī)劃。為簡(jiǎn)單起見，網(wǎng)絡(luò)資源的能量消耗將被視為同一種類型的。

1.1 輸入及變量

(1)輸入。

物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的模型均使用有向圖拓?fù)洌謩e用G(V,A)和Gk(Vk,Ak)表示，其中V,Vk分別表示物理節(jié)點(diǎn)和虛擬節(jié)點(diǎn)集合，A,Ak分別表示物理鏈路和虛擬鏈路集合；NDPP(ik)表示虛擬節(jié)點(diǎn)ik的帶寬及過程能量請(qǐng)求；LDBW(ik,jk)表示虛擬鏈路(ik,jk)的帶寬請(qǐng)求；NRPP(i)表示物理節(jié)點(diǎn)的帶寬及過程能量資源；LRBW(i,j)表示物理鏈路的帶寬資源；MaxDegree表示物理網(wǎng)絡(luò)中的最大節(jié)點(diǎn)度。物理節(jié)點(diǎn)和鏈路分別有兩種狀態(tài)，喚醒和休眠(或者開啟和關(guān)閉)，為了區(qū)別這兩種狀態(tài)，網(wǎng)絡(luò)模型中使用二進(jìn)制數(shù)表示不同的狀態(tài)。NOi,LO(i,j)均是二進(jìn)制參數(shù)變量，取“1”時(shí)分別表示物理節(jié)點(diǎn)或物理鏈路在映射前處于激活狀態(tài)，“0”反之；match(ik)表示可用于映射虛擬節(jié)點(diǎn)ik的候選物理節(jié)點(diǎn)集合；match(ik,jk)表示可用于映射虛擬鏈路(i,j)的第n條分割鏈路(ik,jk)n的候選物理鏈路集合。

(2)變量。

1.2 基于可分割流的能量感知虛擬網(wǎng)絡(luò)映射混合整數(shù)規(guī)劃

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

約束條件：

傳輸約束：

流約束：

容量約束：

二進(jìn)制約束：

一個(gè)虛擬節(jié)點(diǎn)僅對(duì)應(yīng)一個(gè)物理節(jié)點(diǎn)約束：

激活的物理節(jié)點(diǎn)約束：

2 性能評(píng)估

ALEVIN仿真軟件能夠?qū)λ惴ㄟM(jìn)行仿真實(shí)現(xiàn)與性能分析。ALEVIN是由A.Fisher等開發(fā)的一種專門針對(duì)虛擬網(wǎng)絡(luò)映射算法進(jìn)行開發(fā)、比較、分析的仿真平臺(tái)，文獻(xiàn)[5]中有其功能及使用的詳細(xì)描述。VNE-EA-FS算法的性能將與文獻(xiàn)[4]中的VNE-EA算法進(jìn)行比較。

仿真結(jié)果如圖2所示。

(a)節(jié)點(diǎn)節(jié)約的能量

(b)鏈路節(jié)約的能量

(c)虛擬網(wǎng)絡(luò)請(qǐng)求接受率

采用三個(gè)不同的映射標(biāo)準(zhǔn)將兩種算法進(jìn)行對(duì)比，分別是未激活的節(jié)點(diǎn)比率、未激活的鏈路比率和虛擬網(wǎng)絡(luò)請(qǐng)求接受率。從結(jié)果中可得結(jié)論：

在網(wǎng)絡(luò)負(fù)載非常低的時(shí)候(20%～30%)，就未激活的節(jié)點(diǎn)比率而言，VNE-EA-FS算法表現(xiàn)略低于VNE-EA，但在負(fù)載比較低與負(fù)載高的情況下，VNE-EA-FS得到的結(jié)果略高于VNE-EA。造成這一結(jié)果的原因是在負(fù)載非常的環(huán)境下，流分割可能造成映射的物理路徑中包含了隱藏跳(hiddenhops)[7，10-12]，從而增加了網(wǎng)絡(luò)中的物理節(jié)點(diǎn)數(shù)量?，F(xiàn)如今，啟發(fā)式和元啟發(fā)式的算法也相繼提出[13-17]，未來有望解決這一問題。

未激活的鏈路比率相比于VNE-EA有較高的提升。因?yàn)榱鞣指钍规溌防寐实玫搅颂嵘跃W(wǎng)絡(luò)激活的鏈路數(shù)量較少，未激活的鏈路數(shù)量較多。

虛擬網(wǎng)絡(luò)請(qǐng)求接受率在負(fù)載低時(shí)，兩種算法的接受率大致相同；在負(fù)載高的情況下，提出算法接受率有較小的提升。在負(fù)載較高的情況下，資源利用率變高，從而使虛擬網(wǎng)絡(luò)請(qǐng)求接受率變高。

3 結(jié)束語(yǔ)

為提高網(wǎng)絡(luò)的節(jié)能性能，提出了一種基于可分割流的虛擬網(wǎng)絡(luò)映射精簡(jiǎn)式節(jié)能算法。假設(shè)虛擬網(wǎng)絡(luò)請(qǐng)求中的虛擬鏈路是可分割的。在精簡(jiǎn)式的節(jié)能算法基礎(chǔ)上，在典型的節(jié)點(diǎn)節(jié)能算法中結(jié)合了鏈路分割，映射過程中，在映射節(jié)點(diǎn)之后，依據(jù)鏈路約束條件對(duì)鏈路進(jìn)行映射，在不滿足約束時(shí)，將鏈路分割成多條鏈路映射。這樣在映射時(shí)，物理鏈路的帶寬資源可以得到充分利用，從而提高了整體的映射性能。

仿真結(jié)果表明，在小規(guī)模網(wǎng)絡(luò)中，與VNE-EA算法相比，流分割能夠提高物理網(wǎng)絡(luò)中的鏈路利用率，從而節(jié)省較多的物理鏈路。在網(wǎng)絡(luò)負(fù)載很低的情況下，物理節(jié)點(diǎn)利用率略低于VNE-EA，這是因?yàn)榱鞣指罘椒ㄒ肓穗[藏跳問題，使物理鏈路在映射時(shí)經(jīng)過了未激活的節(jié)點(diǎn)；然而，在網(wǎng)絡(luò)負(fù)載較高的情況下，物理節(jié)點(diǎn)的利用率也有較小提高，物理網(wǎng)絡(luò)中激活的物理節(jié)點(diǎn)數(shù)變少，并且提升了虛擬網(wǎng)絡(luò)接受率。

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

[2] 王 博,陳庶樵,王志明,等.基于中心度尋核的能效優(yōu)化虛擬網(wǎng)映射算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(7):2087-2091.

[3]FisherW,SucharaM,RexfordJ.Greeningbackbonenetworks:reducingenergyconsumptionbyshuttingoffcablesinbundledlinks[C]//ACMSIGCOMMworkshopongreennetworking2010.NewDelhi,India:ACM,2010:29-34.

[4]BoteroJF,HesselbachX,DuelliM,etal.Energyefficientvirtualnetworkembedding[J].IEEECommunicationsLetters,2012,16(5):756-759.

[5]FischerA,BeckMT,deMeerH.Anapproachtoenergy-efficientvirtualnetworkembeddings[C]//IFIP/IEEEinternationalsymposiumonintegratednetworkmanagement.[s.l.]:IEEE,2013:1142-1147.

[6]SuS,ZhangZ,ChengX,etal.Energy-awarevirtualnetworkembeddingthroughconsolidation[C]//IEEEconferenceoncomputercommunicationsworkshops.[s.l.]:IEEE,2012:127-132.

[7]BoteroJF,HesselbachX,FischerA,etal.Optimalmappingofvirtualnetworkswithhiddenhops[J].TelecommunicationSystems,2012,51(4):273-282.

[8]GhazisaeediE,HuangC.Off-Peakenergyoptimizationforlinksinvirtualizednetworkenvironment[J].IEEETransactionsonCloudComputing,2015,99:1.

[9]GhazisaeediE,HuangC,YanJ.Off-peakenergy-wiselinkreconfigurationforvirtualizednetworkenvironment[C]//IFIP/IEEEinternationalsymposiumonintegratednetworkmanagement.[s.l.]:IEEE,2015:814-817.

[10]BianzinoAP,ChaudetC,RossiD,etal.Asurveyofgreennetworkingresearch[J].IEEECommunicationsSurveys&Tutorials,2012,14(1):3-20.

[11]NondeL,El-GorashiTEH,ElmirghaniJMH.Energyefficientvirtualnetworkembeddingforcloudnetworks[J].JournalofLightwaveTechnology,2015,33(9):1828-1849.

[12]BoteroJF,HesselbachX.Greenernetworkinginanetworkvirtualizationenvironment[J].ComputerNetworks,2013,57(9):2021-2039.

[13]TrikiN,KaraN,BarachiME,etal.Agreenenergy-awarehybridvirtualnetworkembeddingapproach[J].ComputerNetworks,2015,91(C):712-737.

[14]LiraV,TavaresE.Energy-awaremappingfordependablevirtualnetworks[C]//Internationalworkshoponpowerandtimingmodeling,optimizationandsimulation.[s.l.]:IEEE,2015.

[15]GuanX,ChoiBY,SongS.Energyefficientvirtualnetworkembeddingforgreendatacentersusingdatacentertopologyandfuturemigration[J].ComputerCommunications,2015,69:50-59.

[16]GuanX,ChoiBY,SongS.Topologyandmigration-awareenergyefficientvirtualnetworkembeddingforgreendatacenters[C]//Internationalconferenceoncomputercommunicationandnetworks.[s.l.]:IEEE,2014:1-8.

[17]MeloM,SargentoS,KillatU,etal.Optimalvirtualnetworkembedding:energyawareformulation[J].IEEETransactionsonNetwork&ServiceManagement,2013,10(4):1-13.

Energy Aware Virtual Network Embedding Based on Flow Splitting

LIU Ren-lun，SUN Dong-dong

(College of Communication and Information Engineering,Nanjing University ofPosts and Telecommunications,Nanjing 210003,China)

It is estimated that energy consumption in Information and Communication Technology account for 10% of the total energy consumed in industrial countries.In order to solve the problem of energy consumption in network infrastructure,the technology of energy saving is invented.Virtual Network Embedding (VNE) is one of the critical technology for network virtualization and it is applied for more and more network environment.Insufficient utilization of substrate resource may exist in VNE,resulting in unreasonable usage of resource and energy.Although the research of energy aware VNE has been studied sufficiently,it is valuable to do research on it.An energy-aware virtual network embedding algorithm based on flow splitting is proposed,aiming at energy saving.The network model and the mixed integer program of energy aware virtual network embedding based on flow splitting are proposed.The simulation results demonstrate that the proposed algorithm has better performance in terms of energy saving.

virtual network embedding；flow splitting；energy aware；energy saving

2016-05-23

2016-09-13 網(wǎng)絡(luò)出版時(shí)間：2017-03-13

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372124)；國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329104)

劉認(rèn)倫(1991-)，男，碩士，研究方向?yàn)橐苿?dòng)通信與無線技術(shù)；導(dǎo)師：楊龍祥，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)無線通信系統(tǒng)和物聯(lián)網(wǎng)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1545.014.html

TP301.6

A

1673-629X(2017)05-0051-03

10.3969/j.issn.1673-629X.2017.05.011