基于资源需求预测的动态服务功能链迁移方法

阳勇 孟相如 康巧燕 陈港

（空军工程大学信息与导航学院 西安 710077）

传统网络硬件与软件紧耦合的架构带来网络功能部署设备开销大、管理困难和失效率高等问题[1-2].自从2012 年网络功能虚拟化（network function virtualization，NFV）的概念正式诞生后，以其能解决传统网络“僵化”的优势获得了学术界和工业界的广泛关注，并带动了学术界和工业界的积极研究与踊跃尝试，产生了大量理论与实践成果[3-5].NFV 旨在使用软件实现能在行业标准服务器上运行的网络功能，并在不安装新专用硬件前提下，根据需求动态将网络功能部署在网络不同位置[6-7].NFV 环境中业务通过由虚拟网络功能（virtual network function，VNF）组成的链式结构实现，这组链式结构被称为服务功能链（service function chain，SFC）[8-10].

SFC 部署到底层网络后，资源需求随业务变化而动态变化.随着时间的推移，其部署的服务器或链路将出现过载问题，严重时可能导致服务中断，不但对服务质量（quality of service，QoS）产生影响，还可能增加运营商因中断服务导致的赔偿损失.文献[11-13]研究了VNF 备份机制.其中：文献[11]提出一种考虑中心性和可靠性的节点排序算法，用于备份节点的选择和备份VNF 的部署，能降低带宽资源的消耗,但未考虑SFC 时延；文献[12]采用广度优先搜索算法，最大限度聚合主VNF，并提出一种资源高效的备份选择方法部署备份VNF，提高SFC 可靠性的同时降低了端到端时延，但降低了部署主VNF 的成功率；文献[13]在构建节点负载与失效率之间关系模型的基础上，提出一种热备份与冷备份相结合的保护策略，降低节点负载的同时有效抑制了SFC 中断服务概率，但未降低底层网络资源开销.使用备份机制实现网络负载均衡的方法，在服务器出现过载时能及时将网络功能从过载服务器切换到备份服务器，从而提高服务质量，但带来的备份资源消耗在一定程度上增加了运营成本.

文献[14-18]研究了SFC 部署.其中：文献[14]为提高SFC 在不确定性网络中的可用时间，首先构建鲁棒优化模型，然后按时隙逐一部署VNF，并使用启发式算法对模型求解，对SFC 可靠性有较大优化，但难以实现VNF 快速部署；文献[15]在综合考虑负载均衡和运营开销的基础上，研究新用户SFC 部署和老用户SFC 调整问题，并将该问题构建成整数线性规划模型，采用遗传算法对模型求解，实现网络负载均衡的同时降低了资源开销，但算法复杂度较高；文献[16]提出一种基于强化学习的SFC 动态部署算法，该算法将图卷积网络和时间差分学习相结合，在提高网络长期受益开销比上有较好性能，但依赖大量的准确数据对神经网络模型进行训练；文献[17]在SFC 资源需求、端到端时延和可靠性的约束下，建立最大化SFC 部署总收益数学模型，并提出基于贪心的SFC 部署算法对模型求解，在保证QoS 的同时提高了网络总收益，但算法容易陷入局部最优结果中；文献[18]基于PageRank 算法对底层网络节点进行评价，以负载均衡和协调链路映射为原则，将VNF 部署在综合评价度最高的节点上，实现了SFC 时延和可靠性的全局优化，但资源开销较大.通过SFC 部署实现网络负载均衡的方法，在部署初期有较好效果，但随时间推移，底层网络节点和链路仍然难以避免过载问题.

文献[19-22]研究了SFC 迁移.其中：文献[19]研究共享VNF 迁移问题，提出一种基于最优排序的多阶段启发式算法,在保证网络负载均衡的同时优化了SFC 时延，但算法容易陷入局部最优结果中；文献[20]针对SFC 资源需求变化引起的底层网络过载问题，提出一种基于深度强化学习的VNF 迁移优化算法，并建立基于马尔可夫决策过程的随机优化模型，实现了网络能耗和SFC 时延的联合优化，但未考虑SFC 可靠性；文献[21]建立VNF 迁移开销模型，并提出节点与链路感知的VNF 迁移算法，基于贪心思想最小化迁移开销，将VNF 从过载节点迁移至资源充足节点，实现网络负载均衡，但增加了迁移次数；文献[22]研究基于VNF 聚合的迁移技术，迁移过程中将VNF 整合到尽可能少的服务器中，有效减少了资源消耗，但迁移成功率不高.通过SFC 迁移实现网络负载均衡的方法，能根据业务资源需求变化动态调配底层网络资源，是解决服务器或链路过载问题的有效办法，但文献[19-22]所提SFC 迁移算法都是在网络已过载时才实施，难以避免网络过载对QoS 的影响.

