基于数据中心光网络的节能虚拟网络嵌入算法

聂嘉琪

(东北大学 计算机科学与工程学院， 沈阳 110169)

0 引 言

随着通信技术的迅猛发展，以及新兴网络服务的出现，数据中心网络(Data Center Networks，DCNs)中的流量呈指数型增长。弹性光网络(Elastic Optical Networks，EONs)通过设置具有一系列光谱连续细粒度频隙(Frequency Slots，FSs)的信道，为光学层中的光谱管理者提供了前所未有的灵活性[1-3]。EONs成为数据中心互连有前途的候选者。人们对互联网需求的多样化使网络出现僵化问题。网络虚拟化技术允许多个虚拟请求(Virtual Requests，VRs)共享底层物理网络的资源，可实现物理资源的合理分配和管理。网络虚拟化技术的核心问题是虚拟网络嵌入(Virtual Network Embedding，VNE)。VNE可以分为两个子问题：节点嵌入和链路嵌入[4]。

能耗问题有两个来源：频谱消耗和网络中的硬件消耗。研究者对上述两个部分均进行了研究。文献[5]研究了嵌入EONs的虚拟光网络的能量和频谱效率的联合优化问题；文献[6]考虑了EONs中的能量感知虚拟光网络嵌入问题；文献[7]研究了基于正交频分复用的软件定义网络跨数据中心EONs中受限于服务质量和物理要求的节能光收发器(Optical Transponder，OTP)配置问题。

基于上述嵌入和节能方法，针对网络能耗问题，本文提出了基于匹配网络资源的节能嵌入(Energy Efficient Embedding based on Matching Network Resources，3E-MNR)算法。

1 问题描述

1.1 基板网络(Substrate Network，SN)

本文把数据中心光网络(Data Center Optical Networks，DCONs)作为SN，用无向加权连通图GS=(NS,ES)来描述，式中：NS为基板节点的集合；ES为基板链路的集合。对于一个SN节点nS∈NS，设c(nS)为节点的计算资源，b(eS)为基板链路的带宽资源，eS∈ES为ES中的一条链路。图1所示为一个拥有6个基板节点和8条链路的SN示意图，图中，方框内的数字为基板节点的计算资源，链路上的数字为链路的带宽资源，横线外的数字为节点间的距离。

图1 SN示意图

为了快速匹配节点，减少时间的复杂度，提出了节点匹配资源R(i)的概念：

式中，lS(i)为与节点i相连的链路。

1.2 VRs

VRs用无向加权连通图GV=(NV,EV)来表示，式中：NV为虚拟节点的集合；EV为虚拟链路的集合。对于一个虚拟节点nV∈NV，设c(nV)为节点的计算资源需求，b(eV)为虚拟链路的带宽资源，eV∈EV为ES中的一条链路。图2所示为一个VRs的示意图，图中，方框内的数字为虚拟节点的计算资源需求，链路上的数字为链路的带宽资源需求。

图2 VRs示意图

1.3 功耗模型

DCONs节点和链路示意图如图3所示，模块主要由网际互连协议 (Internet Protocol，IP) 路由器、再生器、带宽可变的光交叉连接器(Bandwidth Variable Optical Cross Connector，BV-OXC)和带宽可变的OTP(Bandwidth Variable -OTP，BV-OTP)构成。各部分的功能总结如下：IP路由器在光电转换之前/之后执行所有必需的电气处理；再生器必要时再生光信号以保证传输质量；BV-OXC执行光信号交换和添加/删除功能，根据请求建立容量恰当的传输光路，当客户端产生的应用请求大小改变时，BV-OXC会适当地改变其交换窗口的大小从而改变光路的带宽容量，继而实现光路容量的灵活配置；BV-OTP包含光正交频分复用发送机和光正交频分复用接收机，用于生成和接收光正交频分复用信号。发送模块BV-OTP由3个主要部分组成：(1) 数字信号处理器；(2) 数/模转换器；(3) 激光器和马赫曾德尔调制器。而接收模块与发送模块相反。

图3 DCONs节点和链路示意图

在本文中，DCONs的整体能耗主要考虑数据中心、BV-OTP和再生器。数据中心的能耗PDC可描述为

式中：Pidle为在没有流量负载的情况下，用于冷却、照明和电源配置损耗的激活数据中心的闲置功耗；Pl为数据中心在最大流量负载下的比例功耗；ρ(0<ρ<1)为比例因子。

