基于SDN和NFV融合的网络切片资源分配优化算法

朱晓荣，高 健

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

随着新一代网络技术的发展，传统的网络架构已经不适应现在的网络服务功能的需求，网络资源的适配和资源调度缺乏灵活性。而软件定义网络（Software Defined Network，SDN）和网络功能虚拟化（Network Function Virtualizations，NFV）是实现这一目标的关键技术［1］。SDN采用逻辑上集中式的SDN控制器，实现了数据平面和控制平面的分离，实现对网络的可编程性，优化网络资源的利用。NFV将传统网络的物理网元功能虚拟化，使得网络功能不再局限于专用的硬件内，区别于传统的网络，实现了网络功能和硬件的解耦。NFV使服务运营商能够灵活地部署网络功能，可以为每个服务请求构建定制化的虚拟网络。因此，SDN和NFV为设计可扩展、动态的可编程的下一代网络提供了解决方案。

ITU定义了5G的三大应用场景：增强的移动宽带（eMBB），解决以人为中心的多媒体内容、服务和数据访问用例［2］；超可靠低延迟通信（uRLLC），面向的是高可靠和低延时的应用场景，比如无人驾驶，工业控制等方面；大规模机器类型通信（mMTC），面向的是海量连接的物联网应用，通常传输相对低容量的非延迟敏感数据。为了满足不同应用的需求，网络切片技术得到了广泛的研究和应用。网络切片实现的逻辑上端到端的网络，根据客户的需求服务供应商，进行业务和虚拟网络功能的编排为其提供服务，再将编排好的网络切片在网络设备层进行实例化提供服务。这些不同逻辑网络提供不同的服务，来满足不同场景用户的通信需求。网络切片由一组虚拟网络功能按照一定的逻辑编排和虚拟网络功能之间的链路组成，这样经过编排实现的功能逻辑被称为服务功能链（SFC）。服务功能链可以根据动态的需求灵活地分配资源，从而可以为各种复杂的5G通信场景定制网络切片。借助网络切片，服务提供商可以灵活、快速地部署他们的定制化应用和服务，以适应多样化服务的特殊需求。

因此，在提供服务的过程中就需要将编排好的虚拟网络功能和链路进行映射，服务功能链的映射就是为每个虚拟网络功能分配最优的物理节点和链路，所以我们可以把虚拟网络功能链映射问题转化为虚拟网络功能的资源分配问题。NFV-RA（Network Function Virtualization-Resource Allocation）是选择合适的物理节点和链路来进行服务功能的放置，同时，资源的使用必须满足特定的约束目标，例如最大化剩余的物理资源，最小化时延等。

NFV-RA主要包含三个阶段：VNFs（Virtual Network Functions）链构建（VNFs-Chain Composition，VNFs-CC），称为服务功能链接；VNF转发图嵌入（VNF-Forward Graph Embedding，VNF-FGE）以及VNF调度（VNF-Scheduling，VNF-SCH）。VNF转发图嵌入实现的是把服务功能链中的虚拟网络功能放置到合适的位置满足其QoS（Quality of Service）需求，VNF调度是将映射完成的VNF实例之间的流量进行调度。最近几年有很多关于这方面的研究，大部分在对NFV-RA建模时，建立为一个整数线性规划的问题（这被证明了是一个NP-hard问题），通过传统的启发式算法进行迭代求解，但是使用启发式算法不能够对实时的业务进行映射，降低了系统的实时性。

5G核心网中网络切片的资源分配问题受到了国内外学者的广泛关注。文献［3］考虑了在核心网中服务功能链的部署，文中形成的最优化的问题是在满足节点和链路资源约束的条件下，一个物理网络中最多可以同时部署的服务功能链的条数。作者提出了基于最优加权图匹配的算法来解决服务功能链映射的问题，但是模型中没有考虑各类业务的Qos的约束。文献［4］考虑了服务功能链部署的带宽、时延和链路部署成本作为优化的目标，作者提出了服务功能链局部的贪婪部署算法，最后用全局的贪婪算法迭代地确定每个虚拟功能放置的位置。文献［5］作者也是以部署成本最小化为优化目标，在维特比算法的基础上提出了分割融合维特比（Merge-Split Viterbi）算法的启发式算法求解近似最优解。文献［6］采用深度强化学习算法，以整个服务功能链的QoS为优化目标进行网络切片的路由和资源分配的最优策略的求解。文献［7］以最大化链路利用率和最小化带宽消耗联合优化，提出了基于多目标的遗传算法进行问题的求解。文献［8］考虑了服务功能链的时延约束和各种VNFs之间次序的限制，先提出单条服务功能链的路由和资源分配问题，在一条服务功能链的基础上提出了全局的路由和资源分配的问题。最后作者提出了一种快速的启发式算法进行求解。文献［9］VNF的放置和路由资源的分配看起来和 VNE（Virtual Network Embedding）类似，但作者在文中提出了一种更加复杂的VNF链路需求，包括放置VNFs的源目节点之间的流量控制。

