一种支持节点分割的vEPC虚拟网络功能部署模型

汤红波 袁 泉 卢干强 王晓雷 赵 宇



一种支持节点分割的vEPC虚拟网络功能部署模型

汤红波*袁 泉 卢干强 王晓雷 赵 宇

(国家数字交换系统工程技术研究中心 郑州 450002) (移动互联网安全技术国家工程实验室 北京 100876)

软件定义网络(SDN)和网络功能虚拟化(NFV)促进了网络的创新，NFV实现了虚拟网络功能(VNF)的逻辑集中部署。针对vEPC(virtualized Evolved Packed Core)网络中VNF的池组化部署问题，该文提出一种支持节点分割的VNF部署模型，该模型基于虚拟请求业务流量的感知，利用节点分割算法动态调整VNF与底层网络资源切片的映射关系，实现VNF的跨域组池。与传统的多功能链联合映射算法相比，该方法能够实现节点资源细粒度化管理和统筹调度，优化网络视图，减少资源碎片。在SNDlib提供的网络拓扑实例下仿真证明，该模型可以降低虚拟网络的资源开销，并提高虚拟网络的请求接收率。

网络功能虚拟化；虚拟网络功能部署；5G；EPC(Evolved Packed Core)；节点分割

1 引言

当前，有限的网络资源和僵化的网络结构限制了网络的发展。为了满足未来网络的需求，提高网络的管理能力和灵活性，IMT-2020(5G)推进组提出应用软件定义网络(Software-Defined Network, SDN)和网络功能虚拟化(Network Function Virtualization, NFV)技术实现演进分组核心(Evolved Packet Core, EPC)网网元功能基于数据中心网络的集中化部署、编排与管理[1]。

目前，多数文献[2]都是研究互联网服务功能链场景下的虚拟网络功能(Virtualized Network Function, VNF)部署问题。近些年，随着5G的兴起，国内外学者对vEPC网络中VNF部署问题进行了相关研究。由于传统的数据中心网络难以满足5G移动通信高带宽、低时延和集中管控的要求，文献[3]提出了一种分布式云平台上的虚拟化EPC (virtualized EPC, vEPC)网络组网方案。该平台通过分布式云数据中心节点提供vEPC网络中VNF实例化所需的底层资源。云节点之间基于SDN技术实现动态组网，所有的云节点由一个统一的管理和编排模块集中管控。文献[4]首次提出了vEPC网络中VNF的部署问题，并提出了两种部署方式：(1)仅在数据中心内部虚拟化VNF的控制面，数据面通过增强的SDN转发设备实现。(2)将VNF的控制面和数据面全部虚拟化，利用现有骨干网设备完成转发。该文统筹考虑了网络中处理时延和传输时延之间的关系，优化了数据中心网络的总体时延，但该模型必须先对物理网络进行静态子网划分，在每一个子网分别部署相应的EPC服务链，模型中各个子网互相独立，网络视图复杂且不利于全网资源统一编排管理。文献[5]提出了多服务链联合映射模型，该模型对域内的eNodeB进行动态聚簇，每个eNodeB簇连接一条完整的vEPC服务链，假设各条服务链之间相互独立，将一条服务链上的EPC网元功能尽可能集中部署到相邻的数据中心内部，采用定时更新底层网络状态的方式，完成多条独立EPC服务链的联合映射。相比于静态子网划分策略，联合映射思想的优点是对子网进行动态划分，能够相对灵活地调度全网资源而缺点是使网络的全局视图更加复杂，提高了网络功能管理和编排的难度。此外，文献[4]和文献[5]都是以“网元”作为资源分配的粒度，当云节点中剩余的资源不足以实例化一个完整的网元功能时，节点的剩余资源将保持不可达状态，形成资源碎片，降低了物理网络资源的利用率。

现有研究多数假设vEPC保留了EPC现行架构的主要网元功能，包括移动管理实体(Mobility Management Entity, MME)、服务网关(Serving GateWay, SGW)、PDN网关(PDN GateWay, PGW)和归属签约用户服务器(Home Subscriber Server, HSS)。文献[4]和文献[5]借鉴了互联网服务功能链的链式结构部署vEPC服务链，但是在LTE网络中，MME和SGW都采用池组的形式组网。池组技术是指在一定区域内，多套相同的网元设备组成池组，通过通用接口实现资源共享和业务分担，是解决核心网切换、负载均衡和容灾备份的重要方案[6]。为了支持vEPC网络中VNF的组池，本文提出一种基于节点分割的vEPC虚拟网络功能部署模型。该模型将虚拟网络请求的实时业务流量作为节点分割的决策变量，根据物理网络剩余资源的全局视图，动态调整虚拟节点分割的子节点数量，以及各个子节点与物理节点的映射关系。相比于传统多条服务链联合映射部署模型，节点分割模型不再对同一vEPC管理区域内的物理网络进行子网划分，优化了虚拟网络视图，完成了EPC虚拟网络功能的组池，进一步细化资源分配的粒度，提高了资源利用率。

