基于改进灰狼优化算法的服务功能链映射算法

doi:10.11959/j.issn.1000-0801.2022275

电信科学 ›› 2022, Vol. 38 ›› Issue (11): 57-72.doi: 10.11959/j.issn.1000-0801.2022275

基于改进灰狼优化算法的服务功能链映射算法

张岳, 张俊楠, 吴晓春, 洪晨, 周静静

浙江工商大学信息与电子工程学院（萨塞克斯人工智能学院），浙江杭州 310018

修回日期:2022-10-20 出版日期:2022-11-20 发布日期:2022-11-01
作者简介:张岳（1998- ），女，浙江工商大学硕士生，主要研究方向为知识图谱、新一代网络技术架构
张俊楠（1997- ），男，浙江工商大学硕士生，主要研究方向为新一代网络技术架构
吴晓春（1983- ），女，博士，浙江工商大学高级实验师、硕士生导师，主要研究方向为新一代网络技术架构、软件定义网络、网络功能虚拟化、人工智能与网络安全的结合等
洪晨（1998- ），女，浙江工商大学硕士生，主要研究方向为知识图谱、新一代网络技术架构
周静静（1980- ），女，博士，浙江工商大学副教授、硕士生导师，主要研究方向为新一代网络技术架构、软件定义网络、网络流量建模与分析、大数据处理、深度学习等
基金资助:
浙江省自然科学基金资助项目(LY19F020002);浙江省自然科学基金资助项目(LY19F020006);浙江省新型网络标准与应用技术重点实验室(2013E10012)

Improved grey wolf optimization algorithm based service function chain mapping algorithm

Yue ZHANG, Junnan ZHANG, Xiaochun WU, Chen HONG, Jingjing ZHOU

