软件学报  2014, Vol. 25 Issue (7): 1416-1431   PDF    
主动休眠节点链路的高效节能虚拟网络映射
陈晓华1,3, 李春芝2,3, 陈良育1, 曾振柄4    
1. 华东师范大学 软件学院, 上海 200062;
2. 华东师范大学 计算机科学技术系, 上海 200241;
3. 湖州师范学院 信息与工程学院, 浙江 湖州 313000;
4. 上海大学 数学系, 上海 200444
摘要:网络虚拟化,使得智能能量感知网络部署成为可能.由于当前网络为高峰负荷而设计,导致资源利用率不足及能量浪费.而网络设备能量消耗对于流量负载不敏感,资源整合成为有效节能技术.根据虚拟网络映射特点及底层网络能耗,提出虚拟网络映射节能多目标决策模型;由于该模型是混合整数规划模型,求解时间复杂度高,通过分析虚拟网络映射动态特征,构造虚拟网络映射字典库,提出底层网络资源利用率的训练方法以及主动休眠底层节点和链路算法,把虚拟网络映射在一个较小的节点和链路集合中,提高休眠节点和链路数量,实现高效节能虚拟网络映射.系统仿真结果验证了主动休眠方法能够提高底层节点和链路休眠数量,显著减少系统能耗.
关键词虚拟网络映射     主动休眠     高效节能     资源整合    
Energy Efficient Virtual Network Embedding Based on Actively Hibernating Substrate Nodes and Links
CHEN Xiao-Hua1,3, LI Chun-Zhi2,3, CHEN Liang-Yu1, ZENG Zhen-Bing4    
1. Software Engineering Institute, East China Normal University, Shanghai 200062, China;
2. Department of Computer Science and Technology, East China Normal University, Shanghai 200241, China;
3. School of Information and Engineering, Huzhou Teachers College, Huzhou 313000, China;
4. Department of Mathematics, Shanghai University, Shanghai 200444, China
Corresponding author: LI Chun-Zhi, E-mail: lichunzhi82@126.com, http://www.ecnu.edu.cn
Abstract: Network virtualization will be an enabler for intelligent energy-aware network deployment. Current networks are designed for peak loads, resulting in inadequate resource utilization and energy consumption waste. Due to current power consumption insensitiveness of network equipment to traffic load, resource consolidation becomes an effective energy-saving technology. Based on the virtual network mapping characteristics and the substrate network energy consumption, this paper presents a multi-objective decision-making model that is also a mixed integer programming model for energy efficient virtual network embedding. To address high time complexity in solving the mixed integer programming model, the paper analyzes the dynamic characteristics of the virtual network mapping, constructs virtual network mapping dictionary database and proposes a method for training substrate network resource utilization, as well as an algorithm which actively hibernates the substrate nodes and links. By this method, the virtual network can be embedded in a smaller set of substrate nodes and links, which helps to increase the number of hibernating substrate nodes and links, and achieve energy-effective virtual network mapping. Simulation results demonstrate the proposed method can effectively improve the number of hibernating nodes and links of substrate network, and significantly reduce energy consumption of substrate network.
Key words: virtual network embeding     actively hibernate     energy efficient     resource consolidation    

随着电力成本不断上涨和人们生态意识的提高,网络运营商已经意识到能耗管理的重要性,减少能耗已成为亟待解决的问题.当前网络为高峰负荷而设计,网络资源超量供给确保了网络的正常运行,然而也导致资源利用率低下.据统计,大型ISP骨干网的平均链路利用率大约为30%~40%[1],数据中心服务器的平均利用率为11%~50%[2, 3].过低的利用率造成了巨大的电能浪费,促使绿色网络研究的兴起,网络能耗问题成为研究热点[4, 5].

网络虚拟化[6]是未来因特网、云计算和软件定义网络的重要技术[7, 8, 9, 10, 11],其通过整合网络基础设施资源,能够合理有效地使用能量,使得智能能量感知网络部署成为可能.虚拟网络映射是网络资源虚拟化的关键问题.当前,大部分映射算法是基于代价的虚拟网络映射[12],即,以最小化底层资源代价映射虚拟网络请求,以此获得更多的底层物理资源,进而提高虚拟网络接收率与系统收益.然而,由于虚拟网络请求是一个动态变化的过程,而底层物理网络根据流量峰值设计,基于代价的虚拟网络映射必然带来不必要的能耗.以节能为目标的虚拟网络化映射,应在满足当前虚拟网络请求的前提下最小化能耗.由于当前网络设备对流量 负荷的功耗不敏感[13],因此在不影响虚拟网络映射性能的情况下,尽可能多地关闭或休眠网络节点和链路是节能的有效方法.

当前,基于能量感知的虚拟网络映射通过修改虚拟网络映射算法,使得虚拟网络尽可能地映射到活动的节点和链路,以达到系统节能的目的.如:文献[14]通过减少物理网络设备数量分配虚拟网络请求集合,提出混合整数规划的能量感知最优化模型,但是时间复杂度呈指数增长,难以适应大规模网络基础设施的虚拟网络映射;文献[15]考虑到机箱能耗比路由能耗低的特点,提出扩展流量到网络资源的节能方法,但只适合对负载敏感的设备;文献[16]提出虚拟网络重配置的最小化能耗的启发式方法;北京邮电大学的苏森等人提出虚拟网络映射能耗模型以及能量感知两阶段映射算法[17];北京交通大学的常晓林、王冰等人提出混合整数规划能耗模型及能量感知两阶段映射算法[18];文献[19]在云数据中心中应用蚁群优化算法求解虚拟网络节能映射.可见,目前相关节能感知映射算法是通过修改虚拟网络映射算法,被动地休眠网络节点和链路.

