弹性光网络一类调度问题的一个新模型和算法

2022-09-29杨晴东王紫晴郭威王宇平

纯粹数学与应用数学 2022年3期

杨晴东，王紫晴，郭威，王宇平

(西安电子科技大学计算机科学与技术学院，陕西西安 710071)

1 引言

随着互联网技术的发展，波分复用网络(Wavelength Division Multiplexing，WDM)因其固定栅格的频谱分配模式，低的频谱资源利用率，已不能满足实际需求.弹性光网络(EON)因其频谱带宽的灵活分配，网络资源的高利用率而成为未来网络的发展方向，但是，EON的路由和频谱分配(Routing and Spcetrum Allocation，RSA)问题更加复杂.因此，RSA问题已成为弹性光网络中最热门的关键问题之一[1]，许多学者对这一问题进行了研究.如，文献[2]提出了基于相对成本技术的自适应多径路由和频谱分配算法，用来平衡流量分配并减少EON中的呼叫阻塞概率.文献[3]考虑了不断变化的物理层损害所带来的违反传输质量(QoT)的风险，并提出了一种链路状态感知(LSA)的RSA策略，以保证不同链路状态下的QoT要求.为了解决弹性光网络中流量分布不均衡的情况，文献[4]对潮汐流量的形成特点进行了分析，提出了两种基于OTTM模型的算法来提高带宽效率.文献[5]提出了一种基于相对成本概念的自适应RSA算法，该算法可估算在给定网络状态下给定路由/频谱集上的呼叫被允许时的瞬态效应和到达呼叫转发目的地的相对成本，从而选出最优成本的路径.文献[6]分析了三种类型弹性光网络的网络数据流，对频谱分配问题建立了一个整数线性规划模型，并提出了基于粒子群优化和禁忌搜索的两种元启发法.然而RSA问题具有极强的针对性，看待问题的角度不同，则问题的模型也不相同，导致RSA问题的模型适应面窄.另外，随着网络用户数量的不断快速增大，网络硬件的更新速度往往赶不上用户的需求.虚拟网络功能(VNF)是通过软件来实现专用硬件设备的功能，称为虚拟功能.VNF在不增加网络硬件设备的情况下便可实现扩大业务量，提高网络资源利用率.但是，具有VNF的弹性光网络除要完成RSA任务外，还要完成一系列的服务功能链(SFC)，每个SFC由若干个需要依次完成的有序功能组成(如加密，解密，深度包检测，数据监测等).目前其面临着诸多的问题和挑战，挑战之一就是如何同时完成三项任务:负载均衡地在数据中心上部署网络服务功能链使得网络高效和稳定;合理地进行路由选择使得数据快速传输;有效地进行频谱分配使得节约频谱资源.目前，这方面的研究已取得了一定成果.如，为了最大程度地减少能耗和总体成本消耗，文献[7]提出了一种基于VNF迁移策略的整合算法，解决在迁移过程中发生信息丢失和用户遭受的QoS下降所导致的收入损失问题.为处理在网络和云环境中部署虚拟和物理的网络功能链问题，文献[8]提出了一种基于自定义贪婪算法的启发式算法，用以提高性能并提高特征分解方法的能力.文献[9]对VNF的资源分配问题进行了综述，介绍了解决VNF资源分配问题的主要方法，以及解决VNF资源分配问题的最新技术.针对具有带宽可变光路，调制格式约束和虚拟弹性再生器布局的弹性光衬底网络中设计多个虚拟光网络(VON)的问题，文献[10]提出了一种混合整数线性规划(MILP)模型，并设计了启发式和元启发式求解方法.文献[11]研究了如何在弹性光网络(EON)中动态地建立和重新配置多播会话的问题，文献[12]对具有共享数据中心的弹性光网络，提出了基于共享路径保护策略的频谱分配方法.

由于以上三个问题相互冲突，同时解决三个问题非常困难，已有工作主要为解决上述三个问题中的一到两个问题提供高效模型和算法.为了较好地解决以上三个问题，本文将建立可同时解决上述三个问题的优化模型与算法.

2 数据中心负载均衡，路由规划及频谱分配的优化模型及算法

2.1 问题描述

具有VNF的弹性光网络拓扑结构可用无向图G(V，E)表示，其中顶点集合V={v1，v2，···，vNv}表示网络的节点集，数据中心节点集记为VD={v1，v2，···，vNd}，边集合E={Lij|vi，vj∈V}表示网络的链路集，每条链路上有NF个频隙.SFC={r1，r2，···，rk，···，rNR}表示网络中服务功能链 (SFC)的集合，第k个服务功能链 (简称为第k个业务)表示为rk=(sk，dk，bk，tk)，其中sk为源节点，dk为目的节点，tk为第k个业务rk中需依次处理的网络功能序列，其中是第k个业务rk要完成的第i个虚拟网络功能 (VNF)的编号(为方便，网络虚拟功能VNF也简称为功能).tk中各个功能互不相同.Fk表示第k个网络服务功能链中包含的网络功能数目，NT表示NR个业务中所有不同功能的总数.bk表示第k个业务中需要占用的频隙数.

