Dynamic Service Function Chain Migration Method Based on Resource Requirements Prediction
-
摘要:
针对网络功能虚拟化环境下服务功能链资源需求变化引起的底层网络过载问题，提出一种基于资源需求预测的动态服务功能链迁移方法.首先，综合考虑迁移开销和迁移后底层网络的资源占用情况，建立底层网络开销模型.其次，利用经验模态分解将资源需求序列分解成本征模函数分量与残差分量，再通过径向基函数神经网络实现对各分量的预测，神经网络的训练过程采用粒子群算法进行参数优化.最后，对下一时隙即将过载的物理节点或链路，选择对过载资源占用最多的虚拟网络功能或虚拟链路进行迁出，并基于流量优化的原则，通过对全局拓扑的感知选择能最小化底层网络开销的物理节点迁入.仿真实验表明，所提的资源需求预测模型在提高预测精度的同时能缩短预测时间，所提的服务功能链迁移方法在降低底层网络开销、减少端到端时延和提高服务功能链可靠性等方面有较好性能.
Abstract:Aiming at the problem of network overload caused by the change of resource requirements of service function chain (SFC) under network function virtualization (NFV) environment, a dynamic SFC migration method based on resource requirements prediction (RRP-DSFCM) is proposed. Firstly, the migration overhead and resource overhead are considered comprehensively, and the physical network overhead model is established. Secondly, the resource requirements sequence is decomposed into intrinsic mode function (IMF) component and residual component by empirical mode decomposition (EMD), and each component is predicted by radial basis function (RBF) neural network. Particle swarm optimization (PSO) algorithm is used in the training process of neural network to optimize the parameters. Finally, for the physical nodes or links that will be overloaded in next timeslot, the virtual network function (VNF) or virtual link (that takes up the most overload resources) is selected to move out, and based on the principle of traffic optimization, the physical nodes which can minimize the overhead of the physical network are selected to move in through the awareness of the global network topology. The simulation results show that the proposed resource requirements prediction model can shorten the prediction time while improving the prediction accuracy, and the proposed SFC migration method has good performance in reducing the physical network overhead and the end-to-end delay and improving the reliability of the SFC.
-
传统网络硬件与软件紧耦合的架构带来网络功能部署设备开销大、管理困难和失效率高等问题[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 底层网络
物理网络抽象成一张加权无向图G=(N, E)，N是物理节点集合，E是物理链路集合. 任意物理节点ns
∈ N（s=1, 2, …）, ns上附着1个至多个服务器，用来实例化VNF.第t时隙ns的剩余可用计算资源为NCals(t) ，剩余可用存储资源为NMems(t) ，剩余可用转发资源为NFors(t) ，可靠性为r(ns)，运行VNF时产生的时延为d(ns). 任意物理链路es∈ E，剩余可用带宽为Bs(t)，产生的时延为d(es).1.2 SFC请求
SFC用六元组(I, O, D, R, V, L)表示，其中I表示源端点，O表示目的端点，D表示SFC允许的时延上限， R表示SFC允许的可靠性下限，V表示组成SFC的VNF集合，L表示组成SFC的虚拟链路集合.集合V={v1, v2, …, vn}中元素vi表示SFC第i个VNF，第t时隙其计算资源需求为
nCali(t) ，存储资源需求为nMemi(t) ，转发资源需求为nFori(t) ，带宽改变因子为ηi，其中带宽改变因子ηi定义为VNF流量的流出带宽与流入带宽之比. 集合L={l0, l1, …, ln}中元素li为vi到vi+1之间的虚拟链路. 特殊地，当i = 0时，li为源端点I到v1之间的虚拟链路；当i = n时，li为vn到目的端点O之间的虚拟链路. 用bi(t)表示li在第t时隙的带宽需求，则bi(t)的计算公式为bi(t)=b0(t)i∏k=1ηk. (1) 采用二进制变量xij(t)表示第t时隙vi是否部署在物理节点nj上，二进制变量
Xijm(t) 表示第t时隙vi是否从物理节点nj迁移至物理节点nm上，二进制变量yij(t)表示第t时隙li是否部署到底层网络后经过物理链路ej.1.3 底层网络开销模型
定义底层网络开销模型由迁移开销和资源开销2部分组成，其中迁移开销表示因VNF迁移期间中断服务所带来的赔偿损失，根据文献[23]，VNF迁移时间近似等于迁移存储数据的时间，所以第t时隙迁移vi的时间为
TMt(vi)=|N|∑j=1|N|∑m=1Xijm(t)nMemi(t)×hop(j,m)min (2) 其中(j,m)表示节点nj与nm之间的最短路径，hop(j,m)表示(j,m)的跳数. 设单位时间内中断服务的损失为α，则第t时隙SFC的迁移开销为
C_t^{\text{M}} = \sum\limits_{i = 1}^{\left| V \right|} {\alpha T_t^{\text{M}}\left( {{v_i}} \right)} . (3) 资源开销表示SFC部署到底层网络后占用资源所带来的成本，根据文献[24]，SFC迁移不会对底层节点资源占用量产生影响，只会因迁移后VNF部署位置发生变化而引起链路资源占用量改变，所以本模型对资源开销仅考虑链路带宽开销.设单位时隙内占用单位带宽的成本为β，则第t时隙SFC的资源开销为
C_t^{\text{R}} = \beta \sum\limits_{i = 0}^{\left| L \right|} {\sum\limits_{j = 1}^{\left| E \right|} {{y_{ij}}(t){b_i}\left( t \right)} } . (4) 结合迁移开销与资源开销，建立底层网络开销模型如式（5）所示.
{C_t} = C_t^{\text{M}} + C_t^{\text{R}}. (5) 本文主要符号含义如表1所示.
表 1 主要符号含义Table 1. Meaning of main Symbols符号 含义 N_s^{\mathrm{Cal}}(t) 第t时隙ns的剩余可用计算资源 N_s^{\mathrm{Mem}}(t) 第t时隙ns的剩余可用存储资源 N_s^{\mathrm{For}}(t) 第t时隙ns的剩余可用转发资源 r(ns) ns的可靠性 d(ns) ns运行VNF产生的时延 Bs(t) 第t时隙es的剩余可用带宽 n_i^{\mathrm{Cal}}(t) 第t时隙vi的计算资源需求 n_i^{\mathrm{Mem}}(t) 第t时隙vi的存储资源需求 n_i^{\mathrm{For}}(t) 第t时隙vi的转发资源需求 ηi vi的带宽改变因子 bi(t) 第t时隙li的带宽需求 τ(t+1) 第t+1时隙VNF的迁出指数 vmove 待迁移VNF nout 待迁移节点 ngoal 迁入目的节点 n_{\text {move }}^- vmove的上一个VNF所部署节点 n_{\text {move }}^+ vmove的下一个VNF所部署节点 2. 基于EMD-RBF-PSO网络的资源需求预测模型
为实现对资源需求的快速精准预测，本文建立基于经验模态分解、径向基函数神经网络、粒子群算法的预测模型，其运行流程如图1所示.
在模型的训练阶段，首先将历史资源需求数据进行EMD分解，生成N组本征模函数（intrinsic model function, IMF）分量和1组残差分量，目的是对非线性、非平稳的资源需求数据进行预处理，提高预测精度.其次将N组IMF分量合成，并与残差分量一起对RBF神经网络进行训练.训练过程中，将第t时隙的资源需求数据作为模型的输入样本，第t+1时隙的资源需求数据作为模型的输出样本.最后结合预测所得数据与输出样本计算预测误差，若误差高于所设阈值，则通过粒子群算法对RBF神经网络模型参数进行优化，并重复训练过程，直到误差低于所设阈值.
在模型的预测阶段，首先将当前一段时隙的资源需求数据进行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)的低频成分得到新序列
h_1^1 (t).m\left( t \right) = \frac{{{n_{\max }}\left( t \right) + {n_{\min }}\left( t \right)}}{2}, (6) h_1^1\left( t \right) = n\left( t \right) - m\left( t \right). (7) 步骤3. 令n(t)=
h_1^1 (t)，k次重复步骤1和步骤2，得到序列h_1^k (t).若h_1^k (t)满足式(8)，则第1个IMF分量c1(t)=h_1^k (t)，残差序列为r1(t)=n(t)−c1(t)，否则继续重复步骤1和步骤2.\sum\limits_{t = 0}^T {\frac{{{{\left| {h_1^{k - 1}\left( t \right) - h_1^k\left( t \right)} \right|}^2}}}{{{{\left[ {h_1^{k - 1}\left( t \right)} \right]}^2}}}} \leqslant \varepsilon , (8) 通常ε设定在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结果为
n\left( t \right) = \sum\limits_{i = 1}^n {{c_i}\left( t \right) + {r_n}\left( t \right)} . (9) 2.2 基于RBF神经网络的资源需求预测
RBF神经网络是一种激活函数为径向基函数的神经网络，具有学习速度快、分类能力强和近似模拟能力强等优势，能够以任意精度逼近任意连续函数，其神经网络结构如图2所示.
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）. 粒子的速度和位置更新方式分别为：
\begin{split} {v_{ij}}\left( {t + 1} \right) =& {v_{ij}}\left( t \right) + {c_1}{r_1}\left( t \right)\left[ {{p_{ij}}\left( t \right) - {y_{ij}}\left( t \right)} \right] + \\&{c_2}{r_2}\left( t \right)\left[ {{g_j}\left( t \right) - } {y_{ij}}\left( t \right)\right], \end{split} (10) {y_{ij}}\left( {t + 1} \right) = {y_{ij}}\left( t \right) + {v_{ij}}\left( {t + 1} \right). (11) 其中，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迁出，直到待迁移节点不再过载. 迁出指数的计算公式为
\begin{split} \tau \left( {t + 1} \right) =& k_{{\text{over}}}^{{\text{Cal}}}\left( {t + 1} \right){n^{{\text{Cal}}}}\left( {t + 1} \right) + k_{{\text{over}}}^{{\text{Mem}}}\left( {t + 1} \right){n^{{\text{Mem}}}}\left( {t + 1} \right) + \\& k_{{\text{over}}}^{{\text{For}}}\left( {t + 1} \right){n^{{\text{For}}}}\left( {t + 1} \right), \\[-10pt] \end{split} (12) 其中
k_{{\text{over}}}^{{\text{Cal}}}\left( {t + 1} \right) ，k_{{\text{over}}}^{{\text{Mem}}} \left( {t + 1} \right) ，k_{{\text{over}}}^{{\text{For}}} \left( {t + 1} \right) 分别表示第t+1时隙待迁移节点的计算、存储与转发资源是否过载，若过载，则相应变量取1，否则取0.迁出指数可以综合衡量VNF对过载节点上各种过载资源的占用程度，反映VNF适合迁移的程度.若迁移的对象是虚拟链路，同样需要从过载链路上部署的多条虚拟链路中选择待迁移虚拟链路迁出. 由于本模型只考虑虚拟链路对带宽资源的占用，所以直接按照带宽需求的大小对各虚拟链路进行降序排列，依次选择虚拟链路迁出，直到待迁移链路不再过载. RA-MVNFS的具体步骤如算法1所示.
算法1. RA-MVNFS算法.
输入：待迁移节点nout、物理网络G、SFC资源需求预测序列；
输出：待迁移VNF vmove.
① 计算nout下一时隙的剩余计算资源
N_{{\text{out}}}^{{\text{Cal}}}\left( {t + 1} \right) 、剩余存储资源N_{{\text{out}}}^{{\text{Mem}}}\left( {t + 1} \right) 、剩余转发资源N_{{\text{out}}}^{{\text{For}}}\left( {t + 1} \right) ；② 将nout上任意一个VNF赋值给vmove作为初始值；
③
\tau_{\text {move }}(t+1) = k_{\text {over }}^{\mathrm{Cal}}(t+1) n_{\text {move }}^{\mathrm{Cal}}(t+1) + k_{\text {over }}^{\mathrm{Mem}}(t+1) \times n_{\text {move }}^{\mathrm{Mem}} (t+1)+ k_{\text {over }}^{\mathrm{For}}(t+1) n_{\text {move }}^{\mathrm{For}}(t+1) ；④ for nout上每一个VNF vi
⑤
\tau_i(t+1)=k_{\mathrm{over}}^{\mathrm{Cal}}(t + 1) n_{\mathrm{i}}^{\mathrm{Cal}}(t + 1)+ k_{\mathrm{over}}^{\mathrm{Mem}}(t + 1) \times n_i^{\mathrm{Mem}} (t + 1)+ k_{\mathrm{over}}^{\mathrm{For}}(t+1) n_i^{\mathrm{For}}(t+1) ；⑥ if τi（t+1）>τmove（t+1）
⑦ vmove= vi；
⑧ end if
⑨ end for
⑩ return vmove.
3.2 基于流量优化和拓扑感知的迁入目的节点选择
本算法的中心思想是通过对物理网络拓扑的感知实现SFC流量的优化，使VNF迁移后相关联的大带宽需求虚拟链路在物理网络中部署的跳数尽可能小，直至其上的流量变为节点的内部流量.
如图4所示，待迁移VNF vmove的带宽改变因子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带宽.
定义节点的前后距为
Dis\left( {{n_i}} \right) = hop\left( {n_{{\text{move}}}^ - ,{n_i}} \right) + hop\left( {{n_i},n_{{\text{move}}}^ + } \right), (13) 其中
hop\left( {n_{{\text{move}}}^ - ,{n_i}} \right) 表示ni与待迁移VNF所在SFC的上一个VNF所部署节点之间的最短跳数，若待迁移VNF为所在SFC的第1个VNF，则n_{{\text{move}}}^ - 表示源端点.hop\left( {{n_i},n_{{\text{move}}}^ + } \right) 表示ni与待迁移VNF所在SFC的下一个VNF所部署节点之间的最短跳数，若待迁移VNF为所在SFC的最后1个VNF，则n_{{\text{move}}}^ + 表示目的端点.TOTA-MNS流程如图5所示，首先筛选满足vmove当前时隙与下一时隙所需资源需求的物理节点集Ф1.若vmove的带宽改变因子小于1，即流出vmove的带宽小于流入vmove的带宽，则判断节点
n_{{\text{move}}}^ - 是否在集合Ф1中. 若在，则直接输出迁入目的节点ngoal为n_{{\text{move}}}^ - ；若n_{{\text{move}}}^ - 不在集合Ф1中，则从Ф1中筛选Dis(ni)最小的节点集合Ф2，目的是使与vmove相关联的虚拟链路部署到物理网络后跳数最小，从而降低SFC的物理长度. 然后再从Ф2中筛选hop(n_{{\text{move}}}^ - ,ni)最小的节点集合Ф3，目的是实现流量的优化，降低带宽开销. 最后从Ф3中输出迁入目的节点ngoal. 若vmove的带宽改变因子大于1，步骤类似.算法2. TOTA-MNS算法.
输入：待迁移VNF vmove、待迁移节点nout、物理网络G、SFC资源需求预测序列；
输出：迁入目的节点ngoal.
① 计算各节点下一时隙的剩余计算资源 N Cal(t+1)、剩余存储资源N Mem(t+1)、剩余转发 资源N For(t+1)；
② 筛选满足vmove当前时隙与下一时隙资源需求 的节点，并将其放入集合Ф1；
③ if ηmove<1
④ if
n_{{\text{move}}}^ - \in Ф1⑤ ngoal =
n_{{\text{move}}}^ - ；⑥ return ngoal；
⑦ else
⑧ for Ф1中每一个节点ni
⑨ Dis(ni)= hop(
n_{{\text{move}}}^ - , ni)+ hop(ni,n_{{\text{move}}}^ + )；⑩ end for
⑪ 从Ф1中筛选Dis(ni)=min(Dis(ni))的节点， 并将其放入集合Ф2；
⑫ 从Ф2中筛选hop(
n_{{\text{move}}}^ - , ni)=min(hop(n_{{\text{move}}}^ - , ni)) 的节点，并将其放入集合Ф3；⑬ ngoal =Ф3(1)；
⑭ end if
⑮ else
⑯ if
n_{{\text{move}}}^ +\in Ф1⑰ ngoal =
n_{{\text{move}}}^ + ；⑱ return ngoal；
⑲ else
⑳ for Ф1中每一个节点ni；
㉑ Dist(ni)= hop(
n_{{\text{move}}}^ - , ni)+ hop(ni,n_{{\text{move}}}^ + )；㉒ end for
㉓ 从Ф1中筛选Dis(ni)=min(Dis(ni))的节点， 并将其放入集合Ф2；
㉔ 从Ф2中筛选hop(
n_{{\text{move}}}^ + ,ni)=min(hop(ni,n_{{\text{move}}}^ + )) 的节点，并将其放入集合Ф3；㉕ ngoal =Ф3(1)；
㉖ end if
㉗ end if
㉘ return ngoal.
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的指数分布.仿真时间设置代表2500个时隙，每个时隙代表1 min.物理网络和SFC的详细参数设置如表2所示.
表 2 仿真参数Table 2. Simulation Parameters实验参数 参数取值 节点计算资源/GB [70,80] 节点存储资源/GB [70,80] 节点转发资源/GB [70,80] 链路带宽/Mbps [200,300] 节点时延/ms [2,5] 节点可靠性 [0.9,0.98] 链路时延/ms [2,5] SFC的VNF个数 [5,8] VNF带宽改变因子 [0.8,1.3] SFC初始带宽及其变化值/Mbps [2,5] VNF计算资源需求初始值/GB [5,10] VNF计算资源需求变化值/GB [5,10] VNF存储资源需求初始值/GB [5,10] VNF存储资源需求变化值/GB [5,10] VNF转发资源需求初始值/GB [5,10] VNF转发资源需求变化值/GB [5,10] 注：参数值设置均服从均匀分布. 4.2 资源需求预测实验结果分析
随机选取1条SFC（本实验选第3条）的初始带宽序列b0(t)前1800个时隙作为训练样本，后700个时隙作为测试样本进行资源需求预测实验.本文基于EMD-RBF-PSO的预测模型中，径向基函数的扩展速度设置为1.5，神经元最大数目设置为80，每次加进来的神经元数为25.采用均方根误差ERMS衡量预测数据的准确性，其定义为
{E_{{\text{RMS}}}} = \sqrt {\frac{1}{n}\sum\limits_{t = 1}^n {{{\left( {{Y_t} - Y_t^{{\text{pre}}}} \right)}^2}} } , (14) 其中n为测试样本个数，Yt为测试样本真实值，
Y_t^{{\text{pre}}} 为测试样本预测值. ERMS越小，说明预测值与真实值越接近，预测算法性能越优.图6是本文预测模型各分量的预测结果，从图6（a）可看出IMF分量预测结果仅在尖峰处存在少量误差，其余部分基本与真实值拟合. 从图6（b）可看出余波分量预测结果基本与真实值拟合.
![]()
图 6 EMD-RBF-PSO模型对各分量预测结果Figure 6. Prediction results of EMD-RBF-PSO model for each component图7是不同模型对测试数据的预测结果，从图7（a）可发现EMD-RBF-PSO模型的预测结果除尖峰外，基本与真实值拟合.这是因为EMD-RBF-PSO模型对测试数据进行EMD预处理后，有效提高了预测精度. 从图7（b）可发现BP-NN模型的预测结果多处与真实值相差较大. 这是因为BP-NN模型未对测试数据进行预处理. 从图7（c）可发现HTP-POS模型的预测结果在突变处始终无法与真实值拟合. 这是因为HTP-POS模型采用小波分解对测试数据进行了预处理，而小波分解在处理非线性、非平稳数据上不具备明显优势，所以预测精度较低.
表3是3种模型的运行误差(ERMS)与运行时间对比结果，可发现在ERMS上本文预测模型最优，HTP-POS次之，BP-NN最差. 这是因为本文预测模型采用的EMD分解对处理带宽需求变化数据最具有优势；HTP-POS采用的小波分解虽在处理带宽需求变化数据上优势没有EMD明显，但仍然能提高预测精度；而BP-NN是直接对测试数据进行预测，所以预测精度最低. 在运行时间上，本文预测模型运行时间最短，HTP-POS次之，BP-NN最差. 这是因为本文预测模型与HTP-POS均采用了粒子群算法对模型参数进行优化，所以运行速度较快；而BP-NN未使用优化算法，所以运行速度最慢.
表 3 各预测模型误差（ERMS）与运行时间对比Table 3. Comparison of ERMS and Running Time of Each Prediction Model预测模型 ERMS 运行时间/s EMD-RBF-PSO 0.2285 0.9335 BP-NN 2.0507 1.5800 HTP-POS 0.5669 1.1058 4.3 SFC迁移实验结果分析
将3种迁移方法均在本文的EMD-RBF-PSO预测结果下进行实验，为避免随机因素影响，仿真实验进行10次，取每次结果的平均值作为最终实验结果. 单位时间内中断服务的损失α=1，占用单位带宽的成本β=100.
图8是本文SFC迁移方法在进行了资源需求预测和未进行资源需求预测的情况下过载节点数目对比结果，可看出进行资源需求预测后有效降低了物理网络节点过载的次数. 这是因为基于资源需求预测的SFC迁移能在下一时隙节点过载前将其上部署的VNF迁出，从而降低节点过载的概率.
图9是3种迁移方法的SFC平均可靠性对比结果，可以发现RATO-DSFCM的SFC平均可靠性最高，TPGDM次之，NAVMM最差. 这是因为RATO-DSFCM在进行迁入目的节点选择时会优先将
n_{{\text{move}}}^ - 或n_{{\text{move}}}^ + 作为目的节点，从而将vmove与所在SFC的上一个VNF或下一个VNF聚合，从而提高了SFC可靠性.图10是3种迁移方法的SFC平均时延对比结果，可以发现RATO-DSFCM的SFC平均时延最短，TPGDM次之，NAVMM最差. 这是因为RATO-DSFCM与TPGDM均在距离
n_{{\text{move}}}^ - 和n_{{\text{move}}}^ + 最短的节点集中选择迁入目的节点，所以有效降低了链路时延.图11是3种迁移方法的VNF迁移次数对比结果，可以发现TPGDM的VNF迁移次数最少，RATO-DSFCM次之，NAVMM最多. 这是因为TPGM在进行底层网络拓扑感知的基础上，并未对VNF进行聚合，有效降低了迁入目的节点随时间推移过载的概率，所以迁移次数最少. RATO-DSFCM在进行流量优化的同时对VNF进行了聚合，增加了迁入目的节点过载的概率，所以迁移次数多于TPGDM. NAVMM利用贪心算法总是选择最能降低迁移时间的节点进行迁入，未考虑迁入节点是否会在未来一段时间过载，所以迁移次数最多.
图12是3种迁移方法的VNF平均迁移时间对比结果，可发现NAVMM的VNF平均迁移时间最短，这是因为该算法会优先将迁入目的节点选在距离迁出节点较近的节点，所以明显缩短了VNF平均迁移时间. RATO-DSFCM优先将迁入目的节点选在
n_{{\text{move}}}^ - 和n_{{\text{move}}}^ + 的最短路径上，一定程度上也使得迁入目的节点与迁出节点较近，所以VNF平均迁移时间仅次于NAVMM. TPGDM在选择迁入目的节点时未考虑与迁出目的节点之间的联系，所以VNF平均迁移时间最长.图13是3种迁移方法的VNF总迁移时间对比结果，可以发现RATO-DSFCM的VNF总迁移时间最短，TPGDM次之，NAVMM最长. 这是因为RATO-DSFCM在保持较少迁移次数的前提下获得了较短的VNF平均迁移时间. TPGDM虽然获得了最少的迁移次数，但也导致平均迁移时间最长. NAVMM虽然获得了最短的平均迁移时间，但也使迁移次数最多.
图14是3种迁移方法的底层网络开销对比结果，可以发现RATO-DSFCM的底层网络开销最小，TPGDM次之，NAVMM最大. 因为RATO-DSFCM在进行拓扑感知的基础上将VNF迁移至
n_{{\text{move}}}^ - 和n_{{\text{move}}}^ + 的最短路径上，并进行了流量优化，所以获得较小的链路带宽开销；而TPGDM未对流量进行优化，所以链路带宽开销大于RATO-DSFCM；NAVMM在选择迁入目的节点时未考虑与n_{{\text{move}}}^ - 和n_{{\text{move}}}^ + 之间的拓扑联系，所以链路带宽开销最大.5. 结 论
本文针对网络功能虚拟化环境下SFC资源需求变化引起的物理网络过载问题，提出一种基于资源需求预测的动态服务功能链迁移方法.首先综合考虑SFC部署在物理网络中的带宽开销和因迁移而中断服务导致的赔偿损失，建立了底层网络开销模型.然后利用经验模态分解对资源需求序列预处理，通过RBF网络对预处理的结果进行预测，并利用粒子群算法对RBF网络的参数进行优化，建立了EMD-RBF-PSO资源需求预测模型.在实现资源需求预测的基础上，设计基于资源感知和流量优化的SFC迁移方法，通过对各VNF的资源感知筛选占用过载节点上过载资源最多的VNF实施迁移，并通过流量优化和拓扑感知算法选择迁移后能最大优化带宽开销的节点作为迁入的目的节点.最后利用仿真实验验证本文方法的性能，通过与本领域其他预测模型的比较，证明了EMD-RBF-PSO资源需求预测模型在预测精度和运行时间上具有优势，资源感知和流量优化的SFC迁移方法在提高SFC可靠性、降低SFC时延和底层网络开销上具有较好性能.下一步将对SFC的生存性和抗毁性进行研究，进一步提高NFV环境下网络的性能.
作者贡献声明：阳勇负责算法设计、仿真和论文撰写；孟相如负责算法设计、整体指导；康巧燕负责算法仿真、文献整理；陈港负责整体文字把关.
-
![]()
图 6 EMD-RBF-PSO模型对各分量预测结果
Figure 6. Prediction results of EMD-RBF-PSO model for each component
表 1 主要符号含义
Table 1 Meaning of main Symbols
符号 含义 N_s^{\mathrm{Cal}}(t) 第t时隙ns的剩余可用计算资源 N_s^{\mathrm{Mem}}(t) 第t时隙ns的剩余可用存储资源 N_s^{\mathrm{For}}(t) 第t时隙ns的剩余可用转发资源 r(ns) ns的可靠性 d(ns) ns运行VNF产生的时延 Bs(t) 第t时隙es的剩余可用带宽 n_i^{\mathrm{Cal}}(t) 第t时隙vi的计算资源需求 n_i^{\mathrm{Mem}}(t) 第t时隙vi的存储资源需求 n_i^{\mathrm{For}}(t) 第t时隙vi的转发资源需求 ηi vi的带宽改变因子 bi(t) 第t时隙li的带宽需求 τ(t+1) 第t+1时隙VNF的迁出指数 vmove 待迁移VNF nout 待迁移节点 ngoal 迁入目的节点 n_{\text {move }}^- vmove的上一个VNF所部署节点 n_{\text {move }}^+ vmove的下一个VNF所部署节点 
下载: 导出CSV
表 2 仿真参数
Table 2 Simulation Parameters
实验参数 参数取值 节点计算资源/GB [70,80] 节点存储资源/GB [70,80] 节点转发资源/GB [70,80] 链路带宽/Mbps [200,300] 节点时延/ms [2,5] 节点可靠性 [0.9,0.98] 链路时延/ms [2,5] SFC的VNF个数 [5,8] VNF带宽改变因子 [0.8,1.3] SFC初始带宽及其变化值/Mbps [2,5] VNF计算资源需求初始值/GB [5,10] VNF计算资源需求变化值/GB [5,10] VNF存储资源需求初始值/GB [5,10] VNF存储资源需求变化值/GB [5,10] VNF转发资源需求初始值/GB [5,10] VNF转发资源需求变化值/GB [5,10] 注：参数值设置均服从均匀分布.
下载: 导出CSV
表 3 各预测模型误差（ERMS）与运行时间对比
Table 3 Comparison of ERMS and Running Time of Each Prediction Model
预测模型 ERMS 运行时间/s EMD-RBF-PSO 0.2285 0.9335 BP-NN 2.0507 1.5800 HTP-POS 0.5669 1.1058
下载: 导出CSV
-
[1] Yu Ye, Bu Xiangyuan, Yang Kai, et al. Network function virtualization resource allocation based on joint benders decomposition and ADMM[J]. IEEE Transactions on Vehicular Technology, 2020, 69(2): 1706−1718 doi: 10.1109/TVT.2019.2959347
[2] Herrera J G, Botero J F. Resource allocation in NFV: A comprehensive survey[J]. IEEE Transactions on Network & Service Management, 2017, 13(3): 518−532
[3] Hawilo H, Shami A, Mirahmadi M, et al. NFV: State of the art, challenges and implementation in next generation mobile networks[J]. IEEE Network, 2014, 28(6): 18−26 doi: 10.1109/MNET.2014.6963800
[4] Lv Zhihan, Xiu Wenqun. Interaction of edge-cloud computing based on SDN and NFV for next generation IoT[J]. IEEE Internet of Things Journal, 2020, 7(7): 5706−5712 doi: 10.1109/JIOT.2019.2942719
[5] Ordonez-Lucena J, Ameigeiras P, Lopez D, et al. Network slicing for 5G with SDN/NFV: Concepts, architectures and challenges[J]. IEEE Communications Magazine, 2017, 55(5): 80−87 doi: 10.1109/MCOM.2017.1600935
[6] Yousaf F Z, Bredel M, Schaller S, et al. NFV and SDN—Key technology enablers for 5G networks[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2468−2478 doi: 10.1109/JSAC.2017.2760418
[7] 周伟林,杨芫,徐明伟. 网络功能虚拟化技术研究综述[J]. 计算机研究与发展,2018,55(4):675−688 doi: 10.7544/issn1000-1239.2018.20170937 Zhou Weilin, Yang Yuan, Xu Mingwei. Network function virtualization technology research[J]. Chinese Journal of Computers, 2018, 55(4): 675−688 (in Chinese) doi: 10.7544/issn1000-1239.2018.20170937
[8] Siasi N, Jaesim A, Aldalbahi A, et al. Deep learning for service function chain provisioning in fog computing[J]. IEEE Access, 2020, 8: 167665−167683 doi: 10.1109/ACCESS.2020.3021355
[9] Xu Siya, Liao Boxian, Hu Bo, et al. A reliability-and-energy-balanced service function chain mapping and migration method for Internet of things[J]. IEEE Access, 2020, 8: 168196−168209 doi: 10.1109/ACCESS.2020.3023502
[10] Li Guanglei, Feng Bohao, Zhou Huachun, et al. Adaptive service function chaining mappings in 5G using deep Q-learning[J]. Computer Communications, 2020, 152(2): 305−315
[11] Wang Ying, Zhang Leyi, Yu Peng, et al. Reliability-oriented and resource-efficient service function chain construction and backup[J]. IEEE Transactions on Network and Service Management, 2021, 18(1): 240−257 doi: 10.1109/TNSM.2020.3045174
[12] Zhai Dong, Meng Xiangru, Yu Zhenhua, et al. Reliability-aware service function chain backup protection method[J]. IEEE Access, 2021, 9: 14660−14676 doi: 10.1109/ACCESS.2021.3051045
[13] Zhu Mengfei, He Fujun, Oki E. Optimal primary and backup resource allocation with workload-dependent failure probability[C]//Proc of the 2020 Int Conf on Information and Communication Technology Convergence (ICTC). Piscataway, NJ: IEEE, 2020: 606−611
[14] Kang Rui, He Fujun, Sato T, et al. Virtual network function allocation to maximize continuous available time of service function chains with availability schedule[J]. IEEE Transactions on Network and Service Management, 2021, 18(2): 1556−1570 doi: 10.1109/TNSM.2020.3007712
[15] Liu Junjie, Lu Wei, Zhou Fen, et al. On dynamic service function chain deployment and readjustment[J]. IEEE Transactions on Network and Service Management, 2017, 14(3): 543−553 doi: 10.1109/TNSM.2017.2711610
[16] Pan Pan, Fan Qilin, Wang Sen, et al. GCN-TD: A learning-based approach for service function chain deployment on the fly[C]//Proc of the 2020 IEEE Global Communications Conf. Piscataway, NJ: IEEE, 2020: 7−11
[17] Li Yimi, Gao Lifang, Xu Siya, et al. Cost-and-QoS-based NFV service function chain mapping mechanism[C]//Proc of the 2020 IEEE/IFIP Network Operations and Management Symp. Piscataway, NJ: IEEE, 2020[2021-10-11]. https://doi.org/10.1109/NOMS47738.2020.9110356
[18] 唐伦,赵培培,赵国繁,等. 基于QoS保障的服务功能链动态部署算法[J]. 北京邮电大学学报,2018,41(6):90−96 doi: 10.13190/j.jbupt.2018-013 Tang Lun, Zhao Peipei, Zhao Guofan, et al. Dynamic deployment algorithm for service function chaining with QoS guarantee[J]. Journal of Beijing University of Posts and Telecommunications, 2018, 41(6): 90−96 (in Chinese) doi: 10.13190/j.jbupt.2018-013
[19] Li Biyi, Cheng Bo, Chen Junliang. A multi-stage approach for virtual network function migration and service function chain reconfiguration in NFV-enabled networks [C]//Proc of the 2020 IEEE Int Conf on Web Services (ICWS). Piscataway, NJ: IEEE, 2020: 207−215
[20] Tang Lun, He Lanqin, Tan Qi, et al. Virtual network function migration optimization algorithm based on deep deterministic policy gradient[J]. Journal of Electronics and Information Technology, 2021, 43(2): 404−411
[21] Yi Bo, Wang Xinwei, Huang Min, et al. Design and implementation of network-aware VNF migration mechanism[J]. IEEE Access, 2020, 8: 44346−44358 doi: 10.1109/ACCESS.2020.2978002
[22] Eramo V, Miucci E, Ammar M, et al. An approach for service function chain routing and virtual function network instance migration in network function virtualization architectures[J]. IEEE/ACM Transactions on Networking, 2017, 25(4): 2008−2025 doi: 10.1109/TNET.2017.2668470
[23] 唐伦,赵培培,赵国繁,等. 基于深度信念网络资源需求预测的虚拟网络功能动态迁移方法[J]. 电子与信息学报,2019,41(6):1397−1404 Tang Lun, Zhao Peipei, Zhao Guofan, et al. Virtual network function migration algorithm based on deep belief network prediction of resource requirements[J]. Journal of Electronics and Information Technology, 2019, 41(6): 1397−1404 (in Chinese)
[24] 丁绍虎,谢记超,张鹏,等. 基于风险感知的关键虚拟网络功能动态迁移方法[J]. 通信学报,2020,41(4):102−113 doi: 10.11959/j.issn.1000-436x.2020063 Ding Shaohu, Xie Jichao, Zhang Peng, et al. Dynamic migration method of key virtual network function based on risk awareness[J]. Journal on Communications, 2020, 41(4): 102−113 (in Chinese) doi: 10.11959/j.issn.1000-436x.2020063
[25] Lang Xun, Zheng Qian, Zhang Zhiming, et al. Fast multivariate empirical mode decomposition[J]. IEEE Access, 2018, 6: 65521−65538 doi: 10.1109/ACCESS.2018.2877150
[26] Qiu Xueheng, Ren Ye, Suganthan P N, et al. Empirical mode decomposition based ensemble deep learning for load requirement time series forecasting[J]. Applied Soft Computing, 2017, 54(5): 246−255
[27] Moradi M J, Roshani M M, Shabani A, et al. Prediction of the load-bearing behavior of SPSW with rectangular opening by RBF Network[J]. Applied Sciences, 2020, 10(3): 1185−1196 doi: 10.3390/app10031185
[28] Pati J, Kumar B, Manjhi D, et al. A comparison among ARIMA, BP-NN, and MOGA-NN for software clone evolution prediction[J]. IEEE Access, 2017, 5: 11841−11851 doi: 10.1109/ACCESS.2017.2707539
[29] 史朝卫,孟相如,康巧燕,等. 基于混合流量预测的虚拟网络拓扑重构方法[J]. 系统工程与电子技术,2021,43(5):1382−1388 doi: 10.12305/j.issn.1001-506X.2021.05.27 Shi Chaowei, Meng Xiangru, Kang Qiaoyan, et al. Virtual network topology reconfiguration approach based on hybrid traffic prediction[J]. System Engineering and Electronics, 2021, 43(5): 1382−1388 (in Chinese) doi: 10.12305/j.issn.1001-506X.2021.05.27
[30] Tang Lun, He Xiaoyu, Zhao Peipei, et al. Virtual network function migration based on dynamic resource requirements prediction[J]. IEEE Access, 2019, 7: 112348−112362 doi: 10.1109/ACCESS.2019.2935014
-
期刊类型引用(1)
1. 刘行，郭靓，王正琦，韦小刚，徐雪菲，刘京. 基于Q学习的安全服务功能链编排算法. 计算机与现代化. 2024(11): 34-40 . 
百度学术
其他类型引用(1)
计量
- 文章访问数: 134
- HTML全文浏览量: 12
- PDF下载量: 64
- 被引次数: 2