本文考虑虚拟网络映射成本收益比以及系统能耗,提出多目标决策的虚拟网络映射能耗模型,在保证虚拟网络映射收益成本比的前提下降低系统能耗.由于该模型是混合整数规划模型,求解时间复杂度高,我们通过分析虚拟网络映射动态特征,定义系统饱和与非饱和状态,并提出主动休眠底层节点和链路的方法,把虚拟网络映射在一个较小的节点和链路集合中,提高休眠节点和链路数量,有效节约系统能耗.

本文第1节分析虚拟网络映射模型和底层物理网络能耗模型,建立虚拟网络映射多目标决策模型.第2节分析虚拟网络映射动态特征,构建虚拟网络映射字典库,设计底层网络资源利用率的训练方法,建立休眠底层节点和链路公式,设计主动休眠链路算法.第3节仿真验证了在系统非饱和状态下主动休眠链路算法节能的有效性.最后是总结和展望.

1 虚拟网络映射及其能耗模型

网络虚拟化节能映射,应在保证虚拟网络映射收益成本比的前提下降低系统能耗.本节首先描述了虚拟网络映射模型和底层物理网络能耗模型,然后提出多目标决策的虚拟网络映射能耗模型.

1.1 虚拟网络映射模型

虚拟网络映射是网络虚拟化的主要问题之一,下面介绍底层网络、虚拟网络以及虚拟网络映射模型.

· 底层网络

本文通过无向图对底层网络建模,其中,Ns为节点集合,Ls为链路集合,为节点属性集合,为链路属性集合.本文设置节点属性为CPU处理器资源,链路属性为带宽资源.

· 虚拟网络

与底层网络相同,本文通过无向图对虚拟网络建模,其中,Nv为节点集合,Lv为链路集合, 为节点属性集合(CPU处理器资源),为链路属性集合(带宽资源).

· 虚拟网络映射

把虚拟节点和链路映射到满足虚拟资源需求的底层节点和路径,可进一步分为节点映射和链路映射.节点映射分为:一个虚拟网络的不同节点不允许映射到同一节点、一个虚拟网络的不同节点可映射到一个节点.链路映射分为单路径映射和多路径映射[20].本文假设在一个虚拟网络的不同节点不允许映射到同一节点的情况下,研究虚拟网络节能映射问题.

1.2 底层网络能耗

底层网络的能耗主要包括节点能耗和链路能耗两个部分.

网络节点主要是服务器,其能耗主要包括处理器、内存、磁盘I/O以及用于冷却的风扇,其中,处理器和内存占有节点能耗的大部分.当前,处理器能耗与负载具有较好的相关性,例如Intel公司的Speedstep以及AMD公司的PowerNow技术,处理器能够根据负载动态地调节性能[4].本文抽象节点的属性为处理器的属性,网络节点的能耗与该节点承载的虚拟网络节点总和成比例关系.定义第i个节点能耗为

(1)

其中,Pb为节点的基本能耗,Pm为节点的最大能耗,Pl=Pm-Pb为与处理器利用率u的能耗因子.

由于当前网络设备对流量负荷的功耗不敏感[13],通常认为专有的减负引擎将被广泛地部署在网络虚拟化中[21, 22, 23],因为这种引擎既能够保持高的数据包处理率,又能够产生低的处理延时.无论接口是否空闲或者满负荷运行,网络链路的能耗Pn为常量[22, 24].定义第j条链路能耗为

(2)

底层网络的节点和链路能耗模型为虚拟网络映射多目标决策模型提供了现实基础.

1.3 虚拟网络映射多目标决策模型

基于代价的虚拟网络映射,是以收益成本比最大化为目标,基于能耗的虚拟网络映射应在满足系统收益成本比最大化的前提下,实现节能的目标.本节把基于能耗的虚拟网络映射转化为多目标决策模型,采用分层法建模,如下所示:

设定收益成本比r/c和系统能耗Paver这两个目标,并给出重要性序列:r/c,PAver.首先针对r/c目标,找到满足最大r/c的虚拟网络映射解集合R0;然后在R0内,求满足最小系统能耗PAver的虚拟网络映射解集合R1.这样就把虚拟网络映射问题转化为多目标决策模型,具体虚拟网络映射的多目标决策模型如下所示.

· 目标函数:

(3)

· 映射成本比最大化约束:

(4)

· 容量约束:

(5)

(6)

· 传输约束:

(7)

· 一个虚拟节点映射到一个底层节点的约束:

(8)

· 相同虚拟节点不能映射到同一底层节点的约束:

(9)

其中,

· CPU(j)表示,如果j是底层节点,则CPU(j)是j剩余CPU资源量;如果j是虚拟节点,则CPU(j)是j请求的CPU资源量;

· BWL(ljk)表示如果ljk为底层链路,则BWL(ljk)是ljk剩余带宽;如果ljk为虚拟链路,则BWL(ljk)是ljk请求

带宽;

· Bw(lv,ls)为虚拟链路lv分配的底层链路ls带宽;

· 为二进制变量,若虚拟节点u映射到底层节点j上,则;否则

· NNo为虚拟网络节点数量;

· 为二进制变量,若虚拟链路luv映射到底层链路ljk上,则,否则

· 表示底层节点ij为虚拟网络分配的带宽总量,由一个或者多个虚拟链路luv带宽组成, LDBW(u,w)为虚拟链路luw带宽.

根据不同的链路映射条件具有不同的涵义,即,单路径链路映射与多路径链路映射.的约束是

不同的,下面介绍单路径流以及多路径流的概念.

· 单路径流

在底层网络中,设path是底层节点st的一条无环路径,满足下述条件的函数flow称为stpath上的可行流.

(1) 容量限制条件:在path中的每条边(i,j),满足0≤flow(lij)≤BWL(lij);

(2) 方向条件:"i,jÎNs,flow(lij)=-flow(lji),单路径流有方向性;

(3) 平衡条件:对于中间点,流出量等于流入量,即在path中对每个u(u¹s,t),有;对于st,

· 多路径流

在底层网络中,st是底层的两个节点,则st的多路径流mflow由多条单路径流flow组成,同时满足以下条件:

