A Reliability-aware 5G Network Slice Reconfiguration and Embedding Algorithm

1.   引言

网络切片(Network Slice, NS)是5G理想的网路架构^[1]，本质是共享底层基础设施但逻辑上完全隔离的专有网络，根据业务请求按需动态组合网络功能^[2]。网络切片映射(Network Slice Embedding, NSE)是网络切片生成的一个关键步骤^[3]，其目的是在底层物理网络中找到满足映射约束的节点和路径，实现虚拟网络功能(Virtual Network Function, VNF)的部署和互通^[4]。业界普遍认可NSE是虚拟网络映射(Virtual Network Embedding, VNE)的扩展，为非确定性多项式困难(Non-deterministic Polynomial hard, NP-hard)问题，解决方案主要依赖于启发式算法。文献[5]详述了现存NSE算法，主要针对理想网络状态下提高NSE成功率和优化链路资源利用率^[6,7]。

NS比单层网络更需要可靠映射策略来满足用户的可靠性需求。针对轻量级可靠映射，文献[8]在无需备份资源的情况下最大化虚拟网络的可靠性。文献[9,10]利用备份方式提高网络可靠性。文献[11,12]提出了成本有效的可靠映射算法和虚拟网络“过可靠性”的概念。文献[13]首次利用可靠性分配(Reliability Allocation, RA)的方法保证每个VNF的可靠性要求，但没有提出基于RA的NSE方案。综上所述，传统NSE在保证NS高可靠时忽略了资源利用率，导致较高的映射成本，同时没有考虑到VNF有不同可靠性需求的网络特性。

2.   系统模型与问题描述

2.1   系统模型

5G网络切片集中映射架构如图1所示，端到端NS将终端设备、接入网资源、核心网资源及管理系统等进行有机组合。虚拟网络运营商(Virtual Network Operation, VNO)依据获取的网络信息，利用映射算法实例化NS，建立逻辑独立、相互隔离的完整网络。

图  1  5G网络切片场景

下载: 全尺寸图片 幻灯片

2.2   物理网络

底层物理网络为带权无向图${G_{\rm{s}}} = \left( {{N_{\rm{s}}},{L_{\rm{s}}}} \right)$，其中${N_{\rm{s}}} = \left\{ {1, 2, ···,n,···M} \right\}$为物理节点集。$C_n$和${R_n}$表示物理节点$n$的计算资源和可靠性，$C_n^{\rm{r}}$表示节点$n$剩余的可用资源。${L_{\rm{s}}} = \left\{ {{l_{mn}}\left| {n,m \in {N_{\rm{s}}}} \right.} \right\}$表示物理链路集，${l_{nm}}$表示物理节点$n,m$之间的直接链路，$b_{nm}$和$b_{nm}^{\rm{r}}$分别表示通信链路${l_{nm}}$分配的带宽资源和剩余可用带宽。

2.3   网络切片请求

NS请求(NS Request, NSR)${\rm{g}}$由$G_v^{\rm{g}} = (V_{\rm{g}},E_{\rm{g}},$$R_{{\rm{req}}}^{\rm{g}})$表示，其中${V_{\rm{g}}} = \{ v_1,v_2, ···,v_{{K_{\rm{g}}}}\}$为切片${\rm{g}}$所经过的VNF节点序列，${K_{\rm{g}}}$为切片${\rm{g}}$中VNF节点数量。$E_{\rm{g}} =$$\{ {e_k}|{v_k},{v_{k + 1}} \in {N_{\rm{g}}}\}$为虚拟链路集，$e_k = \left( {v_k,v_{k + 1}} \right)$为切片${\rm{g}}$第$k$条虚拟链路，$b_{{e_k}}^{\rm{g}} = b\left( {v_k,v_{k + 1}} \right)$切片${\rm{g}}$中VNF节点$v_k$与$v_{k + 1}$间的带宽需求。$C_k^{\rm{g}}$表示节点${v_k} \in N_v^{\rm{g}}$的计算资源需求，$R_{{\rm{req}}}^{\rm{g}}$表示NSR的整体可靠性需求，${C_{\rm{g}}}$和${b_{\rm{g}}}$为NSR${\rm{g}}$的计算和带宽资源消耗。

