面向节点异构的能耗感知虚拟网络映射算法

龚水清 陈 靖 王 崴



面向节点异构的能耗感知虚拟网络映射算法

龚水清*①陈 靖①王 崴②

①(空军工程大学信息与导航学院 西安 710077)②(空军工程大学防空反导学院 西安 710051)

在底层网络节点异构的环境中，能耗优化的虚拟网络映射问题并不是最小化工作节点和链路数。该文针对此问题，构建底层网络节点和链路的负载能耗模型，并以能耗最优为目标，建立虚拟网络映射问题的数学模型，提出一种能耗感知虚拟网络映射算法。该算法在节点映射阶段以最小化能耗和协调链路映射为原则，将虚拟节点映射至综合资源能力最大的底层节点上，并采用改进的能耗感知最短路径法进行链路映射。仿真结果表明，该算法显著减少虚拟网络映射的能耗，且底层网络节点异构性越大，能耗优势更为明显。

网络虚拟化；虚拟网络映射；能耗模型；资源能力

1 引言

随着全球能源危机的出现，电力价格不断上涨，能耗成本已成为互联网服务提供商(Internet Service Provider, ISP)最主要的运营开销。但现有互联网络大都采用超额资源供给以应对网络突发性的峰值负载，并进行冗余设计以提高网络可靠性，网络资源和能源的利用率较低。且大型ISP骨干网的最大链路利用率不足40%[1]，网络设备大多7´24 h全速运转，这导致网络闲时大量资源和能源的浪费。因此，减少网络能源消耗，降低网络运维成本，构建绿色节能的网络已成为当前研究亟待解决的问题[2]。

网络虚拟化[3]是近年来提出来的用于解决互联网“僵化”问题[4]，促进未来网络创新发展的重要技术。它通过资源抽象、聚合、隔离等机制允许多个异构的虚拟网络(Virtual Network, VN)共享同一底层物理网络(Substrate Network, SN)，可实现对多样化网络技术部署和应用的支持。虚拟网络映射[5]作为网络虚拟化中的核心问题，是指为带有节点和链路资源需求约束的虚拟网络请求分配底层物理网络资源。目前，大部分虚拟网络映射算法[5–7]主要以降低虚拟网络映射成本，提高底层网络映射收益为目标。然而，这些研究未考虑虚拟网络映射过程中的能耗优化，必然带来不必要的能耗。

当前，由于网络节点和链路的能耗对流量负荷不敏感[8]，因此在满足虚拟网络资源请求的前提下，运营商通过让网络中空闲的节点和链路处于低功耗模式甚至关闭可以达到节能的目的。受到这一启发，文献[9]以最小化底层网络工作节点和链路数量为目标，建立了虚拟网络映射问题的混合整数规划能耗优化模型，通过将虚拟网络集中映射至底层网络工作的节点和链路上，并关闭空闲的节点和链路以减少网络能耗。文献[10]进一步考虑映射成本和负载均衡，改进了文献[9]的算法，并针对大规模虚拟网络映射问题提出了能耗感知重配置启发式算法。由于节点和链路的能耗与其负载有关，文献[11,12]提出了节点和链路的能耗模型，以最小化映射能耗开销为目标，建立虚拟网络映射问题的整数线性规划模型，并提出启发式算法对该问题进行求解。文献[13]针对不同时间不同地区的电力价格不同，以减少电力成本为目标，提出了一种跨域能耗优化的虚拟网络映射算法。

然而，上述虚拟网络映射算法都假设底层网络中所有节点的功耗相同，通过优化映射过程中工作节点数并关闭空闲节点，达到节能目的。但由于底层网络设备存在采购时间、使用年限和品牌等异构性，导致功耗各不相同，此时，虚拟网络映射的能耗优化问题并不是最小化工作节点数量。因此，目前已提出的大部分节能虚拟网络映射方法不能很好地应用在一般网络的能耗管理中。

