1.   引言

5G网络架构下涌现的多种应用场景在移动性、安全性、时延和可靠性等方面要求各不相同^[1]。下一代移动网络联盟提出了网络切片的概念^[2]，在该场景下的服务功能链(Service Function Chaining, SFC)创造了动态的网络服务，由于SFC中的虚拟网络功能(Virtual Network Function, VNF)运行在通用服务器中，这种业务处理架构保证了VNF的灵活性和可调整性^[3]。然而，如何设计有效的VNF部署、网络资源配置方案是一个巨大的挑战^[4]。

文献[5]采用遗传算法解决了服务功能链的部署问题，虽然实现了各条链间更公平的资源分配，但只能解决单一调度周期上的资源调度问题。文献[6]设计了一种基于马尔可夫近似算法最大化混合型SFC网络效用，但并未考虑网络负载的动态变化对业务速率需求的影响。文献[7]基于无线虚拟化网络内的缓存空间和无线带宽调度问题建立了一种博弈机制，但并未考虑虚拟网络间的差异化需求。文献[8]提出了一种基于深度学习的虚拟机工作负载预测方法，然而该模型仅适用于单个虚拟机的资源预测。文献[9]提出一种基于图形神经网络(GNN)的算法预测VNF对资源的需求，并通过Openstack平台实现了VNF的调度和动态的资源管理，但该方法过于依赖网络的拓扑信息。

综上所述，在研究SFC部署的相关文献中，大多数工作只停留在解决单一部署周期的资源调度问题上，而在实际网络场景中，若未动态地分配网络资源处理变化的业务请求，可能会引起数据的积压而导致队列溢出概率增大、端到端时延增加等问题，因此网络应根据当前的队列状态动态地调整资源分配以提供稳定的服务^[10]；同时，将预测与SFC的部署相结合的研究较少，导致在VNF的调度过程由于滞后性引起服务性能的下降。本文基于业务请求动态变化的5G网络切片应用场景，设计了一种基于长短时记忆网络(Long Short-Term Memory, LSTM)预测的虚拟网络功能部署算法，本文的主要贡献总结如下：(1)设计基于时延感知的SFC队列缓存模型，并在包含多种时间尺度的时间域上分配虚拟资源；(2)考虑到用户请求业务的动态性和信息反馈的延迟引起不合理的虚拟网络资源分配或缓存溢出概率增大等问题，提出一种基于LSTM神经网络的流量感知算法，通过各个切片业务的历史队列信息来预测未来的负载情况，从而实现了网络的在线监测；(3)基于对多个切片业务负载情况的预测结果，提出了一种动态的VNF调度与资源分配方案，引入了一种最大最小蚁群算法(Maximum and Minimum Ant Colony Algorithm, MMACA)实现多条服务功能链的动态部署，根据各个切片的队列大小实时地为其分配虚拟网络资源。

2.   系统模型

在5G网络功能虚拟化、无线云化环境中，资源的分配是在“池”的层面上进行的，这种方式带来了资源的灵活分配，从而实现了更加动态的网络服务，满足更多样化的需求^[11]。

图1为网络切片场景下的SFC部署系统架构图，从左至右依次为无线虚拟网络用户、虚拟网络管理平台、虚拟网络功能调度层、虚拟资源池。在该系统中，虚拟资源池中的云服务器提供包含计算资源、缓存资源、带宽资源等多种类型的虚拟网络资源，虚拟网络管理平台则根据虚拟网络用户的业务状态，QoS需求等实现VNF的调度、虚拟网络资源的灵活分配。本文设计的虚拟网络管理平台由业务请求单元、负载分析模块、资源管理实体、网络状态监控实体、虚拟网络调度器等部分组成。其中，业务请求单元用于缓存各切片用户新到达的数据包；负载分析模块用于分析各切片的缓存负载特征，并预测下一周期负载状态；虚拟网络调度器则根据负载分析模块的评估结果决定每条SFC的部署方案；资源管理实体在SFC完成部署后分配各个虚拟网络功能模块获得的最佳虚拟资源量；网络状态监控实体的作用是观察各虚拟资源的实时状态。

图 1  网络切片场景下的SFC部署系统架构图

