虚拟网络映射高效节能运输模型及算法

陈晓华,李春芝,陈良育,曾振柄,蒋云良

(1.湖州师范学院信息工程学院,浙江湖州 313000; 2.华东师范大学软件学院,上海 200062;

3.华东师范大学计算机科学技术系,上海 200241; 4.上海大学数学系,上海 200444)



虚拟网络映射高效节能运输模型及算法

陈晓华1,2,李春芝1,3,陈良育2,曾振柄4,蒋云良1

(1.湖州师范学院信息工程学院,浙江湖州 313000; 2.华东师范大学软件学院,上海 200062;

3.华东师范大学计算机科学技术系,上海 200241; 4.上海大学数学系,上海 200444)

摘要：网络虚拟化使得智能能量感知网络部署成为可能,已有研究忽略了节点映射能耗最优化.本文把节点映射能耗优化问题转化为生产地与销售地之间物资运输代价最优化问题,建立高效节能节点映射运输模型.根据最大元素法,提出了混合一阶段与两阶段映射算法,在链路映射的约束下找到节点分配最小能耗代价最优解;利用主动休眠策略,提出了基于运输模型的主动休眠虚拟网络映射节能算法;利用节点可重复映射技术,提出了基于运输模型的节点可重复映射算法,进一步提高了底层网络资源休眠数量.仿真结果验证了本文所提算法能够显著降低系统能耗,适合大规模高效节能虚拟网络映射.

关键词:虚拟网络映射;运输模型;混合一阶段与两阶段算法;高效节能

1引言

当前网络为高峰负荷而设计,网络资源超量供给确保了网络的正常运行,然而也导致资源利用率低下.网络虚拟化[1],是未来因特网、云计算和软件定义网络的重要技术[2～7].其管理底层网络基础设施以及分配虚拟网络资源,使得智能能量感知网络部署成为可能.虚拟网络映射是网络虚拟化的关键技术.当前大部分算法是基于代价的映射算法[8～10],然而,由于底层节点能耗与CPU利用率关系较大[11],基于代价的映射算法未考虑到节能,造成不必要的能耗.

当前基于能量感知虚拟网络映射针对链路能耗对负载不敏感的设备,采用资源整合策略实现节能.如:文献[12]提出混合整数规划的能量感知最优化模型,但是时间复杂度呈指数增长,难以适应大规模网络基础设施的虚拟网络映射;文献[13]提出虚拟网络重配置的最小化能耗的启发式方法;苏森等提出虚拟网络映射能耗模型以及能量感知两阶段映射算法[14],在文献[15]中考虑电价波动提出了能耗成本最小化模型以及能量感知两阶段映射算法:常晓林、王冰等提出混合整数规划能耗模型及能量感知两阶段映射算法[16],文献[17]在云数据中心应用蚁群优化算法求解虚拟网络节能映射.文献[18]提出了多目标决策虚拟网络映射节能模型,并提出主动休眠底层网络资源策略.此外,针对链路能耗对负载敏感的设备,文献[19]考虑到路由能耗以及机箱能耗,提出扩展流量到网络资源的节能方法.由上可见,已有文献通过资源整合策略以及流量扩展策略实现节能,但忽略了节点映射能耗代价最优化.

本文提出节点分配能耗代价最小化运输模型;以最小元素法为基础,设计高效节能虚拟网络映射的混合一阶段与两阶段算法;针对动态特征对底层休眠资源的影响,设计基于运输模型的主动休眠节能算法;利用节点可重复映射技术,提出了基于运输模型的节点可重复映射算法,以降低系统能耗.

2虚拟网络映射节能运输模型及算法

2.1虚拟网络映射与底层网络能耗模型

当前处理器能耗与负载具有较好相关性[11].设定Pb为节点基本能耗,Pm为节点最大能耗,Pl=Pm-Pb,u为CPU利用率.定义第i个节点能耗为:

(1)

当前网络设备对流量负荷的功耗不敏感[20],专有的减负引擎将部署在网络虚拟化中[21～23],网络链路的能耗为常量[22,24].定义第j条链路能耗为:

(2)

2.2虚拟网络映射能耗代价最小化运输模型

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2.3虚拟网络映射最小化能耗代价算法

为了求解模型,本节以最小元素法为基础,提出混合一阶段与两阶段虚拟网络映射算法,求解虚拟网络映射节点分配最小能耗代价最优解,如算法1所示.

第1步,构造虚拟网络映射节点分配最小能耗代价运输模型,dist是承载运输模型的数据结构,其中dist[i][j]表示从虚拟节点j分配到底层节点i的相关数据,即dist[i][j].uPrice为分配虚拟节点j到底层节点i每个CPU资源量所消耗的CPU能耗单价;dist[sub.nodes][]为运输模型数据结构的最后一行,其中dist[sub.nodes][j].cpu为虚拟节点j请求的CPU资源量;dist[][req[index].nodes]为运输模型数据结构的最后一列,其中dist[i][req[index].nodes].cpu为底层节点i可用CPU资源量;req[index].nodes为第index个虚拟网络的节点数量;sub.nodes为底层节点数量.当底层节点i剩余的CPU资源量大于等于虚拟节点j请求的CPU资源量,则从i到j分配CPU资源的能耗单价为1.0/CPUSi;当底层节点i的CPU资源量小于虚拟节点j请求的CPU资源量,则dist[i][j].uPrice=-1,表示底层节点资源量不足,不能分配CPU资源;第i个底层节点(生产地)生产产品的产量为dist[i][req[index].nodes].cpu=CPULi;第j个虚拟节点(销售地)对产品的需求量为dist[sub.nodes][j].cpu=CPUVj.

第2步,根据最小元素法求解虚拟网络映射最小能耗代价.2.1步,num记录成功映射虚拟节点数量,初始化为0;集合AE为已经映射的节点集合,初始化为空集.2.2步,判断所有的虚拟节点是否成功映射.2.3步调用GetMinNum()函数,该函数在AE的补集(即未映射的底层节点和虚拟节点集合)中寻找最小能耗单价及未映射的虚拟节点最大CPU请求资源元素(sNode,vNode).2.5步循环调用FindNoEmbedVLink()函数,直到没有发现未映射的虚拟链路.FindNoEmbedVLink()函数在AE中(即已经映射虚拟节点集合)检测是否存在一条未映射的虚拟链路,并返回虚拟链路vFindLink相关信息,包括vFindLink带宽bw、两个虚拟端点(vNode、vFNode)以及映射的两个底层节点(sNode、sFNode).2.6步调用EmbedLinkBySpfa()函数,该函数在底层节点sNode到sFNode以最短路径映射虚拟链路vFindLink,这条最短路径的所有链路剩余带宽必须大于等于bw,其中采用经典最短路径算法计算最短路径.链路之间的距离设置如下:如果底层链路带宽大于等于bw,则设置为1,表示该链路可以映射;如果底层链路小于bw,则设置为0,表示该底层链路不能映射,不参与最短路径的计算.如果EmbedLinkBySpfa()找到了一条最短路径映射虚拟链路,则2.7步记录链路映射结果,并更新vFindLink虚拟链路映射标志,否则链路映射失败,返回-1.

算法1是混合一阶段和两阶段虚拟网络映射算法;其不同于一阶段映射算法,因为当映射一个虚拟节点后,并没有映射与该节点连接的所有链路;也不同于两阶段映射算法,因为当映射一个虚拟节点后,立即检查AE中未映射的链路.算法1采用最小元素法寻找虚拟网络节点分配最小能耗代价最优解.虚拟网络映射运输模型的特殊性,使得最小元素法找到的可行解即为最优解.因为应用闭回路检验法找不到闭回路,其检验数也不存在负数,所以可行解即为最优解.

算法1的时间复杂度主要集中在第2步,为o(n2·vl·m3),n为虚拟节点数量,vl为虚拟链路数量,m为底层节点数量,通常n和vl较小,能够保证在线虚拟网络映射的实时性.

