基于最优加权图匹配的服务功能链部署方法

李丹，兰巨龙，王鹏，胡宇翔



基于最优加权图匹配的服务功能链部署方法

李丹，兰巨龙，王鹏，胡宇翔

（国家数字交换系统工程技术研究中心，河南 郑州 450000）

服务功能链技术通过对虚拟网络功能的编排来支持灵活的网络服务请求。针对资源有限网络中的服务功能链部署问题，提出了一种基于优加权图匹配的服务功能链部署方法，把服务功能链组合为功能拓扑图，利用邻接矩阵特征向量分解算法获取功能拓扑与物理拓扑的加权图匹配方式，并通过爬山算法对匹配结果进一步优化。仿真结果表明，所提方法在降低服务功能链部署所需带宽的同时，优化了节点负载和链路带宽的均衡度，可以支持更多的服务请求，且复杂度低，具有较高的时效性。

服务功能链；加权图匹配；特征向量分解；爬山算法

1 引言

互联网的高速发展和广泛应用，对网络中的新功能和新服务提出了更高的要求。网络功能虚拟化技术（NFV，network function virtualization）[1]通过分离逻辑功能与物理资源，将多样化的网络功能和服务从底层物理资源中抽象出来，改变了传统网络功能的设计和部署方式，可以更加灵活、高效地利用网络资源。NFV技术将传统网络中部署在特定硬件设备上的功能虚拟化为虚拟网络功能，可以根据需要灵活部署在任意一个通用功能平台。在NFV的基础上，服务功能链技术（SFC，service function chaining）[2]将不同的网络功能按照一定的顺序连接起来，支持某种具体的服务请求，实现网络服务的个性化定制。要将虚拟的服务功能链与实际的网络拓扑结合起来，需要将这些功能部署在网络中的节点上，并选择路径使数据依次经过提供这些功能的节点。软件定义网络（SDN, software defined networking）[3]将控制平面和数据平面分离，在控制平面集中计算最优的功能部署位置和数据传输路径，使服务功能链的动态配置和部署成为可能。

为了在网络中提供多样化的服务，需要部署大量功能顺序不同的服务功能链，但是由于网络中的节点处理能力和链路带宽有限，如何在资源有限的条件下尽可能多地部署服务功能链是本文研究的主要问题。目前，针对服务功能链的部署问题已经有了一些相关研究，文献[4]建立了基于SDN架构的服务功能链部署模型，通过统一控制机制来确保功能部署和数据传输的准确性，并举例说明了该架构可以支持的优化目标，但是没有给出具体的部署算法。文献[5-6]以优化数据传输和处理时延为目标，给出了服务功能链部署的问题模型以及优化求解算法。文献[7-8]从时延、分组丢失率、中继节点数等方面建立了多参数混合优化模型，来提高服务功能链的综合服务性能。文献[9-10]通过遗传算法来适应服务功能链对服务质量的动态需求，在网络环境变化时仍能提供较好的服务质量。

以上算法主要针对服务性能进行优化，而没有考虑网络资源的限制。文献[11]以整个网络的带宽资源需求为优化目标，研究了虚拟网络功能的优化部署问题。文献[12]针对同时优化带宽需求和数据传输处理时延的问题，设计了一种启发式搜索算法。文献[13-14]研究了在数据中心网络中部署服务功能链的网络流量均衡算法。文献[15]研究了一种功能合并部署算法，该算法统计各个功能之间的带宽需求，将带宽需求较大的功能合并部署在同一节点上来降低路径带宽。但是这些文献侧重于对带宽资源的优化利用，而缺少对节点处理能力和链路带宽的综合考虑。针对节点处理能力和带宽资源有限的情况，文献[16-17]通过启发式算法来实现降低链路带宽需求和减少功能部署开销之间的平衡。文献[18]将网络中所有节点的剩余处理能力、存储空间和带宽加权组合为节点剩余资源，把服务功能链部署在满足约束条件且剩余资源总和最大的路径上，但是该算法需要遍历所有部署方式，计算复杂度较高。文献[19]将服务功能链分解为多层有向图的组合，通过维特比算法求解每一层的节点选择，但该算法在选择节点的过程中会优先将功能部署在相同节点中，容易导致部分节点负载过重而无法支持新的服务请求。文献[20]将服务功能链的部署问题转化为功能拓扑和物理拓扑的加权图匹配问题，将节点处理能力和链路带宽作为参数来选择符合要求的节点匹配方式，该算法可以快速生成符合传输需求的部署方式，但是会将带宽需求较大的虚拟链路映射为跳数较多的物理传输路径，造成大量带宽损耗，且带宽和负载均衡效果较差。文献[21]提出了一种最优加权图匹配算法，该算法利用特征向量分解算法实现2幅同构加权图的快速匹配，可以较大概率实现最优匹配，即使得到的不是最优解，所得结果仍然可以通过爬山算法修正为最优解，但是该方法对待匹配的加权图有一定的要求，无法直接解决服务功能链部署问题。