本文考虑的问题是:如何将每个业务中的网络功能在数据中心上部署?如何为每一个业务选择路径以及分配频谱?使得完成所有业务时，路径合理，数据中心负载均衡及频谱资源占用少.

2.2 模型建立

1.构建目标函数

本文以数据中心负载最均衡及频谱资源消耗最小为目标建立约束优化模型.

(A)负载均衡函数S(x)的计算:用x=(x1，x2，···，xNR)T表示各业务在数据中心部署 VNF 功能的方案，表示第k个业务rk在各数据中心上的网络功能部署方案.其中表示第k个业务rk部署在第i个数据中心的VNF功能数，i=1，2，···，Nd，k=1，2，···，NR.S(x) 为各数据中心上分配待处理网络功能数的标准差，它可衡量数据中心负载均衡程度.S(x)可计算如下:因NT为NR个网络服务功能链中所有网络功能的总数，即所有数据中心处理网络功能的总次数，Fk为第k个网络服务功能链中包含的网络功能数目，则NR个网络服务功能链中所有网络功能的总数NT为

每个数据中心处理网络功能数的平均值为

第h个数据中心上处理网络功能的数量为

则标准差S(x)计算公式为

2.3 模型求解算法

因上模型是一个难以求解的非线性整数规划模型，没有现成的方法可以利用，本节设计一个进化算法对模型进行求解.算法的主要框架如下:先设计了产生初始种群的方法;其次，设计了变异算子;最后，通过不断对种群进行变异进化，得到最优解的一个近似.下面依次介绍算法的各个模块.

3 数值实验

3.1 仿真环境及参数配置

本文所采用的实验环境是 Windows 11操作系统，16G内存，锐龙R7-5800H八核3.2GHz.代码由Python 3.7语言编写而成，实验工具是PyCharm IDE.仿真实验中采用了四种网络拓扑:NSFNET[14]，CHNNET[15]，ARPANET[15]和 USANET[10]，网络图及详情见文献[10，14-15]，网络参数如表1所示.

表1 网络参数

下面通过计算机模拟来验证模型和算法的有效性.实验分为四组，每组针对一个网络，对 NSFNET和 NSFNET，设置数据中心节点个数为Nd=7，对 ARPANET和USANET，设置数据中心节点个数为Nd=10.每组实验设置了不同的业务个数NR.表2给出了每组实验的业务个数(NR)，VNF数量(NT)，种群规模(NPop)，最大进化代数(Ngen)的实验参数.对每种情况进行了10次仿真实验，取10次仿真实验结果的平均值作为最终结果.

表2 仿真环境参数

3.2 对比算法

为后面记号方便，本文模型的求解算法3简记为算法1，对比算法分别记为算法2和算法3.

3.3 实验结果分析

四种网络NSFNET，USANET，ARPANET和CHNNET的每一种包含三种情况，对每种情况均进行了10次实验，获得10次性能指标的均值和标准差.实验中，采用如下三个性能指标:(1)最大频隙占用号的均值与标准差，记为NSmean和NSstd.均值可反映网络链路中频隙消耗量，值越小说明网络中的频谱消耗越少;(2)数据中心VNF部署数目的标准差的均值和标准差，记为V NFmean和V NFstd.均值可反映数据中心的负载均衡情况，值越小说明弹性光网络的数据中心负载越均衡，网络的运行效率也越高;(3)目标函数值的均值和标准差，记作Fmean和Fstd.均值越小，说明算法的效果越好.而三个指标的标准差可反映算法的稳定性.值越小，算法的稳定性越好.

表3对比了三个算法的平均频隙消耗量.从表中可以看出，在每个网络及同样业务量的情况下，算法1的频谱消耗量少于算法2和算法3，并且随着业务量的增加，这种优势一直保持.同时，本文算法对应的标准差在大部分情况下也小于对比算法的标准差.说明本文算法的稳定性更好.

表3 10次运行中三个方法频隙消耗量对比

图1给出了在不同网络拓扑结构下，三种算法在不同业务量情况下的最大频隙号的对比结果.

图1 频隙消耗量对比

表4对比了三个算法在数据中心部署任务量标准差的均值.可以看出，在NSFNET中，算法1的表现一直优于算法2和算法3.在ARPANET和CHNNET中，在大业务量情况下，算法1的表现也优于算法2和算法3.这说明本文的算法对提高网络的负载均衡也有较好作用.

表4 10次运行中三个方法的数据中心负载均衡对比

图2给出了在不同网络拓扑结构下，三种算法在不同业务量情况下的数据中心负载均衡的对比结果.

表 5对比了三个算法 10次运行得到的最优目标函数均值和标准差.从表 5可看出，对四种网络的各个任务量情况下，本文算法 1的表现均优于算法 2和算法 3的表现.从10次实验结果的标准差来看，本文算法稳定性在大多数情况下也优于算法2和算法3.综上，本文算法在频谱消耗量上优于算法2和算法3，在负载均衡方面，在NSFNET，ARPANET和CHNNET网络结构中均有一定优势，在频谱消耗量和负载均衡两个指标的综合指标来看，本文算法优势明显.