(1) 容量限制条件:每条边(i,j),满足0≤mflow(lij)≤BWL(lij);

(2) 方向条件:"i,jÎNs,mflow(lij)=-mflow(lji),多路径流有方向性;

(3) 平衡条件:对于中间点,流出量等于流入量,即:对每个u(u¹s,t),有;对于st,

如果为单路径流flow,则映射为单路径链路映射;如果为多路径流mflow,则映射为多路径链路

映射.

设计的多目标决策模型实现了在保证虚拟网络映射成本比r/c最大化下的系统能耗最小化,同时,该模型是基于混合整数规划模型的多目标决策模型;由于混合整数规划求解时间复杂度随着问题规模呈指数增长,本文分析网络虚拟化动态特征,设计基于主动休眠节点和链路的启发式算法,找到虚拟网络映射解.

2 底层网络资源主动休眠

本文根据虚拟网络映射动态特征,定义系统饱和状态与非饱和状态,构建虚拟网络映射字典库,提出底层网络资源利用率训练方法;定义底层网络节点和链路休眠公式;然后,采取主动休眠底层节点和链路的方法,缩小虚拟网络映射的底层网络资源范围,以提高休眠节点和链路数量,达到底层网络节能目的.

2.1 一个节能例子

在负荷较低的情况下,底层网络具有足够的资源使得虚拟网络接受率和系统收益达到最大值,系统节能成为重要目标.如图 1所示,底层网络具有足够的资源,能够全部接收两个虚拟网络请求,其中,方案(a)的映射使得所有节点和链路资源处于激活状态;而方案(b)把虚拟网络映射到较小的底层资源集合中,使得节点D以及与之连接的两条链路(灰色表示)未被映射,可以进入节能休眠状态.本文在底层网络资源中找到一个集合,该集合中的所有节点和链路可以休眠,而对应的补集能够接受所有的虚拟网络请求.具体方法是:首先,根据虚拟网络映射的动态特征,构建虚拟网络映射字典库;然后,由机器学习方法训练出底层网络最大资源利用率;最后,求解最大资源量与当前虚拟网络请求资源量之间的差额,得到可以休眠的底层网络资源数量,从而主动休眠底层节点和链路,实现节能的目的.

Fig. 1 An example of energy-saving virtual network mapping 图 1 虚拟网络映射节能例子
2.2 网络虚拟化动态特征及系统状态

网络虚拟化动态特征包括虚拟网络、底层网络和虚拟网络映射算法动态特征,具体如下:

· 虚拟网络动态特征:虚拟网络请求的到来时间、存在时间、虚拟网络节点个数、虚拟链路条数,节点CPU、链路带宽等;

· 底层网络动态特征:随着虚拟网络请求的到来和离开,底层网络剩余CPU、链路剩余带宽资源量和分布将会动态地发生变化;

· 映射算法动态特征:随着虚拟网络请求资源量的变化,在不同映射算法下,底层网络资源利用率、虚拟网络接收率和系统收益是不同的.

系统饱和状态以及非饱和状态:虚拟网络全部接收的状态为系统非饱和状态;反之,为饱和状态.

当系统处于非饱和状态时,底层网络具有足够的资源,能够映射所有的虚拟网络请求,虚拟网络接收率达到100%,系统收益达到最高值;当系统处于饱和状态时,底层网络没有足够的资源,不能映射所有的虚拟网络请求,虚拟网络接收率小于100%.

2.3 构建虚拟网络映射字典库

由于虚拟网络映射具有动态特征,虚拟网络映射字典库的数据项包括虚拟网络特征值、底层网络特征值以及虚拟网络算法映射结果.

· 虚拟网络特征值

Rv表示一个时间窗内到达的虚拟网络请求数量,其数学期望为E(Rv);表示一个虚拟网络的链路数量,其数学期望为表示一条虚拟链路带宽,其数学期望为;Sv表示一个虚拟网络的生存时间,其数学期望为E(Sv);设表示一个虚拟网络的节点数量,其数学期望为表示一个虚拟节点CPU处理器资源量,其数学期望为

· 底层网络特征值

表示一条底层链路带宽的数学期望,表示一个底层节点CPU资源的数学期望,底层节点数量为|Ns|;底层链路数量为|Ls|.

· 虚拟网络映射结果

映射算法名称AName、虚拟网络接收率mr、收益成本比r/c、底层链路资源利用率crl、底层节点资源利用率crn.crlcrn是长期平均的利用率:crl使用的是已利用的底层带宽总和除以底层带宽总和的计算方法,crn使用的是已利用的底层节点CPU总和除以底层节点CPU总和的计算方法.

构造虚拟网络映射字典库的方法是:创建多组具有相同动态特征的虚拟网络请求和多个底层网络;然后,分别运行虚拟网络映射算法,并记录结果.为了保证性能评估的稳定性,记录长期虚拟网络映射结果,其中,每个相同特征的虚拟网络请求构造多组,取特定特征的底层网络.即:在特定特征的底层网络的基础上,每次映射多组具有相同动态特征的不同虚拟网络请求.

2.4 底层节点与链路资源利用率训练算法

基于虚拟网络映射字典库,根据输入底层网络、虚拟网络和算法名称,训练底层网络资源利用率,如算法1所示.设X为输入的特征向量,包括底层网络特征项、虚拟网络特征项;设M为字典库的历史数据数量,字典库有M个特征向量,表示为Y1,Y2,…,YM;特征向量X与字典库第i个特征向量Yi相同,由底层网络特征项、虚拟网络特征项组成.字典库的字段包括crl,crn;而Yi由其中的一部分组成,包括

XYi的欧几里德距离为

(10)

