基于业务类型的网络切片可靠性映射算法

赵季红，乔琳琳，曲 桦，张文娟

（1.西安邮电大学通信与信息工程学院，西安710121；2.西安交通大学电子信息工程学院，西安710049）

0 概述

网络切片（Network Slicing，NS）是5G 网络中的关键架构技术［1］。软件定义网络（Software Defined Network，SDN）和网络功能虚拟化（Network Function Virtualization，NFV）使网络切片能够以经济高效的方式满足5G 业务多样性的需求［2-4］，但与此同时也存在一些问题［5］，其中关键问题之一是如何确保网络切片对底层网络软件和硬件故障的恢复能力。在网络运行过程中，当底层网络发生故障时，保障网络切片上的多样性业务正常运行是非常必要的，然而现阶段SDN/NFV 网络切片中的弹性和可靠性问题尚未得到较好解决［6］。

目前，关于网络切片可靠性问题的研究较少。文献［7］考虑到每个切片的流量需求是随机的并且流量的剧烈变化可能会导致切片重新配置，从重映射恢复切片和重新配置切片两个角度设计切片的弹性机制。本文从底层链路故障出发，基于可生存性虚拟网络映射（Survivable Virtual Network Embedding，SVNE）［8］来解决网络切片可靠性问题。网络虚拟环境中对链路故障的研究主要分为恢复策略和保护策略［9］。恢复策略不预备任何备份资源，在链路故障时重映射故障链路，在底层资源有限的情况下，并不能保证恢复所有的故障链路［10］。保护机制又可分为专用保护［11］和共享保护［12］。文献［13］针对链路故障，为每条链路采用1∶1 保护方法，尽管使虚拟网的生存性得到了保障，但这样的备份方法在网络正常工作时浪费了大量的底层资源。文献［14-15］在为链路备份资源时虽然引入了资源共享机制，快速了恢复故障，但是资源消耗依然很大。文献［16］将网络编码和p 圈保护相结合，对核心链路提供1+N 保护。该方法虽然能够提高底层资源利用率并且保证虚拟网的可靠性，但过程相对复杂。以上解决链路故障问题的方法大都在共享保护策略上加以改进，并未对业务类型进行分类。

单一的应对故障的方法不能有效处理网络切片业务类型多需求的问题。在实际网络环境下，当一条物理链路发生故障时，引起失效的多个切片可能承载不同的业务类型。在承载自动驾驶、远程控制、远程医疗手术等对时延和可靠性极其敏感的业务时，发生故障应立即处理；而在承载高清视频等高带宽通信业务时，则可给予此类故障一定的恢复时延。因此，当链路发生故障时，应先判断失效切片的类型，再选取适当的方法应对故障。

本文提出一种区分业务类型的网络切片可靠性映射方法。针对单链路故障失效的切片请求，遵循区分业务原则对其进行划分。若故障链路承载高可靠性低时延业务类型，则将其直接迁移到备份链路，映射时对该切片请求中的最大生成树链路（Maximum Spanning Tree Link，MSTL）进行备份，在提供共享保护的同时减少备份资源消耗；若故障链路承载高带宽业务类型，则为其寻找满足约束条件的高可靠性链路进行重映射，以此来提高故障恢复率。

1 问题描述与系统模型

1.1 物理平面和网络切片请求

物理底层网络（Substrate Network，SN）定义为加权无向图GS=(NS,ES)。其中，NS为物理节点集合，ES为物理链路集合。每个节点ns∈NS的节点属性包括节点CPU 资源c(ns)和每个物理链路ls∈ES的带宽资源b(ls)。网络切片同样定义加权无向图GV=(NV,EV)。每个虚拟节点nv∈NV的节点CPU 资源需求用c(nv)表示，每个虚拟链路lv∈EV的带宽需求用b(lv)表示。

1.2 切片映射描述