${P^{\rm{g}}} = \left[ {P\left( {{V_{\rm{g}}}} \right),P\left( {{E_{\rm{g}}}} \right)} \right]$表示$G_v^{\rm{g}}$映射方案。$P\left( {{V_{\rm{g}}}} \right) =$$\left\{ {P^{\rm{g}}\left( {{v_k}} \right)|\forall {v_k} \in {V_{\rm{g}}}} \right\}$表示VNF功能节点的部署方案，$P\left( {{E_{\rm{g}}}} \right) = \left\{ {P^{\rm{g}} \left( {{e_k}} \right)|\forall {e_k} \in {E_{\rm{g}}}} \right\}$为切片${\rm{g}}$虚拟链路的映射方案。

2.4   可靠映射效用函数

本文利用有效度作为物理设备的可靠性度量指标^[14]，由服务器平均修复时间(Mean Time To Repair, MTTR)和平均故障间隔时间(Mean Time Between Failures, MTBF)来衡量。

NSR的不同VNF分别映射到不同的物理节点，VNF的可靠性由其所映射的物理服务器来保证。通过计算${P^{\rm{g}}}$中VNF部署涉及的每个物理节点可靠性的乘积来估计NS的总可靠性。

为了保证网络切片的可靠性，网络切片可靠映射必须满足

VNO通过向基础设施提供商租赁资源创建NS为用户提供服务。VNO的收益${I_{{\rm{VNO}}}}$定义为提供服务获得的收入${H_{\rm{g}}}$与NSE成本${T_{\rm{g}}}$的差值。${T_{\rm{g}}}$和${H_{\rm{g}}}$由实例化该NS的资源量和提供资源的物理服务器可靠性共同决定，从VNO角度出发网络切片可靠映射效用函数可以定义为

其中，${k_1},\,{k_2},\,{k_3}$为常系数可调整。可靠映射模型可初步建立为式(5)，即在满足NS可靠性需求的前提下，最大化网络切片可靠映射效用函数

3.   网络切片可靠映射模型

NSR由一组VNF通过网络互连形成逻辑服务，本节根据VNF重要度指标，计算VNF可靠性需求，为其提供不同的可靠性保证。当NSR整体可靠性需求$R_{{\rm{req}}}^{\rm{g}}$给定时，获得VNF可靠性需求，可以采用RA的方法^[15]。定义VNF的3个重要度指标分别为：VNF${v_i}$计算资源需求${S_i} = C_i^{\rm{g}}$; VNF带宽资源需求，定义为与VNF${v_i}$相连的所有邻接链路的带宽资源之和 ${D_i} = \displaystyle\sum\nolimits_{{e_i},{e_{i + 1}} \in {E_{\rm{g}}}} {\left( {b_{{e_i}}^{\rm{g}} + b_{{e_{i + 1}}}^{\rm{g}}} \right)}$; VNF度中心性，从VNF位置的角度反映其重要性，定义为${M_i} = {1 \bigr/ {\displaystyle\sum\nolimits_{{v_j} \in {V_{\rm{g}}}} {{d_{ij}}} }}$。其中，${d_{ij}}$表示VNF${v_i}$与${v_j}$之间的跳数距离。VNF中心度越大，表示VNF在网络切片中处于中间位置越重要。基于3个重要度指标，${v_i}$的归一化权重指标为

根据RA的组件可靠性计算公式可得

其中，$R_i^{\rm{g}},i \in \left[ {1,2, ···,n} \right]$为${v_i}$的可靠性需求，且NS整体可靠性$R_{{\rm{req}}}^{\rm{g}}$与各个VNF的可靠性要求满足式(8)