第1步,通过底层网络、映射算法名称和设定mr的范围,过滤虚拟网络映射字典库;采用公式(10)计算特征向量X与字典库的特征向量Yi的距离Di(X);根据Di(X)降序排列,取Nov个最小项组成历史数据集合A,其字段包括了Yi特征项以及mr,r/c,crl,crn等信息.字典库中存在着不同特征的虚拟网络映射结果(即,E(Rv),

E(Sv),是不同的),公式(10)能够识别出相同特征的虚拟网络映射结果.Nov的取值与字典库中虚拟网络映射训练的数量有关,本文设置为100,表示每个相同拓扑结构的虚拟网络请求记录了100组映射数据.

第2步,按照优先mr降序、其次升序的规则,排序A中数据项,取Nov个最小的数据项,然后计算底层节点与链路的利用率平均值,设置crlcrn.

基于网络特征期望值而训练crlcrn,是一种机器学习的估算方法.通过XYi的欧几里德距离的匹配,能够找到有效历史数据项.取Nov个最小有效数据项的平均值,可减少虚拟网络映射动态性对系统性能的影响.算法1从字典库中训练有效的crlcrn,下文的算法2通过算法1计算主动休眠底层节点和链路数量.算法1的时间复杂度取决于选择的排序算法时间复杂度,故时间复杂度较低.

算法1. 训练底层节点与链路的利用率算法.

输入:虚拟网络映射字典库,底层网络,虚拟网络,映射算法名称;

输出:底层节点与链路的利用率.

1. 设定底层网络、映射算法名称和mr范围,筛选历史数据信息集合;然后,根据公式(10)的判别函数计算距离Di(X),并根据Di(X)降序排列,取Nov个最小项组成历史数据集合A;

2. 按照优先mr降序、其次升序的规则,排序A中的数据项;取Nov个最小数据项,计算 底层节点与链路利用率平均值,设置crlcrn,并输出.

2.5 节点和链路主动休眠

由于当前底层网络为高峰负荷而设计,则当系统处于非饱和状态时,必然存在一个底层网络资源集合,能够保证虚拟网络映射性能.这个底层网络资源集合包含于底层网络资源.通过计算底层网络资源与映射虚拟网络请求的所需资源之间的差额,求解主动休眠底层网络节点和链路数量,以休眠底层网络节点和链路,从而缩小了底层网络资源集合,提高了休眠节点和链路数量,达到了减少系统能耗的目的.

2.5.1 链路休眠数量

根据一个时间窗虚拟请求个数、虚拟链路数量、虚拟链路带宽、生存时间和虚拟网络接收率,计算映射的虚拟网络链路资源Res(VSl),即:

(11)

在非饱和状态下,公式(11)中的mr为1,是一个时间窗的虚拟网络请求链路资源的总和.

底层网络链路总会存在一部分链路资源碎片不能利用,因此设定链路资源整体利用率crl.通过crl以及底层物理链路的总和,计算可使用的底层链路网络链路资源Res(Sl),即:

(12)

其中,bws为底层网络带宽,为底层网络带宽总和.

在非饱和状态下,可以休眠底层链路,以达到节能的目的,计算休眠的底层链路数量sleepl公式如下:

(13)

其中,Res(Sl)为非饱和状态下的可以使用的底层网络链路资源;crl通过训练得到,针对不同的映射算法,crl是不同的; Res(VSl)通过公式(11)计算,表示一个时间窗的所有虚拟网络链路资源总量;INT_表示取下整函数.

根据sleepl的计算结果,判断是否可以休眠链路:如果sleepl大于0,说明可以通过休眠底层链路的方式节能;如果小于等于0,则说明不能通过休眠链路的方式节能,否则将会影响系统收益以及虚拟网络接收率.

2.5.2 节点休眠数量

根据一个时间窗虚拟请求个数、虚拟节点数量、虚拟节点CPU处理器资源量、生存时间和虚拟网络接收率,计算映射的虚拟网络节点资源Res(VSn),即:

(14)

在非饱和状态下,公式(14)中的mr为1,是一个时间窗的虚拟网络请求节点资源的总和.

底层网络节点总存在一部分节点资源碎片不能利用,设定节点资源整体利用率crn.通过crn以及底层节点CPU资源量的总和,计算可使用的底层节点资源Res(Sn),即:

(15)

其中CPUs为底层网络CPU资源量,为底层网络CPU资源量总和.

在非饱和状态下,可以休眠底层节点,以达到节能的目的,计算休眠的底层节点数量sleepn的公式如下所示:

(16)

其中,Res(Sn)为非饱和状态下可以使用的底层网络节点资源;crn通过训练得到,针对不同的映射算法,crn是不同的;Res(VSn)通过公式(14)计算,表示一个时间窗的所有虚拟网络链路资源总量.

根据sleepn的计算结果,判断是否可以休眠节点:如果sleepn大于0,说明可以通过休眠底层节点的方式节能;如果小于等于0,则说明不能通过休眠节点的方式节能,否则将会影响系统收益以及虚拟网络接收率.

2.5.3 主动休眠节点和链路算法

主动休眠底层节点和链路需要注意两点:① 在非饱和状态下,休眠节点和链路应该考虑到底层网络的连通性,即,休眠节点的同时应该考虑休眠链路,在休眠链路的同时也应该考虑休眠节点,两者之间相互关联;② 在休眠底层节点和链路时,应满足休眠节点总数小于等于sleepn且休眠链路总数小于等于sleepl.设计主动休眠底层节点和链路算法如算法2所示.

算法2. 主动休眠底层节点和链路算法.

输出:休眠的节点和链路集合.

1. 根据公式(13)和公式(16),求出底层链路休眠数量sleepl和节点休眠数量sleepn;

    1.1. 根据第1个时间窗的虚拟网络请求、当前底层网络以及当前算法,调用算法1,得到系统非饱和状态下的节点资源整体利用率crn和链路资源整体利用率crl;

    1.2. 根据公式(11),设定mr等于1,计算虚拟网络链路资源Res(VSl);

    1.3. 根据公式(12),求出底层网络可以利用的链路资源Res(Sl);

    1.4. 根据公式(13),求出底层链路休眠数量sleepl;

    1.5. if (sleepl小于等于0),则不休眠任何链路,返回;

    1.6. 根据公式(14),设定mr等于1,计算虚拟网络节点资源Res(VSn);

    1.7. 根据公式(15),求出底层网络可以利用的节点资源Res(Sn);

    1.8. 根据公式(16),求出底层节点休眠数量sleepn;

    1.9. if (sleepn小于等于0),则不休眠任何节点,返回;

