胡颖，庄雷，陈鸿昶，马丁,3



时间和能量感知的贝叶斯虚拟网映射

胡颖1，庄雷1，陈鸿昶2，马丁1,3

（1. 郑州大学信息工程学院，河南郑州 450000； 2. 国家数字交换系统工程技术研究中心，河南郑州 450002； 3. 河南工业大学信息科学与工程学院，河南郑州 450000）

针对虚拟网的节能映射问题，建立了结合时间和能量感知的虚拟网映射算法。在对节点和路径的评价标准中加入了时间因素，综合考虑了物理资源的运行时间等因素，用概率理论辅助分析了每个虚拟节点的多个可用物理节点被选中的概率。在节点选择阶段，综合考虑底层节点的剩余资源量、CPU资源利用率增量、节点开启情况和是否延长使用时间等因素，并使用条件概率理论辅助分析得到各可用节点的重要性；在链路选择阶段，综合考虑链路开启情况、延长使用时间和链路长度等因素。不仅使虚拟网请求映射在当前较小的节点和链路集合中，而且映射到了延长时间较短的设备上。实验结果表明，与未考虑时间因素的方法相比，该方法能带来更好的性能和更低的能耗。

虚拟网映射；节能；贝叶斯；条件概率；时间感知

1 引言

随着电力成本的不断上涨，网络运营商已经认识到能耗管理问题的重要性。据有关研究显示[1,2]，在数据中心，能耗开销已经占数据中心总开销的12%~20%，占运营开销的40%~50%。在Internet中，能耗开销也已经成为Internet服务提供商总开销的重要组成部分。能耗开销过大是由于当前网络为高峰负荷设计，网络资源超需供给确保了网络正常运行，却也导致资源利用率低下。据统计，大型ISP骨干网的平均链路利用率为30%~40%[5]。过低的利用率造成能源的极大浪费，使网络能耗问题成为研究人员关注的热点问题[6,7]。

网络虚拟化技术是解决网络僵化问题的关键解决方案，是未来网络研究中的一种重要技术。在网络虚拟化环境中，多个服务提供商(SP, service provider)以虚拟网请求的方式请求租用同一个基础设施提供商(InP, infrastructure provider)提供的物理网络，从而向端用户提供服务；InP负责部署和管理底层物理网络，优化虚拟网映射策略以使利益最大化，即映射更多的虚拟网请求的同时，使占用底层网络资源量最小化，以减少运行成本。运行成本不仅包括资源的占用，还包括运行的能耗。在网络虚拟化环境中降低能耗的方式有2种：虚拟网映射时（建立虚拟网时）和虚拟网运行中（建立虚拟网后）。本文关注虚拟网映射时的节能问题，即虚拟网节能映射问题。

在虚拟网节能映射中包括2个问题：1)如何对虚拟网节能映射问题建立模型；2)如何确定虚拟网节能映射算法，即根据模型建立的目标确定节点和链路映射的方法，以整合资源开启较小的节点和链路集合，达到减少能耗的目的。

当前已有一些学者对虚拟网节能映射问题进行了有意义的研究。文献[8]将虚拟网映射问题成功扩展到虚拟网节能映射问题，并建立了混合整数线性规划模型，将节能映射的目标设置为开启的节点数量和开启的链路数量之和；文献[9]从节能和占用资源最小化2个角度对虚拟网映射问题建立了整数线性规划模型，并分别以其中一个为主要目标，另一个为次要目标进行了解决和分析；文献[10]从能耗、请求优先级和请求的位置限制等3个条件来限制虚拟网节能映射问题，分析并得到了较优的结果；文献[11]为数据中心网络的虚拟网节能映射问题建立了模型，从实际因素出发，在计算资源和网络资源2个角度对问题进行了分析讨论；文献[12]应用最优化理论为虚拟网节能映射问题建立了模型；文献[13]为云计算网络的虚拟网节能映射问题建立了混合整数线性规划模型；文献[14]从节能、负载均衡等多个目标设计虚拟网映射模型，并针对云计算网络中的节点或链路故障问题，提出了一个容错的映射算法。