针对上述问题，本文提出基于资源需求预测的动态服务功能链迁移方法（dynamic service function chain migration method based on resource requirements prediction，RRP-DSFCM）.首先对已部署SFC 下一时隙资源需求进行预测，将即将过载的节点和链路作为实施迁移的对象；然后利用资源感知算法挑选对过载资源占用最多的VNF 和虚拟链路作为待迁出的对象；最后在进行流量优化和拓扑感知的基础上，选择能实现最优底层网络开销的节点作为迁入的目的节点.本文的主要贡献有3 方面：

1）综合考虑迁移开销和迁移后网络的资源占用情况，建立底层网络开销模型，为SFC 迁移提供优化目标；

2）建立基于经验模态分解（empirical mode decomposition，EMD）、径向基函数（radial basis function，RBF）神经网络、粒子群优化（particle swarm optimization，PSO）算法的预测模型，在减少预测时间的同时提高了预测精度；

3）提出基于流量优化和拓扑感知的SFC 迁移方法，在实现网络负载均衡的同时降低了底层网络开销、提高了SFC 的可靠性.

1 网络模型

1.1 底层网络

1.2 SFC 请求

采用二进制变量xij(t)表示第t时隙vi是否部署在物理节点nj上，二进制变量表示第t时隙vi是否从物理节点nj迁移至物理节点nm上，二进制变量yij(t)表示第t时隙li是否部署到底层网络后经过物理链路ej.

1.3 底层网络开销模型

定义底层网络开销模型由迁移开销和资源开销2 部分组成，其中迁移开销表示因VNF 迁移期间中断服务所带来的赔偿损失，根据文献[23]，VNF 迁移时间近似等于迁移存储数据的时间，所以第t时隙迁移vi的时间为

其中(j,m)表示节点nj与nm之间的最短路径，hop(j,m)表示(j,m)的跳数.设单位时间内中断服务的损失为α，则第t时隙SFC 的迁移开销为

资源开销表示SFC 部署到底层网络后占用资源所带来的成本，根据文献[24]，SFC 迁移不会对底层节点资源占用量产生影响，只会因迁移后VNF 部署位置发生变化而引起链路资源占用量改变，所以本模型对资源开销仅考虑链路带宽开销.设单位时隙内占用单位带宽的成本为β，则第t时隙SFC 的资源开销为

结合迁移开销与资源开销，建立底层网络开销模型如式（5）所示.

本文主要符号含义如表1 所示.

2 基于EMD-RBF-PSO 网络的资源需求预测模型

为实现对资源需求的快速精准预测，本文建立基于经验模态分解、径向基函数神经网络、粒子群算法的预测模型，其运行流程如图1 所示.

在模型的训练阶段，首先将历史资源需求数据进行EMD 分解，生成N组本征模函数（intrinsic model function,IMF）分量和1 组残差分量，目的是对非线性、非平稳的资源需求数据进行预处理，提高预测精度.其次将N组IMF 分量合成，并与残差分量一起对RBF 神经网络进行训练.训练过程中，将第t时隙的资源需求数据作为模型的输入样本，第t+1 时隙的资源需求数据作为模型的输出样本.最后结合预测所得数据与输出样本计算预测误差，若误差高于所设阈值，则通过粒子群算法对RBF 神经网络模型参数进行优化，并重复训练过程，直到误差低于所设阈值.

Table 1 Meaning of main Symbols表 1 主要符号含义

Fig.1 Operation process of EMD-RBF-PSO network图 1 EMD-RBF-PSO 网络操作流程

在模型的预测阶段，首先将当前一段时隙的资源需求数据进行EMD 分解，然后将得到的IMF 分量合并后与残差分量一起作为RBF 神经网络的输入，得到的结果即为下一时隙的资源需求预测结果.

