开放科学(资源服务)标志码(OSID):

0 概述

软件定义网络(Software Defined Network，SDN)通过核心技术Openflow分离网络设备的控制平面和数据平面，实现了网络可编程化和对网络流量的灵活控制，使网络更加智能、动态和灵活^[1]。网络功能虚拟化(Network Function Virtualization，NFV)将网络功能与专用硬件解耦，在网络管理和维护方面获得更高灵活性，同时减少了网络运营成本和支出^[2-3]。服务功能链(Service Function Chains，SFC)是当客户端的服务请求到达时，网络服务供应商利用SDN技术在虚拟网络上连接的一组链式有序的虚拟网络功能(Virtualized Network Function，VNF)，该功能可使数据包在指定路由上传输^[4-5]。

第5代移动通信网络旨在提供高速率、低延迟的服务，这些服务通常以特定的顺序分发和访问。但在部署服务功能链时须考虑多种因素，例如计算资源、带宽等。用户根据所定制的业务，对服务功能链的需求有所不同。也正是需求的不同使有效部署服务功能链变得更加困难。体验质量(Quality of Experience，QoE)是从用户角度反映应用或服务质量的有效指标，一方面可作为提供者的优化目标，表示当前服务与网络质量和用户体验之间的关系；另一方面可作为反馈信息用以指导服务功能链的部署，在保证应用程序或服务的QoE的同时优化资源使用状况^[6]。与QoE相比，服务质量(Quality of Service，QoS)从网络性能方面处理业务，为用户提供业务质量的保障，并满足每个用户的需求。使用定性的QoE指标代替定量的QoS指标，可以为更多用户优化服务功能链的部署，提升用户的体验质量。

为提高用户的满意度，以往的文献通常选取1个或2个QoS指标对服务功能链进行优化部署。文献[7]采用神经网络的方法预测所需虚拟网络功能实例的数量实现自动缩放，利用整数线性规划进行SFC部署从而达到最小时延。文献[8]提出四阶段自适应调度方案以权衡不同的调度目标，并提出多项式时间复杂度的最小权路径选择算法以实现实际的SFC调度，从而实现了较高的网络吞吐量和资源利用率，并降低了网络缩放频率。文献[9]设计一种高效能的SFC算法以满足客户的QoS要求和实现最小化能耗。该算法基于Dijkstra算法根据具体需求计算服务的最短路径，在考虑功耗的前提下沿路径分配VNFs到虚拟机。此外，还考虑了闲置服务的能源消耗，当成本超出给定的阈值时将重组服务功能链的路径。文献[10]研究了具有能量效率和QoS保证的VNFs动态布局问题，并提出能耗最小化的VNF-EQ算法。

传统的服务功能链部署，只选取1个或2个QoS指标作为QoE指标，并未对QoE进行系统研究。文献[11]提出在SDN/NFV支持的5G切片中基于强化学习的QoS/QoE感知服务功能链，采用IQX假设和WFL假设进行QoS与QoE之间的映射，并采用强化学习算法进行SFC的算法编排，但只进行了映射并没有进行QoE的预测。文献[12]提出一种基于延迟预测的QoE驱动服务链部署算法，该算法显著提高了用户的体验质量，但该算法只把时延作为QoE进行预测并没有考虑其他参数的影响。文献[13]设计了一种基于马尔科夫链的多实例VNF布局算法，最大程度地降低了时延和成本，保证了不同服务功能数量下的QoE要求，使网络负载均衡。然而该算法只保证了QoE要求，并没有对服务功能链中的QoE进行研究和预测。文献[14]提出了ScaRL算法，该算法利用启发式解决方案的试错机制、奖励机制和探索开发能力，以及利用强化学习算法做出最优决策，通过降低SFC请求的平均延迟和阻塞率保证QoE不降低。但该算法并未对QoE进行研究。

传统的QoE预测模型一般为单维或低维的，其实时性差且准确度不高。近年来，机器学习预测算法受到广泛关注，被用于从网络指标中预测QoE。文献[15]通过对比BP神经网络和深度置信网络(Deep Belief Network，DBN)发现基于DBN的QoS到QoE的映射模型的迭代次数和收敛效果更好。文献[16]建立了一种基于机器学习的移动视频流多维QoE预测模型，实验结果表明基于决策树的模型性能如预测性能优于以往的模型。