以上虚拟网节能映射算法的主要节能方式是尽可能地将节点链路映射到活动的底层节点链路上，达到了较好的节能效果，但都没有考虑延长运行时间对映射效果的影响。本文在对节点和链路评价标准的设计中考虑时间因素，加入了对物理资源的延长运行时间这一要素，设计了基于时间和能量感知的虚拟网映射算法(TEAVNE, time and energyaware virtual network embedding)。算法中，用传统概率理论辅助分析，并确定了每个虚拟节点的多个可用物理节点将被选中的概率，并通过仿真实验对该算法进行了验证与分析。

2 虚拟网节能映射模型

底层网络能耗包括物理节点能耗和物理链路2个部分，对其分析前，首先对符号定义如表1所示。

表1 符号表示

2.1 物理节点功耗

同文献[15]，设置物理节点的功耗（ECN, energy consumption in node）为

2.2 物理链路功耗

同文献[15]，定义底层网络物理链路l的功耗（ECL, energy consumption in link）为

其中，物理链路的功耗n是常量。

2.3 底层网络总能耗

为方便分析描述，首先做如下定义。

定义1 如果在某个时间段内，底层网络上没有发生虚拟网请求的到达或离开事件，称此时段的底层网络处于稳定状态。

定义2 如果在某时刻发生了虚拟网请求的映射或离开事件（这里认为映射和离开事件的发生时间忽略不计），称该时刻为分裂点。

定义3 相邻2个分裂点间的时间段，称为有效时间片。

由以上定义可知，在有效时间片内，底层网络处于稳定状态；在不同的有效时间片间，底层网络单位能耗量不同。于是，计算底层网络总能耗前应先确定所有分裂点，由各分裂点将运行时间分为多个有效时间片，在各个有效时间片内分别计算底层网络的能耗，底层网络的总能耗即各有效时间片的能耗总和为

其中，为分裂点划分出的有效时间片总个数，E为有效时间片内底层网络的单位能耗，T为有效时间片的时长。

在有效时间片内，物理网络设备稳定运行，底层网络能耗即物理节点和物理链路的能耗之和。由式(1)和式(2)，得到底层网络的单位能耗E为

2.4 虚拟网节能映射问题模型

根据式(4)，设置虚拟网节能映射问题的目标如下。

目标函数为

和虚拟网映射问题一样，虚拟网节能映射问题的约束条件包括以下几项。

1) 容量约束

2) 传输约束

(7)

一个虚拟节点只能映射到一个底层节点的约束

3) 相同虚拟网请求的虚拟节点不能映射到同一个底层节点的约束

(9)

4) 变量约束

以上基于混合整数规划设计得到虚拟网节能映射模型，下面针对该问题设计节点和链路的节能评价标准以及节能映射的贪婪算法，找到虚拟网节能映射的较优解。

3 时间和能量感知的虚拟网映射算法

与传统的虚拟网节能映射算法相比，TEAVNE算法最主要的不同点在于：在为虚拟节点选取映射目标时，将会把占用设备的时间纳入其评价要素，并应用传统概率论方法分析可用节点的选中概率，使虚拟网请求优先映射在已开启、延长资源占用时间较短且增加资源利用率较少的物理节点上；在为虚拟链路选取物理路径时，兼顾了路径的长度、路径中物理链路的开启量和物理链路的延长使用时间等3个因素。下面首先给出节点和链路的评价要素和评价标准。

3.1 节点和链路的评价要素

由虚拟网映射的基本指标——占用资源量和请求接收率等，可知评价要素中应包括如资源剩余量、物理路径的长度等要素。由虚拟网节能映射的目标式(5)，应将物理节点和物理链路的开关状态以及增加的CPU资源利用率作为评价要素。加入时间因素后，还应将当前的虚拟网请求是否延长设备运行时间以及延长运行时间的大小加入评价要素，否则将可能造成较差的节能效果。一个虚拟网映射的例子如图1所示。

图1中，六边形节点构成的拓扑代表虚拟网，圆形节点构成的拓扑代表底层物理网络，正方形框中的数字代表虚拟网的运行时间，矩形框中的数字表示底层网络节点或链路还要被占用的时间。

设图1中的底层网络的带宽和CPU剩余资源足够多，各物理节点或链路均可满足虚拟网请求的资源量，并设物理节点的CPU资源总量都相等。这里忽略执行映射操作的时间。