为此，本文针对底层网络节点异构的能耗优化虚拟网络映射问题进行研究，首先建立底层网络节点和链路的负载能耗模型，并以最小化映射能耗为目标，构建虚拟网络映射问题的数学优化模型。然后，设计能耗感知虚拟网络映射启发式(Energy- Aware Virtual Network Embedding Heuristic, EA- VNEH)算法对模型进行求解。EA-VNEH算法以最小化能耗和协调链路映射为原则，将虚拟节点映射至综合资源能力最大的底层节点上，并采用改进的能耗感知最短路径算法进行链路映射。最后，在底层网络节点不同异构性的环境下对该算法进行性能评估与分析。仿真结果表明，算法在能耗优化、映射成功率和底层网络收益等方面明显优于已有的虚拟网络映射方法。

2 系统模型与问题描述

2.1网络模型

2.2能耗模型

虚拟网络请求映射至底层网络产生的能耗主要包括节点能耗和链路能耗两部分。

(1)节点能耗： 底层网络中的节点主要指服务器，其功耗主要包括基本功耗和动态功耗两部分。基本功耗是指服务器空载时的功耗，与负载无关，而动态功耗是指与载荷相关的功耗。现有研究表明服务器节点的功耗与其CPU利用率呈近似线性关系[14]，而服务器的其他部分如内存、存储等功耗相对较小[15]。因此，本文用式(1)估计底层网络节点的功耗。

(2)链路能耗：链路能耗主要包括底层路径两端点(工作节点)收发数据包的能耗和中间节点转发数据包的能耗。现有研究通常认为网络虚拟化中部署有专用的离线引擎[16]，用于高效的数据包处理并保持低处理延时，且无论端口是空载还是满负荷运转，该引擎的功耗都接近于常量[17]。

2.3虚拟网络映射问题描述

3 能耗感知虚拟网络映射问题的数学模型

本节以最小化虚拟网络映射总能耗为目标函数，以满足虚拟网络资源需求为约束，对能耗感知虚拟网络映射问题进行混合整数线性规划(Mixed Integer Linear Program, MILP)建模，具体过程如下：

目标函数：

约束条件：

说明 在底层网络节点能耗异构的环境中，能耗感知虚拟网络映射的目标并不是最小化工作节点数量，而是最小化总映射能耗，因此本文以式(8)作为该模型的目标函数。虚拟网络映射时，需考虑满足虚拟网络请求的资源需求约束，主要包括节点约束和链路约束。式(9)和式(11)分别是节点的CPU资源约束和位置约束。式(10)和式(12)分别表示链路的带宽资源约束和连通性约束。式(13)和式(14)表示同一虚拟网络请求的虚拟节点必须映射到底层网络中不同的物理节点上。式(15)和式(16)为该模型的变量范围的约束，和需满足整数约束条件，导致该模型成为非确定性多项式时间难问题(NP-hard)。

4 EA-VNEH算法设计

由于虚拟网络映射问题的MILP模型是一个NP-hard问题，虽然传统的方法如分支定界法可以求得其最优解，但随着问题规模的增长，其时间复杂度较高，计算时间过长，不适用于大规模网络的映射。因此，本节设计EA-VNEH算法对能耗感知虚拟网络映射问题进行求解。

4.1 节点映射

由于资源需求高的虚拟节点映射更加困难，很可能由于底层网络节点没有足够多的资源而导致映射失败，因此，在节点映射阶段，优先选择资源需求高的虚拟节点进行映射。节点的邻接链路可用带宽的多少直接影响后续的链路映射阶段，为此，本节将节点的资源能力定义[6,11]为

在节点映射阶段，首先按照式(17)计算虚拟网络中节点的资源能力需求，并按照从大到小顺序依次进行映射。针对节点，提出如下映射原则：

节点映射算法的主流程如表1所示。与已有节能映射算法[11,13]相比，EA-VNEH算法在节点映射过程中考虑了节点的资源能力和能耗，并以综合资源能力CR作为节点的排序标准，将虚拟节点映射至CR最大的底层物理节点上，可有效节省能耗，提高映射成功率，进而增加底层网络收益。

4.2链路映射