本文采用易测可控的网络层QoS参数进行QoE映射、评估与预测，构建一种面向SDN/NFV的服务功能链部署模型。利用此模型收集影响服务功能链部署的网络QoS参数，并提出一种基于层次分析法的多参数网络QoS到QoE(Multi-Parameter Network QoS to QoE，MPNQ2)映射算法。根据所得数据集构建基于随机森林的QoE预测模型，利用评价指标验证算法的可行性，并对QoE进行预测。

1 系统模型

把底层网络看成一个无向图$ {G}^{S}=({N}^{S}, {L}^{S}) $。其中：$ {N}^{S} $为底层节点集合，每个节点均可部署一个或多个VNF；$ {L}^{S} $是所有底层链路的集合。将SFC看成一个有向图$ {G}^{V}=({N}^{V}, {L}^{V}) $。其中：$ {N}^{V} $为所有VNF的集合；$ {L}^{V} $为连接VNF的所有虚拟链路的集合。服务功能链的集合表示为$ S=\left\{{S}_{p}|p=\mathrm{1, 2}, \cdots , K\right\} $，VNF节点的集合表示为$ V=\left\{{V}_{q}|\mathrm{1, 2}, \cdots , N\right\} $，其中VNF具有防火墙、深度检测包、加密、解密等网络功能。当每个VNF只能映射到一个底层节点上时，如式(1)所示，当SFC上的VNF需要部署在不同的底层节点上时，如式(2)所示：

$ \sum\limits_{i \in {N^S}} {x_i^u} = 1{\rm{,}}\forall u \in {N^v} $

(1)

$ \sum\limits_{u\in {N}^{v}}{x}_{i}^{u}\le 1\text{,}\forall i\in {N}^{S} $

(2)

其中：定义一个二进制决策变量$ {x}_{i}^{u}=\left\{\mathrm{0, 1}\right\} $，以指示虚拟节点i是否已映射到物理节点u。

当所有成功映射的虚拟链路的带宽资源小于底层物理链路的带宽资源时，如式(3)所示：

$ \sum\limits _{{l}_{uv}\in {L}^{V}}\left({A}_{ij}^{uv}+{A}_{ij}^{uv}\right){B}_{uv}^{V}\le {B}_{ij}^{S}, \forall {l}_{ij}\in {L}^{S} $

(3)

其中：定义一个二进制决策变量$ {A}_{ij}^{uv}=\left\{\mathrm{0, 1}\right\} $以指示虚拟链路$ {l}_{uv} $是否已映射到物理链路$ {l}_{ij} $；$ {B}_{uv}^{V} $表示连接相邻u，v 2个VNF的虚拟链路$ {l}_{uv} $带宽需求；$ {B}_{ij}^{S} $表示连接物理节点i和j的链路$ {l}_{ij} $的带宽。

当所有成功部署在底层节点的VNF其要求的CPU资源小于该物理节点的CPU资源限制时，如式(4)所示：

$ \sum\limits _{u\in {N}^{V}}{x}_{i}^{u}{C}_{u}^{V}\le {C}_{i}^{S}\text{，}\forall i\in {N}^{S} $

(4)

其中：$ {C}_{i}^{S} $表示每个底层节点$ i\in {N}^{S} $的节点CPU资源；$ {C}_{u}^{V} $表示每个VNF的CPU资源需求。

当每条虚拟链路必须映射到连续的底层链路上时，如式(5)所示：

$ \sum\limits _{i\in {N}^{S}}{A}_{ij}^{uv}-\sum\limits _{i\in {N}^{S}}{A}_{ji}^{uv}={x}_{n}^{u}-{x}_{n}^{v}\text{，}\forall n\in {N}^{S}, \forall {l}_{uv}\in {L}^{V} $

(5)

当每一条虚拟链路至少映射到一条或多条底层链路时，如式(6)所示：

$ \sum\limits _{{l}_{ij}\in {L}^{S}}\left({A}_{ij}^{uv}+{A}_{ji}^{uv}\right)\ge 1, \forall {l}_{uv}\in {L}^{V} $

(6)

图 1所示为服务功能链链路映射流程，其中SFC1、SFC2分别有4个、3个虚拟网络功能，SFC1的部署路径为(s1，1)→(1，3)→(3，2)→(2，4)→(4，t1)。SFC2的部署路径为(s2，2)→(2，5)→(5，4)→(4，t2)或(s1，2)→(2，5)→(5，6)→(6，4)→(4，t2)，其中物理节点6只负责转发但不消耗存储资源。