如果按照传统的节能映射目标和节点链路的评价因素，在节能映射时不考虑延长节点或链路的运行时间等因素，那么将、、映射到、、或将其映射到、、的这2种方案的节点或链路开启量都是零，CPU资源上增加的总的资源利用率也相等。也就是说，2种映射方案得到的当时的映射目标值是相等的。而在5个时间单位后，映射到、、的方案下释放的节点和链路量较多。也就是说，不纳入时间因素的评价标准可能会增加长期的系统能耗。因此，在虚拟网节能映射中，为节点和链路设计评价标准时，应考虑时间因素，即将延长节点或链路的使用时间这一因素纳入评价要素。

综上，在对虚拟网节能映射时，对节点的评价要素包括设备是否已开启、增加的CPU资源利用率之和、是否延长设备运行时间以及延长运行时间的大小、资源剩余量等要素；对物理路径的评价要素包括需要开启的设备量、延长设备使用的时间和物理路径的长度等要素。

3.2 节点的评价标准

在为虚拟节点选取映射目标时，需要建立一种针对候选底层节点的评价标准，该标准对底层物理节点是否适合承载该虚拟节点进行评价，从而确定每个可用节点的重要性。

节点评价要素中有关节能的2个布尔型变量是物理节点是否已被开启和是否延长了物理节点的使用时间，用这2个布尔变量将可用节点集划分为3个节点集合：令1表示已开启且使用时间不会被延长的节点集；2表示已开启且使用时间会被延长的节点集；3表示未开启的节点集。这样，3个节点集1、2和3是所有可选节点样本空间的一个划分。

令A表示选中节点集S的事件，若N表示选中可用节点的事件，那么(NA)是联合概率，表示节点集S中的被选中的概率。由条件概率公式，联合概率(NA)可由条件概率与边缘概率之积得到

其中，S是节点所隶属的节点集；(N|A)表示已选中子节点集S的条件下选择节点的概率；(A)表示选择子节点集S的概率。

3.2.1 对边缘概率(A)的计算

为达到较好的节能效果，应优先选择已开启且未延长使用时间的节点，其次选择已开启且使用时间将被延长的节点，即3个节点集中元素的选中次序为1→2→3，因此，应保证隶属于3个节点集的节点联合概率的平均值满足如下关系

于是，定义(A)为

其中，常数1、2和3分别为节点集1、2和3的经验权重系数。为满足式(12)，应设置权重系数大小满足1>2>3。这里令1+2+3=1。由式(13)，。

3.2.2 对条件概率(N|A)的计算

1) 节点集1

节点集1中的节点都已被开启，且使用时间未被延长，那么，节点集内节点间的相对重要性只与CPU资源利用率的增量和资源剩余量有关。

定义节点CPU资源剩余量如下

(18)

其中，1和2为经验权重常系数。表示其该节点集中资源剩余量最小的节点，则表示该节点集中最小的资源剩余量。表示该节点集中资源剩余量最大的节点，则表示该节点集中最大的资源剩余量。表示该节点集中CPU资源总量最小的节点，则表示该节点集中最小的CPU资源总量。表示该节点集中CPU资源总量最大的节点，则表示该节点集中最大的CPU资源总量。1和2为2个相近的极小正数，1<2<<1，2用来避免2个最值相等时，使分母为0的情况；1用来避免分子为0的情况；当所有节点延长时间相等时，1和2的比值决定了对这种情况的评价值。

定义节点集1中节点被选择的条件概率

2) 节点集2

节点集2中的节点已被开启且将被延长使用时间，延长使用时间的长短对节能效果是有影响的，应优先选择延长时间较短的节点。另外，加入节点集1中的2个评价要素，可定义节点集2中节点的相对重要性为

其中，1、2和3为经验权重系数，表示节点集2中节点的最长延长时间，表示该节点集中节点的最短延长时间，表示节点将被延长的时间。

类似地，定义节点集2中节点被选择的条件概率为

3) 节点集3

节点集3中的节点尚未被开启，延长的使用时间为零，其评价要素由节点的CPU资源总量以及映射虚拟节点后CPU资源利用率增量决定。

首先定义资源量

在节点集3中，对CPU资源利用率增量的分析和节点集1中是一致的。类似于对条件概率(N|1)的定义，定义节点集3中节点的相对重要性如下

定义3中节点被选择的条件概率

(24)

以上从节点的开关状态和节点是否被延长了使用时间2个角度将底层节点分类，根据经验倾向和各节点集中元素的数量确定选择各集合的概率，即确定边缘概率；在各节点集中，从剩余资源量、CPU资源利用率增量以及所延长的节点使用时间这3个方面，综合评价隶属各节点集中物理节点的相对重要性，从而确定条件概率。