2.4基于主动休眠方法的运输模型节能算法

由于虚拟网络映射的动态性对底层网络休眠节点和链路数量造成干扰,文献[18]提出了主动休眠方法,能够应用在不同的虚拟网络映射算法上,实现底层网络节能.因此本文在虚拟网络映射运输模型基础上,应用主动休眠方法,设计基于运输模型的虚拟网络映射算法,如算法2所示.第1步,根据映射字典库,计算主动休眠的底层节点和链路数量;第2步,在第一个时间窗设置底层节点和链路的休眠和激活标志;第3步,在设置激活标志的底层网络资源中,采用算法1映射虚拟网络.

算法2的优势是抗干扰性:虚拟网络到来和退出,引起底层网络资源的分配和回收,引起底层网络可休眠的节点和链路数量的动态变化,节能休眠状态与激活状态的切换必然导致底层网络不必要的能耗开销;算法2利用历史数据,能够快速找到适合当前虚拟网络的激活底层网络资源集合,避免了底层网络在两种不同状态频繁切换.算法2是建立在虚拟网络映射字典库,且只在第一个时间窗内计算激活的底层网络休眠和激活标志,其时间复杂度与算法1相同.

2.5节点可重复映射的运输模型节能算法

当前大部分虚拟网络映射算法在映射单个虚拟网络时,是在底层节点不可重复的条件下进行的.文献[25]提出了节点可重复映射算法,但其未考虑到能耗因素.为此,本文考虑节点分配能耗代价最小化,提出基于运输模型的节点可重复映射算法.在映射单个虚拟网络时,多个节点可映射到一个底层节点上,对应的虚拟链路则不需要映射.这样使得一些底层节点空闲出来,进入休眠节能状态.具体见算法3.

3性能仿真

3.1仿真环境

本文采用GT-ITM工具创建对称网络拓扑结构.底层网络包括100个节点、570条链路,每对节点以0.5的概率相连,相当于中等规模网络.底层节点CPU和链路带宽资源服从50-100均匀分布.每个时间窗为100个时间单元.每个虚拟网络请求节点个数服从2～20的均匀分布,每对虚拟节点以0.5的概率相连,每个虚拟网络平均有12条链路;虚拟网络请求过程模拟泊松过程,每个时间窗内虚拟网络请求到达个数服从均值为10的泊松分布,每个虚拟网络生存时间服从均值为5个时间窗的指数分布,等待映射时间为1个时间窗.设置虚拟节点CPU与带宽都服从0～6(非饱和状态)、0～20(饱和状态)的均匀分布.每次运行500个时间窗.与文献[22,27]一致,设置2.1节定义的Pb、Pm和Pn分别为150W,300W和15W;由于链路功耗差异较大[28,29],比较了链路功耗在1、15、30W的系统能耗,如图5、10所示.实验记录运行10个实例的平均值.

本文提出的算法1、2和3分别记为TR-VNE、 TR-AH-VNE和TR-VNE-S,其中算法2计算的主动休眠链路和节点数量分别为120和29.为了评价网络虚拟化映射节能性能,与基于能耗感知启发式算法[14]、元启发式算法[17]、节点可重复映射算法[25]以及经典启发式算法[29],即EA-VNE、ACO-VNE、VNE-S及PR-VNE比较.基于整数规划、线性规划的映射算法难以满足大规模虚拟网络映射的实时性要求,因此本文不与它们比较.本文的主要贡献在于节点映射,采用单路径链路映射.

与现有文献[14,18]相同,设定系统能耗、休眠节点数量、休眠链路数量、系统收益、收益成本比和接收率为性能评价指标,并在非饱和状态与饱和状态下,比较算法性能,其中系统收益是虚拟网络带宽与CPU总和.

3.2非饱和状态下的仿真结果