使用Openflow协议进行控制，通过对虚拟交换机下发控制转发的流表以控制交换设施的转发行为。对VNF而言，每一种VNF分别与Openvswitch相连并映射到相应的物理节点上。每个物理节点有2个虚拟接口，数据包从其中一个接口进入VNF，并从另一个接口离开^[18]。通过数据包在该网络拓扑中的传输将所采集的特征包括带宽、时延、吞吐量、抖动、丢包率作为QoE预测训练的输入，如表 1所示。平均意见评分(Mean Opinion Score，MOS)是目前使用最广泛的主观评价方法，主要分为5个等级，从1到5，分别代表很差、差、一般、好、很好，本文用其衡量用户的QoE。

2 基于层次分析法的QoS/QoE映射模型 2.1 QoS与QoE

QoE是对服务和应用满意程度的一个定性度量指标，其影响因素包括环境层面、用户层面、服务层面等^[19]。用户相关因素包括用户的感知和过去的经验。环境因素包括服务运行环境、自然环境等。从QoS到以服务为中心的网络管理，再从网络到以客户为中心的架构，是网络从4G网络到5G网络的一步转变。

通常QoS与QoE呈现非线性变化，因此，高质量的QoS可以导致高质量的QoE，但不能保证高质量的QoE，QoS与QoE的关系如图 2所示^[20]。当QoS扰动小于x₁时，QoE值较高，即用户的欣赏度不受影响；当QoS扰动位于x₁与x₂之间时，QoE随着QoS扰动的增加而减小；当QoS扰动大于x₂时，用户的感受受到很大影响，极有可能完全停止使用服务。

在OSI(Open System Interconnection)参考模型中，针对QoS不同解决方案已被提出。通常QoS为应用层和网络层。应用层包括为实现QoS请求而提供的服务，应用层的QoS与分辨率、颜色、音视频编解码器类型等相关。网络层由交换机和路由器等设备提供，一般包括时延、抖动、丢包率等QoS参数。研究面向终端用户的QoE与面向网络的QoS参数十分重要，且网络QoS参数可以用来测量和量化QoE，因此本文提出基于层次分析法的MPNQ2算法，实现易测可控的网络层QoS参数与QoE映射。

2.2 MPNQ2算法

2.1选取了时延、抖动、流量、吞吐量、带宽、丢包率作为QoE评价的主要指标。本文利用层次分析法将QoE建模如下：

$\begin{aligned} {\rm{QoE}} = & \sum\limits_{i = 1}^n {{W_i}} {C_i} = {W_D}D + {W_B}B + {W_{{T_r}}}{T_r} + {W_J}J + \\ & {W_P}P + {W_{{T_h}}}{T_h} \end{aligned} $

(7)

其中：$ {W}_{i} $表示对应网络变量的重要程度；$ {C}_{i} $代表对应的QoS参数；D表示时延；B表示带宽；T_r表示流量；J表示抖动；P表示丢包率；T_h表示吞吐率。

层次分析法分为以下步骤：

步骤1  建立层次结构模型。如图 3所示，第1层为总评分QoE，反映了用户的满意程度，第2层为网络层QoS层，第3层为各个QoS影响参数。

步骤2  构造判断矩阵，即采用一致矩阵法对QoS参数进行比较。判断比较的标度原则如表 2所示。

步骤3  从QoS参数中任意选取2个参数i和j，以$ {a}_{ij} $表示$ {C}_{i} $和$ {C}_{j} $对QoE的影响程度，则$ {C}_{j} $对$ {C}_{i} $的影响之比为$ 1/{a}_{ij} $，即$ {a}_{ji} $。所有比较结果均由矩阵$ \mathit{\boldsymbol{A}} = {({a_{ij}})_{6 \times 6}} $表示。使用一致性检验法检验矩阵A的合理性。一致性指标C_CI计算公式如式(8)所示：

$ {C}_{\mathrm{C}\mathrm{I}}=\frac{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}-1}{n-1} $

(8)

其中：$ {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}} $代表所判断矩阵的最大特征值；n是所判断矩阵的维数。

由于传统的非交互业务数据突发性大，丢包率成为了其关键影响因素，带宽和吞吐量的影响因素次之。该业务不需要明显的流量作为业务保障，传统的非交互业务对时延抖动和传播时延没有具体要求，时延抖动和传播时延对该业务的影响程度最小，几乎可以忽略不计。基于上述分析其判断矩阵如式(9)所示：

$ \begin{array}{cc}& \begin{array}{cccccc}D& B &  {T}_{\mathrm{r}}& J&   P& {T}_{h}\end{array}\\ \begin{array}{c}D\\ B\\ {T}_{r}\\ J\\ P\\ {T}_{h}\end{array}& \left[\begin{array}{cccccc}1& 1/7& 1/3& 1& 1/9& 1/5\\ 7& 1& 4& 5& 1/3& 3\\ 3& 1/4& 1& 1/3& 1/8& 1/4\\ 1& 1/5& 3& 1& 1/6& 1/2\\ 9& 3& 8& 6& 1& 5\\ 5& 1/3& 4& 2& 1/5& 1\end{array}\right]\end{array} $