对于BV-OTP，其能耗Potp可描述为

式中：TR为传输速率；Poverhead为空闲功耗；η为比例参数。

对于再生器，其能耗Pre可描述为

式中：Pspare为空闲功耗；μ为比例参数；Pd为再生器在调制格式下，最大传输距离下的比例功耗。

因此，总能耗P可表示为

本文的目标是最小化总能耗。

2 启发式算法

本文主要针对BV-OTP和再生器来设计启发式算法，在VNE的过程中考虑整个网络的能耗，根据节点匹配资源，为VRs选择能耗最低的节点和链路完成嵌入。

2.1 基于节点匹配资源的节能嵌入算法

首先，计算SN和VRs节点匹配资源的大小，并将其按照降序排序，若SN节点之间或VRs节点之间的匹配资源大小相等，则将节点计算资源较大的排序在前，将排序好的SN和VRs节点分别放进集合中。接下来，按照集合中的顺序为VRs的各个节点找到候选嵌入节点;按照链路的带宽资源限制，为VRs找到候选链路。接着，根据路径的长度选择合适的调制格式，放置合适数量的OTP和再生器。最后，计算各个候选路径的能耗，进而计算所有候选嵌入网络的能耗，然后，比较所有候选嵌入的能耗，选择能耗最低的候选方式完成嵌入。

值得注意的是，VRs节点选择SN节点时，SN节点不仅要满足VRs节点的计算资源限制，还要满足与VRs节点相连的VRs链路的带宽限制。一旦排序靠前的VRs节点被选定为候选节点，排序靠后的节点便不可再选择。寻找候选链路时，按照广度优先搜索(Breadth First Search，BFS)算法遍历整个网络。选择调制格式的原则是：在不超过最大传输距离的情况下，选择高的调制格式，若路径长度等于调制格式的最大传输距离，则选择更低一级的调制格式。3E-MNR算法的流程图如图4所示。

图4 3E-MNR算法流程图

伪代码如下所示。

输入： SN， VRs；

输出：嵌入完成的SN；

1．初始化集合ps，pv，pq，m(i)，p(i)；

2．//寻找候选路径

4． 计算SN节点的计算匹配资源RS(i)；

5． ifRS(i)=RS(j),i≠j

6． 按SN节点的计算资源降序排序；

7． else

8． 按SN节点的匹配网络资源降序排序；

9． end if

10． 将排序结果放入ps中；

11．end for

13． 计算VRs节点的匹配资源RV(i)；

14． ifRV(i)=RV(j),i≠j

15． 按VRs节点的计算资源降序排序；

16． else

17． 按VRs节点的匹配网络资源降序排序；

18． end if

19． 将排序结果放入pv中；

20．end for

21．//寻找候选链路

23． 按照pv中的顺序从ps中寻找候选节点，放入m(i)中；

24． 根据m(i)中的VRs节点情况得到候选嵌入方式；

25．end for

26．do

27． 按照BFS算法为候选嵌入中的VRs找到候选路径；

28．until 找到所有候选嵌入方式的路径；

29．for 每一种候选嵌入的路径

30． 计算路径长度；

31． 根据路径长度选择调制格式；

32． 计算候选嵌入的网络能耗，将网络能耗存入p(i)；

33．end for

34．将p(i)中的数值按降序排序放入pq；

35．选择pq中第一个数值所对应的候选嵌入完成嵌入。

2.2 基于节点匹配资源的节能嵌入算法举例

为了进一步解释3E-MNR算法的步骤，根据图1和图2来说明算法的过程。VRs节点的匹配资源和SN节点的匹配资源由式(1)计算，得到SN节点的顺序为{D，C，B，F，E，A}，VRs节点的顺序为{b，a，c}。根据计算资源和带宽资源的约束，找到各VRs节点的候选节点为：b{F}，a{D，B}，c{A，E}，得到如图5所示的4种候选嵌入方式。以候选嵌入方式4为例来说明剩余步骤。按照BFS算法找到VRs a-b的候选路径为D-F，a-c的候选路径为D-C-E。由图1可知，D-F之间的距离为1 000 km，D-C-E之间的距离为1 100 km。表1给出了各调制格式的最大传输距离及OTP的能耗，都选择正交相移键控(Quadrature Phase Shift Keying，QPSK)的调制格式，D-F的能耗为266.92 W，D-C-E的能耗为533.84 W，候选嵌入方式4的总能耗为800.76 W。比较4种候选嵌入方式的能耗，最后，选择能耗最低的候选嵌入方式4完成嵌入。