2.1 基于EMD 的数据预处理

EMD 是一种依据数据自身的时间尺度特征来进行的数据分解，相比傅里叶分解需预先设定谐波基、小波分解需预先设定小波基，EMD 可以在不设定任何参数的前提下，将数据序列自适应分解成一系列IMF 分量和残差分量[25].EMD 可以应用于任何类型的数据分解，尤其在处理非线性、非平稳数据上具有优势[26].本文首先将VNF 的资源需求序列进行EMD 分解，然后送入RBF 神经网络进行预测的训练和测试.以VNF 的某种资源需求序列n(t)为例，进行EMD 的4 个基本步骤：

步骤1.分别找出n(t)的所有极大值和极小值，然后通过3 次样条插值确定n(t)的上包络序列nmax(t)和下包络序列nmin(t).

步骤2.利用式（6）计算均值序列m(t)，然后利用式（7）去掉n(t)的低频成分得到新序列

通常ε设定在0.2～0.3 之间.

步骤4.返回步骤1，令n(t)=r1(t)，执行步骤1～3 得到第2 个IMF 分量c2(t)与残差序列r2(t).依次类推，循环执行步骤1～4，得到后续IMF 分量，直到cn(t)小于预定误差或rn(t)单调，终止步骤循环，得到n(t)的EMD 结果为

2.2 基于RBF 神经网络的资源需求预测

RBF 神经网络是一种激活函数为径向基函数的神经网络，具有学习速度快、分类能力强和近似模拟能力强等优势，能够以任意精度逼近任意连续函数，其神经网络结构如图2 所示.

Fig.2 Structure of RBF neural network[27]图 2 RBF 神经网络结构[27]

RBF 神经网络是一个具有单隐藏层的3 层前馈型神经网络.图2 所示RBF 网络输入为X=（x1,x2,…,xn）的n维向量，从输入层到隐藏层为非线性变换.隐藏层由m个神经元组成，φi表示第i个神经元的径向基函数，x′i表示φi的中心点.网络的输出是隐藏层各神经元输出的线性加权和，wi表示第i个神经元的权值.通常m＞n，所以隐藏层可将n维的低维数据映射到m维的高维空间，使低维度不可分的情况到高维度变得线性可分.

本文将经过预处理的当前时隙资源需求数据作为RBF 神经网络的输入，下一时隙的资源需求数据作为输出，展开对资源需求预测的训练和测试.

2.3 基于粒子群算法（PSO）的参数优化

RBF 网络对资源需求预测的过程中，径向基函数的中心点x′、宽度σ和隐藏层对输出层的权值w是影响预测结果的主要参数，为提高预测效率和精度，利用粒子群算法选择出合适的x′,σ,w.算法流程如图3 所示.

粒子的位置是一个a维向量，表示待优化的参数x′，σ，w.其中第i个粒子的位置为Yi=（yi1,yi2,…,yia），第i个粒子的速度也是一个a维向量，记为Vi=（vi1,vi2,…,via）.粒子的适应度用该粒子所表示参数下RBF 网络预测误差的倒数表示，粒子的个体最优值表示该粒子迄今为止适应度最大时的位置，群体的全局最优值表示迄今为止群体中适应度最大的粒子的个体最优值.记第i个粒子的个体最优值为Pbest=（pi1,pi2,…,pia），整个群体的全局最优值为Gbest=（g1,g2,…,ga）.粒子的速度和位置更新方式分别为：

Fig.3 Parameter optimization process based on PSO algorithm图 3 基于粒子群算法的参数优化流程

其中，c1和c2是加速常数，本文取值为1.5，r1和r2是介于0～1 之间的随机数.

3 基于资源感知与流量优化的动态服务功能链迁移方法

为避免SFC 因资源需求增加而导致底层节点或链路过载，本文在实现SFC 资源需求预测的基础上，对下一时隙即将过载的底层节点或链路实施VNF 或虚拟链路迁移，并提出一种基于资源感知与流量优化的动态服务功能链迁移方法（dynamic service function chain migration method based on resource awareness and traffic optimization，RATO-DSFCM）.该方法由3 个子算法组成，分别是基于资源感知的待迁移VNF 选择算 法（migrated VNF selection algorithm based on resource awareness,RA-MVNFS）、基于流量优化和拓扑感知的迁入目的节点选择算法（migration destination node selection algorithm based on traffic optimization and topology awareness,TOTA-MNS）以及虚拟链路重部署算法.