(9)

一致性指标R_RI如表 3所示，判断矩阵维度为6，通过查表可知R_RI=1.24。

步骤4  计算一致性比例C_CR，最后裁剪生成决策树。C_CR的计算公式如式(10)所示：

$ {C}_{\mathrm{C}\mathrm{R}}=\frac{{C}_{\mathrm{C}\mathrm{I}}}{{R}_{\mathrm{R}\mathrm{I}}} $

(10)

其中：只有当C_CR小于0.1时，认为判断矩阵的一致性可以接受，否则需要对判断矩阵进行适当的修改^[21]。根据式(10)计算可得C_CR=0.03，因此该判断矩阵通过了一致性检查，其对应于最大特征值$ {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}} $的判断矩阵A的特征向量$ \mathit{\boldsymbol{W}}=({W}_{1}, {W}_{2}, {W}_{3}, {W}_{4}, {W}_{5}, {W}_{6}) $，并将特征向量$ \mathit{\boldsymbol{W}}$归一化：

$ {\mathit{\boldsymbol{W}}_i} = \frac{{{\mathit{\boldsymbol{W}}_i}}}{{\sum\limits_{i = 1}^6 {{\mathit{\boldsymbol{W}}_i}} }}$

(11)

按照上述步骤计算得到时延、带宽、流量、抖动、丢包、吞吐量对QoE的影响权重值分别为0.035、0.249、0.049、0.066、0.472、0.129，则最终QoS到QoE的映射表达为：

$ \begin{aligned}\mathrm{Q}\mathrm{o}\mathrm{E}= & \sum\limits _{i=1}^{6}\mathit{\boldsymbol{W}}_{i}{C}_{i}=0.035D+0.249B+0.049{T}_{\mathrm{r}}+\\ & 0.066J+0.472P+0.129{T}_{\mathrm{h}}\end{aligned} $

(12)

3 基于随机森林的QoE预测模型

随机森林是一种基于Bagging集成学习的混合学习方法，用于回归和分类。其实质是将bootstrap方法应用于分类回归树算法中，采用bootstrap方法对随机森林进行采样，并使用CART算法构建独立的决策树模型，将所有决策树组合成随机森林。该方法具有精度高、鲁棒性强、应用范围广等优点，本文选用随机森林进行QoE的预测。

随机森林算法的过程分为决策树的生长和投票过程2个主要步骤，其中生长过程分为3个方面：训练集的随机选择，随机森林的构建和分裂节点。构建过程如图 4所示。

3.1 训练集的选择

基于MPNQ2算法得到的原始样本集中共有5 000个样本及6个特征，将原始样本集按照7∶3的比例分割成训练集和测试集。通过Bootstrap方法连续独立地从原始样本中随机抽取3 500个样本作为训练集。由于采样过程使用了随机替换方法，因此抽取的所有样本在一定程度上都包含重复样本。但由于抽取的样本并不包含所有样本，因此避免了输入所有样本进入模型时而导致的过度拟合。

3.2 分类回归树

分类回归树(Classification and Regression Tree，CART)算法的基本思想是选择基尼系数最小的特征作为分割属性^[22]。根据节点的剖分属性，使用二进制递归分割技术将当前样本集分为2个子样本集，以递归形式形成一个简单的二叉树。Gini系数的计算公式如式(13)所示：

$ \mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\left(F\right)=1-\sum\limits _{i=1}^{n}{p}_{i}^{2} $

(13)

其中：F代表样本集；$ {P}_{i} $表示样本集F包含第i类的概率，$ i\in \left\{\mathrm{1, 2}, \mathrm{3, 4}, 5\right\} $。

计算分裂节点的系数公式如下：

$ \mathrm{G}\mathrm{i}\mathrm{n}{\mathrm{i}}_{\mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}}\left(F\right)=\left|\frac{{F}_{1}}{F}\right|\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\left({F}_{1}\right)+\left|\frac{{F}_{2}}{F}\right|\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\left({F}_{2}\right) $

(14)

其中：$ \left|F\right| $是样本集F的样本数；$ \left|{F}_{1}\right| $、$ \left|{F}_{2}\right| $分别代表子集$ {F}_{1} $和$ {F}_{2} $的样本数。

3.3 投票过程

