一种基于Viterbi算法的虚拟网络功能自适应部署方法

刘彩霞 卢干强 汤红波 王晓雷 赵 宇



一种基于Viterbi算法的虚拟网络功能自适应部署方法

刘彩霞 卢干强*汤红波 王晓雷 赵 宇

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

为了应对移动数据流量的爆炸性增长，5G移动通信网将引入新型的架构设计。软件定义网络和网络功能虚拟化是网络转型的关键技术，将驱动移动通信网络架构的创新，服务链虚拟网络功能的部署是网络虚拟化研究中亟待解决的问题。该文针对已有部署方法未考虑服务链中虚拟网络功能间顺序约束和移动业务特点的问题，提出一种基于Viterbi算法的虚拟网络功能自适应部署方法。该方法实时感知底层节点的资源变化并动态调整拓扑结构，采用隐马尔科夫模型描述满足资源约束的可用的底层网络节点拓扑信息，基于Viterbi算法在候选节点中选择时延最短的服务路径。实验表明，与其它的虚拟网络功能部署方法相比，该方法降低了服务链的服务处理时间，并提高了服务链的请求接受率和底层资源的成本效率。

5G；网络功能虚拟化；虚拟网络功能部署；隐马尔科夫模型；Viterbi算法；自适应

1 引言

随着移动互联网的快速发展，智能终端和OTT业务正趋向主导地位，这大大增加了移动数据业务的消费需求。经研究预测，2010~2020年间，移动数据流量将增长1000倍[1]。为了满足业务流量的需求，运营商需要不断加大基础设施建设，扩充网络容量，因而网络规模不断膨胀，运营商的运营成本不断提高。此外，随着移动互联网的发展，移动通信网被边缘化和管道化的趋势日益明显，因而运营商的业务利润将逐渐下滑[2]。运营成本增加而收益逐渐降低的趋势迫使运营商不得不进行网络转型，采用诸如网络功能虚拟化等技术来降低运维成本，同时增加运营效益。5G提出将满足超高流量密度、超高连接数密度、超高移动性的需求。此外，包括5G在内的未来移动通信网将是多种异构网络融合互通且要求新业务的创新与部署更加灵活。因此，引入新型移动通信网络架构势在必行。

在信息通信技术(ICT)融合发展的背景下，以软件定义网络(SDN)和网络功能虚拟化(NFV)为代表的新技术，将共同驱动5G及未来移动通信网的架构创新，为解决移动通信网发展中面临的挑战提供了途径。SDN的核心是实现网络控制平面和数据平面的分离，NFV的主要思想是实现网元功能与专属硬件平台的解耦，二者将增强网络的灵活性和可扩展性，促进基础设施资源的高效共享，大幅提高网络建设的成本效率，从而降低网络的CAPEX和OPEX，增大基础设施收益[3]。

目前，移动通信网的虚拟化研究处于起步阶段，存在许多亟待研究的问题。本文主要关注分组核心网(Evolved Packet Core, EPC)应用场景下虚拟化网络功能(VNF)的部署问题。移动通信对系统的服务时延要求较高，5G提出为用户提供毫秒级的端到端时延。因此，如何在满足资源约束的条件下保证业务请求承载量，并降低服务时延是VNF部署面临的挑战。SDN早在2006年被斯坦福大学Clean Slate课题提出，NFV于2012年被运营商联盟提出，重在解决网络的僵化问题。随着5G技术的提出，业界将SDN和NFV作为移动通信网网络架构演进的两项重要技术，也是5G移动通信网的核心技术。文献[4]提出一种新型网络架构，实现了数据转发和功能特征的分离，网络只负责数据转发，功能特征转移到云平台，可根据用户的需求自动化迁移或伸缩。文献[5]提出一种基于SDN的可扩展架构，通过集中化的配置可以动态地将不同类型的业务流转发到任何中间件，允许用户自由选择网络服务。文献[6]提出应用NFV技术管理5G网络，并讨论了5G虚拟化中VNF实例化等关键问题。文献[7]提出一种VNF资源分配模型，该模型将网络的功能分解为不同的组件，实现功能虚拟化，并根据需要动态重组提供功能服务，可以快速应对资源请求变化，提高VNF的部署效率。文献[8]针对高动态网络及其服务环境的管理问题，提出一种VNF编排模型，通过监控系统资源状态，动态编排VNF节点，实现虚拟网络的自动化部署及资源的自动化分配。文献[9]提出一种VNF功能链架构，提出资源池概念，即同种类型的VNF部署在同一资源池，可以减少VNF间不必要的通信，但该模型对不同类型VNF之间的带宽提出更高要求。为了有效地运行虚拟化的网络服务，文献[10]提出了HSD和VSD两种VNF部署方案，并分析了其在资源约束下的部署开销。目前，VNF部署问题的研究处于概念验证阶段，可参考的方法很少。现有的方法更多地关注节点资源利用率且未考虑移动业务的特点，传统的虚拟网络映射算法未考虑功能链中VNF间的顺序约束，并不完全适用。因此，本文提出的VNF自适应部署方法主要关注时延，以应对5G低时延的性能要求。