2. 初始化所有的节点和链路为激活状态;sln=0;snn=0;求出底层网络节点的度;

3. while (sln<sleepl & & snn<sleepn) do

4.     找到激活的最小度的节点node;if (没有找到有效的node) break;

5.     foreach (与node节点连接的所有激活底层链路lw) {

6.             休眠链路lw,并更新与该链路连接的两节点uv的度,sln++;

7.             if (节点u的度==0) {休眠u节点;snn++;}

8.             if (节点v的度==0) {休眠v节点;snn++;}

9.             if (slnsleepl||snnsleepn) break;

10.         }

11. end while

12. return 休眠的底层节点和链路.

底层节点和链路休眠算法的关键是第1步,求出可休眠的底层节点和链路数量sleepnsleepl.由训练算法计算系统非饱和状态下的crncrl;根据公式(11)~公式(13),求出底层链路休眠数量sleepl;根据公式(14)~公式(16),求出底层节点休眠数量sleepn.如果sleepl小于等于0或者sleepn小于等于0,则说明难以通过休眠的方式在不影响映射收益比的前提下节约系统能耗.第2步,sln为底层链路已经休眠的数量,snn为底层节点已经休眠的数量,计算底层网络节点的度.第3步~第11步,找到最小度的激活节点,休眠该节点以及与该节点相连的链路,并记录休眠底层节点和链路数量,更新底层节点的度,这样可以保证底层网络的连通性.特别是第3步,应满足sln<sleepl & & snn<sleepn条件,表示休眠底层节点或链路必须同时不能超过通过公式(13)和公式(16)计算的数量,否则将会影响收益成本比、系统收益及虚拟网络接收率.

算法2保证了底层网络的连通性,同时能够尽可能主动地休眠底层节点和链路数量,达到节能的目的.算法2的算法时间复杂度为o(l×n),l为底层网络链路数量,n为底层网络节点数量.

2.6 性能评价指标

主动休眠底层节点和链路的方法可提高底层网络资源休眠数量,节约系统能耗,设定能量消耗、休眠节点数量、休眠链路数量和收益成本比为性能评价指标.

2.6.1 能量消耗

底层网络的能量消耗由节点和链路能耗两部分组成.虚拟网络映射将会导致底层网络的节点和链路处于激活状态或者休眠状态,且底层网络节点负载随着虚拟节点的映射而发生变化,其处理器的利用率将会产生变化,从而影响底层网络的能耗.

定义在第t个时间窗底层网络能耗为

定义底层网络在总共T个时间窗内能耗总量为

Tn为一个时间窗占用的时间单元,定义平均每个时间单元能耗为

PAver为比较不同映射算法能耗的重要性能指标,在系统非饱和状态下,应尽量提高休眠底层节点和链路数量,降低PAver.

2.6.2 休眠节点数量

底层节点分为休眠节点和激活节点.休眠节点是指未承载任何虚拟节点,与之相连的底层链路未承载任何虚拟链路.激活节点分为两类:第1类是指既承载了虚拟节点,与之相连的链路最少也承载一条虚拟链路,称为活动节点;第2类是指未承载虚拟节点,但与之相连的链路最少承载一条虚拟链路,称为传输节点.活动节点能耗为Pb+Pl×u,传输节点能耗为Pb,休眠节点能耗为0.

定义:

定义在第t个时间窗底层休眠节点数量为

定义底层网络在总共T个时间窗内,底层休眠节点总量为

定义每个时间窗的平均休眠节点数量为

2.6.3 休眠链路数量

底层链路分为休眠链路和激活链路.休眠链路是指未承载任何虚拟链路的底层链路.激活链路是指最少承载一条虚拟链路的底层链路.活动链路能耗为Pn,休眠链路能耗为0.

定义:

定义在第t个时间窗底层休眠链路数量为

定义底层网络在总共T个时间窗内,底层休眠链路总量为

定义每个时间窗的平均休眠链路数量为

2.6.4 收益成本比

定义系统收益:

其中,为接收的虚拟网络链路带宽总和,为接收的虚拟网络节点CPU总和.

定义映射代价:

其中,为底层网络所消耗的带宽总和.

定义长期平均收益成本比:

3 虚拟网络映射主动休眠节点节能仿真

本节首先介绍仿真环境、比较算法和构建的字典库,然后介绍参数训练、节能和其他方面的比较.其中,系统节能仿真在非饱和状态下进行,从休眠节点数量、休眠链路数量和能量消耗这3个方面讨论本文所提算法的节能性能.

3.1 仿真环境

由于网络虚拟化是一个新兴领域,底层网络与虚拟网络请求的实际特征还没有得到充分掌握,因此,本文采用对称网络拓扑结构.采用GT-ITM工具[25]随机生成一个由100个节点、570条链路组成的底层网络拓扑,相当于一个中等规模的物理网络.底层网络节点CPU资源和链路带宽资源服从50-100的均匀分布.每个时间窗为100个时间单元.虚拟网络请求过程模拟泊松过程,在每个时间窗内虚拟网络请求到达个数服从均值为20的泊松分布,每个虚拟网络的生存时间服从均值为5个时间窗的指数分布,每个虚拟网络请求节点个数服从2-20的均匀分布,每对虚拟网络节点以0.5的概率相连.虚拟网络节点CPU资源与链路带宽资源需求服从0-6的均匀分布.每个虚拟网络请求等待映射的时间为1个时间窗.每次模拟实验运行约50 000个时间单元,包含10 000个虚拟网络请求.根据文献[22, 26],本文设置第1.2节中定义的Pb,PmPn分别为150W,300W和15W;由于不同环境下的链路功耗差异较大[27, 28],本文比较了链路功耗下在1W,15W,30W的系统能耗,如后文图 6所示.为了提高实验结果的置信水平,所有的实验运行10组不同虚拟网络请求,然后取平均值作为结果.