在节能目标下，为某个虚拟节点选择映射节点时，应首先为所有可用物理节点计算联合概率。联合概率值越大，说明节点的重要性越高，节点越适宜承载该虚拟节点。

3.3 物理路径的评价标准

在虚拟网映射中，节点映射成功后，通常是使用最短路径算法得到多条较短的物理路径。物理路径越长，消耗的底层链路带宽资源越多，所以从占用资源量的角度应选择最短物理路径。然而，在虚拟网节能映射中，最短路径上可能需要开启较多的物理链路，因此不一定是最节能的路径。为达到较好的节能效果，在选择物理路径时，要兼顾路径的长度、物理链路的开启量和物理链路的延长使用时间等多个因素。

最后，通过定义节能路径长度来对虚拟链路的多个可用物理路径进行评价。

由式(26)可以看出，从物理链路的延长运行时间、物理链路的开启量以及物理路径的长度这3个方面对底层物理路径做出综合评价。值越大，说明路径长度较长、需要开启的物理链路较多或延时较长，越不适于承载虚拟链路；值越小，评价结果越好，因此，取多个较短路径中值最小的作为承载路径。

3.4 映射算法

现已设计了加入时间因素的节点和链路节能评价标准，为了便于突出该评价标准的优势，采用较为简单的算法——贪婪算法。算法中，在多个可用节点中，选择概率值最高的作为映射节点；在最短路径算法[16]得到的多条最短路径中，选择值最小的作为映射路径。

下面对该算法描述如下。

算法1 TEAVNE(time and energy aware virtual network embedding)

输入 虚拟网请求拓扑G(N,L)，底层网络拓扑图G(N,L)；

输出 映射结果(E,E)。

1) 将虚拟节点按照请求资源量的大小降序排序，得到虚拟节点映射序列：

4) 如果集合中元素个数为0，返回NODE_MAP_FAILED；

6) End for

7) 将虚拟链路按照请求资源的多少降序排序，得到虚拟链路映射序列：；

10) 利用最短路径算法求出前条从E()到E()的最短路径；

11) 由式(26)计算每条路径的值，将映射到值最小的一条路径min上，即E()=min；

12) 如果最短路径不存在，返回EDGE_ MAP_FAILED；

13) End for

14) Return MAP_SUCCESS;

最短路径算法[16]的时间复杂度为(|N|log|N|+|N|+|L|)，其中，|N|和|L|分别为底层网络的节点个数和链路个数。由上述流程可知，TEAVNE算法的时间复杂度为(|L||N|log|N|+|N||L|+|L||L|+ |N||N|)，其中，|N|和|L|分别为虚拟网请求的节点个数和链路个数。

4 实验

4.1 实验环境

同文献[17]，这里设置3种不同的实验场景分别测试算法的节能效果。实验在双核CPU 3.4 GHz，4 GB内存的PC机上运行。底层网络拓扑和虚拟网请求拓扑由GT-ITM[18]工具生成。

1) 实验场景1

将该实验环境标识为中等规模—低集中（medium-sized &low-concentration），实验设置同文献[19]。

底层物理网络拓扑：底层网络共包含100个节点，每两节点间连接的概率为0.5，底层节点的CPU资源量和底层链路的带宽资源量取值在[50,100]内均匀分布。

虚拟网请求拓扑：虚拟网请求的到达时刻服从平均100个时间单元到达5个请求的泊松过程，持续时间服从均值为1 000的指数分布。每个请求的节点个数在[2,10]内均匀分布，节点连接率为0.5，虚拟节点请求的CPU资源取值在[0,20]，虚拟链路请求的带宽资源取值在[0, 25]之间均匀分布，虚拟网请求共计2 500个，实验共运行50 000个左右的时间单元。

2) 实验场景2

将该实验环境标识为中等规模—中度集中（medium-sized &moderate-concentration），实验设置同文献[17,20~23]。

底层物理网络拓扑：网络设置同实验场景1的物理网络设置。

虚拟网请求拓扑：虚拟网请求的到达时刻服从平均100个时间单元到达5个请求的泊松过程，持续时间服从均值为1 000的指数分布，每个请求的节点个数在[2,20]内均匀分布，节点连接率为0.5，虚拟节点请求的CPU资源取值在[0,50]，虚拟链路请求的带宽资源取值在[0, 50]之间均匀分布，虚拟网请求共计2 500个，实验共运行50 000个左右的时间单元。

