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

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

通信学报 ›› 2019, Vol. 40 ›› Issue (3): 10-18.doi: 10.11959/j.issn.1000-436x.2019059

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

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

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

修回日期:2019-02-21 出版日期:2019-03-01 发布日期:2019-04-04
作者简介:李丹（1989-），男，辽宁沈阳人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由交换技术。|兰巨龙（1962-），男，河南郑州人，博士，国家数字交换系统工程技术研究中心教授、博士生导师，主要研究方向为网络体系结构、信息安全。|王鹏（1985-），男，河南周口人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由技术。|胡宇翔（1982-），男，河南周口人，博士，国家数字交换系统工程技术研究中心副研究员、硕士生导师，主要研究方向为新型网络体系结构、网络安全。
基金资助:
国家高技术研究发展计划（“863计划”）基金资助项目(2015AA016102);国家自然科学基金资助项目(61521003);国家自然科学基金资助项目(61702547)

Service function chain deployment algorithm based on optimal weighted graph matching

Dan LI,Julong LAN,Peng WANG,Yuxiang HU

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

Revised:2019-02-21 Online:2019-03-01 Published:2019-04-04
Supported by:
The National High Technology Research and Development Program of China (863 Program)(2015AA016102);The National Natural Science Foundation of China(61521003);The National Natural Science Foundation of China(61702547)

摘要/Abstract

摘要：

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

关键词: 服务功能链, 加权图匹配, 特征向量分解, 爬山算法

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.

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

中图分类号:

TP393

李丹,兰巨龙,王鹏,胡宇翔. 基于最优加权图匹配的服务功能链部署方法[J]. 通信学报, 2019, 40(3): 10-18.

Dan LI,Julong LAN,Peng WANG,Yuxiang HU. Service function chain deployment algorithm based on optimal weighted graph matching[J]. Journal on Communications, 2019, 40(3): 10-18.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 23

[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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 10

Metrics

推荐阅读 0

[1]	陈浩, 杨芫, 徐明伟, 裴丹, 尤艺霖. 支持多模态网络的可扩展异构服务功能链并行编排部署系统[J]. 通信学报, 2022, 43(9): 1-11.
[2]	徐泽汐, 庄雷, 张坤丽, 桂明宇. 基于知识图谱的服务功能链在线部署算法[J]. 通信学报, 2022, 43(8): 41-51.
[3]	丁绍虎,谢记超,张鹏,普黎明,谷允捷. 基于风险感知的关键虚拟网络功能动态迁移方法[J]. 通信学报, 2020, 41(4): 102-113.
[4]	王侃,赵楠,李军怀,王怀军. 移动边缘计算网络中联合无线多播的服务功能链部署算法[J]. 通信学报, 2020, 41(10): 37-47.
[5]	赵中楠,王健,郭红微. 基于SDN的自适应路由与波长分配方法[J]. 通信学报, 2019, 40(9): 95-105.
[6]	兰巨龙,金子晋,孙鹏浩,江逸茗,王月. 基于可靠性的服务功能链构建算法[J]. 通信学报, 2019, 40(1): 64-70.
[7]	朱晓荣,张倩. 面向多业务需求的NFV和SDN融合的资源优化算法[J]. 通信学报, 2018, 39(11): 54-62.
[8]	袁泉,汤红波,黄开枝,王晓雷,赵宇. 基于Q-learning算法的vEPC虚拟网络功能部署方法[J]. 通信学报, 2017, 38(8): 172-182.
[9]	李超,胡朋松,海昕. 布尔函数设计中的爬山算法及其改进[J]. 通信学报, 2007, 28(3): 130-133.
[10]	曹明,黄银锋,胡正名,杨义先. 演化设计布尔函数[J]. 通信学报, 2007, 28(11A): 70-73.