为保证网络切片可靠性的前提下，最大化VNF部署收益同时最小化带宽资源开销，降低映射成本，基于式(5)网络切片可靠映射建模为式(9)整数规划问题。根据VNF可靠性权重指标，通过满足VNF的可靠性需求保证NS整体可靠性。其中，${\rm{C}}1$为二进制变量约束，当VNF节点${v_i}$映射到物理节点$n$时${x_{{v_i},n}}$为1，否则为0；如果NSR的虚拟链路${e_i}$映射到物理链路${l_{nm}}$则${y_{{e_i},{l_{nm}}}}$为1，否则为0。${\rm{C}}2$表示属于同一NS的VNF节点不能映射到同一物理节点上。${\rm{C}}3$表示物理节点的可靠性${R_n}$概率值不大于1。${\rm{C}}4$表示每个VNF都有不同的可靠性需求，在映射过程中要求单个VNF达到可靠性要求。${\rm{C}}5$在无备份保护物理网络中，NS实际实现的整体可靠性至少要满足NS整体可靠性要求。${\rm{C}}6$表示部署到同一物理节点的各个NS中所有VNF节点所需求的计算资源总和小于等于该物理节点的计算资源容量。${\rm{C}}7$表示部署VNF节点的剩余计算资源必须大于节点所需的计算资源。${\rm{C}}8$表示部署到同一物理链路的各个NS所有链路所需求的带宽资源总和小于等于该物理链路的链路资源容量。${\rm{C}}9$表示映射的物理链路剩余带宽资源必须大于虚拟链路所需带宽资源。为解决上述问题，将NSR分为3类：$C_i^{\rm{g}} > {C_n},\forall n \in {N_{\rm{s}}},v_i^{\rm{g}} \in {V_{\rm{g}}}$, ${C_n} \ge C_i^{\rm{g}}$ & ${R_n} \ge R_i^{\rm{g}},n \in {N_{\rm{s}}},v_i^{\rm{g}} \in {V_{\rm{g}}}$和${C_n} > C_i^{\rm{g}}$ & $R_i^{\rm{g}} > {R_n},\forall n \in {N_{\rm{s}}},v_i^{\rm{g}} \in {V_{\rm{g}}}$，本文提出了面向可靠性的网络切片重构及映射策略(Reliability-aware Network Slice Reconfiguration and Embedding algorithm, RNSRE)。

4.   可靠性感知的网络切片重构及映射策略

4.1   基于邻域搜索的网络切片映射算法

针对第2类NSR，提出基于邻域搜索的网络切片映射算法。$P_{{\rm{init}}}^{\rm{g}}$利用贪婪准则搜索当前最可靠的节点和利用Dijkstra算法寻找最短路径获得。${P^{\rm{g}}}$的物理节点集从${P_i}$节点集的邻域解中获得，邻域解为满足资源限制未被占用的可靠性次高节点集，根据部署阶段获得的节点集$P^{\rm{g}}\left( {{v_k}} \right),\forall {v_k} \in {V_{\rm{g}}}$找出最短路径，最小化带宽资源消耗${b_{\rm{g}}}$。${P_i}$为满足计算资源和可靠性约束的物理节点集，即VNF节点映射备选集，利用贪婪准则在备选集内选择可靠性与$R_i^{\rm{g}}$最接近的节点${r_{{\rm{min}}}}$

通过不断搜索当前解${P_i}$的邻域集，根据优化目标获得更优的可行解${P^{\rm{g}}}$，不断逼近目标解$P_{{\rm{opt}}}^{\rm{g}}$。其中，邻域搜索空间为$S \!=\! \left\{ {n,n \in {N_{\rm{s}}}\left| {C_i^{\rm{g}} \!>\! {C_n}{\rm{\& }}R_i^{\rm{g}} \!>\! {R_n}} \right.} \right\}$。其次，为了提高资源利用率定义优化目标的更新函数如式(11)，其指明算法搜索的方向。当可行解变化时映射方案被改变，当前解的邻域集能够作为可行解的条件是其对应的更新函数${\rm{Obj}}\left( {{P^{\rm{g}}}} \right)$优于当前解获得的更新函数值，通过不断地搜索获得优化方案。

考虑到可靠性差值与带宽之间的数量级，以及两目标的优先级，进一步完善优化目标如式(12)，其中${B_{{\rm{total}}}}$为当前网络的总带宽，其值远远大于当前NSE的带宽资源${b_{\rm{g}}}$。

最终，邻域搜索的终止条件为实际可靠性差值与带宽差值，避免大数效应，两者均归一化。

上述网络切片映射过程总结在表1算法中。

表  1  基于邻域搜索的网络切片映射算法

