基于数据中心光网络的节能虚拟网络嵌入算法
2022-02-21聂嘉琪
聂嘉琪
(东北大学 计算机科学与工程学院, 沈阳 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,且保持了较低的阻塞概率。在运行时间方面也实现了一定的权衡。