下载: 全尺寸图片 幻灯片

3.   网络模型

3.1   基于时延的服务功能链队列模型

本文将不同用户对同一类型网络业务请求的数据集合定义为切片，用$S$表示。$F\,$表示所有VNF模块的集合，对于第$i$个网络切片${S_i}$，业务请求的VNF集合用${F_i} = \{ {f_{i1}},{f_{i2}}, ·\!·\!· ,{f_{ij}}, ·\!·\!·,{f_{iJ}}\}$表示。其中，$i \in {[1,\left| S \right|]_z},j \in {[1,\left| {{F_i}} \right|]_z}$, ${f_{ij}}$表示网络切片$i$需要调度的第$j$个VNF。虚拟网络拓扑由无向图$G = \left( {V,E} \right)$表示，其中，$V\;$表示虚拟节点的集合，$E$表示虚拟链路的集合。$F_m{\!\!'}\left( {m \in {{[1,\left| V \;\right|]}_z}} \right)$表示虚拟节点$m$能处理的VNF种类集合，例如$F_m{\!\! '} = \{ {f_1},{f_3},{f_6}\}$表示虚拟节点$m$能够处理虚拟网络功能${f_1}$, ${f_{\rm{3}}}$, ${f_{\rm{6}}}$，本文假设网络内的虚拟链路带宽资源充足。令${N_{{f_{ij}}}}\left( {i \in {{[1,\left| S \right|]}_z},j \in {{[1,\left| {{F_i}} \right|]}_z}} \right) \subseteq V\;$表示能够执行虚拟化网络功能f_ij的虚拟节点集合。

$x_{{f_{ij}}}^m$表示网络切片$i$需要调度的第$j$个VNF是否选择在虚拟节点$m$上执行

$y_{{f_{ij}}}^l$表示执行完虚拟网络功能${f_{ij}}$后传输数据流的虚拟链路的选择

本文将网络运行的时间维度分为若干个时隙，用$\varGamma {\rm{ = }}\left\{ {1,2,·\!·\!· ,t, ·\!·\!· ,T} \,\right\}$表示网络运行的时隙集合，其中，定义每个时隙$t$的持续时间为${T_{\rm s}}$。因此在时隙$t$内，${R_i}(t)$表示在时隙$t$内提供给切片${S_i}$的服务速率。令${C_{{f_{ij}}}}(t) = {\eta _{{f_{ij}}}} \cdot {R_i}(t)$，其中，${C_{{f_{ij}}}}(t)$表示切片${S_i}$在时隙$t$内节点执行$f_{ij}$提供一定服务速率所需的计算资源。$\eta$表示服务速率系数，该系数表示不同种类VNF提供一定服务速率所对应的资源关系^[12]。

假设${Q_i}(t)$表示在时隙$t$切片${S_i}$的队列长度，${A_i}(t)$表示数据包的到达过程且服从参数为${\lambda _i}$的泊松分布，所有用户的包到达过程在不同调度时隙是独立分布的，令${P_i}(t)$代表数据包大小，数据包大小服从均值为${\bar P_i}$的指数分布^[13]。那么平均包的处理速率为${\mu _i} = {R_i}/{\bar P_i}$。所以缓存中队列的长度更新过程表示为

其中，${D_i}(t) = {\mu _i}(t) \cdot {T_{\rm s}}$表示在时隙$t$内被处理的数据包数目。

令$Q_i^{\max }$表示第$i$个切片队列所允许的最大缓存大小，为了降低切片的平均比特丢失率，计算防止切片队列溢出所需最低的服务速率，对于任意$t$内，第$i$个切片队列长度的增量表示为${I_i}(t) = {A_i}(t) -$${D_i}(t)$，且切片队列不溢出需满足${Q_i}(t + 1) \!-\! Q_i^{\max } \le 0$，因此服务速率应保证

本文考虑的端到端时延主要由排队时延和处理时延所决定。由于假设虚拟链路带宽资源是足够的，因此假设传输时延、VNF迁移产生的时延以及数据包大小差异造成的等待时延忽略不计。令${\overline {T\,}}_{\rm w}^{\ i}$, ${\overline {T\,}}_{\rm p}^{\ i}$分别表示切片${S_i}$数据包平均排队时延、在整个网络相应虚拟节点上的平均处理时延。因此端到端时延$\tau$可表示为