2 网络模型与问题描述

5G及未来移动通信网将是基于IT技术的集中化的云网络，将打破网络的封闭性。虚拟化技术是网络高弹性和可重构的基础，是解决运营商网络未来发展的关键技术，SDN和NFV将促进运营商网络的数字化转型[11,12]。

2.1 移动通信网络虚拟化模型

如图1所示，SDN将网络实体中异构的网元抽取分离，不同实体中同质的网元集中化部署，实现了控制平面与数据平面的分离，在智能编排管理器的控制下，表现出高度的虚拟化和智能化特性。如图2所示，NFV将网元功能与专属硬件平台解耦，网元功能从高昂的专属硬件迁移到通用的服务器，实现了网元功能的软件化、模块化和IT承载，并通过VNF的虚拟化实例部署提供服务[13]。该架构实现了网络资源虚拟化，即对网络进行逻辑化的抽象和封装，屏蔽复杂的物理细节；实现了网络的集中化控制，可以支持多个网络实体的协调和调度；实现了网络的智能化，即自动感知VNF请求及资源状态，并随着VNF的迁移或网络位置的改变，自动化配置网络。网络服务的实现需要一组有序的网元功能，如图3所示。为了满足不同的业务请求，运营商需要部署一系列有顺序约束的网元功能集合，从而实现所需要的功能服务，该有序的功能集合被称为“功能链”或“服务链”[14]。在虚拟化模型中，网络可根据业务需求动态实例化，促进了底层资源的共享，业务的部署与编排更加智能化，增强了网络的灵活性和可扩展性。不同的部署方案会影响到网络的服务质量，因此，VNF部署是移动通信网虚拟化的关键问题之一。

2.2 服务链功能部署问题描述

NFV可以根据需要动态调配VNF，是颠覆性的网络重构技术。EPC网络由多种网元功能组成，网络服务基于功能链。在传统的网络架构中，改变网元功能的连接方式或部署新功能比较复杂。NFV简化了网元功能的连接和部署方式，使服务更加灵活。在网络虚拟化模型中，不同的VNF逻辑服务链，具有不同的功能表现，可根据部署策略在底层节点选择部署位置与服务路径。如图4所示，VNF管理层根据服务请求，组合功能组件形成逻辑的VNF链；底层网络是通用的硬件资源平台，实际承载服务请求；虚拟化资源管理平台根据服务链的请求信息和底层资源的状态信息，实现服务链VNF在底层网络中的部署。

图1 移动通信网络虚拟化模型

图3 网络功能虚拟化示意图

图4 服务链功能部署模型

图5 底层物理网络拓扑图

服务链功能的实例化流程，如图6所示。首先，根据用户的服务请求组合VNF功能模块，形成逻辑功能链；其次，根据底层网络的资源状态信息，获得当前可部署位置逻辑视图，并将功能链与底层网络可用信息的逻辑视图按照一定策略匹配。若服务功能链映射成功，则底层资源池为其分配相应的资源实现服务链功能的实例化；然后，输出服务链中VNF及链路的部署信息，并更新底层网络的状态信息，设置服务链的生存周期并实时监测其生存状态，基于服务链构建的新业务即可向用户提供相应的服务。定义表示服务的起始时刻，表示当前时刻，当服务链的服务时间时，服务结束，收回为其分配的资源。定义二元变量表示服务链是否部署成功，若服务链部署成功，则；否则，。

2.3 优化目标

虚拟化网络功能部署主要是实现系统容量的优化配置，实现资源的动态共享。服务链功能部署面临两个挑战：其一，如何区别服务请求的差异性，组合不同的VNF形成逻辑功能链并映射到底层网络；其二，如何制定部署策略，实现VNF的优化部署，满足差异化的服务请求，并提高服务请求接受率和资源利用率。与互联网相比，移动通信网对服务的时延要求更高。因此，本文考虑在保证资源约束的前提下，将服务时延作为服务链VNF部署的优化目标，即根据服务链的顺序约束，在底层物理网络中寻找服务请求的时延最短服务路径。

