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

劉認倫，孫冬冬

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

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

劉認倫，孫冬冬

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

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

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

0 引 言

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

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

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

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

1 網(wǎng)絡模型

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

1.1 輸入及變量

(1)輸入。

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

(2)變量。

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

目標函數(shù)：

約束條件：

傳輸約束：

流約束：

容量約束：

二進制約束：

一個虛擬節(jié)點僅對應一個物理節(jié)點約束：

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

2 性能評估

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

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

(a)節(jié)點節(jié)約的能量

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

(c)虛擬網(wǎng)絡請求接受率

采用三個不同的映射標準將兩種算法進行對比，分別是未激活的節(jié)點比率、未激活的鏈路比率和虛擬網(wǎng)絡請求接受率。從結(jié)果中可得結(jié)論：

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

未激活的鏈路比率相比于VNE-EA有較高的提升。因為流分割使鏈路利用率得到了提升，所以網(wǎng)絡激活的鏈路數(shù)量較少，未激活的鏈路數(shù)量較多。

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

3 結(jié)束語

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

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

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

[2] 王 博,陳庶樵,王志明,等.基于中心度尋核的能效優(yōu)化虛擬網(wǎng)映射算法[J].計算機應用研究,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)絡出版時間：2017-03-13

國家自然科學基金資助項目(61372124)；國家“973”重點基礎(chǔ)研究發(fā)展計劃項目(2013CB329104)

劉認倫(1991-)，男，碩士，研究方向為移動通信與無線技術(shù)；導師：楊龍祥，教授，博士生導師，研究方向為移動無線通信系統(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