输入：NSR $G_v^{\rm{g}} = (V_{\rm{g}},E_{\rm{g}},R_{{\rm{req}}}^{\rm{g}})$，物理网络${G_{\rm{s}}} = \left( {{N_{\rm{s}}},{L_{\rm{s}}}} \right)$	(5)　　　　${P_i} = P_{{\rm{next}}}^{\rm{g}}$, ${R_{{\rm{gap}}}} = \displaystyle\prod\limits_{{n_i} \in P_{{\rm{next}}}^{\rm{g}}} {{R_i}} - R_{{\rm{req}}}^{\rm{g}}$
输出：NSE方案${P^{\rm{g}}} = \left[ {P^{\rm{g}}\left( {{v_k}} \right),P^{\rm{g}}\left( {{e_k}} \right)} \right]$	(6)　　　　计算当前的带宽消耗为${b_{\rm{g}}}$
(1) 搜索空间$S$, $P_{{\rm{opt}}}^{\rm{g}} = {P_{{\rm{init}}}}$; ${P_i} = P_{{\rm{init}}}^{\rm{g}}$	(7)　　　end if
(2) while($0.5 \le { { {R_{ {\rm{gap} } } }} / { {R_{ {\rm{req} } } } } } + { {\left( { {b^{\rm{g} } } - b_{ {\rm{req} } }^{\rm{g} } } \right)} / {b_{ {\rm{req} } }^{\rm{g} } } } \le 1$), do	(8)　　　if $\left( {{\rm Obj}\left( {P_{ {\rm{next} } }^{\rm{g} } } \right) < {\rm Obj}\left( {P_{ {\rm{opt} } }^{\rm{g} } } \right)} \right)$ then
(3)　　　在${P_i}$的邻域解中搜索当前更优的个体$P_{{\rm{next}}}^{\rm{g}}$	(9)　　　　$P_{{\rm{opt}}}^{\rm{g}} = P_{{\rm{next}}}^{\rm{g}}$
(4)　　　if $\displaystyle\prod\limits_{ {n_i} \in P_{ {\rm{next} } }^{\rm{g} } } { {R_i} } \ge R_{ {\rm{req} } }^{\rm{g} }$ then	(10)　　　end if
	(11)　end while

下载: 导出CSV 

| 显示表格

4.2   关键VNF备份的网络切片重构映射算法

对于第3类NSR，为提高映射成功率，设计了一种可靠性感知的网络切片重构映射算法。备份后VNF的可靠性发生变化，假设备份后VNF$v_i^{\rm{g}}$可靠性增量为${\varDelta _i}$。由式(2)可知NS的可靠性为当前VNF可靠性的乘积，则备份模式下NS可靠性为

在实际的网络场景中，由于存在多个VNF共享底层物理节点，每个VNF可靠性增量${\varDelta _i}$很难得到。为计算NS的可靠性，针对不同的备份方式提出不同的估算模型，备份方式主要分为专有备份和共享备份。

专有备份，只要同种类型的VNF有一个可靠则NS整体可靠，估算模型为

其中，$S_i^{\rm{g}}$为NSR${\rm{g}}$的第$i$个VNF的备份物理节点集，$R\left( {G_{{\rm{backup}}}^{\rm{g}}} \right)$为备份后网络切片的可靠性。

共享备份，以所选的VNF为边界将NS划分为$K_{\rm{g}}'$个串联的子拓扑结构$G_{{\rm{sys}}}^{\rm{g}}$，子拓扑的可靠性为$R\left( {G_{{\rm{sys}}}^{\rm{g}}} \right)$，整个网络切片的可靠性为所有子拓扑可靠性的乘积