2 数学模型

本文采用虚拟网络映射方法对vEPC网络中的VNF部署问题建模，将底层网络和虚拟网络请求分别表示为一个无向带权图，根据优化目标设计相应的映射算法寻找最优部署结果。

2.1 底层网络

2.2 虚拟网络请求

支持池组技术的vEPC虚拟网络视图如图1所示，接入网中将同一跟踪区域内的eNodeB聚合在一起，对接入云进行分簇，并假设同一个簇内的eNodeB在回传网络中都连接到了同一个汇聚节点(Traffic Aggregation Point, TAP)。虚拟网络请求可表示为一个无向带权图。其中，表示VNF的集合，。表示虚拟链路的集合，每一条虚拟链路表示为。是表示虚拟网络功能属性的集合，与物理网络相同，。是表示虚拟链路属性的集合，即虚拟链路的带宽。虚拟网络映射可以定义为：虚拟节点映射和虚拟链路映射。

2.3 构建一个底层网络的增广图

区别于传统数据中心网络中各节点同质化，各个云节点提供的服务类型具有差异性，因此在进行功能部署之前必须预先判断每一个云节点能够承载的EPC网络功能类型。本文参考了ViNEYard[7]算法，通过构建基于底层网络和虚拟网络的增广网络，为虚拟网络功能选择候选底层节点。

图1 移动核心网功能链

图2 增广网络示意图

3 节点分割算法

文献[8-10]针对互联网功能链部署提出了多种节点分割算法，文献[8]研究了物理节点可接受同一虚拟网络的多个节点映射问题，提高了请求接受率，但是该算法是一个两阶段的映射算法，无法同时获得节点和链路映射的最优解。文献[9]提出了节点和链路协同映射的一阶段映射算法，但是该算法仅支持物理节点承载不在同一个虚拟网络的多个节点映射。文献[10]提出了虚拟机功能链部署模型中，根据底层网络资源分配情况拆分虚拟网络节点的方法。参考以上文献，本文提出了EPC网络的节点分割算法，该算法基于5G非栈式协议，提出了根据底层网络流量动态拆分EPC虚拟网络功能的分割方案。节点分割EPC模型用到的符号和含义如表1所示。

表1 节点分割EPC模型用到的符号和含义

3.1 决策变量设置和底层网络资源测量

(1)决策变量设置： 传统网络协议栈中传输流量不可分割，节点分割算法一般选择虚拟节点和底层节点的映射关系变量作为决策变量，此时，虚拟网络功能到底层网络节点的映射关系是一个模糊集合，应用混合整数规划的方法不能获得全局最优解。目前，多采用两阶段映射与启发式算法相结合的方式寻找节点分割算法最优解，但是两阶段映射策略无法同时获得节点和链路的最优解而启发式会陷入局部最优[11]。5G移动通信提出了“非栈式”协议架构[12]，对协议栈进行虚拟化，使5G网络具备智能处理数据流的能力。基于5G非栈式协议的设想以及流分割技术的研究成果，本文提出在映射过程中，将底层网络的流量作为决策变量，利用混合整数规划设计一阶段的节点分割算法。整数规划决策变量和映射关系变量的符号和含义如表2所示。

表2 整数规划决策变量和映射关系变量

(2)底层网络资源测量： 本文提出的节点分割算法是一种动态映射算法，在映射过程中根据底层网络流量不断调整映射关系矩阵。为了降低计算时延，基于已有研究，我们利用了以下两个结论来降低底层网络测量的计算复杂度。

结论1 根据文献[13]，假设在映射过程中一个虚拟网络功能()分割成个子节点，其与业务量相关的节点属性资源需求按照承担的业务量映射到个子节点上，如式(1)所示。其中，是子节点序号，表示部署该虚拟网络功能所必须消耗的基本属性资源，表示第个节点所承担的该虚拟网络功能的业务量，表示第个节点承担的业务量而消耗的属性资源。同样，虚拟网络功能的总带宽资源请求等于各个子节点上的数据流量之和，即。