基于以上分析，本文提出了一种基于最优加权图匹配的服务功能链部署方法，把相邻的服务功能链组合为功能拓扑图，将功能链的部署问题转化为功能拓扑与物理拓扑的加权图匹配问题，通过对加权图邻接矩阵的扩充和元素替换来满足文献[21]的同构条件，采用邻接矩阵特征向量分解算法和爬山优化算法得到功能和链路的最优匹配。与其他算法相比，本文方法的创新点体现在以下3个方面：1)可以实现多条服务功能链的同时部署，降低计算复杂度，具有较高的时效性；2)通过合理的元素替换，均衡链路匹配过程中路径带宽和传输跳数的关系，避免带宽浪费，节省网络资源；3) 计算节点和链路资源的最优匹配，能够同时均衡全网的节点负载和链路带宽资源，可以支持更多的服务请求。

2 服务功能链部署与加权图匹配问题

2.1 服务功能链部署问题

本文将服务功能链的部署问题建模为一个多约束优化问题，如式(1)~式(3)所示。

2.2 加权图匹配问题

根据定义1，最优加权图匹配问题可表示为式(4)。

其中，()表示匈牙利算法。

利用特征向量分解算法进行加权图匹配需要一定的前提条件，为了利用文献[21]的算法对服务功能链和物理拓扑进行匹配，需要在算法中解决以下3个问题。

1) 在加权图匹配问题中，2幅图的顶点和边的数目相同，但是通常情况下服务功能链中的功能数少于物理拓扑中的节点数。

2) 在加权图匹配问题中，2幅图的链路是一一对应进行匹配的，而在服务功能链的部署过程中，2个相邻功能间的虚拟链路既可以映射为一条物理链路，也可以映射为多条物理链路。

3) 特征向量分解算法要求待匹配的2个图近似同构，但是服务功能链与物理拓扑顶点数不同，链路权值不相关，不满足同构条件。

3 方法设计

3.1 服务功能链组合

本文方法利用最优加权图匹配算法计算功能和链路的映射关系，支持多条服务功能链的同时部署，首先需要将服务功能链组合为功能拓扑图。以图1所示的2条服务功能链为例，将2条功能链中的相同功能合并，图中的功能权值表示该功能需要的节点处理能力，链路权值表示其连接的功能间传输路径所需带宽，需要注意的是，2条功能链重叠部分的权值应为二者之和。

图1 服务功能链组合为功能拓扑

3.2 邻接矩阵扩充

图2 待匹配的功能拓扑与物理拓扑

3.3 矩阵元素替换

在服务功能链的部署过程中，相邻功能既可以匹配到相邻节点，也可以匹配到非相邻节点。为了在链路映射的过程中满足以上要求，需要对物理拓扑邻接矩阵中表示链路带宽的矩阵元素进行替换，为每一对节点选择一条最优路径并更新匹配权值。在文献[20]中，按照最小带宽最大原则为非相邻节点计算路径并以该带宽作为新的链路匹配权值，虽然该方法支持相邻功能与非相邻节点的匹配，但是存在以下2个问题：1) 没有更新相邻节点间的路径带宽，导致相邻节点间直连带宽较小时无法进行链路匹配；2) 最小带宽最大路径很可能需要经过多次转发，路径较长，匹配带宽需求较高的虚拟链路后会造成大量的带宽损耗。为此，算法1为任意一对节点计算一条路径，使该路径的最小带宽与传输跳数的比值最大，并把该比值更新为链路匹配权值，从而均衡路径带宽和传输跳数的关系，避免带宽浪费。