School of Information and Electronic Engineering (Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018, China

Revised:2022-10-20 Online:2022-11-20 Published:2022-11-01
Supported by:
The Natural Science Foundation of Zhejiang Province(LY19F020002);The Natural Science Foundation of Zhejiang Province(LY19F020006);Zhejiang Key Laboratory of New Network Standards and Application Technology(2013E10012)

摘要/Abstract

摘要：

随着工业互联网、车联网、元宇宙等新型互联网应用的兴起，网络的低时延、可靠性、安全性、确定性等方面的需求正面临严峻挑战。采用网络功能虚拟化技术在虚拟网络部署过程中，存在服务功能链映射效率低与部署资源开销大等问题，联合考虑节点激活成本、实例化开销，以最小化平均部署网络成本为优化目标建立了整数线性规划模型，提出基于改进灰狼优化算法的服务功能链映射（improved grey wolf optimization based service function chain mapping，IMGWO-SFCM）算法。该算法在标准灰狼优化算法基础上添加了基于无环K最短路径（K shortest path，KSP）问题算法的映射方案搜索、映射方案编码以及基于反向学习与非线性收敛改进三大策略，较好地平衡了其全局搜索及局部搜索能力，实现服务功能链映射方案的快速确定。仿真结果显示，该算法在保证更高的服务功能链请求接受率下，相较于对比算法降低了11.86%的平均部署网络成本。

关键词: 网络功能虚拟化, 服务功能链, 资源优化

Abstract:

With the rise of new Internet applications such as the industrial Internet, the Internet of vehicles, and the metaverse, the network’s requirements for low latency, reliability, security, and certainty are facing severe challenges.In the process of virtual network deployment, when using network function virtualization technology, there were problems such as low service function chain mapping efficiency and high deployment resource overhead.The node activation cost and instantiation cost was jointly considered, an integer linear programming model with the optimization goal of minimizing the average deployment network cost was established, and an improved grey wolf optimization service function chain mapping (IMGWO-SFCM) algorithm was proposed.Three strategies: mapping scheme search based on acyclic KSP algorithm, mapping scheme coding and improvement based on reverse learning and nonlinear convergence were added to the standard grey wolf optimization algorithm to form this algorithm.The global search and local search capabilities were well balanced and the service function chain mapping scheme was quickly determined by IMGWO-SFCM.Compared with the comparison algorithm, IMGWO-SFCM reduces the average deployment network cost by 11.86% while ensuring a higher service function chain request acceptance rate.

Key words: network function virtualization, service function chain, resource optimization

中图分类号:

TP393

张岳, 张俊楠, 吴晓春, 洪晨, 周静静. 基于改进灰狼优化算法的服务功能链映射算法[J]. 电信科学, 2022, 38(11): 57-72.

Yue ZHANG, Junnan ZHANG, Xiaochun WU, Chen HONG, Jingjing ZHOU. Improved grey wolf optimization algorithm based service function chain mapping algorithm[J]. Telecommunications Science, 2022, 38(11): 57-72.

图/表 13

表1

图1

图2

图3

图4

图5

图6

表3

表4

图7

图8

图9

图10

参考文献 40

[1]	彭新玉, 周扬, 董振江 . 基于车联网远程驾驶的虚拟资源智能协同管理技术[J]. 电信科学, 2020,36(4): 61-68.
	PENG X Y , ZHOU Y , DONG Z J . Intelligent collaborative management technology of virtual resources based on internet of vehicles remote driving[J]. Telecommunications Science, 2020,36(4): 61-68.
[2]	李卓峰 . 低能耗服务功能链的映射研究[D]. 成都:电子科技大学, 2018.
	LI Z F . Energy-efficient research of service function chain mapping[D]. Chengdu:University of Electronic Science and Technology of China, 2018.
[3]	QU L , ASSI C , SHABAN K . Delay-aware scheduling and resource optimization with network function virtualization[J]. IEEE Transactions on Communications, 2016,64(9): 3746-3758.
[4]	LUIZELLI M C , BAYS L R , BURIOL L S ,et al. Piecing together the NFV provisioning puzzle:efficient placement and chaining of virtual network functions[C]// Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway:IEEE Press, 2015: 98-106.
[5]	MOENS H , DE TURCK F . VNF-P:a model for efficient placement of virtualized network functions[C]// Proceedings of 10th International Conference on Network and Service Management (CNSM) and Workshop. Piscataway:IEEE Press, 2014: 418-423.
[6]	汤红波, 邱航, 游伟 ,等. 基于联合备份的服务功能链可靠性保障的部署方法[J]. 电子与信息学报, 2019,41(12): 3006-3013.
	TANG H B , QIU H , YOU W ,et al. A reliability-guarantee method for service function chain deployment based on joint backup[J]. Journal of Electronics ＆ Information Technology, 2019,41(12): 3006-3013.
[7]	LI J L , SHI W S , YE Q ,et al. Online joint VNF chain composition and embedding for 5G networks[C]// Proceedings of 2018 IEEE Global Communications Conference. Piscataway:IEEE Press, 2018: 1-6.
[8]	孙士清, 彭建华, 游伟 ,等. 5G 网络下资源感知的服务功能链协同构建和映射算法[J]. 西安交通大学学报, 2020,54(8): 140-148.
	SUN S Q , PENG J H , YOU W ,et al. A coordinating composition and mapping algorithm for a service function chain with resource-aware[J]. Journal of Xi'an Jiaotong University, 2020,54(8): 140-148.
[9]	BOUET M , LEGUAY J , COMBE T ,et al. Cost-based placement of vDPI functions in NFV infrastructures[J]. International Journal of Network Management, 2015,25(6): 490-506.
[10]	SUN Q Y , LU P , LU W ,et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]// Proceedings of 2016 IEEE Global Communications Conference. Piscataway:IEEE Press, 2016: 1-6.
[11]	BECK M T , BOTERO J F . Coordinated allocation of service function chains[C]// Proceedings of 2015 IEEE Global Communications Conference. Piscataway:IEEE Press, 2015: 1-6.
[12]	程洪闪, 孟欢, 张晓辉 . 服务功能链的优化映射策略[J]. 计算机与网络, 2021,47(8): 54-56.
	CHENG H S , MENG H , ZHANG X H . Optimized mapping strategy of service function chain[J]. Computer ＆ Network, 2021,47(8): 54-56.
[13]	COHEN R , LEWIN-EYTAN L , NAOR J S ,et al. Near optimal placement of virtual network functions[C]// Proceedings of 2015 IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2015: 1346-1354.
[14]	TAJIKI M M , SALSANO S , CHIARAVIGLIO L ,et al. Joint energy efficient and QoS-aware path allocation and VNF placement for service function chaining[J]. IEEE Transactions on Network and Service Management, 2018,16(1): 374-388.
[15]	YUAN B , REN B B . Embedding the minimum cost SFC with end-to-end delay constraint[C]// Proceedings of 2020 5th International Conference on Mechanical,Control and Computer Engineering (ICMCCE). Piscataway:IEEE Press, 2020: 2299-2303.
[16]	MIRJALILI S , MIRJALILI S S M , LEWIS A . Grey wolf optimizer[J]. Advances in engineering software, 2014(69): 46-61.
[17]	BLIEKLU C , BONAMI P , LODI A . Solving mixed-integer quadratic programming problems with IBM-CPLEX:a progress report[C]// Proceedings of the 26th RAMP Symposium.[S.l.:s.n.], 2014: 16-17.
[18]	GRANT M , BOYD S . CVX:MATLAB software for disciplined convex programming,version 2.1[J]. 2014.
[19]	OPTIMIZATION G . Gurobi optimizer reference manual[Z]. 2020.
[20]	BARI F , CHOWDHURY S R , AHMED R ,et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016,13(4): 725-739.
[21]	TAJIKI M M , SALSANO S , SHOJAFAR M ,et al. Energy-efficient path allocation heuristic for service function chaining[C]// Proceedings of 2018 21st Conference on Innovation in Clouds,Internet and Networks and Workshops (ICIN). Piscataway:IEEE Press, 2018: 1-8.
[22]	CZIVA R , PEZAROS D P . On the latency benefits of edge NFV[C]// Proceedings of 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Piscataway:IEEE Press, 2017: 105-106.
[23]	陈学松, 杨宜民 . 强化学习研究综述[J]. 计算机应用研究, 2010,27(8): 2834-2838,2844.
	CHEN X S , YANG Y M . Reinforcement learning:survey of recent work[J]. Application Research of Computers, 2010,27(8): 2834-2838,2844.