3) 实验场景3

将该实验环境标识为小规模—高集中（small- sized & high-concentration），设置同文献[17,22~24]。

底层物理网络拓扑：底层网络共包含50个节点，每两节点间连接的概率为0.5，底层节点的计算资源和底层链路的带宽资源取值在[50,100]内均匀分布。

虚拟网请求拓扑：虚拟网请求的到达时刻服从平均100个时间单元到达4个请求的泊松过程，持续时间服从均值为1 000的指数分布。每个请求的节点个数在[2,10]内均匀分布，节点连接率为0.5，虚拟节点请求的CPU资源取值在[0,20]，虚拟链路请求的带宽资源取值在[0, 50]之间均匀分布。虚拟网请求共计2 000个，实验共运行50 000个左右的时间单元。

4) 其他参数设置

在参数设置上，同文献[25~28]中的设置，得到节点和链路能耗中常数的值为：为150 W，为300 W，为15 W。其他参数设置为1=10−6、2=10−9，1=0.5，2=0.3，3=0.2，1=0.6，2=0.4，1=0.4，2=0.4，3=0.2，=0.2，=7。

5) 比较算法

TEAVNE算法是以节能为目标分两阶段映射的贪婪算法，为检验加入时间因素的节点和链路评价标准的节能效果，并保证比较的公平性，实验选取2个较经典的同为两阶段映射的贪婪算法作为比较对象，即以最大化收益成本比为目标的贪婪映射算法SP[20]和同样以节能为目标的贪婪映射算法EAVNE[8]。

4.2 实验结果分析

4.2.1 对度量指标的定义

1) 能耗度量指标

在能耗度量指标上做如下5个定义。

定义平均节点开启量（ANON, average number of open nodes）为

定义平均链路开启量（ANOL, average number of open links）为

定义平均节点资源利用率（AUCPU, average utilization of CPU）为

定义平均链路资源利用率（AUBW, average utilization of BW）为

定义平均能耗量（AAEC, average amount of energy consumption）为

从以上定义可以看出，每次平均值的计算都是从起始时刻开始的。

2) 资源使用情况的度量指标

虚拟网映射算法一方面要满足服务提供商的构建需求，另一方面需要高效地使用基础设施提供商的物理网络资源，因此可用虚拟网映射的请求接受率和收益成本比来衡量映射算法的资源使用情况。请求接受率用来衡量虚拟网请求的映射成功率，收益成本比用来衡量已映射虚拟网的资源占用情况。请求接受率和收益成本比从不同角度反映算法对资源的使用情况，其值越高，映射算法对资源的使用越充分。这里用收益成本比来衡量资源的使用情况。

对平均收益成本比（ARRC, average ratio of revenue and cost）定义如下

(33)

由上式可以看出，在映射某个虚拟网请求时，收益成本比只和物理路径的长度有关，映射的物理路径越短，收益成本比越高。

3) 映射时间长度的度量指标

定义平均映射时间(AMT, average mapping time)为

图2 实验场景1的映射结果

4.2.2 对实验场景1的结果分析

在实验场景1（medium-sized & low- concentration）中，各算法的请求接受率均为100%，此时只需要比较各算法的节能情况。图2给出了在该场景下TEAVNE算法、EAVNE算法和SP算法的映射结果。

本文的TEAVNE算法降低了底层网络节点和链路的开启数量，很大程度地减少了底层网络能耗。图2(a)~2(c)展示了节点和链路的平均开启量以及底层网络的平均能耗量随时间变化的情况。图中表明了在开启的节点数量和能耗量上，TEAVNE算法较SP和EAVNE有较为明显的优势。这是由于TEAVNE算法在每次映射时不仅考虑本次映射的节能效果，在节点和路径的选择标准中，还加入了延长节点（或链路）的时长等因素，考虑了对后续映射的节能效果，从而使总体的节能效果更好。

TEAVNE算法提高了节点和链路的资源利用率。图2(d)、图2(e)展示了节点的CPU资源利用率和链路的带宽资源利用率随时间变化的情况。图中表明了在提高资源利用率方面，TEAVNE算法较SP和EAVNE有较明显的优势。在该场景下，各算法所接受的请求完全相同，节能算法的目标是开启尽可能少的节点和链路，即要在更少的节点和链路集合上满足相同的虚拟网请求，从而使节能效果越好，资源利用率越高。