3.2 比较算法

虚拟网络映射问题是NP-hard问题,随着网络规模(包括虚拟网络和底层网络)的扩大,基于整数规划的虚拟网络映射求解难以满足虚拟网络映射的实时性要求,因此,本文不与整数规划的方法进行比较,而选择基于能耗感知的启发式算法[17]与元启发式算法[19]以及经典的虚拟网络映射启发式算法[29],即,EA-VNE[17],ACO-PE- VNE[19]及PR-VNE[29]进行比较,并在EA-VNE,ACO-PE-VNE和PR-VNE上应用了本文提出的主动休眠节点和链路方法,即,AS-EA-VNE,AS-ACO-PE-VNE和AS-PR-VNE.具体实现如下:首先统计第1个时间窗内所有的虚拟网络请求动态特征参数,然后根据算法2主动休眠底层节点和链路;再分别采用EA-VNE,ACO-PE-VNE或者PR-VNE算法,映射限制在未主动关闭的底层节点和链路集合中.特别说明的是:每次映射虚拟网络请求不需要重新主动休眠底层节点和链路,主动休眠只发生在第1个时间窗,且不同算法采用不同的单路径链路映射.

3.3 虚拟网络映射字典库

根据比较算法,虚拟网络映射字典库记录EA-VNE,ACO-PE-VNE和PR-VNE算法的映射结果.底层网络采用第3.1节中介绍的由100个节点、570条链路组成的对称网络拓扑结构.虚拟网络与第3.1节的仿真环境基本相同,所不同的是,虚拟网络节点CPU资源与链路带宽资源需求分别服从0-4,0-5,0-6,0-7,0-8,0-9,0-10,0-11, 0-12,0-13的均匀分布,意味着节点和链路资源量的期望值为2,2.5,3,3.5,4,4.5,5,5.5,6,6.5,即,有10个不同动态特征的虚拟网络请求.每个相同特征的虚拟网络创建10组不同实例,总共有100组不同实例;每组实例有10 000个虚拟网络请求,总共映射了1x106个虚拟网络请求;3种算法在100组虚拟网络实例上映射,数据字典总共记录了300组虚拟网络映射结果.

3.4 仿真结果 3.4.1 参数训练

1) 在保证mr=1的条件下,底层网络资源利用率存在最大值.

图 2显示随着节点CPU和链路带宽的期望值的增加,数据字典库中3种算法的接收率、链路资源利用率以及节点资源利用率的变化趋势,即:随着节点和链路资源量期望值的增长,链路和节点的资源利用率随之增长,虚拟网络接收率保持100%,直到节点和链路资源量在4.5时出现下降趋势.这给了我们一个启示:在非饱和状态,底层网络能够接收虚拟网络资源存在最大值,表现在节点和链路资源利用率上,即EA-VNE,PR-VNE和ACO-PE-VNE的链路资源利用率最大值分别在0.298 539,0.311 195和0.325 887附近,节点资源利用率最大值分别在0.592 600 4,0.669 519 8和0.6 69 492 2附近.

Fig. 2 Average node utilization, link utilization and acceptance ratio in dictionary database 图 2 字典库的节点和链路资源利用率以及接收率

2) mrNov对资源利用率训练值的影响.

图 3中图例对应着[mr,Nov],例如,[0.999,20]表示mr的范围为[0.999,1]以及Nov为20,意味着算法1统计虚拟网络接收率在0.999以上的字典库数据项,取20个数据项的平均值作为训练的crncrl.从图 3可以看出:随着mr范围的扩大以及Nov的减小,所训练的crncrl逐渐增大.当mr范围为[0.9999,1]、Nov为20时,资源利用率最小,EA-VNE,PR-VNE和ACO-PE-VNE训练的crl分别为0.2871 194,0.291 995 25和0.307 2768 5,crn分别为0.644 253 35,0.700 267 35和0.623 920 05;当mr范围为[0.999,1]、Nov为10时,资源利用率最大,EA-VNE, PR-VNE和ACO-PE-VNE训练的crl分别为0.330 187 7,0.348 522 9和0.35 2 377 2,crn分别为0.738 213 2,0.813 139 9和0.797 208 9.

Fig. 3 Average node and link utilization of different mr and Nov value 图 3 不同mrNov下的链路与节点资源利用率

3) 算法2能够训练出有效的主动休眠节点和链路数量.

mr,Nov不同取值下,主动休眠节点和链路数量的期望值与标准差见表 1,可以看出:随着mr范围的扩大、Nov取值的减小,主动休眠的底层链路和节点数量逐渐增多;不同算法主动休眠底层节点和链路数量是不同的;3种算法的休眠链路和节点数量具有相近的标准差,这表明训练方法能够适应多种算法.

Table 1 Expected value and standard deviation of the training number of active-sleeping nodes and links 表 1 训练的主动休眠节点和链路数量期望值与标准差
3.4.2 节能比较

1) 本文提出的主动休眠方法显著提高了底层网络节点和链路休眠数量,很大程度地减少了系统能耗.

图 4表示在mr范围为[0.999,1]、Nov为20、Pn为15W的环境下,平均运行51~504个时间窗底层休眠节点和链路数量以及系统能耗的变化情况.图 4(a)、图 4(b)表明,AS-EA-VNE,AS-PR-VNE和AS-ACO-PE-VNE算法较EA-VNE,PR-VNE和ACO-PE-VNE至少提高了25%的休眠节点数量和10.9%的链路数量.图 4(c)显示, AS-EA-VNE, AS-PR-VNE和AS-ACO-PE-VNE的系统能 耗较EA-VNE,PR-VNE和ACO-PE-VNE分别降低了11.7%,6.7%和14.5%.这是因为在非饱和状态下,基于主动休眠方法把虚拟网络映射在一个较小的节点和链路集合中,使得其他底层节点和链路能够休眠,从而提高了休眠节点和链路数量,降低了系统能耗.