算法1 物理拓扑链路权值更新算法

1) for any nodesandindo //：源节点，：目的节点

2)(1)=,=, hop()=0, label()=0 if¹, label()=10 000 //：已确定节点集合，：转接点，hop：各节点到源节点跳数，label：各节点权值

3） whileis not indo

4) for=1 toandis not indo

6) if label()

7) label()=, hop()=hop()+1,()=

8) end if

9) end for

10)=node with maximum label

11) putinto

12) end

13) path(1)=,=//path：节点和之间的传输路径，：前序节点

14) whileis not in path do

15)=()

16) putinto path

17) end

18) end for

特征向量分解算法要求待匹配的2个加权图近似同构，因此需要进一步对功能拓扑的邻接矩阵元素进行替换，使其与更新后的物理拓扑图同构。替换方法如下。首先，将各功能和各节点分别按照处理能力由大到小的顺序排列，把功能拓扑邻接矩阵中表示处理能力需求的元素依序替换为各节点的剩余处理能力，“0”元素则随机替换为较小的节点处理能力，实现2个加权图的顶点同构。然后，用同样的办法将功能拓扑邻接矩阵中表示带宽需求的元素进行替换，实现2个加权图的边同构，满足文献[21]的算法要求。这种替换方法的目的是，在构建同构加权图的过程中，尽可能将处理能力需求较高的功能和带宽需求较高的链路匹配到剩余资源较多的节点和路径上。图2中功能拓扑的邻接矩阵元素替换过程如式(9)所示，加号两边分别是非“0”元素和“0”元素的替换矩阵。

3.4 特征值分解与匈牙利算法

利用匈牙利算法对该效率矩阵进行求解，得到最优映射函数如式(11)所示。

3.5 爬山优化算法

算法2 映射函数修正爬山算法

1) flag=1 //flag：判断修正过程是否结束标志

2) while flag=1 do

3) flag=0,=||1T−2|| //：映射函数作用后2个图差值

4) for=1 todo

5) for=1 todo

6)=

7) exchange columnand columnof//：交换一对顶点后的映射函数

8)=||1T−2|| //：新的映射函数作用后2个图差值

9) if there is no negative number in1T−2and

10)=,=, flag=1

11) end if

12) end for

13) end for

14) end

3.6 方法流程说明与复杂度分析

图3 本文方法流程示意

4 性能仿真与分析

为了对本文提出的服务功能链部署方法性能进行验证，在2.80 GHz CPU，4 GB内存的PC机上通过Matlab软件进行了仿真实验并对实验结果处理分析。仿真场景设计为，由20个节点构成随机网络拓扑按照Waxman-Salam模型[23]生成，每个节点能够提供的处理能力为50 MHz，每条链路的总带宽为50 Mbit/s。网络可以提供8种功能，每个需要部署的服务功能链由任意顺序排列的2~8个互不相同的功能组成，每个功能需要的处理能力在0~2 MHz之间，每条服务功能链所需带宽在0~5 Mbit/s之间，每个功能拓扑图由2条服务功能链合并生成。为了提高算法评估的精确性，采用蒙特卡洛方法，在每个测试场景下进行了100组仿真测试，取平均值作为测试结果。

本文将平均服务请求处理时间、节点负载均衡度、链路带宽均衡度、平均链路剩余带宽和网络能够支持的最大服务请求数作为方法性能的评价指标，其中节点负载均衡度是指节点剩余处理能力的均方差，链路带宽均衡度是指链路剩余带宽的均方差，并将本文方法与文献[20]中同样采用图匹配策略的特征值分解算法和文献[19]中的多层图算法进行比较。特征值分解算法将非相邻节点间的最大路径带宽更新为链路权值，根据邻接矩阵的特征向量计算效率矩阵，最后采用启发式算法依次为每个功能选择符合限制条件的匹配方式。多层图算法将服务功能链分解为多层有向图，通过维特比算法计算每一层的节点选择代价，最后回溯搜索最优的节点和链路匹配方式。

图4显示了各算法对服务请求的平均处理时间和服务功能链长度的关系。从图中可以看出，多层图算法的平均处理时间和服务功能链的长度近似成正比关系，这是因为该算法的分层数由服务功能链中的功能个数决定，分层数越多需要的计算时间越长。由于本文方法和特征值分解算法的计算复杂度仅与物理拓扑的节点数相关，因此平均处理时间不会随着服务功能链长度的增加而变化，特征值分解算法的处理时间略小于本文方法，是因为本文方法增加了映射函数的修正过程。