文献［10］将网络切片中的资源分配问题表示为分布式服务函数链问题，作者采用局部搜索的启发式方法来求解。文献［11］提出了一种启发式算法来解决服务功能链的映射，来减少全局的能量消耗。文献［12］提出了一种基于SDN／NFV场景下的服务功能链的放置模型和VNF的基于时延的调度算法以满足各个不同服务功能链的时延约束。文献［13］以在网络切片过程中出现故障进行VNF和链路的迁移，以最小化整个过程所消耗的带宽为优化目标，提出了基于变邻域搜索的网络切片启发式算法对故障进行修正。文献［14］以最小化网络中所有的链路流量为目标，形成了混合整数线性问题，提出了 PSUM （Penalty Successive Upper-bound Minimization）算法和PSUM-R的算法来进行求解。文献［15］分析了不同网络业务的网络切片和物理网络之间的关系，建立逻辑网络函数映射到物理网络的数学模型，并且针对5G的三类业务的QoS分别提出了最优的目标函数进行优化。文献［16］提出了新的混合整数线性规划（MILP）优化模型，在模型中考虑了端到端的时延，提出了一种新的启发式解决方案——NFV平台组件编排的介数中心性算法（BACON）来解决VNF布局问题。文献［17］提出了一种新的映射方案，对具有相同VNF链路集合的链路只选择同一条物理链路进行映射，减少网络的负载和部署成本，并仿真验证了所提模型在相同的成本下可以部署更多的服务功能链。文献［18］提出了一个基于特征分解方法来执行VNF映射和VNF转发图的流量控制的方案，但是这只是简单的图映射关系，没有动态实时业务的处理，因此不能满足业务的实时性。文献［19］对要部署的VNF对各种资源的消耗进行了相关性分析，提出了一个线性整数规划问题，从时变工作量和维持基本功能所需能量的角度提出了资源消耗的两阶段启发式算法提高资源利用率。

文献［20］考虑5G的三个典型业务场景为其提供不同的部署策略来满足各自的QoS需求。在此基础上，利用复杂网络理论获得了基础网络的拓扑信息，利用拓扑信息定义了节点重要性度量，对节点映射中的节点进行排序。文献［21］提出了基于强化学习的网络切片的资源分配，在智能体的学习过程中以资源的利用率和QoE（Quality of Experience）的满足率为联合奖励值对智能体进行训练，实现了实时业务的资源分配策略。文献［22］提出了一种最小化VNF迁移和放置总费用和收益损失的整数线性规划模型。但是作者所提出的工作忽略了其中的各种约束，如时延的容忍以及两个虚拟功能之间的依赖关系。上述文献研究的场景均是将底层网络视为一个整体，从整体上进行映射，没有考虑底层物理设备资源的分布类别，提出将底层物理设备按照功能和区域进行聚类，按照三大场景，为每类业务划分出优先映射的物理节点集合，再进行相应的映射，而且他们在进行最优化问题的求解过程中大多采用了启发式算法，不能满足业务的实时性需求，所以有研究提出基于深度强行学习的网络切片资源分配优化算法，对实时的业务需求提供更好的解决方案。

1 系统模型

文中研究的基于SDN和NFV的网络切片按业务进行映射的应用场景如图1所示，从图中可以看出，由SDN控制器层、网络切片实例层和物理资源层组成。物理资源层由各种交换机和路由器等设备构成，可以实例化部署一些虚拟网络功能，按照提出的物理器件的聚类方法，将底层的物理节点聚类为三类专用器件。网络切片实例层按照用户的业务需求，对各种虚拟网络功能进行设计和编排形成相应的服务功能链。SDN控制器层从底层的物理网络中收集节点和链路的资源使用情况并且从网络切片实例层得到需要实时映射的服务功能链的信息，根据各条服务功能链的业务类别以及带宽、时延等的QoS约束选择最适合的节点进行映射，以此为用户提供服务。

图1 基于SDN和NFV的网络切片按业务映射应用场景图

1.1 底层物理网络模型

1.3.6 优化目标

针对上面的网络切片资源分配的场景，所提出的优化目标为整个网络的资源利用率最大化，即使得网络中资源利用率最低的节点及链路的资源利用率达到最大。

因此，基于SDN和NFV的网络切片的资源分配的全局最优化问题为

将上面网络整体资源利用率最大化的复杂优化问题拆分为以下三个子业务的联合优化问题。

低时延的uRLLC业务的子问题为

mMTC的业务子问题为最大化节点和每条链路上的资源使用率，使网络可以接入更多的业务

2 本文算法

2.1 基于对偶分解的求解算法

针对uRLLC低时延业务，将目标问题转化为节点和链路的资源使用率最大化：

1.3.5 mMTC服务功能链约束

mMTC服务功能链要求高计算资源和低拥塞率。因此，部署目标应该是最小化物理链路上的带宽使用。尽可能使每条链路的带宽负载均衡，换言之，使得物理链路上的剩余带宽最大化。

其中，p、l分别表示虚拟功能的映射和链路的映射关系是原始变量，μ、v、ω称为对偶变量。

如果已知对偶变量μ，v，ω，则拉格朗日函数可以改写为节点和链路的函数之和