本节针对网络切片可靠性问题构建一个混合整数规划模型，对约束条件和目标函数进行表述。

1.2.1 切片基本映射过程

分节点映射和链路映射两部分介绍切片的基本映射过程。

1）节点映射

本文主要关注链路映射，节点映射采取贪婪的算法［17］，这种算法与递归算法和元优化算法（例如模拟退火算法）相比既简单又高效。贪婪算法将节点映射到底层资源最充足的节点上，有利于映射成功。约束条件包括：

式（2）表示虚拟节点CPU 需求不得超过底层节点的CPU 资源，式（3）保证底层节点最多承载来自同一切片中的一个节点。

2）链路映射

将已完成映射的节点作为端点进行链路映射。底层网络的物理链路的带宽资源必须满足所承载虚拟链路的带宽需求，约束条件包括：

1.2.2 切片可靠性问题描述

网络切片可靠性映射本质上与可生存性虚拟网映射［7］类似，即在映射过程中加入故障恢复策略以确保底层网络故障时NS 能够快速恢复，并保证网络服务的连续性。图1 是切片请求映射示意图，下文分别描述2 种业务类型切片的可靠性问题。

图1 切片请求映射示例Fig.1 Example of slice request mapping

1）高可靠性低时延切片请求可靠性映射

对于这一类请求，在映射工作路径的同时，设计一种基于最大生成树链路的备份资源共享保护方法。如图1所示，将虚拟链路分为最大生成树（Maximum Spanning Tree，MST）链路（a，b）、（a，c）和非最大生成树（Non-Maximum Spanning Tree，NMST）链路（b，c）。虚拟链路映射方案为｛（a，b）→（B，C），（a，c）→（B，E），（b，c）→（C，E）｝，MST 链路备份保护方案为｛（a，b）→（B，A，C），（a，c）→（B，D，E）｝。NMST 链路通过与MST 链路共享备份资源获得间接保护：｛（b，c）→（C，A，B，D，E）｝。

在映射过程中，不仅要避免将MST 链路和NMST 链路映射到同一SN 路径，而且还要避免主要路径和备份路径重合，约束条件包括：

式（6）表示切片请求中MST 的虚拟链路lv映射至物理链路ls，式（7）表示切片请求中NMST 的虚拟链路lv'映射至物理链路ls'，式（8）表示同一切片请求中的MST 链路和NMST 链路不能映射至同一条物理链路。

2）高带宽切片请求可靠性映射

如果要恢复因底层链路故障而失效的高带宽切片请求，就需要为其重新分配资源。给定底层网络GS以及失效的这一类切片请求，对于图1 中的切片映射关系，若底层链路（D，F）发生故障，则将虚拟故障链路（d，e）重映射至底层链路（D，E，F）。

3）链路可靠性定义

将高带宽请求中故障链路映射在高可靠性底层链路能够提高恢复率。链路发生故障的次数以及可用资源都是影响底层链路可靠性的因素。链路可靠性与其发生故障次数以及所承载的虚拟链路成反比，与链路剩余资源成正比。借鉴文献［18］定义节点可靠性的思想，将链路可靠性定义如下：

其中：br(ls)表示物理链路ls剩余带宽资源；f(ls)表示物理链路ls的失效次数；m(ls)表示物理链路ls所承载虚拟链路的数量。

1.3 目标函数

由于要对部分切片请求采取备份，为提高物理资源利用率，用最少的物理资源接受更多的切片请求，以最大化底层剩余资源为映射目标。

其中：α和β分别表示节点资源和链路资源的价值转换权重；cr(ns)表示节点剩余资源；br(ls)表示链路剩余带宽资源。剩余资源越大表示有更多的可用资源去承载更多的切片请求。

1.4 问题复杂性分析

混合整数规划问题在本质上是一个NP-hard 问题，这使得在大规模网络环境中不能直接使用此模型来求解。为解决这个问题，本文提出一种基于上述数学模型快速恢复故障链路的启发式算法。