[24]	PEI J N , HONG P L , PAN M ,et al. Optimal VNF placement via deep reinforcement learning in SDN/NFV-enabled networks[J]. IEEE Journal on Selected Areas in Communications, 2019,38(2): 263-278.
[25]	KUO T W , LIOU B H , LIN K C J ,et al. Deploying chains of virtual network functions:on the relation between link and server usage[J]. IEEE/ACM Transactions on Networking, 2018,26(4): 1562-1576.
[26]	MECHTRI M , GHRIBI C , ZEGHLACHE D . A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016,13(3): 533-546.
[27]	ABDEL-BASSET M , ABDEL-FATAH L , SANGAIAH A K . Metaheuristic algorithms:a comprehensive review[M]// Computational Intelligence for multimedia big data on the cloud with engineering applications. Amsterdam: Elsevier, 2018: 185-231.
[28]	MIJUMBI R , SERRAT J , GORRICHO J L ,et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]// Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft). Piscataway:IEEE Press, 2015: 1-9.
[29]	朱国晖, 景文焕, 李世昌 . 基于改进麻雀搜索算法的服务功能链优化映射算法[J]. 计算机应用研究, 2022,39(7): 2120-2123,2131.
	ZHU G H , JING W H , LI S C . Optimized mapping algorithm of service function chain based on improved sparrow search algorithm[J]. Application Research of Computers, 2022,39(7): 2120-2123,2131.
[30]	DWARAKI A , WOLF T . Adaptive service-chain routing for virtual network functions in software-defined networks[C]// Proceedings of the 2016 Workshop on Hot Topics in Middleboxes and Network Function Virtualization.[S.l.:s.n.], 2016: 32-37.
[31]	刘雪, 田云娜, 田园 . 群智能算法研究综述[J]. 信息与电脑(理论版), 2021,33(24): 63-69.
	LIU X , TIAN Y N , TIAN Y . A survey of swarm intelligence methods[J]. China Computer ＆ Communication, 2021,33(24): 63-69.
[32]	徐涛, 丁晓璐, 李建伏 . K最短路径算法综述[J]. 计算机工程与设计, 2013,34(11): 3900-3906,3911.
	XU T , DING X L , LI J F . Review on K shortest paths algorithms[J]. Computer Engineering and Design, 2013,34(11): 3900-3906,3911.
[33]	HERSHBERGER J , MAXEL M , SURI S . Finding the K shortest simple paths:a new algorithm and its implementation[J]. ACM Transactions on Algorithms (TALG), 2007,3(4): 45.
[34]	GUPTA S , DEEP K . Cauchy grey wolf optimiser for continuous optimisation problems[J]. Journal of Experimental ＆ Theoretical Artificial Intelligence, 2018,30(6): 1051-1075.
[35]	GAIDHANE P J , NIGAM M J . A hybrid grey wolf optimizer and artificial bee colony algorithm for enhancing the performance of complex systems[J]. Journal of Computational Science, 2018(27): 284-302.
[36]	XIA X W , LIU J N , LI Y X . Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Journal of Software, 2014,9(2): 350-357.
[37]	MARINI F , WALCZAK B . Particle swarm optimization (PSO).A tutorial[J]. Chemometrics and Intelligent Laboratory Systems, 2015,149: 153-165.
[38]	刘昀 . 虚拟网络功能资源分配与服务功能链路由研究[D]. 合肥:中国科学技术大学, 2020.
	LIU Y . Virtual network function resource allocation and service function chain routing[D]. Hefei:University of Science and Technology of China, 2020.
[39]	MILLS D L , BRAUN H . The NSFNET backbone network[C]// Proceedings of the ACM Workshop on Frontiers in Computer Communications Technology - SIGCOMM '87. New York:ACM Press, 1988: 191-196.
[40]	PEI J N , HONG P L , XUE K P ,et al. Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system[J]. IEEE Transactions on Parallel and Distributed Systems, 2019,30(10): 2179-2192.