图6 服务链功能实例化流程

本文中主要参数符号定义如表1所示。

表1主要参数符号定义

参数定义 服务节点的物理资源集合， 实例化的资源需求集合， VNF功能模块集合 服务节点中资源的容量 f实例化对资源的需求数量 f功能模块实例化的处理容量 物理网络转发节点,之间物理链路的带宽容量 物理网络转发节点,之间物理链路的时延 服务链l中VNF功能节点之间的带宽需求 服务链l的时延约束 服务链中功能f在服务节点n的处理时延 服务链l的生存周期

3 算法描述

底层网络模型如图5所示，由传输管道和云计算服务平台组成。VNF部署算法分以下几步：首先，根据服务请求组合逻辑功能；其次，根据逻辑功能链和当前网络状态描述底层网络中全部VNF可部署位置的逻辑视图；然后，根据策略部署功能链，并输出部署方案。

3.1 基于隐马尔可夫模型的底层网络描述

如图5所示，在VNF部署问题中，服务链的VNF组成及其上下文关系和VNF可部署的位置是可以观测的，但服务链的具体服务路径是无法观测的。因此，服务链中VNF的部署问题具有隐马尔可夫特性，服务路径是一条隐马尔可夫链。

3.2基于Viterbi算法的服务链路径选择

Viterbi算法可用于寻找观测事件的隐含状态序列，适用于隐马尔可夫模型。Viterbi算法的特点可以解决有向图网络中的路径优化问题，可用于服务链中VNF的优化部署。如图8所示，VNF1和VNF2分别表示服务链中相邻的上下文两种功能。,,表示在时刻部署在节点的处理时延；表示在时刻部署在节点的处理时延，表示在时刻,分别部署在节点,时，与节点,关联的转发节点间的链路时延。定义维特比变量表示按照服务链的顺序约束完成在节点部署时的最短时延。从流入节点开始，在每层部署中计算层到层候选节点的最短时延，直至流出转发节点。

图7 服务链中VNF可部署位置的逻辑视图

图8 基于Viterbi算法的VNF部署

目标函数：

约束条件：

3.3 服务链VNF的自动化部署

基于Viterbi算法的VNF自动化部署方法如表2所示。

3.4 复杂度分析

4 实验结果及分析

为了评估模型可行性及算法有效性，本文采用服务请求的处理时间、接受率、底层网络的收益和平均利润成本比作为性能评价指标，并与基于贪婪算法(Greedy)和禁忌搜索(Tabu Search)的方法比较[15]。

4.1 实验环境

实验配置为Intel Core i7-4790 3.60 GHz CPU、8 GB内存、Linux系统，参数设置如表3，表4所示，每对物理转发节点之间等概率生成物理链路。为了评估算法的自适应性，假设服务请求动态到达，且服从强度为0~1000的泊松分布。每个服务请求由一个或多个VNF组成，数量服从2~5的均匀分布。

表2 基于Viterbi的VNF自动化部署方法

4.2 性能分析

图9表示不同请求强度下不同算法的请求接受率性能。从图中可以看出，随着请求强度的增大，请求接受率不断降低，但不同算法的请求接受率的下降速度和幅度不同。在相同的资源环境和服务请求强度下，基于Viterbi算法的VNF部署方法的下降速度和幅度最小。基于Greedy的GFP和GLL算法以及基于TS的方法主要考虑节点的资源利用，没有考虑链路资源的使用情况。随着请求强度的增加，有限的链路资源限制的服务链的功能部署，使请求接受率大幅下降。而基于Viterbi算法的部署方法综合考虑了底层节点和链路的资源状态，且对VNF实行细粒度管理，增加了VNF部署和资源分配的灵活性。因此，基于Viterbi算法的VNF部署存在更优的部署方案，可以接受更多的服务请求，请求接受率最高。虽然GFP和GLL都是基于Greedy的方法，但GFP以底层节点的处理能力作为选择策略，造成服务请求在节点的处理等待时间较长，而GLL以节点缓存的容量作为选择策略，使服务请求到达后能够及时处理，从而减少节点处理的排队时间。因此，GLL的请求接受率高于GFP。虽然基于TS的部署方法也是主要考虑节点的资源使用，但TS通过反复迭代计算搜索更优的部署方案，相比于GLL改善了服务请求接受率。

表3 底层网络服务节点参数

表4 VNF 参数