随机森林采用Bagging方法生成多个决策树分类器。本文给定一个弱学习算法和一个训练数据集T，进行多次随机抽样替换。每次采样时从原始训练集T中抽取n个样本以形成训练数据集的一个子集，训练的每个子集将得到一个决策树分类器^[23]。将每个决策树分类器的结果作为一次投票，通过投票计数选择最终样本分类预测结果。

4 仿真与性能分析 4.1 评价指标

评估的目的是验证所获得的模型能否满足学习过程中的目标及帮助决定所研究模型的部署^[24]。模型预测结果的混合矩阵如表 4所示，其中：T_TP表示实际为正，预测为正；F_FP表示实际为正，但预测为负；T_TN意味着实际为负，预测为负；F_FN意味着实际为正，但预测为负。

分别采用准确率、查准率、召回率、F1分数对结果进行表征。

1) 准确率，如式(15)所示：

$ {A}_{\mathrm{A}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}=\frac{{T}_{\mathrm{T}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}+{F}_{\mathrm{F}\mathrm{N}}} $

(15)

准确率反映了对输入样本做出正确预测的数量和总样本数的比值。一般来说，准确率越高，分类器越好。

2) 查准率，如式(16)所示：

$ {P}_{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}}=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{P}}} $

(16)

查准率指预测的正比例数与预测为正例总量之比。

3) 召回率，如式(17)所示：

$ {R}_{\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{N}}} $

(17)

召回率又称查全率，反映预测对的正比例数占真正的正例数的比率。召回率是覆盖面的度量，召回率越高，覆盖范围越广。

4) F1分数，如式(18)所示：

$ \mathrm{F}1=\frac{2{R}_{\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}\times {P}_{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}}}{{R}_{\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}+{P}_{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}}} $

(18)

其中：F1分数是精确度和召回率加权调和平均，当F1较高时，实验方法更有效。

4.2 实验结果分析

表 5所示为在同一数据集下不同预测模型的评价结果。由表 5可知，逻辑回归的模型最差，线性分类分析和决策树的模型次之。梯度提升决策树、随机森林、支持向量机的结果非常相似，且均高于80%，但随机森林的各个评价指标都略高于其他2个。这是由于随机森林能对训练集和特征集随机进行选择，且对于缺省值问题也能取得很好的结果。此外，其抗过拟合能力和泛化能力比较强，预测精度较高，具有较好的鲁棒性和容错性。因此，随机森林对于QoE预测而言是较佳的算法。

如图 5所示，通过评估分类器的准确性表明随机森林对服务功能链中QoE进行分类和预测具备可行性。

图 6为使用随机森林法对影响服务功能链部署的变量重要性进行评估的结果，从图中可以看出，随机森林与层次分析法中的特征重要性排序相同，但是随机森林是在大量随机抽取的样本数据集中进行不同的特征选择训练得出，其准确率高于层次分析法。其中，丢包率影响最明显，达到了62%。带宽、吞吐量次之，分别为23%和10%，抖动、时延、流量最小，几乎可以忽略不计。

图 7所示为对预测目标MOS评分的随机森林模型。该模型的测试和验证遵循10倍交叉验证标准，以减小潜在的过度拟合和有偏差结论的影响，提高结果的可靠性。从图中可以看出丢包率对用户体验质量有更直接的影响，当丢包率大于4.4%时，不论其他参数如何变，MOS为1，用户体验质量达到最差。当丢包率越小，带宽和吞吐量越大时，MOS达到了5，用户满意度达到最大。但是流量的减小在一定程度上会造成用户体验质量的下降，例如当带宽大于156.5 Mb/s、丢包率小于0.4%时。MOS为5；丢包率大于0.4%时，MOS为4.5，但是当流量大于48.2 MB时，MOS有所下降。时延和抖动对用户满意度的影响很小，几乎可忽略不计。

5 结束语

本文针对服务功能链中的QoE评估和预测问题，提出一种基于机器学习的服务功能链部署模型。通过SDN/NFV的服务功能链部署模型收集影响服务功能链部署的网络QoS参数，采用层次分析法建立3层结构模型，利用MPNQ2算法计算每个参数的影响权重，实现QoS与QoE的映射。此外，提出一种基于随机森林的QoE预测模型以提高预测结果的准确性。实验结果表明，与梯度提升决策树、线性判别分析等机器学习算法相比，随机森林具有较高的准确性。下一步将考虑更多影响服务功能链部署的参数，如设备性能、内容类型等，以便不断获取用户反馈，从而对用户感知进行实时、准确的描述。