优化算法类型	特点
求解器	小规模的网络拓扑时求解速度快，较为复杂的网络模型时求解速度较慢
强化学习	针对优化目标的通用性主要由设置不同的反馈算法来实现，对算法设计者要求高
启发式算法	求解速度较快，但无法保障得到的是全局最优解，且单种启发式算法适用场景和目标有限制
元启发式算法	启发式算法的改进，问题在于面对大规模的物理拓扑时易陷入局部最优解

算法		f ₁(x)	f ₂(x)	f₃(x)	f₄(x)	f₅(x)	f ₆(x)
IMGWO	最优	1.80×10^-50	7.27×10^-31	5.40×10^-14	3.22×10^-14	25.449 1	0.000 2
	平均	1.35×10^-48	7.55×10^-30	3.71×10^-10	1.92×10^-12	26.479 0	0.000 6
	最差	1.21×10^-47	2.68×10^-29	5.13×10^-9	6.72×10^-12	27.186 5	0.001 4
GWO	最优	2.20×10^-35	1.31×10^-20	4.30×10^-11	3.52×10^-9	24.581 7	0.000 2
	平均	1.68×10^-33	8.68×10^-20	5.68×10^-8	2.16×10^-8	26.782 9	0.001 1
	最差	1.82×10^-32	3.95×10^-19	1.20×10^-6	9.06×10^-8	28.758 5	0.002 3
PSO	最优	1.44×10^-6	0.000 3	477.774 9	3.101 21	16.661 8	0.013 79
	平均	0.000 2	0.341 5	1 674.914	5.391 991	6 084.7	0.036 41
	最差	0.001 9	10.001 2	8 203.233	7.874 278	90 063.95	0.058 7

仿真对象	仿真参数	仿真值
NSFNET拓扑	物理节点数	14
	物理链路数	21
	链路带宽资源	1 000 Mbit/s
	节点CPU资源	100 MIPS
	节点内存资源	1 000 MB
	节点激活成本	50
服务功能链请求	单服务功能链VNF数	4,5,6
	入口节点及出口节点	1,13
	带宽需求	(0,10]Mbit/s
虚拟网络功能	类型数	8
	CPU开销及内存开销	每种类型前期确定
	单VNF部署成本	1

基于改进灰狼优化算法的服务功能链映射算法

Improved grey wolf optimization algorithm based service function chain mapping algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 40

相关文章 15

Metrics

推荐阅读 0

[1]	唐鑫新, 曾学文, 凌致远, 宋磊. 可编程数据平面技术综述[J]. 电信科学, 2023, 39(4): 1-16.
[2]	李传煌, 唐晶晶, 陈泱婷, 雷睿, 陈超, 王伟明. 基于拟态防御架构的服务功能链执行体动态调度方法[J]. 电信科学, 2022, 38(4): 101-112.
[3]	吴晓春, 洪晨, 张岳, 张俊楠, 周静静. 基于微服务架构的粒度可变服务功能链映射算法[J]. 电信科学, 2022, 38(12): 11-26.
[4]	全硕, 王旭亮, 朱泽亚. 5G+时代的软件定义安全技术架构研究与实践[J]. 电信科学, 2021, 37(12): 60-71.
[5]	曹畅,张帅,刘莹,唐雄燕. 基于通信云和承载网协同的算力网络编排技术[J]. 电信科学, 2020, 36(7): 55-62.
[6]	刘增义, 雷波, 杨明川. 人工智能在NFV中的应用[J]. 电信科学, 2019, 35(5): 1-8.
[7]	陈天骄,刘江,黄韬. 人工智能在网络编排系统中的应用[J]. 电信科学, 2019, 35(5): 9-16.
[8]	冯博昊,周华春. 移动边缘计算场景下网络服务灵活适配的解决方案[J]. 电信科学, 2019, 35(3): 18-24.
[9]	潘洁,薛曌. 基于Docker的DPI虚拟化部署[J]. 电信科学, 2019, 35(12): 131-136.
[10]	贾海宇,陈佳,王铭鑫. 无线接入网络中网络功能虚拟化研究综述[J]. 电信科学, 2019, 35(1): 97-112.
[11]	毕军,孙晨,于恒. 网络功能虚拟化场景下的并行加速[J]. 电信科学, 2018, 34(7): 41-48.
[12]	王燚,罗凤娅,孙国林. 面向5G RAN的网络切片技术[J]. 电信科学, 2018, 34(3): 124-131.
[13]	王海宁,赵慧玲. NFVO标准和实践[J]. 电信科学, 2017, 33(4): 3-9.
[14]	赵鹏,段晓东. SDN/NFV发展中的关键：编排器的发展与挑战[J]. 电信科学, 2017, 33(4): 18-25.
[15]	魏亮,李蓉,吴正东,张玉亮,程智炜,黄韬. 基于SDN/NFV的未来网络实验平台[J]. 电信科学, 2017, 33(4): 39-47.