TEAVNE算法较EAVNE算法和SP算法降低了收益成本比。图2(f)展示了平均收益成本比随时间变化的情况。图中表明了在最大化收益成本比这一目标上，TEAVNE算法较SP和EAVNE算法有较差的效果。

根据式(32)~式(34)，对于相同的虚拟网请求，收益成本比的大小只与虚拟链路映射到的物理路径长度（即虚拟链路的长度）有关。虚拟链路长度越长，收益成本比越小。在节能映射的初始阶段，将开启较小的物理链路集合，使部分物理链路的资源利用率过高，从而无法继续承载虚拟链路，这样的物理链路越多，虚拟链路将越长，甚至无法映射成功。因此，在接受相同虚拟网请求的情况下，算法的节能效果越好，收益成本比越低。

4.2.3 对实验场景2的结果分析

在实验场景2（medium-sized & moderate- concentration）中，各算法的请求接受率不再是100%。图3给出了该场景下TEAVNE算法、EAVNE算法和SP算法的映射结果。

在请求接受率不再为100%的场景下，节能算法TEAVNE依然有较好的节能效果；和另一节能算法EAVNE一样，其平均收益成本比较低。

从图3(a)~图3(e)可以看出，3种算法中，TEAVNE算法有最好的节能效果。

在收益成本比上，从图2(f)和图3(f)的对比中可以看出，请求接受率的下降伴随着收益成本比的下降。其中，SP算法的收益成本比下降幅度较小，TEAVNE和EAVNE算法的收益成本比下降幅度较大。这是由于节能算法集中映射的方式使部分链路的利用率过高，平均链路利用率越高（对比图2(e)和图3(e)），链路利用率过高的物理链路越多，虚拟链路的长度越长，从而使节能算法的收益成本比下降的幅度越大。

3种算法的请求接受率差距越来越小。从图3(g)中可以看出，SP算法的请求接受率随时间的变化不大，而节能算法TEAVNE和EAVNE的请求接受率随时间增长的下降趋势较为明显。在运行5 000个左右的时间单元后，三者的平均请求接受率相差无几。

这是由于集中映射的方式使部分节点或链路的资源利用率较高，节点或链路的负载越不均衡，请求接受率越低。

4.2.4 对实验场景3的结果分析

在实验场景3（small-sized & high-concentration）中，各算法的请求接受率较低。图4给出了该场景下TEAVNE算法、EAVNE算法和SP算法的映射结果。

两节能算法TEAVNE和EAVNE较SP算法的节能效果更加明显，TEAVNE算法较EAVNE算法在后期有更优的节能效果。从图4(a)~图4(c)可以看出，TEAVNE算法较EAVNE算法在后期有更优的节能效果。两节能算法使节点或链路的开启更加集中，节能效果更加显著。由于TEAVNE算法中加入了时间因素，纳入了对后续映射的节能效果的考虑，从而在后期，TEAVNE算法较EAVNE算法有更优的节能效果。

两节能算法较SP算法的收益成本比更低。从图2(f)、图3(f)和图4(f)可以看出，随着请求接受率的下降，两节能算法的收益成本比下降更为显著。这是由于集中映射的策略使有些链路的资源利用率过高，无法承载虚拟链路。物理链路的平均资源利用率越高（对比图2(e)、图3(e)和图4(e)），链路利用率过高的链路越多，虚拟链路的长度越长，从而降低了收益成本比。

节能算法的请求接受率较低。从图4(g)可以看出，节能算法较SP算法的请求接受较低。其中，TEAVNE算法的请求接受率最低。这是由于集中映射的策略使有些节点或链路的资源利用率过高，无法承载虚拟节点或虚拟链路。节点或链路的平均资源利用率越高，节点或链路的利用率过高的节点或链路越多，不均衡的现象越为严重，从而降低了请求接受率。

4.2.5 算法映射时间的比较

TEAVNE算法与同为贪婪算法的SP算法和EAVNE算法运行时间相当。

实验中，底层网络分别在3种拓扑环境下运行所用的平均映射时间如图5所示。

可以看出，同为贪婪算法的TEAVNE算法增加了运行时间，这是因为其在节点选择时增加了对每个节点选择概率的计算。但从图中也可以看出，平均运行时间仍保持在毫秒级，且增加量比较小。

5 结束语