由Little定理可以得到切片$i$的平均排队时延与平均队列长度的关系为${\bar Q_i} = {\lambda _i}{\bar T}_{\rm w}^{\ i}$，处理时延${X_i}$由执行各个VNF的时延${X_{{f_{ij}}}}$组成，且${X_{{f_{ij}}}} = {P_i}/{R_i}$, ${X_i} = {X_{{f_{i1}}}} + {X_{{f_{ij}}}} + ·\!·\!· + {X_{{f_{iJ}}}}$，数据包大小相互独立，同时各个节点服务速率保持一致性，所以传输切片${S_i}$的数据包总平均端到端时延为

本文的目标是从而最小化网络内多条服务功能链VNF整体调度产生的端到端时延，因此SFC动态部署问题可建立成式(7)的数学模型

式(8)中相应约束说明：${\rm C}1$保证了处理切片${S_i}$的1个VNF只能在1个相应的虚拟节点上运行。${\rm C}2$保证了执行完${f_{ij}}$后传输数据流的虚拟链路不超过1条。${\rm C}3$保证了对于${f_{ij}}$在虚拟节点上执行后数据通过链路$l$传输，如果该链路的头部节点是$m$，则表明执行${f_{ij}}$的虚拟节点一定是$m$。${\rm C}4$保证了数据流从第$j - 1$个VNF到第$j$个VNF只使用了1条链路$l$。${\rm C}5$保证了虚拟节点$m$上的虚拟化网络功能${f^{'}}$同时只能被1个切片的服务功能链所调度。${\rm C}6$确保VNFs的资源需求不能超过虚拟节点的资源限制。

3.2   基于LSTM神经网络的预测方法

由上一节可知各切片业务的负载特征直接影响着SFC部署的有效性，而采用预测的机制实现网络的在线监测能解决资源管理的滞后性，因此本文采用基于LSTM的预测方法，提前预测缓存内的未来负载状态。该方法定义每一个节点$n$对应的特征${F_n}$，通过这些特征信息，LSTM模型为每个节点$n$制定了隐藏层状态${h_n}$，进而决定每个节点的输出${o_n}$。基于LSTM的动态资源管理系统对于单个切片的模型如图2所示

图 2  单个切片基于LSTM的资源预测模型

下载: 全尺寸图片 幻灯片

3.2.1   特征与状态

切片特征由观察到的当前缓存中队列长度${Q_i}$与用户请求该业务的数据包到达率${A_i}$组成，具体为在虚拟网络$G = \left( {V,E} \right)$中，对于服务功能链$i$第$j$个VNF，令${C_{{f_{ij}}}}$表示防止队列溢出的最低计算资源需求，为了简化问题，本文仅考虑CPU资源的使用。所以切片$i$的特征可以表示为${x_i} = \{ {A_i},{Q_i}\}$，所以对于某一时刻$t$，神经网络输入为${x_i}(t) =$$\left\{ {{A_i}(t),{Q_i}(t)} \right\}$。另外定义1个历史数据集的窗口长度$\varepsilon$，在历史时刻$t - \varepsilon$至$t$的范围内，网络模型输入的数据集可以表示为

本文构建的LSTM网络模型可以描述为

其中，${i_t}$为输入门，${f_t}$为遗忘门，${o_t}$为输出门，$g{}_t$决定了输入有多少保存到单元状态中，$c{}_t$为单元状态，$\text{Λ}$为包含学习的参数仿射变换矩阵，${h_{t - 1}}$为隐藏层，$\sigma$和⊙分别表示激活函数sigmoid和元素级乘积。

本文的模型将历史的队列状态以及用户请求业务的数据包历史到达率作为输入，输出为缓存内的未来负载状态进而得到服务功能链VNF具体资源需求的预测结果。该过程具体的描述如表1所示。

表 1  基于LSTM的VNF资源需求预测模型

1 初始化：W，迭代次数$\kappa = 0$，状态$h\left( \kappa \right) = 0$
2 \*网络状态的监测*\
3　　监测不同时刻用户请求业务的数据包到达率
4　　利用SFC部署算法更新队列状态并记录当前队列大小
5 \*状态计算*\
6　　while $\left( {\kappa < T} \right)$ do
7　　　通过式(10)—式(12)计算$h\left( {\kappa + 1} \right)$
8　　　$\kappa = \kappa + 1$
9　　end while
10 \*输出计算*\
11 计算不同切片业务负载的预测值
12 计算输出各个VNF资源需求预测值$C_{f_{ij}}$

下载: 导出CSV 

| 显示表格

3.2.2   网络学习与训练

为了实现VNF资源需求精确的预测，权重函数需要反复的训练，因此针对本文解决的问题，需要大量的样本数据，其中包含切片历史特征信息${x_i}(t - \varepsilon ),{x_i}(t - \varepsilon {\rm{ + 1}}), ·\!·\!·,{x_i}(t)$，未来时间段内负载状态的实际值${\xi _t}$。训练的目标是式(13)的2次成本惩罚函数最小化

其中，式(13)的第1项为损失函数，${o_i}$为预测值，${\xi _i}$为真实值；第2、第3项分别为惩罚项，L2正则化约束项，$\alpha$为惩罚系数，$\gamma$为权值衰减系数，$\psi$为阈值，$w$表示模型中所有的权重参数。训练的目标是找到最佳的权重$W$(拟合数据的特征)使得成本函数最小化，具体的学习流程如表2所示。

表 2  学习与训练权重

1 迭代$\kappa = 0$时，采用Xavier[14]初始化权重，即令权重的概率分布 函数服从$W \sim U\left[ { - \dfrac{{\sqrt 6 }}{{\sqrt {{\chi _p} + {\chi _{p + 1}}} }},\dfrac{{\sqrt 6 }}{{\sqrt {{\chi _p} + {\chi _{p + 1}}} }}} \right]$的均匀分布，其 中$\chi$为网络层数，p为神经元个数
2 while(未达到训练要求标准)do
3　　使用表1中算法计算状态$h\left( \kappa \right)$和输出$o\left( \kappa \right)$等参数
4　　利用反向传播算法(BPTT)，使用惩罚函数式(13)计算惩罚 函数的梯度
5　　通过式(14)更新权重W
6　　$\kappa = \kappa + 1$
7 end while

下载: 导出CSV 

| 显示表格

式(14)为权重的更新，$\dfrac{{\partial G}}{{\partial W}}$表示惩罚函数的梯度，$\varphi$表示学习率，$G$表示惩罚函数。

3.3   基于最大最小蚁群算法的服务功能链部署方法

在应用蚁群算法求解服务功能链问题的过程中，使用一个2维矩阵pathMatrix表示多条服务功能链的部署列表，其中，2维矩阵的行数为$\displaystyle\sum\nolimits_{i \in {{[1,\left| S \right|]}_z}} {{F_i}}$，列数为$\left| M \right|$。将每只蚂蚁在1次循环内的搜索到的VNF调度路径看成是服务功能链部署的1个解，考虑到每种业务用户请求数据大小的不同，从而导致VNF处理时延的要求有一定的差异，这些因素都将影响算法的寻优过程。具体的算法设计流程如表3所示。

表 3  基于最大最小蚁群算法的多条服务功能链部署算法

1 初始化：蚂蚁规模antNum、信息素因子$\partial$、启发函数重要程度 因子$\beta$等参数
2 for ${\rm itCount=1:iteratorNum}$ do
3　　for ${\rm antCount=1:antNum}$ do
4　　\*VNFs的调度*\
5　　　for $i=1:I$ do
6　　　　for $j=1:J$ do
7　　　　根据式(18)计算转移概率$P\left( k \right)$并采用轮盘赌法选择下 一个VNF部署的节点$m$
8　　　　更新路径矩阵pathMatrix和节点剩余资源向量${\text{C}_{ {\rm{re} } } }\left( m \right)$
9　　　　end
10　　　end
11　　end
12 \*虚拟节点计算资源的分配*\
13　　//对每个虚拟节点上的VNF按需求比例进行资源的分配
14　　for $m=1:M$ do 　15　　　　${C_{\rm max}}({f_{ij}}) = {C_{\rm total}}(m)\cdot {C_{\rm pr}}({f_{ij}})\Bigr/\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {{C_{\rm pr}}({f_{ij}})\cdot x_{{f_{ij}}}^m} }$
16　　end
17　　//计算每条服务功能链提供最大服务速率时实际分配 VNF的计算资源
18　　for $i=1:I$ do
19　　　　${C_{{f_{ij}}}} = \mathop {\min }\limits_{j \in J} \left\{ {{C_{\max }}({f_{ij}})/{\eta _{{f_{ij}}}}} \right\} \cdot {\eta _{{f_{ij}}}}$
20　　end
21 根据式(19)更新信息素矩阵；根据式(15)—式(17)，式(22)对 $\rho$, $\partial$, $\beta$, $\zeta$进行更新
22 end
23 多次迭代后得到近似最优的SFC部署方案${\rm De}{{\rm p}_{{\rm SF}{{\rm C}_i}}}$
24　　\*计算服务功能链VNF平均调度时延*\
25　　　for $i=1:I$ do
26　　　　根据式(6)计算平均端到端时延${\tau _i}$
27　　　end

下载: 导出CSV 

| 显示表格

在自适应蚁群算法中，将信息素浓度挥发因子$\rho$，信息素因子$\partial$，启发函数重要程度因子$\beta$分别限制在区间$\left[ {{\rho _{\min }},{\rho _{\max }}} \right]$, $\left[ {{\partial _{\min }},{\partial _{\max }}} \right]$, $\left[ {{\beta _{\min }},{\beta _{\max }}} \right]$，其中${\rho _{\min }}$, ${\partial _{\min }}$, ${\beta _{\min }}$代表了$\rho$, $\partial$和$\beta$的最小值，${\rho _{\max }}$, ${\partial _{\max }}$, ${\beta _{\max }}$代表了$\rho$, $\partial$和$\beta$的最大值。因此，当算法陷入局部最优时对以上3个参数按式(15)—式(17)更新。

在进行服务功能链路径选择的过程中，当前节点转移至$k$节点的状态转移概率为

$c$表示执行${f_{ij - 1}}$的虚拟节点，$k$表示下一节点，${N_{{f_{ij}}}}$表示能够执行${f_{ij}}$的虚拟节点集合，$k \in {N_{{f_{ij}}}}$，$\partial$表示信息素因子，$\beta$为启发函数重要程度因子，${\delta _k}$代表了启发函数，其值可由式${\delta _k}{\rm{ = }}{C_{{\rm{re}}}}{\rm{(}}k{\rm{) - }}{C_{{\rm{pr}}}}({f_{ij}})$可得，其中，${C_{{\rm{re}}}}{\rm{(}}k{\rm{)}}$表示当前$k$节点剩余的资源，${C_{{\rm{pr}}}}({f_{ij}})$表示${f_{ij}}$对资源的最低需求预测结果。信息素的更新为

$\rho$为信息素挥发因子，${C_{{\rm{ac}}}}(s)$表示第$s$只蚂蚁路径选择完成之后计算出的服务功能链所分配的计算资源总和；$Q$为常系数，${\rm{iN}}$为迭代次数，${\rm{aN}}$表示蚂蚁规模。为了防止局部最优的出现，本文将各条寻优路径上的信息素浓度限制在$\left[ {{\zeta _{\min }},{\zeta _{\max }}} \right]$，即按照式(22)对信息素浓度进行约束

4.   仿真与性能分析

本文将VNFs的平均端到端时延、平均比特丢失率等作为评价指标，同时VNF的调度及资源分配上，为了更好地体现MMACA算法的性能，对比了基于普通的蚁群算法静动态的资源分配方案(ACA-D、ACA-S)，以及文献[5]中基于遗传算法的VNF部署及资源动态分配方案(GA-D)。在资源需求的预测问题上，对比了文献[15]基于ARMA的负载预测算法。本文仿真的过程中假设的网络场景为全连接型网络，网络规模包含8个VM和3种网络切片业务。同时假设实现每一种网络切片业务的服务功能链由固定且相等的VNF个数组成，并且每一VNF至少能在3～5个VM上执行。相关的仿真参数设置如表4所示。

表 4  仿真参数

仿真参数	仿真值
网络切片业务数量	3
短周期时长	10 s
长周期时长	4 h
数据包到达过程	泊松分布
数据包到达速率	[50, 100]个/s
数据包大小	指数分布
队列缓存大小	10 MB
数据训练窗口	8
神经元个数	10
仿真时间	24 h
学习率	0.01

下载: 导出CSV 

| 显示表格

本文每个长周期内用户请求切片业务数据包的到达速率${\lambda _i}$服从均值为[50，100]个/s的泊松分布，每个数据包的大小服从均值为500 kbit的指数分布，同时假设每个数据包被VNF模块处理后大小不发生变化。为了模拟业务到达以天为单位的周期性循环，业务到达模式以每经过140000个请求循环^[9]。

接下来首先对本文所提方案中切片未来负载的预测能力进行验证。为了验证模型的预测效果，本文采用平均绝对百分比误差(Mean Absolute Percentage Error, MAPE)对预测的准确度进行衡量，MAPE定义为

其中，${o_i}(t)$为预测值，${\xi _i}(t)$为真实值，$\varOmega$为测试样本的数量。MAPE的值越小，说明预测的准确度越高。图3和图4刻画了在6个连续长周期下数据包处理后切片队列状态的真实情况与基于不同预测方案所得值的拟合效果。图5表示不同方案对最大负载预测误差对比，可以看出基于LSTM的预测方案整体效果优于ARMA。图6表示LSTM训练过程的平均误差，从图6中可知初始训练阶段总平均误差处于较高水平，经过约300次迭代之后，误差基本平稳并控制在较低范围。

图 3  切片业务队列负载情况LSTM预测值与实际值对比图

下载: 全尺寸图片 幻灯片

图 4  切片业务队列负载情况ARMA预测值与实际值对比图

下载: 全尺寸图片 幻灯片

图 5  预测误差对比图

下载: 全尺寸图片 幻灯片

图 6  LSTM训练过程平均误差

下载: 全尺寸图片 幻灯片

图7显示了不同长周期内不同方案下的平均端到端时延对比图，可以看出本文提出的MMACA算法在性能上与其它3种方案相比处于较高水平，这是因为MMACA算法采用了基于流量感知的资源分配机制，提前进行针对性的VNF调度并按需以比例公平的方式进行资源配置，并在SFC部署过程中通过参数动态自适应的改进策略，降低了算法陷入局部最优解的可能性，提高了SFC部署的寻优能力。而其它3种资源配置方案存在算法性能上的不足，或忽略了网络业务动态变化这一特点，在某种程度上会造成资源配置与实际需要的不匹配问题。图8显示了在6个不同的长周期下，不同方案在比特丢失率上的性能评估。可以看出，当长周期的数据包到达率处于较低水平时，所以各方案的比特丢失率都处于较为理想的水平。当长周期的数据包到达率增大时，各VNF开始竞争有限的CPU资源，此时由于MMACA方案合理地按需调度有限的资源，所以采用该算法的VNF调度及资源分配方案在平均比特丢失率上依然保持较高的性能，而由于GA-D和ACA-D方案容易陷入局部最优解，所以出现了相对于MMACA方案较为严重的比特丢失情况。而ACA-S方案采用的是静态的资源调度方案，在比特丢失率上的性能表现得十分不理想。

图 7  平均端到端时延的对比图

下载: 全尺寸图片 幻灯片

图 8  不同方案平均比特丢失率对比图

下载: 全尺寸图片 幻灯片

5.   结束语

针对无线虚拟化网络中在时间域上用户请求业务的变化性和信息反馈的时滞效应而引起虚拟资源分配的不合理，本文提出了一种基于预测的虚拟网络功能部署算法MMACA，该算法将计算资源作为虚拟化的载体，考虑到变化的业务请求引起数据的积累而产生的队列积压，提出了一种基于LSTM神经网络的流量感知模型，并利用SFC最低资源需求的预测结果设计了一种基于自适应蚁群算法的虚拟网络功能调度方案。仿真结果表明，本文的预测算法精确度很高，同时，将预测与虚拟网络功能结合的方案可有效地降低网络切片业务的整体端到端时延和比特丢失率。