(1)在非饱和状态下,所提算法显著减少了系统平均能耗,如图1.因为TR-VNE,能够最小化节点分配能耗代价;TR-AH-VNE进一步降低了虚拟网络映射动态特征对底层网络资源休眠数量的干扰;TR-VNE-S利用节点可重复映射技术显著降低了底层网络激活资源的数量.虽然TR-VNE休眠节点数量比PR-VNE少(如图2),但提高了链路休眠数量(如图3);TR-AH-VNE休眠节点数量比PR-VNE多,并且提高了链路休眠数量.

(2)随着链路能耗的增大,所提算法节约能耗也越多.图4显示链路能耗在1、15和30,所提算法能减少系统能耗.这是由于当节点能耗不变的情况下,系统能耗变化部分集中在链路能耗上.由图3可知,本文所提算法的可休眠链路数量比PR-VNE多.随着链路能耗增大,节约能耗越多,这是由于节约能耗为ΔE=Pn·ΔL,不同链路能耗下ΔL是相同的,ΔE随着Pn增大而增多.

(3)在非饱和状态下,TR-VNE-S显著提高了收益成本比.图5显示TR-VNE-S的收益成本比显著提升,达到了1.06,这是因为TR-VNE-S通过节点可重复映射,即映射在同一个底层节点上的虚拟节点之间的链路不需要映射,减小了链路映射代价,从而显著提高了收益成本比.PR-VNE是一个经典映射算法,收益成本比较好,TR-VNE和TR-AH-VNE因为没有考虑到链路映射代价,收益成本比低于PR-VNE.

3.3饱和状态下的仿真结果

在饱和状态下,TR-AH-VNE退化为TR-VNE.

(1)在饱和状态下,所提算法显著减少了系统能耗,如图6显示.这是因为TR-VNE能够最小化节点分配能耗代价;TR-VNE-S能够实现底层网络休眠资源量显著增加(图7、8所示);TR-VNE是没有考虑负载平衡,在资源紧张情况下,导致休眠节点数量比PR-VNE少量增加,而与节点相连的链路利用率高,从而休眠链路数量显著增加.

(2)不同链路能耗情况下,所提算法都能有效降低系统能耗;且随着链路能耗增大,节约能耗越多.这是由于当节点能耗不变的情况下,系统平均能耗变化部分集中在链路能耗上,即由图8可知,TR-VNE、TR-VNE-S可休眠的链路数量比其它算法都要多,随着链路能耗增大,节约的能耗越多.同时,节点分配能耗代价最小化以及可重复映射,使得TR-VNE和TR-VNE-S有效节约了系统能耗如图9所示.

(3)在饱和状态下,TR-VNE-S显著提高了系统收益成本比,如图10所示.这是因为底层节点可重复映射,让一部分虚拟链路不需要映射,从而显著提高了收益成本比.TR-VNE比PR-VNE的收益成本比少1%,这是由于TR-VNE主要考虑节点映射的能耗代价最小化,导致一些底层节点映射较多虚拟节点,这些底层节点的链路可用资源减少,并未考虑负载平衡,从而影响了受益成本比,即TR-VNE节约能耗是以系统收益成本比为代价的.

(4)在饱和状态下,TR-VNE-S提高了虚拟网络接收率和系统收益,如图11和12所示.这是因为底层节点可重复映射,降低了底层链路映射代价,从而提高了虚拟网络接收率和系统受益.在虚拟网络接收率和系统收益方面,TR-VNE与PR-VNE几乎相当,这是由于底层网络资源较丰富,TR-VNE主要考虑的是节点分配能耗代价最小化,未考虑到负载平衡.

3.3仿真时间的比较结果

映射时间比较:同一台计算机模拟仿真,非饱和状态与饱和状态所用时间具有相似性,因此选择非饱和状态时间进行运行时间比较.在非饱和状态下运行500个时间窗所用的时间,EA-VNE、PR-VNE、ACO-PE-VNE、VNE-S、TR-VNE、TR-AH-VNE和TR-VNE-S分别为22、30、400、11、21、 9和18秒.可以看出,所提算法运行时间较少,适合在大规模底层网络上在线实时映射虚拟网络.

4总结