2 区分业务类型的网络切片故障恢复策略

本文根据不同的切片承载业务类型，提出对故障切片采取不同的故障恢复策略。该策略对高可靠低时延业务请求提供备份，对高带宽切片请求故障链路采取重映射，这样既能满足故障的快速修复，又能减少资源消耗。该策略包括区分失效切片请求以及完成高可靠性低时延切片备份链路构建。整个策略的算法描述如下：

算法1区分业务类型的链路故障恢复

2.1 业务类型区分

通过自适应分类算法将失效的网络切片请求划分为高可靠性低时延业务和高带宽业务2 种类型，根据带宽阈值BW对切片进行分类，具体过程如下：

子算法1区分网络切片请求

2.2 备份路径构建

本文考虑底层单链路失效问题，基于节点映射完成链路映射过程。对高可靠性低时延切片请求，如1.2.2 节链路映射所述，采取Kruskal 算法［19］获取其最大生成树链路，为保证备份资源能够共享，应确保满足以下约束条件：1）主链路和备份链路不能重叠；2）若不同切片请求的虚拟链路的备份链路为同一底层路径，则不能共享备份资源；3）如果底层备份资源满足新到达的备份请求，则可以共享备份链路资源。在满足上述约束条件的情况下，通过最短路径算法分别完成主备份路径映射，具体过程如下：

子算法2高可靠性低时延切片备份链路构建

3 仿真与性能分析

3.1 实验环境配置

本文实验的底层网络拓扑和网络切片请求拓扑均由GT-ITM［20］工具生成，通过Matlab R2018a 进行仿真结果分析，具体参数如表1所示。在仿真中，物理故障链路的到达服从泊松分布，参数为0.05，对于区分切片请求的阈值，根据实验所设切片带宽需求变化范围，选取变化范围的中间值8 作为阈值。每次实验运行30 000 个时间单元，每1 500 个单位对数据做统计，取10 次实验的平均值作为最终结果。

表1 实验配置参数Table 1 Experimental configuration parameters

3.2 性能分析

3.2.1 评价指标

通过平均成功运行率、长期收益开销比和故障恢复率这3 项指标，评估本文算法性能。

1）平均成功运行率

平均成功运行率反映了NS 可靠性映射以及对链路故障恢复的有效性，计算公式为：

其中：N(T)是T时刻所有到达NS 的数量集合；Nsuc(T)表示成功运行的NS 数量，成功运行的NS 数量既包括映射成功的NS 请求，又包括恢复成功的NS 请求；δ是趋近于0 的变量。

2）长期收益开销比

对于切片请求GV=(NV,EV)，长期收益与接受虚拟请求的收入和故障产生的惩罚金相关，定义收入R(GV,T)、惩罚金P(GV)和成本开销C(GV,T)为：

其中：μ和υ分别是用于平衡CPU 和带宽资源的加权系数，本文假设μ=υ=1，表明CPU 和带宽的重要性相似；A(GV)表示无法恢复的链路集合；ω为惩罚系数，假设为5；h(lv)是对应于虚拟链路的底层路径的跳数，本文设为4。因此，长期收益开销比的计算公式为：

3）物理链路利用率

物理链路利用率表示一段时间内映射的所有物理链路已占用带宽资源与底层网络链路带宽资源总和之比，计算公式为：

4）故障恢复率

故障恢复率用于反映切片映射算法的可靠性，计算公式为：

其中：Nfail(T)是T时刻所有失效的NS 数量集合；Nrec(T)表示NS 重映射成功的数量；δ是趋近于0 的变量。故障恢复率越高，表示这段时间内恢复的NS 数量就越多，则切片映射算法的可靠性就越高。

3.2.2 结果分析