3.1 基于资源感知的待迁移VNF 选择

在下一时隙（第t+1 时隙）即将过载的底层节点中可能已部署多个VNF，需从中选择待迁移VNF 迁出.为快速缓解节点过载程度，同时减少迁移次数，本算法首先计算第t+1 时隙待迁移节点上各VNF 的迁出指数，并按照迁出指数的降序依次选择VNF 迁出，直到待迁移节点不再过载.迁出指数的计算公式为

若迁移的对象是虚拟链路，同样需要从过载链路上部署的多条虚拟链路中选择待迁移虚拟链路迁出.由于本模型只考虑虚拟链路对带宽资源的占用，所以直接按照带宽需求的大小对各虚拟链路进行降序排列，依次选择虚拟链路迁出，直到待迁移链路不再过载.RA-MVNFS 的具体步骤如算法1 所示.

算法1.RA-MVNFS 算法.

3.2 基于流量优化和拓扑感知的迁入目的节点选择

本算法的中心思想是通过对物理网络拓扑的感知实现SFC 流量的优化，使VNF 迁移后相关联的大带宽需求虚拟链路在物理网络中部署的跳数尽可能小，直至其上的流量变为节点的内部流量.

如图4 所示，待迁移VNFvmove的带宽改变因子n=0.9，其前端虚拟链路带宽需求为96 Mbps，后端虚拟链路带宽需求为86.4 Mbps，则大带宽需求链路为其前端虚拟链路.将vmove从物理节点D迁出后，若选择物理节点F为迁入目的节点，则大带宽虚拟链路将部署到链路B—C—F上，即链路B—C—F均需消耗96 Mbps 带宽.若选择物理节点C为迁入目的节点，则链路B—C需消耗96 Mbps 带宽，而链路C—F只需消耗86.4 Mbps 带宽.若物理节点B有足够资源满足vmove的需求，选择B为迁入目的节点后，大带宽虚拟链路上的流量将成为节点B的内部流量，链路B—C—F均只需要消耗86.4 Mbps 带宽.

定义节点的前后距为

Fig.4 An example of TOTA-MNS图 4 TOTA-MNS 示例

Fig.5 The process of TOTA-MNS图 5 TOTA-MNS 流程

算法2.TOTA-MNS 算法.

3.3 虚拟链路重部署

虚拟链路在2 种情况下需要重部署：1）当某条物理链路在下一时隙即将带宽过载时，需从其中选择迁出的虚拟链路，并在物理网络拓扑中选择其他物理路径重部署；2）当网络实施了VNF 迁移后，需要将与已迁移VNF 相关联的虚拟链路从原部署物理路径上迁出，并在2 端VNF 所部署的物理节点间寻找新的物理路径重部署.

对第1 种情况下迁出的虚拟链路进行选择时，为快速缓解物理链路过载程度，本文选择下一时隙带宽需求最大的虚拟链路迁出.2 种情况下对虚拟链路进行重部署时，首先删除不满足带宽需求的物理链路，然后在剩余网络拓扑中运行k-最短路径算法确定重部署的物理路径.

4 实验仿真

本文设置2 组仿真实验验证方法性能：第1 组实验对资源需求预测模型进行仿真，并与文献[28]的BP-NN 模型和文献[29]的HTP-POS 模型进行对照.第2 组实验对SFC 迁移方法进行仿真，并与文献[30]的TPGDM 算法和文献[21]的NAVMM 算法进行对照.实验在CPU 型号为i5-10210U 的个人电脑上进行，仿真平台为MATLAB R2018a.

4.1 仿真环境设置

仿真环境中物理网络是一张由50 个节点与123条链路组成的连通图，相当于一个小型网络拓扑.生成15 条SFC 并采用文献[18]所提算法进行部署，SFC的资源需求样本在给定初始值和变化值范围下调用自编的资源需求函数进行模拟.资源需求函数对初始值附加的变化值服从λ=1/20 的泊松分布，变化值大小在允许范围内服从均匀分布，变化值的持续时间服从μ=10 的指数分布.仿真时间设置代表2 500 个时隙，每个时隙代表1 min.物理网络和SFC 的详细参数设置如表2 所示.