图10表示不同请求强度下不同算法的服务请求平均处理时间。从图中可以看出，随着请求强度的增大，服务请求的平均处理时间变大，但不同算法的处理时间的上升速度和幅度不同。在相同的条件下，基于Viterbi算法的部署方法处理时间上升速度和幅度最小。由于GFP和GLL主要考虑节点的资源使用，服务请求在节点的等候时间较长。但GLL以节点的缓存容量作为选择策略，可以减少服务请求的排队时间。因此，GLL的服务处理时间性能优于GFP。基于TS的部署方法通过搜索优化的节点选择方案，可以降低节点的服务处理时间。因此，TS的处理时间性能优于GFP和GLL。但由于GFP, GLL和TS未充分考虑链路状态，造成VNF承载节点间的服务路径过长，导致较高的链路传输时间开销。基于Viterbi的部署方法在满足资源请求的可部署节点采用递归方法搜索时延最短路径，不仅考虑了链路传输时间还考虑了节点处理时间，降低了服务处理时间的总开销。因此，该方法进一步优化了服务请求的处理时间，提高了服务处理速度。随着请求到达强度的增加，该方法的性能优势更加明显，在高业务强度下适应性较强。由于移动用户对时延更敏感，该方法可以有效应对5G热点高容量、低时延高可靠的业务需求。

图11表示不同请求强度下不同算法的平均利润。从图中可以看出，随着请求强度的增大，平均利润变大，但不同算法的平均利润上升的速度和幅度不同。在同等条件下，基于Viterbi部署的方法平均利润上升速度和幅度最大。图12表示不同请求强度下不同算法的平均利润成本比。从图中可以看出，随着请求强度的增大，平均利润成本比变小，但不同算法的平均利润成本比下降的速度和幅度不同。与基于GFP, GLL和TS的方法相比，基于Viterbi的部署方法降低了服务时延，提高了服务请求的接受率，促进了资源利用。因此，在相同的条件下，基于Viterbi算法的VNF部署方法的平均利润和平均利润成本比最高，能够有效提高底层网络的基础设施收益。

5 结束语

SDN和NFV增强了运营商网络的弹性，提升了管道的传输能力。本文主要研究了虚拟化环境下服务链VNF的部署问题，针对传统虚拟网络映射算法的不足和5G业务更高的时延要求，提出基于Viterbi算法的VNF部署方法，并验证了方法的有效性。该方法根据服务请求选出满足资源约束的VNF可部署位置，并根据链路时延和节点处理时延选出时延最短路径。该模型能够感知业务的变化，随业务负载调整服务链间容量分配，解决了网络间广域资源的共享问题，实现了资源的高效管理。与传统的基于专属硬件的固定服务路径相比，提高了硬件资源的利用率；与传统的虚拟网络映射相比，考虑了不同VNF间的顺序约束。实验表明，该方法降低了服务请求处理时间，并提高了服务请求接受率和成本效率，可实现网络的优化部署，增强用户的服务体验，提高底层网络的长期受益。虚拟化技术降低了网络的建设成本，实现了服务链VNF的灵活编排，提高了网络服务的智能化运维能力，增强了网络对业务和环境的自适应性。在后续研究中，将针对可靠性条件下VNF部署问题进行研究，以满足移动业务的高可靠性要求。

图9 不同请求强度下的服务请求接受率       图10 不同请求强度下的服务请求处理时间

图11 不同请求强度下的平均利润        图12 不同请求强度下的平均利润成本比

[1] Cisco Visual. Networking Index Global mobile data traffic forecast update, 2012-2017[OL]. http://www.cisco.com/en/ US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/ white paper c11-520862, 2013.

[2] Marketing Charts Staff. Mobile network operators face cost crunch[OL]. http://www.marketingcharts.com/wp/direct/ mobile-network operators-face-cost-crunch-17700/, 2011.

[3] HAWILO H, SHAMI A, MIRAHMADI M,. NVF: State of the art, challenges, and implementation in next generation mobile networks (vEPC)[J]., 2014, 28(6): 18-26. doi: 10.1109/MNET.2014.6963800.

[4] LI L E, LIAGHAT V, ZHAO H,. PACE: Policy-aware application cloud embedding[C]. IEEE International Conference on Computer Communication, Turin, 2013: 638-646. doi: 10.1109/INFCOM.2013.6566849.

[5] ZHANG Y, BEHESHTI N, BELIVEAU L,. Steering: A software-defined networking for inline service chaining[C]. IEEE International Conference on Network Protocols (ICNP), Rio de Janeiro, 2013: 1-10. doi: 10.1109/ICNP. 2013.6733615.