将本文提出的DST-NSRE 算法与SVNE1+1［13］和DPS-VNRA［21］算法进行对比。SVNE1+1 算法节点采取随机映射，利用最短路径为每条链路都采取备份，且备份资源不共享。DPS-VNRA 算法将故障链路按带宽大小降序排列，采用路径分割法为故障链路重新选路。本节从网络切片请求成功运行率、长期收益开销比、链路利用率和平均故障恢复率这4 个方面来评估算法应对故障的能力，验证区分业务类型切片可靠性映射方法的有效性。

3 种算法的平均成功运行率如图2所示。可以看出，随着NS 请求的到达和链路故障的增多，平均成功运行率逐步下降。本文DST-NSRE 算法此项指标较高的原因在于该算法属于部分备份，仅对高可靠切片类型进行备份，采取基于最大生成树链路的方法尽可能减少备份资源，从而使更多的底层资源接受NS 请求，而且在恢复另一类型切片故障链路时用较可靠性高的底层链路进行承载，使恢复成功的NS 数量增多，从而提高了平均成功运行率。DPS-VNRA 算法对所有的故障链路采取路径分裂进行重映射，由于故障链路的增多会影响NS 的运行，因此导致平均成功运行率较低。SVNE1+1 保护算法为每条链路都进行备份，造成了大量的链路资源浪费，同时拒绝了大量的虚拟请求，因此，其成功运行率最低。

图2 平均成功运行率Fig.2 Average success operating rate

3 种算法的长期平均收益开销比如图3所示。可以看出，长期平均收益开销比随着时间的增长出现不同程度的下降，最终趋于稳定。DST-NSRE 算法能够获得更高的收益开销比，这是因为该算法对故障的虚拟链路按带宽进行排列，优先恢复价值更高的高可靠性低时延切片，增加了网络收益，并且对备份资源的合理共享减少了资源消耗，使网络资源开销减少。此外，算法在重映射时选择可靠性高的底层链路，提高了恢复率，减少了因故障恢复失败而产生的罚款，从而提高了长期收益开销比。

图3 长期收益开销比Fig.3 Long-term income-cost ratio

3 种算法物理链路利用率的变化情况如图4所示。可以看出：SVNE1+1 算法的链路资源利用率远低于其他两种算法，这是因为该算法占用了大量链路作为备份路径；本文DST-NSRE 算法在切片映射时综合考虑可靠性和资源利用率的因素，以最大化底层资源作为映射目标，通过链路备份共享的方式，使得有大量的底层资源用以恢复，以此提高切片请求的成功映射，因此具有较高的链路利用率。

图4 物理链路利用率Fig.4 Physical link utilization rate

3 种算法的平均故障恢复率如图5所示。可以看出：DPS-VNRA 算法故障恢复率最低，因为它在故障发生后才寻找可替代路径，当切片请求逐渐增多时，就没有多余的可用资源用来恢复故障链路，所以平均故障恢复率最低；其他两种算法都有备份链路资源；本文DST-NSRE 算法切片类型1 的平均故障恢复率稳定在0.88 左右，备份资源的共享与算法SVNE1+1 相比既能减少冗余备份同时又满足了切片高可靠性需求，切片类型2 即高带宽类型故障恢复率高于重映射DPS-VNRA 算法，这得益于本文算法将故障链路重映射至高可靠性的底层链路，提高了恢复率，稳定在0.84 左右。

图5 平均故障恢复率Fig.5 Average failure recovery rate

4 结束语

本文研究单链路故障下网络切片的可靠性映射问题，提出一种基于业务类型的网络切片可靠性映射算法。仿真结果表明，与SVNE1+1 和DST-VNRA算法相比，该算法具有较高的切片成功运行率、长期收益比、物理链路利用率和故障恢复率。本文只是将切片类型简单地根据带宽阈值分为两类，而目前网络切片有三大应用场景。因此，下一步将继续完善区分切片业务类型的评价方案，并设计更好的启发式可靠性映射算法，以此来平衡可靠性与资源利用率之间的关系。