现有研究主要采用最短路径法进行链路映射[6,11]，但此方法没有考虑底层链路的能耗，导致能源利用效率不高。为此，本节综合考虑链路映射的带宽消耗和能源消耗，设计能耗优先的最短路径链路映射算法，如表2所示。

表2 EA-VNEH的链路映射算法

在链路映射阶段，首先按带宽需求对虚拟链路进行排序，优先选择资源需求高的虚拟链路进行映射。对于虚拟链路，采用最短路径法[18]计算底层节点至的最短路径集合，且对于任意，需满足虚拟链路的带宽资源需求。链路映射时，通过计算将映射至上新增的能耗，将虚拟链路映射到能耗最小的最短路径上。

从表2中可以看出，EA-VNEH在链路映射阶段兼顾链路带宽消耗和能耗，优先选择底层网络最短路径集中能耗最低的路径作为映射目标，可有效降低链路映射成本，减少链路映射能耗，提高映射收益。

5 性能评估与分析

ALEVIN[19]是一个用于开发、比较和分析虚拟网络映射算法的仿真平台。本文以此作为仿真工具，对EA-VNEH和几种能耗优化虚拟网络映射算法进行仿真，并从虚拟网络请求长期平均能耗、虚拟网络请求接受率、底层网络长期收益开销比和运行时间等方面讨论EA-VNEH算法的性能。

5.1 实验环境设置

网络拓扑使用GT-ITM拓扑生成器产生，底层网络设置为50个节点，节点间的连接概率为0.5，相当于一个中小型规模的ISP运营商。底层节点的可用CPU资源和底层链路的可用带宽资源均服从[50,100]的均匀分布。底层节点的位置变量与均服从[0,100]的均匀分布。虚拟网络请求随机生成，每100个时间单元虚拟网络请求到达的个数服从均值为4的泊松分布，其生存期服从均值为25个时间单元的指数分布。虚拟网络的节点数目服从[2,10]的均匀分布，虚拟节点间以0.5的概率连接。虚拟节点的CPU资源需求和虚拟链路的带宽资源需求均服从[0,50]的均匀分布，且假设所有节点的位置需求D取常量50。此外，设置式(17)中的权重和均为1，链路映射最短路径算法中的为5。

本节分别在底层网络节点能耗异构性不同的两种环境下对算法EA-VNEH, EE-VNE[9]和EA- VNE[11]进行仿真实验。算法EE-VNE和EA-VNE均以最小化底层网络工作节点和链路数量为目标，前者采用GLPK工具求解VNE的MILP模型，后者的节点映射阶段采用贪婪算法，链路映射阶段采用最短路径法。为了使整个仿真的运行处于比较平稳的状态，设定实验运行时间为50000个时间单位。为避免随机因素对实验结果产生扰动，仿真实验总共进行10次，并取实验结果的平均值作为最终仿真结果。

5.2性能分析

本文从虚拟网络请求长期平均能耗、虚拟网络请求接受率、底层网络长期收益开销比和运行时间4个方面对算法进行性能比较，仿真结果表明EA- VNEH算法具有以下优势。

(1)显著降低了虚拟网络映射的能耗，且底层网络节点异构性越大，能耗减少更为明显。

图1表示底层网络不同节点异构性环境下虚拟网络请求平均能耗的变化情况。图1(a)表明在底层节点异构性小的环境下，EA-VNEH算法的虚拟网络请求平均能耗稳定在21.73 kW左右，较EE-VNE, EA-VNE分别降低了约19.61%和15.73%。图1(b)表明在底层节点异构性大的环境下，EA-VNEH算法的虚拟网络请求平均能耗稳定在23.24 kW左右，较EE-VNE, EA-VNE分别降低了约30.14%和26.32%。主要原因是EA-VNEH算法考虑了底层网络节点的能耗异构性，在映射过程中将虚拟节点和链路映射到能耗更小的底层网络节点和路径上。而EE-VNE和EA-VNE只优先选择工作的节点和链路进行VNR的映射，但在底层网络节点能耗异构的环境下，这两种方法并不能实现能耗最优化。

