Service function chain deployment algorithm based on optimal weighted graph matching

Dan LI; Julong LAN; Peng WANG; Yuxiang HU

doi:10.11959/j.issn.1000-436x.2019059

您当前的位置：

首页 >

文章列表页 >

Service function chain deployment algorithm based on optimal weighted graph matching

Papers | 更新时间：2024-06-05

- Service function chain deployment algorithm based on optimal weighted graph matching
- Journal on Communications Vol. 40, Issue 3, Pages: 10-18(2019)
- 作者机构：
  
  国家数字交换系统工程技术研究中心，河南郑州 450000
- 作者简介：
- 基金信息：
  
  The National High Technology Research and Development Program of China (863 Program)(2015AA016102);The Innovation Group Program Project of National Natural Science Foundation of China(61521003);The National Natural Science Foundation of China(61702547)
- DOI：10.11959/j.issn.1000-436x.2019059
  CLC： TP393
- Online First：2019-03，
  
  Published：25 March 2019
- 稿件说明：
移动端阅览
Dan LI, Julong LAN, Peng WANG, et al. Service function chain deployment algorithm based on optimal weighted graph matching[J]. Journal on Communications, 2019, 40(3): 10-18.
DOI：

Dan LI, Julong LAN, Peng WANG, et al. Service function chain deployment algorithm based on optimal weighted graph matching[J]. Journal on Communications, 2019, 40(3): 10-18. DOI： 10.11959/j.issn.1000-436x.2019059.

摘要

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

Abstract

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.

关键词

Keywords

references

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 .

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

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 .

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 .

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 .

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

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 .

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 .

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 .

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 .

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 .

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 .

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

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

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 .

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 .

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 .

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 .

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 .

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

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

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

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

Views

1421

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Service function chain orchestration mechanism on embedded DPU

Parallel orchestration and deployment system for scalable heterogeneous service function chain supporting polymorphic network

Online placement algorithm of service function chain based on knowledge graph

Service function chain embedding algorithm with wireless multicast in mobile edge computing network

Dynamic migration method of key virtual network function based on risk awareness

Related Author

Li Yuting

Hao Jiakai

Qiu Xuesong

Guo Shaoyong

Xing Ruopeng

Yuan YANG

Hao CHEN

Mingwei XU

Related Institution

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

State Grid Beijing Electric Power Company

Department of Computer Science and Technology, Tsinghua University

Beijing National Research Center for Information Science and Technology (BNRist)

Zhongguancun Laboratory

AI问答

⁰