上面的对偶问题可以分解为虚拟功能的当前节点映射和当前节点到下一跳链路映射两个子问题进行分别求解。

其中，Δ（m）表示对偶变量迭代的步长，步长后面的乘积分别是对偶变量在拉格朗日函数中的次梯度表达式。

2.2 计算复杂度分析

3 仿真结果与性能分析

本文仿真实验利用Matlab2019a软件对服务功能链部署算法程序进行仿真，运行在Intel Core i7-8500、1.80 GHz CPU、8 GB内存的Windows 10系统PC机上。

3.1 仿真参数设置

本节对文中提出的基于对偶分解的服务功能链部署算法进行仿真评估，我们将本文方法与CoordVNF［23］和一种基于模拟退火SA的算法进行了比较。在CoordVNF中，作者提供了一种启发式方法来协调VNF功能链的组成以及将服务功能链映射到子网网络中。我们将从服务功能链请求接受率、负载均衡度、平均执行时间等方面将文中提出的算法与上述两种算法进行对比。在仿真图中，本文算法的图例使用DD进行标识。

本实验在初始阶段，实验拓扑结构采用10个节点，18条链路，每个节点具有三种资源类型，资源总量服从均值为100、方差为30的均匀分布，链路带宽为200 units，链路时延服从均值为3，方差为1的均匀分布。SFCs的数量为10～100，VNFs种类共有5种，服务功能链所需的VNFs为2～4种，对三种类型的资源需求为0.2～1 units，服务功能链的传输速率需求为1～5 units。

然后，将网络规模扩展为20～100节点的随机网络，VNFs的种类共有9种，每条服务功能链所需的VNFs为3～6种，SFCs数量由200条逐渐增加到1 000条。

3.2 算法实验比对

图2为不同服务请求数量下的服务接受率对比，可以看出，当服务请求数量不超过400时，出现了小幅的服务功能链接受率下降，在服务请求数量超过500时，曲线呈直线下降趋势，请求服务功能链的部署接受率下降严重。对偶分解算法的服务请求接受率比CoordVNF算法平均提高了3%左右，比SA算法提高了10%左右，主要因为对偶分解算法部署服务功能链的目标是最大化使用节点和链路的物理资源，因此在相同的资源设置时能够容纳更多的服务功能链部署。

图2 不同服务请求数量下的接受率

图3表示的是不同服务链请求数量下节点资源和链路带宽资源平均利用率的变化，可以看出，随着服务功能链数量的增加，使用的物理节点的资源和链路带宽的平均利用率总体上是上升的，从图中可以看出基于对偶分解的算法，由于首先将底层的物理网络按照功能划分为三个不同的虚拟子网以及优化目标为最大化资源的使用率，使得物理节点和链路带宽的平均资源使用率得到了提升，明显优于CoordVNF和SA。

图3 不同服务请求数量下的节点和链路的平均资源利用率

图4表示的是在不同规模的底层物理节点，部署长度相同以及数据速率相同的服务功能链所需要的平均执行时间。为了评估平均执行时间，我们分别使用所提出的对偶分解的算法和CoordVNF算法以及基于SA的方法来同时部署相同的服务功能链，从图中的大体趋势可以看出随着服务功能链长度的增加，我们的算法和CoordVNF算法以及SA平均执行时间都在增加。基于对偶分解的部署算法与CoordVNF的执行时间大体相似，比SA的执行时间要明显缩短很多。在执行时间上有一定的优越性。

图4 部署服务功能链的平均执行时间

由于在进行服务功能链的映射之前，先按照物理节点的集合划分为三个虚拟的子网，因此在图5中对映射到不同子网上面的不同类型的服务功能链的节点资源和链路资源的平均使用率进行了仿真，底层采用的实验拓扑为15个节点，30条链路，从图中可以看出随着服务功能链数量的增加，三类业务的节点和链路的平均资源利用率总体上呈上升趋势，eMBB类型服务功能链始终使用较少的物理节点和链路，因此物理节点和链路的资源利用率最高。mMTC类型服务功能链始终要选择较多的物理节点以及使得物理链路带宽最小，以达到减少底层网络冲突的目的，因此物理节点和链路的资源利用率最低。特别地，由于仅考虑了服务功能链的总延迟，uRLLC类型服务功能链的结果基本上位于它们之间。

图5 不同子网的节点和链路的平均资源利用率

4 结束语

文中提出了一种基于SDN和NFV的网络切片资源分配优化算法，在算法中首先将底层物理网络按照服务功能划分为三个虚拟的子网，然后根据5G网络三大业务的不同需求建立最大化节点和链路使用率的最优化模型，在问题求解的过程中由于链路映射问题存在着变量的耦合，因此首先将链路条件解耦，分割为相邻的两个节点之间的映射问题，通过拉格朗日对偶分解的方法，对节点问题和链路分别进行求解，实现服务功能链优化部署。该方法基于多个不同类型服务的同时请求，具有实时、快速、高效特点，能够满足未来5G网络定制化服务场景需求。在执行时间、资源利用率等方面具有较好的性能，在以后的工作中要加入一些人工智能的方法，以满足智慧化网络运营需求。