本文研究了网络虚拟化环境下的系统能耗问题，根据节能运行的实际需要，设计了节能模型，然后借助条件概率理论辅助分析，在对节点和链路的节能评价中加入时间因素，最终设计了时间和能量感知的虚拟网映射算法，把虚拟网映射在一个较小的节点和链路集合中，提高关闭的节点和链路数量，以实现高效节能。实验结果表明了TEAVNE算法能够有效降低底层网络的能量消耗，由于节能算法集中映射的特点，在资源请求量较底层网络的资源剩余量较多的情况下，节能算法会降低请求接受率。于是，以节能为目标的映射是有一定的适用场景的，在确定的场景下，如何平衡节能和提高请求接受率2个相对矛盾的目标，以最大化商家的总收益，将是下一步有待深入研究的问题。

[1] CHUN B, IANNACCONE G, IANNACCONE G, et al. An energy case for hybrid datacenters [J]. ACMSIGOPS Operating Systems Review, 2010,44 (1): 76-80.

[2] APC American Power Conversion. Determining total cost of ownership for data center and network room infrastructure[EB/OL]. http://www.apcmedia.com/salestools/CMRP-5T9PQGR4EN.pdf, 2003.

[3] QURESHI A, WEBER R, BALAKRISHNAN H, et al. Cutting the electric bill for internet-scale systems[C]//The ACM SIGCOMM 2009 Conference on Data Communication. Barcelona, Spain, c2009: 123-134.

[4] China Mobile Research Institute[EB/OL]. http://v7vjw.greentouch.org/ uploads/documents/Chih-Lin_I%20-%20TIA%20Green%20from%20a% 20Service%20Provider%20Perspective .pdf. 2012.

[5] FISHER W, SUCHARA M, REXFORD J. Greening backbone networks: reducing energy consumption by shutting off cables in bundled links[C]//The 1st ACM SIGCOMM Workshop on Green Networking. New Delhi, India, c2010: 29-34.

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

LIN C, TIAN Y, YAO M. Green network and green evaluation: mechanism, modeling and evaluation [J]. Chinese Journal of Computers, 2011,34(4): 593-612.

[7] 叶可江,吴朝晖,姜晓红,等.虚拟化云计算平台的能耗管理[J].计算机学报,2012,35(6):1262-1285.

YE K J, WU Z H, JIANG X H, et al. Power management of virtualized cloud computing platform [J]. Chinese Journal of Computers, 2012,35(6): 1262-1285.

[8] BOTERO J F, HESSELBACH X, DUELLI M, et al. Energy efficient virtual network embedding[J]. IEEE Communications Letters, 2012, 16(5): 756-759.

[9] MELO M, SARGENTO S, et al. Optimal virtual network embedding: energy aware formulation[J]. Computer Networks, 2015, 91(C): 184-195.

[10] TRIKI N, KARA N, BARACHI M E, et al. A green energy-aware hybrid virtual network embedding approach[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 91(C):712-737.

[11] GUAN X J, CHOI B Y, SONG S. Energy efficient virtual network embedding for green data centers using data center topology and future migration[J]. Computer Communications, 2015, 69: 50-59.

[12] CHEN X H, LI C Z, JIANG Y L. Optimization model and algorithm for energy efficient virtual node embedding[J]. IEEE Communications Letters, 2015, 19(8): 1327-1330.

[13] NONDE L, EL-GORASHI T E H, ELMIRGHANI J M H. Energy efficient virtual network embedding for cloud networks[J]. Journal of Lightwave Technology, 2015, 33(9): 1828-1849.

[14] HOUIDI I, LOUATI W, ZEGHLACHE D. Exact multi-objective virtual network embedding in cloud environments[J]. Computer Journal, 2015, 58(3): 403-415.

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

CHEN X H, LI C Z, CHEN L Y, et al. Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J]. Journal of Software, 2014, 25(7): 1416-1431.

[16] EPPATEIN D. Finding theshortest paths[J]. SIAM Journal on Computing, 1998,28(2):652-673.

[17] CHANG X L, MI X M, MUPPALA J K. Performance evaluation of artificial intelligence algorithms for virtual network embedding[J]. Engineering Applications of Artificial Intelligence, 2013, 26(10): 2540-2550.

[18] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an Internet work[C]//IEEE INFOCOM ‘96. Conference on Computer Communications. San Francisco, CA, USA, c1996: 594-602.