本文研究网络虚拟化环境下的系统能耗问题.运用运输模型,把虚拟网络映射问题转化为生产地与销售地之间的运输能耗代价最小化问题,并设计虚拟网络映射高效节能算法,显著降低了系统能耗.

参考文献

[1]Chowdhury N M M K,et al.Network virtualization:state of the art and research challenges[J].Communications Magazine,IEEE,2009,47(7):20-26.

[2]Anderson T,et al.Overcoming the Internet impass through virtualization[J].IEEE Computer Magazine,2005,38(4):34-41.

[3]Sun G,et al.Optimal provisioning for elastic service oriented virtual network request in cloud computing[A].IEEE GLOBECOM[C].Anaheim:IEEE,2012.2517-2522.

[4]Drutskoy D,et al.Scalable network virtualization in software-defined networks[J].IEEE Internet Computing,2013,17(2):21-27.

[5]Sharkh M A,et al.Resource allocation in a network-based cloud computing environment:design challenges[J].IEEE Communications Magazine,2013,51(11):46-52.

[6]魏祥麟,陈鸣,等.数据中心网络的体系结构[J].软件学报,2013,24(2):295-316.

Wei X,Chen M,et al.Architecture of the data center network[J].Journal of Software,2013,24(2):295-316.(in Chinese)

[7]周烨,李勇,等.基于虚拟化的网络创新实验环境研究[J].电子学报,2012,40(11):2152-2157.

Zhou Y,Li Y,et al.Research of Network innovation exerpimental environment based on network virtualization[J].Acta Electronica Sinica,2012,40(11):2152-2157(in Chinese).

[8]Fischer A,et al.Virtual network embedding:A survey[J].IEEE Communications Surveys & Tutorials,2013,(99):1-19.

[9]姜明,王保进,等.网络虚拟化与虚拟网映射算法研究[J].电子学报,2011,39(6):1315-1320.

Jiang M,Wang B,et al.Research on network virtualization and virtual network mapping algorithm[J].Acta Electronica Sinica,2011,39(6):1315-1320.(in Chinese)

[10]程祥,张忠宝,等.基于粒子群优化的虚拟网络映射算法[J].电子学报,2011,39(10):2240-2244.

Cheng X,Zhang Z,et al.Virtual network embedding based on particle swarm optimization[J].Acta Electronica Sinica,2011,39(10):2240-2244.(in Chinese)

[11]林闯,田源,等.绿色网络和绿色评价:节能机制,模型和评价[J].计算机学报,2011,34(4):593-612.

Lin C,Tian Y,et al.Green network and green evaluation:mechanism,modeling and evaluation[J].Chinese Journal of Computers,2011,34(4):593-612.(in Chinese)

[12]Botero J F,et al.Energy efficient virtual network embedding[J].IEEE Communications Letters,2012,16(5):756-759.

[13]Botero J F,et al.Greener networking in a network virtualization environment[J].Computer Networks,2013,57 (9):2021-2039.

[14]Su S,et al.Energy-aware virtual network embedding through consolidation[A].Computer Communications Workshops[C].Orlando:IEEE,2012.127-132.

[15]Su S,et al.Energy-aware virtual network embedding[J].IEEE/ACM Transactions on Networking.2014.10:1-14.

[16]Wang B,et al.Reducing power consumption in embedding virtual infrastructures[A].Globecom Workshops (GC Wkshps)[C].Anaheim,CA:IEEE,2012.714-718.

[17]Chang X,et al.Green cloud virtual network provisioning based ant colony optimization[A].Proceeding of the Fifteenth Annual Conference Companion on Genetic and Evolutionary Computation Conference Companion[C].Amsterdam ACM,2013.1553-1560.

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

Chen X,Li C,et al.Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J].Journal of Software,2014,25(7):1416-1431.(in Chinese)

[19]Rasario G,et al.Does traffic consolidation always lead to network energy savings[J].IEEE Communication Letters,2013,17(9):1852-1855.