结论2 文献[14]中软件路由器的测量结果表明，处理单位分组所消耗的平均计算和存储资源近似为常数。因此，根据式(1)节点计算、存储和带宽资源表达式可以分别近似为式(2)~式(4)，其中和为常数。

(2)

(4)

在上述简化的基础上，我们将在单位时间映射结束后更新底层网络的剩余资源。如式(5)，式(6)所示，表示在单位时间里，网络中被占用的资源与被释放的资源之差。

(6)

3.2 优化目标和约束条件

优化目标：

式(7)中，第1项表示节点间链路流量占用的带宽资源，第2项表示虚拟网络请求占用底层网络节点的计算资源，其中，表示在底层节点上部署某个虚拟网络功能所需要的基本资源，则表示在映射某个的过程中，由节点处理的业务量所产生的资源需求。第3项表示虚拟网络请求占用底层网络节点的存储资源，第4项表示承载虚拟网络功能的底层节点转发业务流所消耗的网络资源。是表示权重的常数，满足条件。对于特定网络环境，可以相应地调整权重参数，例如要着重考虑计算资源的分配时，应该适当增大的权重。

约束条件：

容量约束：

(9)

(10)

流相关约束：

(12)

(14)

二进制变量约束：

(16)

变量定义域约束：

(18)

(19)

式(8)-式(19)详细说明如下：

式(8)-式(11)表示虚拟网络请求的资源数量与底层网络提供的资源数量之间的约束关系。其中，式(8)是对底层网络链路带宽的约束条件，当虚拟链路映射到底层链路时，所有映射经过同一条底层网络路径的流量总和不能大于该路径的可用带宽值，在这里我们假设物理链路是全双工的。式(9)，式(10)是对底层网络节点计算和存储资源的限制条件，当虚拟节点映射到底层时，底层网络节点的资源值必须不小于虚拟网络请求占用的资源。由于式(9)，式(10)是非线性约束且是一个二值化变量，所以我们把式(9)，式(10)简化为式(20)，式(21)的形式。式(11)是对底层网络节点网络资源的约束条件，对于任意一个底层网络节点，流入和流出该节点的流量总和应该小于该节点剩余的网络资源。

(21)

式(12)-式(14)描述的是流量守恒约束。式(12)表示除了在源节点和目的节点的其他节点(在网络中仅作为转发节点存在)上流入和流出的流量是相等的。式(13)，式(14)表示流出(流入)源节点(目的节点)的流量等于相应的虚拟链路的带宽请求。

式(15)表示底层网络是一个无向图，即节点间进行对等通信。式(16)表示候选节点集合约束，考虑到不同的云节点之间存在差异性，对每一个节点所能承载的虚拟网络功能进行了约束。式(17)，式(18)表示决策变量定义域的取值范围，式(19)表示映射关系变量是一个二值变量。

3.3 算法描述

本文提出的节点分割算法命名为EPC-NS算法(表3)，算法分成3个阶段：第1阶段是拓扑准备阶段，根据输入算法的底层网络无向图和虚拟网络请求无向图生成底层网络增广图；第2阶段是资源判断阶段，为了降低混合整数规划的计算发杂度，避免不必要的映射，在运行整数规划之前先对网络中的候选节点集合的剩余节点资源进行判断；第3阶段是算法执行阶段，对增广图运行混合整数规划算法，获取功能部署结果。

(1)拓扑准备：(1)~(4)算法第1行表示EPC-NS算法以在线的虚拟网络请求作为输入，并把嵌入底层网络图生成元节点集合。第2，第3行根据SNDlib中的节点参数初始化变量，选择每个元节点的候选集合。第4行将元节点和候选节点通过元链路链接，生成增广网络图。

(3)算法执行：(9)~(14)对增广网络图运行混合整数规划算法。如果成功完成映射则更新底层网络资源并获取映射结果，如不成功，则直接拒绝请求。

表3 EPC-NS算法

4 模型仿真与性能分析

4.1 参数设置