Fig. 4 Average number of hiberating nodes and links, and energy consumption 图 4 休眠节点、链路数量及系统能耗

2) 主动休眠节点和链路数量对系统能耗的影响.

图 5给出Pn为15W环境下运行500个时间窗的系统能耗情况,图例中的0/0,100/20和200/30表示主动休眠底层链路数量/主动休眠底层节点数量.图 5表明:随着主动休眠底层链路和节点数量的增大,底层网络能耗逐渐降低.即:底层网络主动休眠链路和节点数量越多,底层网络越节能.0/0表示未主动休眠底层链路和节点,AS-EA-VNE,AS-ACO-PE-VNE,AS-PR-VNE算法即是EA-VNE,ACO-PE-VNE,PR-VNE算法.在主动休眠200条链路和30个节点时,系统能耗 最少,AS-EA-VNE,AS-ACO-PE-VNE,AS-PR-VNE能耗比EA-VNE,ACO-PE- VNE,PR-VNE分别降低了23.8%,24.3%和13.3%.

Fig. 5 Energy consumption in different hiberating number 图 5 主动休眠数量对底层网络能耗的影响

3) 底层链路功耗参数对能耗的影响.

图 6给出在mr范围为[0.999,1]、Nov为20环境下底层链路功耗分别在1W,15W,30W下的系统能耗情况.图 6显示出:链路能耗越大,系统能耗越多;主动休眠算法在不同的链路能耗下都能够实现节能目标,这是由于主动休眠方法使得更多的底层资源可以进入休眠节能状态.当链路能耗在1W时,AS-EA-VNE,AS-ACO-PE-VNE, AS-PR-VNE的能耗比EA-VNE,ACO-PE-VNE,PR-VNE分别降低了11%,14.8%和5.8%;当链路能耗在30W时, AS-EA-VNE,AS-ACO-PE-VNE,AS-PR-VNE的能耗比EA-VNE,ACO-PE-VNE,PR-VNE分别降低了12.8%, 17.4%和5.7%.

Fig. 6 Energy consumption in different link power 图 6 不同链路功耗对系统能耗的影响
3.4.3 其他性能比较

1) 主动休眠算法对收益成本比的影响.

图 7给出在mr范围为[0.999,1]、Nov为20环境下不同映射算法的收益成本比情况,可以看出:AS-EA-VNE, AS-ACO-PE-VNE比EA-VNE,ACO-PE-VNE提高了2%.这是因为在非饱和状态下,映射成本比受到链路映射影响,主动休眠方法缩小了可利用的底层资源范围,从而缩短了链路映射路径长度,提高了收益成本比.AS-PR- VNE相对于PR-VNE收益成本比降低了0.3%,这是由于,PR-VNE算法的虚拟节点映射集中在资源丰富的底层节点上,主动休眠算法使得底层资源量减少,导致了收益成本比有所下降,但几乎可以忽略.

Fig. 7 Long-Term r/c ratio (revenue/cost) comparison 图 7 收益成本比

2) 主动休眠算法减少了虚拟网络映射算法运行时间.

mr范围为[0.999,1]、Nov为20的条件下,运行500个时间窗所用的时间,EA-VNE,PR-VNE,ACO-PE-VNE, AS-EA-VNE,AS-PR-VNE和AS-ACO-PE-VNE分别为59s,49s,1084s,50s,42s和987s.可以看出,主动休眠算法缩短了运行时间.这是因为其缩小了虚拟网络映射的底层节点和链路集合,缩短了节点和链路的映射时间;且仅利用了第1个时间窗的虚拟网络请求训练资源利用率,算法时间复杂度低,对运行时间影响很小.

4 结束语

本文研究了网络虚拟化环境下的系统能耗问题.提出多目标决策的虚拟网络映射能耗模型;利用虚拟网络映射动态特征,构造虚拟网络映射字典库,提出底层网络资源利用率的训练算法以及主动休眠底层节点和链路算法,把虚拟网络映射在一个较小的节点和链路集合中,提高休眠节点和链路数量,以实现高效节能.仿真实验结果验证了在系统非饱和状态下,基于主动休眠节点和链路的方法能够有效节约系统消耗能量,与其他算法相比,显著降低了系统能耗.然而,基于资源整合的网络能耗管理与虚拟网络请求动态行为紧密相关,构建有效模型描述系统动态行为特征,使得系统在饱和与非饱和状态之间有效切换有待进一步加以研究.同时,鉴于系统能耗与节点的利用率有关,基于节点分配的虚拟网络映射节能方法也有待深入研究.

致谢 本文仿真实验在C3S2服务器上完成,感谢湖州师范学院C3S2计算中心的大力支持.