Table 2 Simulation Parameters表 2 仿真参数

4.2 资源需求预测实验结果分析

随机选取1 条SFC（本实验选第3 条）的初始带宽序列b0(t)前1 800 个时隙作为训练样本，后700 个时隙作为测试样本进行资源需求预测实验.本文基于EMD-RBF-PSO 的预测模型中，径向基函数的扩展速度设置为1.5，神经元最大数目设置为80，每次加进来的神经元数为25.采用均方根误差ERMS衡量预测数据的准确性，其定义为

其中n为测试样本个数，Yt为测试样本真实值，为测试样本预测值.ERMS越小，说明预测值与真实值越接近，预测算法性能越优.

图6 是本文预测模型各分量的预测结果，从图6（a）可看出IMF 分量预测结果仅在尖峰处存在少量误差，其余部分基本与真实值拟合.从图6（b）可看出余波分量预测结果基本与真实值拟合.

Fig.6 Prediction results of EMD-RBF-PSO model for each component图 6 EMD-RBF-PSO 模型对各分量预测结果

图7 是不同模型对测试数据的预测结果，从图7（a）可发现EMD-RBF-PSO 模型的预测结果除尖峰外，基本与真实值拟合.这是因为EMD-RBF-PSO 模型对测试数据进行EMD 预处理后，有效提高了预测精度.从图7（b）可发现BP-NN 模型的预测结果多处与真实值相差较大.这是因为BP-NN 模型未对测试数据进行预处理.从图7（c）可发现HTP-POS 模型的预测结果在突变处始终无法与真实值拟合.这是因为HTPPOS 模型采用小波分解对测试数据进行了预处理，而小波分解在处理非线性、非平稳数据上不具备明显优势，所以预测精度较低.

表3 是3 种模型的运行误差(ERMS)与运行时间对比结果，可发现在ERMS上本文预测模型最优，HTPPOS 次之，BP-NN 最差.这是因为本文预测模型采用的EMD 分解对处理带宽需求变化数据最具有优势；HTP-POS 采用的小波分解虽在处理带宽需求变化数据上优势没有EMD 明显，但仍然能提高预测精度；而BP-NN 是直接对测试数据进行预测，所以预测精度最低.在运行时间上，本文预测模型运行时间最短，HTP-POS 次之，BP-NN 最差.这是因为本文预测模型与HTP-POS 均采用了粒子群算法对模型参数进行优化，所以运行速度较快；而BP-NN 未使用优化算法，所以运行速度最慢.

Fig.7 Prediction results of different models for test data图 7 不同模型对测试数据的预测结果

Table 3 Comparison of ERMS and Running Time of Each Prediction Model表 3 各预测模型误差（ERMS）与运行时间对比

4.3 SFC 迁移实验结果分析

将3 种迁移方法均在本文的EMD-RBF-PSO 预测结果下进行实验，为避免随机因素影响，仿真实验进行10 次，取每次结果的平均值作为最终实验结果.单位时间内中断服务的损失α=1，占用单位带宽的成本β=100.

图8 是本文SFC 迁移方法在进行了资源需求预测和未进行资源需求预测的情况下过载节点数目对比结果，可看出进行资源需求预测后有效降低了物理网络节点过载的次数.这是因为基于资源需求预测的SFC 迁移能在下一时隙节点过载前将其上部署的VNF 迁出，从而降低节点过载的概率.

Fig.8 Comparison of number of overloaded nodes图 8 过载节点数目对比

图9 是3 种迁移方法的SFC 平均可靠性对比结果，可以发现RATO-DSFCM 的SFC 平均可靠性最高，TPGDM 次之，NAVMM 最差.这是因为RATO-DSFCM在进行迁入目的节点选择时会优先将或作为目的节点，从而将vmove与所在SFC 的上一个VNF或下一个VNF 聚合，从而提高了SFC 可靠性.

图10 是3 种迁移方法的SFC 平均时延对比结果，可以发现RATO-DSFCM 的SFC 平均时延最短，TPGDM次之，NAVMM 最差.这是因为RATO-DSFCM 与TPGDM均在距离和最短的节点集中选择迁入目的节点，所以有效降低了链路时延.

