基于可分割流的虚拟网络映射节能算法

刘认伦，孙冬冬

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

基于可分割流的虚拟网络映射节能算法

刘认伦，孙冬冬

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

据统计，工业国家中，信息与通信技术的能量消耗占所有产业能耗的10%左右。为了解决通信中网络设备的能耗问题，节能技术应运而生。虚拟网络映射是网络虚拟化的关键技术之一，越来越多的场合下都能够见到虚拟网络映射的应用。虚拟网络映射过程中，可能由于物理资源利用不充分，从而导致资源和能量利用得不合理。尽管对有关虚拟网络映射节能的算法与方案已进行了较为充分的研究，但虚拟网络映射的节能算法仍有研究的价值。为节省物理网络资源，提出了一种基于可分割流的虚拟网络映射节能算法，并给出了算法所用的网络模型和公式以及基于可分割流的能量感知虚拟网络映射混合整数规划公式。仿真结果表明，提出算法在网络节能上具有较显著的效果。

虚拟网络映射；可分割流；能量感知；节能

0 引 言

网络虚拟化技术能够使多个异构网络共存于同一个物理实体中，这种技术可以克服互联网技术发展中的一些关键性难题。虚拟网络映射(Virtual Network Embedding)是一种将虚拟网络映射到物理网络的技术，近年来有关虚拟网络映射的研究已经相当充分，国内的相关研究也得到了一定发展[1-2]。能量感知的虚拟网络映射(见图1)是近年来在虚拟网络映射课题研究中出现的新方向，这个方向将重点从传统的注重网络收益转移到注重网络能耗上来。据统计，大型骨干网中的链路平均利用率约为30%～40%[3]，这一现状使得虚拟网络映射在节能方面的研究有了充分可能。

网络虚拟化的关键性问题是资源分配，节能的虚拟网络映射算法的基本思想是将尽可能多的虚拟网络请求映射到相同的物理资源上，同时关闭未被映射到的资源。当物理网络中越多的节点与链路处于开启状态，网络能耗越高，节能的算法使网络中的能量消耗集中在很少的物理实体上。

假设虚拟网络请求的虚拟链路是可分割的，提出了一种基于可分割流的虚拟网络映射节能算法，并在文献[4]提出算法的基础上进行了改进，同时参考了文献[5-9]中的方法，提出了基于可分割流的混合整数规划(Mixed Integer Program based on Flow Splitting)解决该问题。仿真结果表明，该算法能够节省较多的链路能耗，提高了网络接收率。

图1 能量感知虚拟网络映射(左)与基于可分割

1 网络模型

首先介绍算法中使用的网络模型，给出算法的基本输入和变量，然后给出基于可分割流的能量感知虚拟网络映射混合整数规划。为简单起见，网络资源的能量消耗将被视为同一种类型的。

1.1 输入及变量

(1)输入。

物理网络和虚拟网络的模型均使用有向图拓扑，分别用G(V,A)和Gk(Vk,Ak)表示，其中V,Vk分别表示物理节点和虚拟节点集合，A,Ak分别表示物理链路和虚拟链路集合；NDPP(ik)表示虚拟节点ik的带宽及过程能量请求；LDBW(ik,jk)表示虚拟链路(ik,jk)的带宽请求；NRPP(i)表示物理节点的带宽及过程能量资源；LRBW(i,j)表示物理链路的带宽资源；MaxDegree表示物理网络中的最大节点度。物理节点和链路分别有两种状态，唤醒和休眠(或者开启和关闭)，为了区别这两种状态，网络模型中使用二进制数表示不同的状态。NOi,LO(i,j)均是二进制参数变量，取“1”时分别表示物理节点或物理链路在映射前处于激活状态，“0”反之；match(ik)表示可用于映射虚拟节点ik的候选物理节点集合；match(ik,jk)表示可用于映射虚拟链路(i,j)的第n条分割链路(ik,jk)n的候选物理链路集合。

(2)变量。

1.2 基于可分割流的能量感知虚拟网络映射混合整数规划

目标函数：

约束条件：

传输约束：

流约束：

容量约束：

二进制约束：

一个虚拟节点仅对应一个物理节点约束：

激活的物理节点约束：

2 性能评估

ALEVIN仿真软件能够对算法进行仿真实现与性能分析。ALEVIN是由A.Fisher等开发的一种专门针对虚拟网络映射算法进行开发、比较、分析的仿真平台，文献[5]中有其功能及使用的详细描述。VNE-EA-FS算法的性能将与文献[4]中的VNE-EA算法进行比较。

仿真结果如图2所示。

(a)节点节约的能量

(b)链路节约的能量

(c)虚拟网络请求接受率

采用三个不同的映射标准将两种算法进行对比，分别是未激活的节点比率、未激活的链路比率和虚拟网络请求接受率。从结果中可得结论：

在网络负载非常低的时候(20%～30%)，就未激活的节点比率而言，VNE-EA-FS算法表现略低于VNE-EA，但在负载比较低与负载高的情况下，VNE-EA-FS得到的结果略高于VNE-EA。造成这一结果的原因是在负载非常的环境下，流分割可能造成映射的物理路径中包含了隐藏跳(hiddenhops)[7，10-12]，从而增加了网络中的物理节点数量。现如今，启发式和元启发式的算法也相继提出[13-17]，未来有望解决这一问题。

未激活的链路比率相比于VNE-EA有较高的提升。因为流分割使链路利用率得到了提升，所以网络激活的链路数量较少，未激活的链路数量较多。

虚拟网络请求接受率在负载低时，两种算法的接受率大致相同；在负载高的情况下，提出算法接受率有较小的提升。在负载较高的情况下，资源利用率变高，从而使虚拟网络请求接受率变高。

3 结束语

为提高网络的节能性能，提出了一种基于可分割流的虚拟网络映射精简式节能算法。假设虚拟网络请求中的虚拟链路是可分割的。在精简式的节能算法基础上，在典型的节点节能算法中结合了链路分割，映射过程中，在映射节点之后，依据链路约束条件对链路进行映射，在不满足约束时，将链路分割成多条链路映射。这样在映射时，物理链路的带宽资源可以得到充分利用，从而提高了整体的映射性能。

仿真结果表明，在小规模网络中，与VNE-EA算法相比，流分割能够提高物理网络中的链路利用率，从而节省较多的物理链路。在网络负载很低的情况下，物理节点利用率略低于VNE-EA，这是因为流分割方法引入了隐藏跳问题，使物理链路在映射时经过了未激活的节点；然而，在网络负载较高的情况下，物理节点的利用率也有较小提高，物理网络中激活的物理节点数变少，并且提升了虚拟网络接受率。

[1] 陈晓华,李春芝,陈良育,等.主动休眠节点链路的高效节能虚拟网络映射[J].软件学报,2014,25(7):1416-1431.

[2] 王 博,陈庶樵,王志明,等.基于中心度寻核的能效优化虚拟网映射算法[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 网络出版时间：2017-03-13

国家自然科学基金资助项目(61372124)；国家“973”重点基础研究发展计划项目(2013CB329104)

刘认伦(1991-)，男，硕士，研究方向为移动通信与无线技术；导师：杨龙祥，教授，博士生导师，研究方向为移动无线通信系统和物联网。

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