参考文献
[1] Fisher W, Suchara M, Rexford J. Greening backbone networks: Reducing energy consumption by shutting off cables in bundled links. In: Proc. of the ACM SIGCOMM Workshop on Green Networking. 2010.29-34 .
[2] Barroso LA, Holzle U. The case for energy-proportional computing. IEEE Computer, 2007,40(12):33-37 .
[3] Bohrer P, Elnozahy EN, Keller T, Kistler M, Lefurgy C, McDowell C, Rajamony R. The case for power management in Web servers. In: Graybill R, ed. Power Aware Computing. Norwell: Kluwer Academic Publishers, 2002. 261-289. http://dl.acm.org/citation.cfm?id=783075
[4] Lin C, Tian Y, Yao M. Green network and green evaluation: Mechanism, modeling and evaluation. Chinese Journal of Computers, 2011,34(4):593-612 (in Chinese with English abstract) .
[5] Ye KJ, Wu ZH, Jiang XH, He QM. Power management of virtualized cloud computing platform. Chinese Journal of Computers, 2012,35(6):1262-1285 (in Chinese with English abstract).
[6] Chowdhury NMMK, Boutaba R. Network virtualization: State of the art and research challenges. IEEE Communications Magazine, 2009,47(7):20-26 .
[7] Anderson T, Peterson L, Shenker S, Turner J. Overcoming the Internet impass through virtualization. IEEE Computer Magazine, 2005,38(4):34-41 .
[8] Sun G, Anand V, Yu HF, Liao D, Li L. Optimal provisioning for elastic service oriented virtual network request in cloud computing. In: Proc. of the Global Communications Conf. (GLOBECOM). Anaheim: IEEE, 2012. 2517-2522 .
[9] Drutskoy D, Keller E, Rexford J. Scalable network virtualization in software-defined networks. IEEE Internet Computing, 2013, 17(2):20-27 .
[10] Sharkh MA, Jammal M, Shami A, Ouda A. Resource allocation in a network-based cloud computing environment: Design challenges. IEEE Communications Magazine, 2013,51(11):46-52 .
[11] Wei XL, Chen M, Fan JH, Zhang GM, Lu ZY. Architecture of the data center network. Ruan Jian Xue Bao/Journal of Software, 2013,24(2):295-316 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4336.htm
[12] Fischer A, Botero JF, Beck MT, Meer HD, Hesselbach X. Virtual network embedding: A survey. IEEE Communications Surveys & Tutorials, 2013,15(4):1888-1906 .
[13] Chabarek J, Sommers J, Barford P, Estan C, Tsiang D, Wright S. Power awareness in network design and routing. In: Proc. of the INFOCOM. Phoenix: IEEE, 2008. 457-465 .
[14] Botero JF, Hesselbach X, Duelli M, Schlosser D, Fischer A, Meer HD. Energy efficient virtual network embedding. IEEE Communications Letters, 2012,16(5):756-759 .
[15] Garroppo R, Nencioni G, Tavanti L, Scutella MG. Does traffic consolidation always lead to network energy savings. IEEE Communication Letters, 2013,17(9):1852-1855 .
[16] Botero JF, Hesselbach X. Greener networking in a network virtualization environment. Computer Networks, 2013,57(9):2021-2039 .
[17] Su S, Zhang ZB, Cheng X, Wang YW, Luo Y, Wang J. Energy-Aware virtual network embedding through consolidation. In: Proc. of the Computer Communications Workshops (INFOCOM WKSHPS). Orlando: IEEE, 2012. 127-132 .
[18] Wang B, Chang XL, Liu JQ, Muppala JK. Reducing power consumption in embedding virtual infrastructures. In: Proc. of the Globecom Workshops (GC Wkshps). Anaheim: IEEE, 2012. 714-718 .
[19] Chang XL, Wang B, Liu JQ, Muppala JK. Green cloud virtual network provisioning based ant colony optimization. In: Proc. of the 15th Annual Conf. Companion on Genetic and Evolutionary Computation. New York: ACM Press, 2013. 1553-1560 .
[20] Yu ML, Yi Y, Rexford J, Chiang M. Rethinking virtual network embedding: Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29 .
[21] Turner JS, Crowley P, DeHart J, Freestone A, Heller B, Kuhns F, Kumar S, Lockwood J, Lu J, Wilson M, Wiseman C, Zar D. Supercharging planetlab: A high performance, multi-application, overlay network platform. ACM SIGCOMM Computer Communication Review, 2007,37(4):85-96 .
[22] Lu GH, Guo CX, Li YL, Zhou ZQ, Yuan T, Wu HT, Xiong YQ, Gao R, Zhang YG. Serverswitch: A programmable and high performance platform for data center networks. In: Andersen D, ed. Proc. of the 8th USENIX Conf. on Networked Systems Design and Implementation. Berkeley: USENIX Association, 2011. 1-14.
[23] Unnikrishnan D, Vadlamani R, Liao Y, Dwaraki A, Crenne J, Gao LX, Tessier R. Scalable network virtualization using FPGAs. In: Proc. of the 18th Annual ACM/SIGDA Int’l Symp. on Field Programmable Gate Arrays. New York: ACM Press, 2010. 219-228 .
[24] Sivaraman V, Vishwanath A, Zhao Z, Russell C. Profiling per-packet and per-byte energy consumption in the NetFPGA gigabit router. In: Proc. of the Computer Communications Workshops (INFOCOM WKSHPS). Shanghai: IEEE, 2011. 331-336 .
[25] Zegura EW, Calvert KL, Bhattacharjee S. How to model an internetwork. In: Proc. of the 15th Annual Joint Conf. of the IEEE Computer and Communications Societies Conf. on Computer Communications. San Francisco: IEEE, 1996. 594-602 .
[26] Barroso LA, Hölzle U. The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines. Morgan and Claypool Publishers, 2009. 1-108.
[27] Ananthanarayanan G, Katz RH. Greening the switch. In: Proc. of the 2008 Conf. on Power Aware Computing and Systems. Berkeley: USENIX Association, 2008. 1-14. https://www.usenix.org/legacy/event/hotpower08/tech/
[28] Chiaraviglio L, Mellia M, Neri F. Energy-Aware backbone networks: A case study. In: Proc. of the Int’l Conf. on Communications Workshop. Dresden: IEEE, 2009. 1-5 .
[29] Cheng X, Su S, Zhang ZB, Wang HC, Yang FC, Luo Y, Wang J. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Computer Communication Review, 2011,41(2):38-47 .
[4] 林闯,田源,姚敏.绿色网络和绿色评价:节能机制、模型和评价.计算机学报,2011,34(4):593-612 .
[5] 叶可江,吴朝晖,姜晓红,何钦铭.虚拟化云计算平台的能耗管理.计算机学报,2012,35(6):1262-1285.
[11] 魏祥麟,陈鸣,范建华,张国敏,卢紫毅.数据中心网络的体系结构.软件学报,2013,24(2):295-316. http://www.jos.org.cn/1000-9825/4336.htm