EPC-NS算法仿真所使用的底层网络拓扑结构取自SNDlib中的Polska12节点测试例[15]，如图3(a)所示。图中节点位置部署了运营商的云数据中心，假设所有节点都可以承载除了PGW之外的任意核心网功能，PGW作为移动核心网和互联网之间的锚点，位置通常是固定的。在Polska12节点测试例中，设定只有Rzeszow和Bydgoszcz节点可以承载PGW。在底层网络中，节点网络资源的数量和链路带宽由SNDlib给出，底层节点的计算和存储资源根据节点网络资源按比例随机生成。在虚拟网络请求中，用户面的流量是服从泊松分布的随机过程，控制面中节点所需的计算、存储和网络资源请求与用户面业务流量呈预定的比例，根据SNDlib给出的测试数据，下文将采用流量因数(Traffic Demand Scaling Factor, TDSF)表示流量的变化情况，Polska12节点测试例中TDSF的理论取值范围是。为了便于比较且不失一般性，我们假设所有节点上单位计算、存储和网络资源的开销是相等的。为了使部署节点所需的基本开销与该节点上由业务量产生的开销能够保持在同一个数量级，设定目标函数中。此外，需要根据网络拓扑中的资源分布情况通过实验确定资源权重参数,和。本次仿真实验的平台是CPU型号为Intel i7 4790，内存为4 GB的个人电脑。混合整数规划的求解方案选择了CPLEX version 12.4，在MATLAB环境下使用YALMIP接口编写了仿真程序。

4.2 性能评估

图3 对部署结果的影响

图4 EPC-NS算法在TDSF=20时的部署结果

图5 Andreas算法在TDSF=20时的部署结果

图8显示了两种算法在不同流量因子条件下的虚拟网络映射开销。映射开销由式(7)所示的目标函数定义，采用虚拟网络请求在映射过程中消耗的节点计算、存储、网络资源以及链路带宽资源的加权和表示。文献[5]算法以“网元”为颗粒度进行资源分配，当节点的剩余资源不足以承载任何EPC“网元”时，剩余资源将成为资源碎片，在底层网络视图更新前保持不可达状态。EPC-NS算法在混合整数规划寻优过程中选择底层链路的流量值作为决策变量，因此底层网络流量必须是最小分组的整数倍。根据文献[14]，底层节点处理单位分组所消耗的平均计算和存储资源近似为常数。综上，EPC-NS算法将资源分配的颗粒度由“网元级”降低为处理单位数据流占用的资源片，实现了资源的细粒度分配。在相同的虚拟网络请求下，EPC-NS部署的节点数量更少，减少了网络中非业务因素占用的基本资源开销。当网络流量因子时，因网络中资源碎片过多文献[5]算法无法生成有效解空间，虚拟网络请求被拒绝。

5 结束语

本文从vEPC中VNF的池组化部署问题入手，兼顾5G移动通信更高的资源需求，提出了一种支持节点分割的VNF部署模型。该模型借助EPC-NS算法将资源分配的粒度从传统模型的“网元级”降低到处理单位流量所占用的网络切片，提高了网络的灵活性和硬件资源利用率。仿真结果和性能评估验证了其有效性。后续将针对vEPC池组模型的可靠性问题进行研究，以满足5G移动业务的高可靠性要求。

图6 EPC-NS算法在TDSF=80时的部署结果

图7 文献[5]算法在TDSF=80时的部署结果

图8 网络开销对比图

图9 请求接受率对比图

[1] IMT-2020(5G). 5G concept whitepaper[OL]. http://www. imt-2020.cn/zh/documents/download/23. 2015.

[2] FISCHER A, BOTERO J F, TILL BECK M,Virtual network embedding: a survey[J].&, 2013, 15(4): 1888-1906. doi: 10.1109/ SURV.2013.013013.00155.

[3] SAMA M R, CONTRERAS L M, KAIPPALLIMALIL J,Software-defined control of the virtualized mobile packet core[J]., 2015, 53(2): 107-115. doi:10.1109/MCOM.2015.7045398.

[4] BASTA A, KELLERER W, HOFFMANN M,Applying NFV and SDN to LTE mobile core gateways, the functions placement problem[C]. ACM Workshop on All Things Cellular: Operations, Applications, & Challenges, Chicago, USA, 2014: 33-38. doi:10.1145/2627585.2627592.

[5] BAUMGARTNER A, REDDY V S, and BAUSCHERT T. Mobile core network virtualization: a model for combined virtual core network function placement and topology optimization[C]. IEEE Conference on Network Softwarization, London, United Kingdom, 2015: 1-9. doi:10.1109/NETSOFT.2015.7116162.

[6] TALEB T, CORICI M, PARADA C,EASE: EPC as a service to ease mobile core network deployment over cloud[J]., 2015, 29(2): 78-88. doi:10.1109/MNET. 2015.7064907.