图1 虚拟网络请求平均能耗

(2)提高了虚拟网络请求接受率和底层网络的收益。

图2和图3分别表示底层网络不同节点异构性环境下虚网请求接受率和底层网络长期收益开销比的变化情况。从图中可以看出，由于初始时段底层网络可用资源较为丰富，3种算法的虚网请求接受率和收益开销比都较高。随着资源的逐步消耗，接受率和收益开销比都逐渐下降。但由于3种算法随着虚拟网络请求的动态到达和离开而达到一个稳态过程，所以虚网请求接受率和收益开销比都趋于平稳。图2和图3表明在底层网络不同节点异构性环境下，EA-VNEH算法的虚拟网络请求接收率和收益开销比明显高于其它两种算法。主要原因是EA- VNEH在节点映射过程中采用了协调链路映射的原则，使后续链路映射更容易成功，从而提高了虚拟网络请求接受率，进而映射收益较高。而EE-VNE和EA-VNE优先将虚拟节点和链路映射至工作的节点和链路上，容易产生瓶颈节点和链路，降低了随后到达的虚拟网络请求的映射成功率。

图2 虚拟网络请求接受率

图3 底层网络收益开销比

(3)降低了虚拟网络映射的求解时间

表3表示不同算法的虚拟网络映射的平均求解时间。从表中可看出，相较于EA-VNEH和EA-VNE算法，EE-VNE需要运行更多的时间映射虚拟网络请求。主要原因是EA-VNEH和EA-VNE采用启发式算法求解虚拟网络映射问题，有效降低了算法的运行时间，而EE-VNE采用标准的MILP求解工具GLPK来求取虚拟网络映射的最优解，其求解时间随网络规模的增长呈指数增加。

表3算法运行时间

算法EE-VNEEA-VNEEA-VNEH 运行时间1.23 s41 ms52 ms

6 结束语

本文研究了底层网络节点异构环境下的能耗优化的虚拟网络映射问题。由于底层网络节点的能耗异构性，虚拟网络映射到底层网络产生的动态能耗也不同。此时，能耗优化的虚拟网络映射问题并不是最小化工作节点和链路数。针对此问题，构建了底层网络节点和链路的能耗模型，并将能耗感知虚拟网络映射问题建模为MILP模型，提出了EA- VNEH映射算法。仿真实验结果表明，与传统的能耗优化虚拟网络映射算法相比，EA-VNEH提高了虚拟网络请求接受率和底层网络的收益，降低了运行时间，显著减少了虚拟网络映射的能耗，且底层网络节点异构性越大，能耗优势更为明显。

参考文献

[1] Fisher W, Suchara M, and Rexford J. Greening backbone networks: reducing energy consumption by shutting off cables in bundled links[C]. Proceedings of the first ACM SIGCOMM Workshop on Green Networking, New Delhi, India, 2010: 29-34.

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

Lin Chuang, Tian Yuan, and Yao Min. Green network and green evaluation: mechanism, modeling and evaluation[J]., 2011, 34(4): 593-612.

[3] Chowdhury N M and Boutaba R. A survey of network virtualization[J]., 2010, 54(5): 862-876.

[4] Turner J S and Taylor D E. Diversifying the Internet[C]. Proceedings of the IEEE Global Communications Conference, Saint Louis, USA, 2005, 2: 1-6.

[5] Fischer A, Botero J F, Till B M,.. Virtual network embedding: a survey[J].&, 2013, 15(4): 1888-1906.

[6] Hsu W H and Shieh Y P. Virtual network mapping algorithm in the cloud infrastructure[J]., 2013, 36(6): 1724-1734.

[7] 余建军, 吴春明. 支持接入控制的虚拟网映射近似算法[J]. 电子与信息学报, 2014, 36(5): 1235-1241.

Yu Jian-jun and Wu Chun-ming. Virtual network mapping approximation algorithm with admission control[J].&, 2014, 36(5): 1235-1241.