[19] 江逸茗,兰巨龙, 程东年,等. 网络虚拟化环境中面向服务聚合的映射算法[J]. 软件学报, 2014, 25(6): 1328-1338.

JIANG Y M, LAN J L, CHENG D N, et al. Mapping algorithm for service aggregation in network virtualization [J]. Journal of Software, 2014,25(6): 1328-1338.

[20] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):19-29.

[21] CHENG X, SU S, ZHANG Z B, et al. Virtual network embedding through topology awareness and optimization [J]. Computer Networks, 2012, 56(6): 1797-1813.

[22] CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping [J]. IEEE/ACM Transactions on Networking, 2012, 20(1): 206-219.

[23] MI X M, CHANG X L, LIU J Q, et al. Embedding virtual infrastructure based on genetic algorithm[C]//2012 13th International Conference on Parallel and Distributed Computing Applications and Technologies(PDCAT). Beijing, China, c2012: 239-244.

[24] MOSHARAF N M, CHOWDHURY K, RAHMAN M R, et al. Virtual network embedding with coordinated node and link mapping[C]//28th Conference on Computer Communications(IEEE INFOCOM 2009). Rio de Janeiro, Brazil, c2009: 783-791.

[25] LU G, GUO C, LI YL, et al. Serverswitch: a programmable and high performance platform for datacenter networks[C]//The 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley: USENIX Association, c2011: 1-14.

[26] SIVARAMANV, VISHWANATH A, ZHAO Z, et al. Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]//2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS 2011). Shanghai, China, c2011: 331-336.

[27] UNNIKRISHNAN D, VADLAMANI R, LIAO Y, et al. Scalable network virtualization using FPGAs[C]//18th ACMSIGDA International Symposium on Field-Programmable Gate Arrays(FPGA’10). c2010: 219-228.

[28] BARROSO L A, HOLZLE U. The datacenter as a computer: an introduction to the design of warehouse-scale machines[J]. Synthesis Lectures on Computer Architecture, 2009, 6: 1-107.

Time and energy aware virtual network embedding using Bayesian theory analysis

HU Ying1, ZHUANG Lei1, CHEN Hong-chang2, MA Ding1,3

(1. School of Information Engineering, Zhengzhou University, Zhengzhou 450000, China; 2. National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China; 3. College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450000, China)

Aiming at the energy consumption problem in virtual network embedding, a virtual-network-embedding algorithm was proposed by combining the time and energy aware. Taking the running time during the evaluation of physical nodes and physical paths into account, it considered multiple factors which included the processing time of physical devices, and used probability theory to help analyze the selected probability of each available physical node for a virtual node. During the selection of substrate nodes, the factors of remaining resources, the increment of CPU utilization, the switch state and the amount of extended time of physical nodes were considered. The theory of conditional probability was further used to analyze the importance of available nodes. The factors of the switch state, the amount of extended time and the length of physical paths were also considered. The proposed approach could effectively map the current virtual network request onto a smaller set of nodes and links which are switched on, and also the devices which have less amount of extended time. Experimental results show that the proposed approach has better performance, and can effectively decrease energy consumption comparing with the methods without taking the time factor into consideration.

virtual network embedding, energy-saving, Bayesian, conditional probability, time aware

TP393

A

10.11959/j.issn.1000-436x.2016105

2015-08-06；

2016-03-10

庄雷，ielzhuang@zzu.edn.cn

国家重点基础研究发展计划（“973”计划）基金资助项目（No.2012CB315901）；国家自然科学基金资助项目（No.61379079）；河南省科技厅攻关基金资助项目（No.122102210042）

The National Basic Research Program of China (973 Program)(No.2012CB315901), The National Natural Science Foundation of China (No.61379079), Science and Technology Key Project of Henan Province (No.122102210042)

胡颖（1982-），女，河南商丘人，郑州大学博士生，主要研究方向为未来网络、网络虚拟化、虚拟网映射等。

庄雷（1963-），女，山东日照人，郑州大学教授、博士生导师，主要研究方向为未来网络、网络虚拟化等。

陈鸿昶（1964-），男，河南郑州人，国家数字交换系统工程技术研究中心教授、博士生导师，主要研究方向为未来网络、网络安全等。

马丁（1978-），男，河南郑州人，郑州大学博士生，河南工业大学讲师，主要研究方向为未来网络、网络功能虚拟化等。