[7] CHOWDHURY M, RAHMAN M R, and BOUTABA R. Vineyard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219. doi: 10.1109/TNET.2011.2159308.

[8] 李文, 吴春明, 陈健, 等. 物理节点可重复映射的虚拟网映射算法[J]. 电子与信息学报, 2011, 33(4): 908-914. doi: 10.3724/ SP.J.1146.2010.00735.

LI Wen, WU Chunming, CHEN Jian,Virtual network mapping algorithm with repeatable mapping over substrate nodes[J].&, 2011, 33(4): 908-914. doi: 10.3724/SP.J.1146.2010.00735.

[9] JARRAY A and KARMOUCH A. Decomposition approaches for virtual network embedding with one-shot node and link mapping[J]./, 2015, 23(3): 1012-1025. doi: 10.1109/TNET. 2014.2312928.

[10] LIU L, XU J, YU H,A novel performance preserving VM splitting and assignment scheme[C]. IEEE International Conference on Communications, Sydney, Australia, 2014: 4215-4220. doi: 10.1109/ICC.2014.6883982.

[11] ZHOU Y, LI Y, JIN D,A virtual network embedding scheme with two-stage node mapping based on physical resource migration[C]. IEEE International Conference on Communication Systems, Amsterdam, Netherlands, 2010: 761-766. doi: 10.1109/ICCS.2010.5686504.

[12] CHIH-LIN I, HAN S, XU Z,5G: rethink mobile communications for 2020+[J]., 2016, 374(2062): 20140432. doi: 10.1098/ rsta.2014.0432.

[13] 蔡志平, 刘强, 吕品, 等. 虚拟网络映射模型及其优化算法[J]. 软件学报, 2012, 23(4): 864-877. doi: 10.3724/SP.J.1001.2012. 04063.

CAI Zhiping, LIU Qiang, LÜ Pin,Virtual network mapping and optimization algorithm[J].2012, 23(4): 864-877. doi: 10.3724/SP.J.1001.2012.04063.

[14] DOBRESCU M, EGI N, ARGYRAKI K,RouteBricks: exploiting parallelism to scale software routers[C]. ACM SIGOPS Symposium on Operating systems principles, Big Sky, USA, 2009: 15-28. doi: 10.1145/1629575.1629578.

[15] Orlowski S, Wessäly R, Pióro M,SNDlib 1.0-survivable network design library[OL]. http://sndlib. zib.de/home.action. 2015.

A Model for Virtualized Network Function Deployment Based on Node-splitting in vEPC

TANG Hongbo YUAN Quan LU Ganqiang WANG Xiaolei ZHAO Yu

(450002,) (,100876,)

Software Defined Networking (SDN) and Network Function Virtualization (NFV) promote network innovation. NFV realizes logic centralized deployment of Virtualized Network Function (VNF). This paper proposes a kind of node-splitting VNF deployment model for problem of pooling deployment of VNF in virtualized Evolved Packet Core (vEPC) network. Based on the acknowledgement of virtual request traffic-aware, the model uses node-splitting algorithm to realize the dynamic adjustment of the mapping relation between VNF and physical network slices and organize the same VNFs across different domains as one pool. Compared with the traditional joint mapping algorithm of multi-function chain, the method can realize fine-grained management and overall scheduling of node resources, optimize network view, and reduce resource fragments. It is proven by network topology instance provided by SNDlib that the model can reduce resource overhead of virtual network and improve the ratio of acceptance of virtual network requests.

Network Function Virtualization (NFV); Virtualized network function placement; 5G;Evolved Packet Core(EPC); Node-splitting

TN915.81

A

1009-5896(2017)03-0546-08

10.11999/JEIT160507

2016-05-17；改回日期：2016-09-06；

2016-11-17

汤红波 thb@mail.ndsc.com.cn

国家863计划项目(2014AA01A701)，国家自然科学基金(61521003)，科技部支撑计划(2014BAH30B01)

The National 863 Program of China (2014AA01A701), The National Natural Science Foundation of China (61521003), The Ministry of Science and Technology Support Plan (2014BAH30B01)

汤红波： 男，1968年生，教授，研究方向为移动通信网络、新型网络体系结构.

袁 泉： 男，1991年生，硕士生，研究方向为移动通信网络、网络功能虚拟化.

卢干强： 男，1990年生，硕士生，研究方向为移动通信网络、网络功能虚拟化.