图4 平均服务请求处理时间

图5和图6分别给出了服务功能链长度为5时，各算法对节点负载和链路带宽的均衡性能。由于多层图算法优先将功能部署在相同节点上，没有考虑对节点负载和链路带宽的均衡，因此节点剩余处理能力和链路剩余带宽的均方差最高。特征值分解算法根据节点和链路的剩余网络资源对服务功能链进行匹配，但是该算法得到的不是最优匹配，因此带宽和负载的均衡性能介于多层图算法和本文方法之间。由于本文方法在匹配过程中对邻接矩阵进行了同构化处理，可以较大概率实现最优匹配，负载均衡度和带宽均衡度都明显优于其他算法，且本文算法通过爬山算法修正映射函数，进一步优化了对负载和带宽的均衡效果。

图5 节点负载均衡性能

图7给出了服务功能链长度为5时，平均链路剩余带宽随着服务请求增加的变化情况。虽然多层图算法的剩余带宽明显高于其他2种算法，但是由于该算法将功能集中部署在相同节点，使得部分节点因剩余处理能力不足而无法支持新功能的部署，当服务请求数大于40后，新的服务请求难以找到符合限制条件的部署方式。与特征值分解算法相比，本文方法采用带宽与跳数的比值来更新物理拓扑邻接矩阵元素，避免为跳数较多的路径匹配带宽需求较高的虚拟链路，因此部署服务功能链需要的带宽更小。图8给出了3种算法能够支持的最大服务请求数与服务功能链长度的关系。可以看出，本文方法由于降低了带宽损耗，且负载均衡度和带宽均衡度高，因此能够提供的服务请求数明显多于特征值分解和多层图算法，且服务功能链越长，本文方法的优势越明显，这是因为较长的服务功能链对负载和带宽的均衡性能要求更高。

图6 链路带宽均衡性能

图7 平均链路剩余带宽

5 结束语

针对资源有限的网络中的服务功能链部署问题，本文提出了一种基于最优加权图匹配的服务功能链部署方法，把多条服务功能链组合为功能拓扑图，通过邻接矩阵的扩充和元素替换实现功能拓扑图与物理拓扑图的同构，采用邻接矩阵特征向量分解算法快速获取最优加权图匹配方式，并通过爬山算法对匹配结果进一步优化。该方法可以支持多条服务功能链的同时部署，计算复杂度低，具有较高的时效性。与其他算法相比，该方法降低了服务功能链部署所需的链路带宽，对节点负载和链路带宽资源的均衡性能更好，可以在相同的网络资源条件下支持更多的服务请求。下一步研究考虑搭建服务功能链部署原型系统，将本方法在真实环境中进行验证。

图8 最大服务请求数

[1] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: state-of-the-art and research challenges[J]. IEEE Communications Surveys & Tutorials, 2017, 18(1):236-262.

[2] QUINN P, GUICHARD J. Service function chaining: creating a service plane via network service headers[J]. Computer, 2014, 47(11):38-44.

[3] NUNES B A A, MENDONCA M, NGUYEN X N, et al. A survey of software-defined networking: past, present, and future of programmable networks[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3):1617-1634.

[4] LI Y, ZHENG F, CHEN M, et al. A unified control and optimization framework for dynamical service chaining in software-defined NFV system[J]. Wireless Communications IEEE, 2015, 22(6):15-23.

[5] LEE G, KIM M, CHOO S, et al. Optimal flow distribution in service function chaining[C]// The, International Conference on Future Internet. ACM, 2015:17-20.

[6] MARTINI B, PAGANELLI F, CAPPANERA P, et al. Latency-aware composition of virtual functions in 5G[C]// Network Softwarization. IEEE, 2015:1-6.

[7] MEHRAGHDAM S, KELLER M, KARL H. Specifying and placing chains of virtual network functions[C]// IEEE International Conference on Cloud NETWORKING. IEEE, 2014:7-13.

[8] LEIVADEAS A, FALKNER M, LAMBADARIS I, et al. Resource management and orchestration for a dynamic service chain steering model[C]// Global Communications Conference. IEEE, 2017:1-6.