图5 候选嵌入方式

表1 各调制格式下的最大传输距离及OTP能耗

3 实验结果与分析

本文将所提3E-MNR算法与两种现有的基线算法：距离自适应(Distance-adaptive，DA)算法[8]和能源感知虚拟嵌入(Virtual Network Embedding Energy Aware Problem,VNE-EA)算法[9]进行对比。把拥有15个节点27条链路的National网络和20个节点32条链路的ARPANet网络作为SN，网络拓扑如图6所示。假设VRs服从泊松分布随机到达，并且其生存时间遵循负指数分布。虚拟节点的数量是随机生成的，范围为[2，7]，具有统一分布的计算资源和带宽资源需求，每个FSs宽度为12.5 GHz。VRs以先到先得的方式嵌入。

图6 网络拓扑图

图7所示为本文所提3E-MNR算法与两种基线算法的总能耗对比图。由图可知，在两种情况下，3E-MNR算法总能耗均随着VRs数量的增加而增加，且总能耗总是低于两种基线算法。在National网络中，当网络负载为40和100 Erl时，3E-MNR算法与VNE-EA算法相比总能耗平均降低了10.25%和8.25%。相比于DA算法，3E-MNR算法总能耗平均降低了14.38%和13.63%，在低网络负载情况下，3E-MNR算法具有更好的性能。在高VRs数时，不同算法的总能耗差别较大。这是因为本文所提算法把VRs嵌入到了能耗最低的路径中，而不仅仅是满足资源需求的链路。

图7 总能耗对比图

图8所示为不同算法在网络负载为40 Erl时的运行时间对比图。由图可知，随着网络负载的增加，3E-MNR算法的运行时间均少于VNE-EA算法，但多于DA算法。图8(a)中，3E-MNR算法较VNE-EA算法运行时间大大减少。这是因为本文所提算法提出了节点匹配资源，在节点嵌入的阶段同时考虑了虚拟节点相连链路的带宽约束，大大减少了候选节点的数量。随着负载的增加，两者运行时间的差值也会越来越大。而对于DA算法来说，在嵌入时仅考虑距离来选择合适的调制格式并分配资源，而不考虑其他因素，相对于3E-MNR算法来说要节省时间。在VRs数为35时，3E-MNR算法比VNE-EA算法运行时间在National和ARPANet网络中分别降低了1.94和2.00 s。

图8 运行时间对比图

图9所示为本文所提3E-MNR算法与基线算法在不同网络负载情况下OTP能耗方面的比较。由图可知，在VRs数较少时，两种算法性能相差不大，随着VRs数的增多，两者的差距变得越来越大。这是因为在VRs数较少时，VNE-EA算法在节点计算资源和能量守恒等方面进行约束，当VRs数变大时，算法约束性变差，能耗增量变大。如图9所示，在VRs数为35时，3E-MNR算法较VNE-EA算法在网络负载为40和100 Erl时在Nationl网络(ARPANet网络)中OTP能耗分别减少了8%(6%)和27%(22%)。

图9 OTP能耗对比图

National和ARPANet网络中，不同方法在不同网络负载下的阻塞率如图10所示。在两种SN拓扑上，所有算法的阻塞率都随着VRs数的增加而增加，但本文所提算法的阻塞率均低于DA和VNE-EA算法。DA算法在路径选择时仅选择使用最少FSs的路径，而不考虑路径上FSs的使用情况。3E-MNR算法在链路嵌入时，考虑了带宽资源的限制，可以在相同的链路上传输更多的请求。由于网络资源的有限性，在高VRs数的情况下，阻塞可能性的升高受到限制。

图10 阻塞率对比图

4 结束语

本文探索了在节省DCONs能耗的同时保持对请求较高接受率的问题。为了节省DCONs的能耗并有效利用资源，本文提出了3E-MNR算法。为了减少时间复杂度，提出了节点匹配资源的概念，快速匹配虚拟节点的候选节点。仿真结果表明，在总能耗方面，本文所提3E-MNR算法要低于基线算法DA和VNE-EA，且保持了较低的阻塞概率。在运行时间方面也实现了一定的权衡。