为计算$R\left( {G_{{\rm{sys}}}^{\rm{g}}} \right)$根据所选择的两个VNF是否已经备份，参考文献[16]分为4种模型，(1)所选择的两个VNF ${v_i}$与${v_j}$均没有备份；(2)所选择的两个VNF中${v_j}$具有备份节点${b'}$；(3)所选${v_i}$与${v_j}$分别存在于两个子拓扑$G_W^{\rm{g}}$和$G_N^{\rm{g}}$中；(4)所选${v_i}$与${v_j}$在同一拓扑$G_N^{\rm{g}}$中。

备份后NS可靠性的增量定义为

为了求解上述问题，本文引入概率重要度的概念^[17]，其可以有效地反映当前VNF可靠性变化对NS整体可靠性的影响。VNF $v_i^{\rm{g}}$的概率重要度定义为

进一步可得VNF备份单位开销，即提高单位可靠性的资源消耗

根据VNF概率重要度和备份单位开销定义VNF备份重要度指标，获得VNF备份顺序

在共享备份中，每次选择两个VNF ${v_i}$与${v_j}$进行备份，此时VNF对的重要度可定义为

若每个VNF备份都计算$\varDelta$，计算繁琐。为简化计算，从NS整体角度出发，定义NS可靠性提高率为

基于文献[16]的共享备份模式(2)可得

其中，${R_1}{R_2}···{R_k}$和${R_p}···{R_q}$是未被选中的子网可靠性，被选中的两个VNF${v_i}$与${v_j}$，备份前的可靠性${R_i}$和${R_j}$，当为其提供备份节点$b$时，NS可靠性提高率为

为了获得可靠性增量$\varDelta$与所选择VNF的关系，分别求$u$关于${R_i}$与${R_j}$的偏导

定义$A = \left( {1 - {R_j}} \right)\displaystyle\prod\nolimits_{k = 1}^M {\left( {1 - {R_{{k_j}}}} \right)}$，可得

基于以上分析，为了获得映射方案$P_{\rm{g}}^*$，提出了如表2所示的网络切片重构算法，将未满足可靠性需求NSR中的VNF分为两类：必须备份节点与可选备份节点。

表  2  关键VNF备份网络切片重构算法

输入：NSR $G_v^{\rm{g}} = (V_{\rm{g}},E_{\rm{g}})$，备份节点集${V_{{\rm{reconf}}}}$ 输出：${P^{\rm{g}}} = \left[ {P_{}^{\rm{g}}\left( {{v_k}} \right),P_{}^{\rm{g}}\left( {{e_k}} \right)} \right]$ (1) for each $v_i^{\rm{g}} \in {V_{{\rm{reconf}}}}$ (2)　专有备份节点$v_i^b$, $C_k^b = C_i^{\rm{g}}$， (3)　备份链路 (4)　基于式(23)得到$R\left( {G_{{\rm{backup}}}^{\rm{g}}} \right)$ (5) end for (6) while($R\left( {G_{ {\rm{backup} } }^{\rm{g} } } \right) \le R_{ {\rm{req} } }^{\rm{g} }$), do (7)　　for all $v_k^{\rm{g}} \in {V_{\rm{g}}}$, do (8)　　　按照VNF可靠性递增，对节点进行排序

(9)　　　选择相邻VNF对提供共享备份节点$v_i^b$, $C_k^b = \max \left\{ {C_i^{\rm g} ,C_j^{\rm{g}}} \right\}$ (10)　　　选择关键VNF对$v_i^{\rm{g}},v_j^{\rm{g}} = {\rm{arg}}\;{\rm{max}}\left\{ {{\theta _{ij}}|v_i^{\rm{g}},v_j^{\rm{g}} \in {V_{\rm{g}}}} \right\}$ (11)　　　根据$v_i^{\rm{g}},v_j^{\rm{g}} \in {V_{\rm{g}}}$的状态，选择共享备份可靠性估算模型得到 　　　　 $R\left( {G_{{\rm{backup}}}^{\rm{g}}} \right)$ (12)　　end for (13)　　　链路备份 (14) end while (15) return

下载: 导出CSV 

| 显示表格

5.   性能仿真与结果分析

5.1   仿真场景设置

为了验证本文提出的RNSRE的有效性，利用MATLAB仿真实验平台模拟物理网络和NSR，参考文献[7]具体仿真参数设置如表3所示。

表  3  仿真参数设置表

仿真参数	参数设置		仿真参数	参数设置
物理节点的数目	N=12, 25, 36		物理节点CPU资源容量	U[10, 20]
物理节点可靠性分布	U[0.95, 0.99]		物理链路带宽资源容量	U[20, 50]
NSR的VNF个数	3		NSR生命周期	[4, 12, 24]
3种类型切片的可靠性需求	U[0.90, 0.98]		VNF节点CPU资源需求	U[2, 6]
VNF之间带宽资源需求	U[8, 16]

下载: 导出CSV 

| 显示表格

同时为了更好地比较和评估RNSRE算法的性能，将其与其他3种基本的可靠映射策略做对比。(1)改进文献[7]中NSR节点排序算法为基于贪婪机制的网络切片可靠映射算法 (Reliable Network Slice Embedding algorithm based on Greedy, RNSEG)。(2)基于可靠性分配的两阶段网络切片映射算法 (two-stages Network Slice Embedding algorithm based on RA, NSERA); (3)基于禁忌搜索的网络切片可靠映射算法(reliable Network Slice Embedding algorithm based on Tabu Search, NSETS)。

5.2   仿真结果分析

图2显示了不同的NSR数目下，所提算法RNSRE与3种算法在映射成本方面的比较。由于RNSEG每次都选择当下最可靠的映射方式，所以映射成本最高。NSERA选择映射成本最低的节点映射，但是节点映射与链路映射分为两阶段，导致较高的带宽资源消耗。所提算法RNSRE与NSETS同时考虑节点映射成本与链路带宽资源，避免了以高昂的成本满足低可靠性需求，从而降低了映射成本。

图  2  不同算法平均成本比较

下载: 全尺寸图片 幻灯片

图3(a)、图3(b)分别显示了所提算法与3种算法平均物理节点、链路资源利用率累积分布函数(Cumulative Distribution Function, CDF)。仿真结果表明RNSRE最多可以利用80%节点资源，NSETS, NSERA和RNSEG分别最多可以利用70%, 55%和60%的节点资源。RNSRE算法一方面在映射过程中综合考虑可靠性与物理资源利用，从而增加节点资源利用率；另一方面，通过备份降低VNF对单个物理节点可靠性的需求，进而提高物理节点资源利用率。NSERA和RNSEG最多可利用50%的链路资源。NSETS在映射过程中综合考虑可靠性与链路资源利用率，最多可利用75%的链路资源。RNSRE提高了NSR映射成功率，所以具有更高的平均物理链路资源利用率。

图  3  所提算法与3种算法的平均物理节点、链路资源利用率累计分布函数

下载: 全尺寸图片 幻灯片

NSR接受率，定义为成功映射的NSR数量占所到达的NSR总数目。如图4所示，本文所提算法RNSRE的平均接受率优于其他3种算法。NSERA在物理资源充足的条件下，单个物理节点的可靠性无法满足每个VNF的高可靠性要求，所以NSR平均接受率最低。RNSEG采用贪心策略选择最可靠节点保证NSR的可靠性，没有考虑当前映射方案对后续NSR的映射。NSETS在映射过程中联合优化节点和链路资源提高接受率。RNSRE同时考虑可靠性与链路带宽资源分配，避免出现瓶颈节点，通过VNF备份保证NSR的高可靠性需求，所以NSR接受率最高。

图  4  不同算法NSR平均接受率比较

下载: 全尺寸图片 幻灯片

图5显示了不同映射算法下，NSR的可靠性。在NSE过程中，RNSEG算法以可靠性最大化为主要目标映射NSR，所以在整体可靠性性能方面产生优于NSETS和NSERA。但是，后面两种算法，综合考虑了用户可靠性与切片映射成本，避免追求高可靠性导致的资源浪费。RNSRE算法在保证网络切片可靠性的同时降低映射成本，通过VNF备份满足网络切片的高可靠需求，所以，在4种算法中具有最好的可靠性性能。

图  5  不同算法到达的可靠性比较

下载: 全尺寸图片 幻灯片

6.   结束语

传统NSE在保证切片高可靠性需求时忽略了资源开销导致资源利用率低，同时忽略了VNF的不同可靠性需求导致切片可靠性差。为了在保证VNF可靠性需求的前提下，提高资源利用率，本文对网络切片可靠映射进行研究。首先，建立网络可靠映射效用函数，将VNF部署的收益与底层节点可靠性和自身可靠性需求相关联，其次，设定重要度评价指标获得VNF可靠性需求，以最大化VNF可靠部署收益的同时最小化链路开销为目标，建立网络切片可靠映射整数线性规划模型。最后设计了面向可靠性的网络切片重构及映射策略对其进行求解。