[6] GIANNOULAKIS I, KAFETZAKIS E, XYLOURIS G,. On the applications of efficient NFV management towards 5G networking[C]. IEEE International Conference on 5G for Ubiquitous Connectivity, Levi, 2014: 1-5. doi: 10.4108/ icst.5gu.2014.2581 33.

[7] MOENS H and DE TURCK F. VNF-P: a model for efficient placement of virtualized network functions[C]. IEEE International Conference on Network and Service Management, Rio de Janeiro, 2014: 418-423. doi: 10.1109/ CNSM.2014.7014205.

[8] CLAYMAN S, MAINI E, GALIS A,. The dynamic placement of virtual network functions[C]. IEEE International Conference on Network Operations and Management Symposium, Krakow, 2014: 1-9. doi: 10.1109/ NOMS.2014.6838412.

[9] XIA M, SHIRAZIPOUR M, ZHANG Y,. Network function placement for NFV chaining in packet/optical datacenters[J]., 2015, 33(8): 1565-1570. doi: 10.1109/JLT.2015.2388585.

[10] YOUSAF F Z, LOUREIRO P, ZDARSKY F,. Cost analysis of initial deployment strategies for virtualized mobile core network functions[J]., 2015, 53(12): 60-66. doi: 10.1109/MCOM.2015.7355586.

[11] MATIAS J, GARAY J, TOLEDO N,. Toward an SDN-enabled NFV architecture[J]., 2015, 53(4): 187-193. doi: 10.1109/MCOM. 2015. 7081093.

[12] AISSIOUI A, KSENTINI A, GUEROUI A M,. Toward elastic distributed SDN/NFV controller for 5G mobile cloud management systems[J]., 2015, 3: 2055-2064. doi: 10.1109/ACCESS.2015.2489930.

[13] BASTA A, KELLERER W, HOFFMANN M,. A virtual SDN-enabled LTE EPC architecture: A case study for S-/P-gateways functions[C]. IEEE International Conference on SDN for Future Networks and Services, Trento, 2013: 1-7. doi: 10.1109/SDN4FNS. 2013.670 2532.

[14] HAN Bo, GOPALAKRISHNAN V, JI Lusheng,. Network function virtualization: Challenges and opportunities for innovations[J]., 2015, 53(2): 90-97. doi: 10.1109/MCOM.2015. 7045396.

[15] MIJUMBI R, SERRAT J, GORRICHO J L,. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]. IEEE Conference on Network Softwarization, London, 2015: 1-9. doi: 10.1109/NETSOFT. 2015.7116120.

Adaptive Deployment Method for Virtualized Network Function Based on Viterbi Algorithm

LIU Caixia LU Ganqiang TANG Hongbo WANG Xiaolei ZHAO Yu

(,450002,)(,100876,)

In order to deal with the explosive growth of mobile data traffic, a novel design of network architecture will be adopted in 5G. Software Defined Network (SDN) and Network Function Virtualization (NFV) are the key technologies for network transformation, which will drive the innovation of mobile communication network architecture. The deployment of Virtualized Network Function (VNF) in service chain is a critical issue in network virtualization. To overcome the ignorance of VNF sequence constraints in service chain and the characteristics of mobile business in existing literatures, an adaptive deployment method of VNF based on Viterbi algorithm is proposed. With real-time perception of the resources change of underlying nodes, the topology structure will be adjusted dynamically. Hidden Markov model is used to describe the topology information of available nodes with resources constraints in underlying network, and the service path with shortest delay is selected based on Viterbi algorithm in candidate service node. Experimental results show that the process time of service chain can be lower compared with existing algorithm. In addition, the acceptance rates of service chain requests and cost efficiency of underlying resources are also raised.

5G; Network Function Virtualization (NFV); Virtualized Network Function (VNF) deployment; Hidden Markov model; Viterbi algorithm; Self-adaption

TN915.81

A

1009-5896(2016)11-2922-09

10.11999/JEIT160045

2016-01-13；改回日期：2016-04-18；

2016-06-16

卢干强 luganqiang@163.com

国家科技重大专项(2013ZX03006002)，国家863计划(2014AA01A701)，国家自然科学基金(61521003)，科技部支撑计划(2014BAH30B01)

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

刘彩霞： 女，1974年生，副教授，研究方向为移动通信网络、新型网络体系结构.

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

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

王晓雷： 男，1982年生，博士生，研究方向为移动通信网络、软件定义网络.

赵 宇： 男，1984年生，博士生，研究方向为移动通信网络、社交网络.