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

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

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于最优加权图匹配的服务功能链部署方法
- Service function chain deployment algorithm based on optimal weighted graph matching
- 通信学报 2019年40卷第3期页码：10-18
- 作者机构：
  
  国家数字交换系统工程技术研究中心，河南郑州 450000
- 作者简介：
  
  [ "李丹（1989-），男，辽宁沈阳人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由交换技术。" ]
  [ "兰巨龙（1962-），男，河南郑州人，博士，国家数字交换系统工程技术研究中心教授、博士生导师，主要研究方向为网络体系结构、信息安全。" ]
  [ "王鹏（1985-），男，河南周口人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为新型网络体系结构、路由技术。" ]
  [ "胡宇翔（1982-），男，河南周口人，博士，国家数字交换系统工程技术研究中心副研究员、硕士生导师，主要研究方向为新型网络体系结构、网络安全。" ]
- 基金信息：
  
  国家高技术研究发展计划（“863”计划）基金资助项目(2015AA016102);国家自然科学基金创新群体基金资助项目(61521003);国家自然科学基金资助项目(61702547)
- DOI：10.11959/j.issn.1000-436x.2019059
  中图分类号： TP393
- 网络出版日期：2019-03，
  
  纸质出版日期：2019-03-25
- 稿件说明：
移动端阅览
李丹, 兰巨龙, 王鹏, 等. 基于最优加权图匹配的服务功能链部署方法[J]. 通信学报, 2019,40(3):10-18.

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.
李丹, 兰巨龙, 王鹏, 等. 基于最优加权图匹配的服务功能链部署方法[J]. 通信学报, 2019,40(3):10-18. DOI： 10.11959/j.issn.1000-436x.2019059.

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 .

浏览量

803

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

支持多模态网络的可扩展异构服务功能链并行编排部署系统

基于知识图谱的服务功能链在线部署算法

移动边缘计算网络中联合无线多播的服务功能链部署算法

基于风险感知的关键虚拟网络功能动态迁移方法