Fig.9 Comparison of average reliability of SFC图 9 SFC 平均可靠性对比

Fig.10 Comparison of average delay of SFC图 10 SFC 平均时延对比

Fig.11 Comparison of number of VNF migrations图 11 VNF 迁移次数对比

图11 是3 种迁移方法的VNF 迁移次数对比结果，可以发现TPGDM 的VNF 迁移次数最少，RATODSFCM 次之，NAVMM 最多.这是因为TPGM 在进行底层网络拓扑感知的基础上，并未对VNF 进行聚合，有效降低了迁入目的节点随时间推移过载的概率，所以迁移次数最少.RATO-DSFCM 在进行流量优化的同时对VNF 进行了聚合，增加了迁入目的节点过载的概率，所以迁移次数多于TPGDM.NAVMM利用贪心算法总是选择最能降低迁移时间的节点进行迁入，未考虑迁入节点是否会在未来一段时间过载，所以迁移次数最多.

图12 是3 种迁移方法的VNF 平均迁移时间对比结果，可发现NAVMM 的VNF 平均迁移时间最短，这是因为该算法会优先将迁入目的节点选在距离迁出节点较近的节点，所以明显缩短了VNF 平均迁移时间.RATO-DSFCM 优先将迁入目的节点选在和的最短路径上，一定程度上也使得迁入目的节点与迁出节点较近，所以VNF 平均迁移时间仅次于NAVMM.TPGDM 在选择迁入目的节点时未考虑与迁出目的节点之间的联系，所以VNF 平均迁移时间最长.

Fig.12 Comparison of average VNF migration time图 12 VNF 平均迁移时间对比

图13 是3 种迁移方法的VNF 总迁移时间对比结果，可以发现RATO-DSFCM 的VNF 总迁移时间最短，TPGDM 次之，NAVMM 最长.这是因为RATO-DSFCM在保持较少迁移次数的前提下获得了较短的VNF 平均迁移时间.TPGDM 虽然获得了最少的迁移次数，但也导致平均迁移时间最长.NAVMM 虽然获得了最短的平均迁移时间，但也使迁移次数最多.

Fig.13 Comparison of total VNF migration time图 13 VNF 总迁移时间对比

图14 是3 种迁移方法的底层网络开销对比结果，可以发现RATO-DSFCM 的底层网络开销最小，TPGDM次 之，NAVMM 最 大.因 为RATO-DSFCM 在进行 拓扑感知的基础上将VNF 迁移至和的最短路径上，并进行了流量优化，所以获得较小的链路带宽开销；而TPGDM 未对流量进行优化，所以链路带宽开销大于RATO-DSFCM；NAVMM 在选择迁入目的节点时未考虑与和之间的拓扑联系，所以链路带宽开销最大.

Fig.14 Comparison of total overhead of the physical network图 14 底层网络开销对比

5 结 论

本文针对网络功能虚拟化环境下SFC 资源需求变化引起的物理网络过载问题，提出一种基于资源需求预测的动态服务功能链迁移方法.首先综合考虑SFC 部署在物理网络中的带宽开销和因迁移而中断服务导致的赔偿损失，建立了底层网络开销模型.然后利用经验模态分解对资源需求序列预处理，通过RBF 网络对预处理的结果进行预测，并利用粒子群算法对RBF 网络的参数进行优化，建立了EMDRBF-PSO 资源需求预测模型.在实现资源需求预测的基础上，设计基于资源感知和流量优化的SFC 迁移方法，通过对各VNF 的资源感知筛选占用过载节点上过载资源最多的VNF 实施迁移，并通过流量优化和拓扑感知算法选择迁移后能最大优化带宽开销的节点作为迁入的目的节点.最后利用仿真实验验证本文方法的性能，通过与本领域其他预测模型的比较，证明了EMD-RBF-PSO 资源需求预测模型在预测精度和运行时间上具有优势，资源感知和流量优化的SFC 迁移方法在提高SFC 可靠性、降低SFC 时延和底层网络开销上具有较好性能.下一步将对SFC 的生存性和抗毁性进行研究，进一步提高NFV 环境下网络的性能.

作者贡献声明：阳勇负责算法设计、仿真和论文撰写；孟相如负责算法设计、整体指导；康巧燕负责算法仿真、文献整理；陈港负责整体文字把关.