[8] Chabarek J, Sommers J, Barford P,.. Power awareness in network design and routing[C]. Proceedings of the IEEE International Conference on Computer Communications, Phoenix, USA, 2008: 1130-1138.

[9] Botero J F, Hesselbach X, Duelli M,.. Energy efficient virtual network embedding[J]., 2012, 16(5): 756-759.

[10] Botero J F and Hesselbach X. Greener networking in a network virtualization environment[J]., 2013, 57(9): 2021-2039.

[11] Su S, Zhang Z, Cheng X,.. Energy-aware virtual network embedding through consolidation[C]. Proceedings of the IEEE International Conference on Computer Communications Workshops, Orlando, USA, 2012: 127-132.

[12] Su S, Zhang Z, Liu A X,.. Energy-aware virtual network embedding[J]./, 2014, 22(5): 1607-1620.

[13] Zhang Z, Su S, Niu X,.. Minimizing electricity cost in geographical virtual network embedding[C]. Proceedings of the IEEE Global Communications Conference, Anaheim, USA, 2012: 2609-2614.

[14] Rivoire S, Ranganathan P, and Kozyrakis C. A comparison of high-level full-system power models[J]., 2008, 15(8): 3-9.

[15] Economou D, Rivoire S, Kozyrakis C,.. Full-system power analysis and modeling for server environments[C]. Proceedings of Workshop Modeling, Benchmarking, Simulation, Boston, USA, 2006: 70-77.

[16] Turner J S, Crowley P, DeHart J,.. Supercharging planetlab: a high performance, multi-application, overlay network platform[J]., 2007, 37(4): 85-96.

[17] Sivaraman V, Vishwanath A, Zhao Z,.. Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]. Proceedings of the 30th IEEE International Conference on Computer Communications Workshops, Shanghai, China, 2011: 331-336.

[18] Eppstein D. Finding theshortest paths[C]. Proceedings of IEEE Symposium on Foundations of Computer Science, Santa Fe, USA, 1994: 154-165.

[19] Beck M T, Linnhoff-Popien C, Fischer A,.. A simulation framework for Virtual Network Embedding algorithms[C]. Proceedings of the IEEE Telecommunications Network Strategy and Planning Symposium (Networks), Madeira Island, Portugal, 2014: 1-6.

[20] Lu G H, Guo C X, Li Y L,.. Serverswitch: a programmable and high performance platform for data center networks[C]. Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, Berkeley, USA, 2011: 1-14.

Energy-aware Virtual Network Embedding Algorithm for Heterogeneous Nodes

Gong Shui-qing①Chen Jing①Wang Wei②

①(,,,710077,)②(,,,710051,)

The energy optimized virtual network embedding problem in the substrate network with heterogeneous nodes is not to minimize the number of working nodes and links. The load-based energy consumption models of the node and link in the substrate network are built, a mathematical model of the virtual network embedding problem is modeled in order to reduce energy consumption, and an energy-aware virtual network embedding heuristic algorithm is proposed. Based on the principles of energy optimization and coordination with link mapping, the virtual node is mapped onto the substrate node with the highest comprehensive resource capacity in the node mapping phase, and the link mapping phase is based on the energy-awareshortest path algorithm. Simulation results show that the proposed algorithm reduces the energy consumption significantly, and the heterogeneity of substrate network nodes is greater, reducing the energy consumption is more obvious.

Network virtualization; Virtual network embedding; Energy consumption model; Resource capacity

TP393

A

1009-5896(2015)08-2021-07

10.11999/JEIT141527

龚水清 gsq0121@126.com

2014-12-02收到，2015-03-06改回，2015-06-09网络优先出版

国家自然科学基金(51075395)和国家863计划项目(2013AA040604)资助课题

龚水清： 男，1987年生，博士生，研究方向为网络虚拟化、下一代互联网.

陈 靖： 女，1963年生，博士，教授，研究方向为分布式计算、移动自组织网络、网络虚拟化等.

王 崴： 男，1974年生，博士，副教授，研究方向为云计算、网络虚拟化等.