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

doi:10.11959/j.issn.1000-0801.2022275

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 13

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

算法		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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 40

Related Articles 15

Metrics

Recommended 0

[1]	Xinxin TANG, Xuewen ZENG, Zhiyuan LING, Lei SONG. Overview of programmable data plane technology [J]. Telecommunications Science, 2023, 39(4): 1-16.
[2]	Chuanhuang LI, Jingjing TANG, Yangting CHEN, Rui LEI, Chao CHEN, Weiming WANG. Dynamic scheduling method of service function chain executors based on the mimic defense architecture [J]. Telecommunications Science, 2022, 38(4): 101-112.
[3]	Xiaochun WU, Chen HONG, Yue ZHANG, Junnan ZHANG, Jingjing ZHOU. Variable granularity service function chain mapping algorithm based on microservice architecture [J]. Telecommunications Science, 2022, 38(12): 11-26.
[4]	Shuo QUAN, Xuliang WANG, Zeya ZHU. Research and practice of software-defined security technology architecture in the 5G+ era [J]. Telecommunications Science, 2021, 37(12): 60-71.
[5]	Zengyi LIU, Bo LEI, Mingchuan YANG. Application of artificial intelligence in NFV [J]. Telecommunications Science, 2019, 35(5): 1-8.
[6]	Haiyu JIA,Jia CHEN,Mingxin WANG. Survey on network function virtualization in RAN [J]. Telecommunications Science, 2019, 35(1): 97-112.
[7]	Yujia LUO,Liang OU,Hong TANG. Bearing thinking of edge computing based on NFV [J]. Telecommunications Science, 2018, 34(8): 153-159.
[8]	Yuan ZHANG. Architecture and key technologies of network on demand for small and medium enterprises [J]. Telecommunications Science, 2018, 34(7): 7-14.
[9]	Fengchao FU,Peng WANG,Yu MAO,Yongmei HUANG,Xiaobing GAO,Aihua ZHANG,Guoqiang LIN. Realization of vOLT and development trend [J]. Telecommunications Science, 2018, 34(7): 157-161.
[10]	Yanbin SHI,Qi YU,Xiaojun XIE. Operation support system blue print and evolution strategy for SDN/NFV [J]. Telecommunications Science, 2018, 34(6): 171-182.
[11]	Yi WANG,Fengya LUO,Guolin SUN. Network slice technology in 5G radio access network [J]. Telecommunications Science, 2018, 34(3): 124-131.
[12]	Xu YANG,Ziyu XIAO,Yongping SHAO,Xiaoming SONG. Discussion on the reliability of NFV [J]. Telecommunications Science, 2017, 33(7): 136-143.
[13]	Yongqing ZHU,Xia GONG,Huanan CHEN. SFP selection algorithm for SFC [J]. Telecommunications Science, 2017, 33(5): 113-118.
[14]	Haining WANG,Huiling ZHAO. NFVO standards and practice [J]. Telecommunications Science, 2017, 33(4): 3-9.
[15]	Peng ZHAO,Xiaodong DUAN. Key of SDN/NFV development:development and challenge of orchestrator [J]. Telecommunications Science, 2017, 33(4): 18-25.