[9] RANKOTHGE W, MA J, LE F, et al. Towards making network function virtualization a cloud computing service[C]// IFIP/IEEE International Symposium on Integrated Network Management. IEEE, 2015:89-97.

[10] OTOKURA M, LEIBNITZ K, KOIZUMI Y, et al. Application of evolutionary mechanism to dynamic Virtual Network Function Placement[C]// IEEE International Conference on Network Protocols. IEEE, 2016:1-6.

[11] SAHHAF S, TAVERNIER W, ROST M, et al. Network service chaining with optimized network function embedding supporting service decompositions[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 93(P3):492-505.

[12] CHUA F C, WARD J, ZHANG Y, et al. Stringer: balancing latency and resource usage in service function chain provisioning[J]. IEEE Internet Computing, 2016, 20(6):22-31.

[13] KLINKOWSKI M, WALKOWIAK K. On advantages of elastic optical networks for provisioning of cloud computing Traffic[J]. IEEE Network, 2013, 27(27):44-51.

[14] ZHANG L, ZHU Z. Spectrum-efficient anycast in elastic optical inter-datacenter networks [J]. Optical Switching & Networking, 2014, 14(4):250-259.

[15] YANG K, ZHANG H, HONG P. Energy-aware service function placement for service function chaining in data centers[C]// Global Communications Conference. IEEE, 2017:1-6.

[16] FANG W, ZENG M, LIU X, et al. Joint Spectrum and it resource allocation for efficient VNF service chaining in inter-datacenter elastic optical networks[J]. IEEE Communications Letters, 2016, 20(8):1539-1542.

[17] KUO T W, LIOU B H, LIN C J, et al. Deploying chains of virtual network functions: On the relation between link and server usage[C]// IEEE International Conference on Computer Communications. IEEE, 2016:1-9.

[18] XIE L, JIANG Y, WANG B, et al. An approach for network function combination based on least busy placement algorithm[J]. China Communications, 2016, 13(S1):167-176.

[19] BARI F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network & Service Management, 2016, PP(99):1-1.

[20] MECHTRI M, GHRIBI C, ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network & Service Management , 2016 , 13 (3) :533-546

[21] UMEYAMA S. An eigendecomposition approach to weighted graph matching problems[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 1988, 10(5):695-703.

[22] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[J]. IEEE Transactions on Acoustics Speech & Signal Processing, 1982, 32(6):1258-1259.

[23] SALAMA H F. Multicast routing for real-time communication of high-speed networks[D]. Raleigh: North Carolina State University, 1996.

Service function chain deployment algorithm based on optimal weighted graph matching

LI Dan, LAN Julong, WANG Peng, HU Yuxiang

National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450000, China

Service function chain can support flexible network service requirement by linking virtual network functions. Aiming at the problem of service function chain deployment in a resource-constrained network, an algorithm for service function chain deployment based on optimal weighted graph matching was proposed. The service function chains was composed into graphs of functional topography, and the optimal matching results between graphs of functional topology and physical topology was obtained using eigendecomposition approach, and furtherly the matching results by hill-climbing method was optimized. Simulation results show that, the proposed algorithm can reduce the required bandwidth to deploy service function chains, balance the load of nodes and bandwidth of links, and support more service requests. What is more, the algorithm has a lower computation complexity and higher time efficience.

service function chain, weighted graph matching, eigendecomposition approach, hill-climbing method

TP393

A

10.11959/j.issn.1000−436x.2019059

2018−05−31；

2019−02−21

国家高技术研究发展计划（“863计划”）基金资助项目（No.2015AA016102）；国家自然科学基金资助项目（No.61521003，No.61702547）

The National High Technology Research and Development Program of China (863 Program) (No.2015AA016102), The National Natural Science Foundation of China (No.61521003, No.61702547)

李丹（1989−），男，辽宁沈阳人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由交换技术。

兰巨龙（1962−），男，河南郑州人，博士，国家数字交换系统工程技术研究中心教授、博士生导师，主要研究方向为网络体系结构、信息安全。

王鹏（1985−），男，河南周口人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由技术。

胡宇翔（1982−），男，河南周口人，博士，国家数字交换系统工程技术研究中心副研究员、硕士生导师，主要研究方向为新型网络体系结构、网络安全。