[20]Chabarek J,et al.Power awareness in network design and routing[A].IEEE INFOCOM[C].Phoenix:IEEE,2008.457-465.

[21]Turner J,et al.Supercharging planetlab:A high performance,multi-application,overlay network platform[J].ACM SIGCOMM Computer Communication Review,2007，37(4):85-96.

[22]Lu G,et al.Serverswitch:A programmable and high performance platform for data center networks[A].Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation[C].Boston:USENIX Association,2011.1-14.

[23]Unnikrishnan D,et al.Scalable network virtualization using FPGAs[A].Proceedings of the 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate Arrays[C].Monterey:ACM,2010.219-228.

[24]Sivaraman V,et al.Profiling per-packet and per-byte energy consumption in the netfpga gigabit router[A].IEEE Computer Communications Workshops (INFOCOM WKSHPS)[C].Shanghai:IEEE,2011.331-336.

[25]李文,吴春明,等.节点可重复映射和链路可分流的虚拟网映射算法[J].电信科学,2010,26(10):114-120.

Li W,Wu C M,et al.Virtual network mapping algorithm with node repeatable embedding and link splitting[J].Telecommunications Science,2010,26(10):114-120.(in Chinese)

[26]Barroso L A,et al.The Datacenter as a Computer:An Introduction to the Design of Warehouse-Scale Machines[M].California:Morgan and Claypool Publishers,2009.1-108.

[27]Ananthanarayanan G,et al.Greening the switch[A].HotPower'08 Proceedings of the 2008 Conference on Power Aware Computing and Systems[C].Berkeley,CA,USA:USENIX Association,2008.

[28]Chiaraviglio L,et al.Energy-aware backbone networks:a case study[A].International Conference on Communications Workshop[C].Dresden,Germany:IEEE,2009.1-5.

[29]Cheng X,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):38-47.

陈晓华男,1977年生于江西九江.湖州师范学院信息工程学院讲师,华东师范大学软件学院博士生.研究方向为下一代网络、云计算.

李春芝(通信作者)女,1982年生于江苏淮安.湖州师范学院信息工程学院讲师,华东师范大学计算机科学技术系博士生,研究方向为最优化方法、图像处理.

E-mail:lichunzhi82@126.com.

Transportation Model and Algorithms for Energy Efficient Virtual Network Embedding

CHEN Xiao-hua1,2,LI Chun-zhi1,3,CHEN Liang-yu2,ZENG Zhen-bing4,JIANG Yun-liang1

(1.SchoolofInformationandEngineering,HuzhouTeachersCollege,Huzhou,Zhejiang313000,China;2.SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai200062,China;3.DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China;4.DepartmentofMathematics,ShanghaiUniversity,Shanghai200444,China)

Abstract:Network virtualization is an enabler for intelligent energy-aware network deployment.In the existing virtual network embedding algorithms,the minimization of energy consumption for mapping virtual nodes is ignored.In this paper,we create a transportation model for energy efficient virtual network embedding,in which energy consumption minimization for mapping virtual nodes is turned into the transportation model.An algorithm based on the largest element is proposed to obtain the optimization solution with node and link resource constraints,which is also a hybrid one-and-two stage algorithm.Besides,on the basis of the transportation model,we design an energy saving algorithm by use of the actively hibernating policy.If multiple virtual nodes in the same virtual network can be mapped to the same substrate node,a largest-element-and-transportation-model-based algorithm is proposed.These algorithms increase the number of substrate network hibernating resources.Simulation results show that the proposed algorithms can significantly reduce energy consumption.The theoretical analyses and the simulation results verify that our proposed algorithms suit energy efficient virtual network embedding for large scale substrate network.

Key words:virtual network embedding;transportation model;hybrid one-and-two stage algorithm;energy efficient

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.034

中图分类号:TP393

文献标识码：A

文章编号：0372-2112 (2016)03-0725-07

基金项目:国家自然科学基金(No.61501184,No.61370173)

收稿日期:2014-07-23;修回日期:2014-11-10;责任编辑:蓝红杰