Improved grey wolf optimization algorithm based service function chain mapping algorithm

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

doi:10.11959/j.issn.1000-0801.2022275

您当前的位置：

首页 >

文章列表页 >

Improved grey wolf optimization algorithm based service function chain mapping algorithm

Research and Development | 更新时间：2024-06-05

- Improved grey wolf optimization algorithm based service function chain mapping algorithm
- Telecommunications Science Vol. 38, Issue 11, Pages: 57-72(2022)
- 作者机构：
- 作者简介：
- 基金信息：
  
  Zhejiang Key Laboratory of New Network Standards and Application Technology(2013E10012)
- DOI：10.11959/j.issn.1000-0801.2022275
  CLC： TP393
- Published Online：2022-11，
  
  Published：20 November 2022
- 稿件说明：
移动端阅览
Yue ZHANG, Junnan ZHANG, Xiaochun WU, et al. Improved grey wolf optimization algorithm based service function chain mapping algorithm[J]. Telecommunications science, 2022, 38(11): 57-72.
DOI：

Yue ZHANG, Junnan ZHANG, Xiaochun WU, et al. Improved grey wolf optimization algorithm based service function chain mapping algorithm[J]. Telecommunications science, 2022, 38(11): 57-72. DOI： 10.11959/j.issn.1000-0801.2022275.

摘要

随着工业互联网、车联网、元宇宙等新型互联网应用的兴起，网络的低时延、可靠性、安全性、确定性等方面的需求正面临严峻挑战。采用网络功能虚拟化技术在虚拟网络部署过程中，存在服务功能链映射效率低与部署资源开销大等问题，联合考虑节点激活成本、实例化开销，以最小化平均部署网络成本为优化目标建立了整数线性规划模型，提出基于改进灰狼优化算法的服务功能链映射（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.

关键词

Keywords

references

彭新玉 , 周扬 , 董振江 . 基于车联网远程驾驶的虚拟资源智能协同管理技术 [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 .

李卓峰 . 低能耗服务功能链的映射研究 [D ] . 成都:电子科技大学 , 2018 .

LI Z F . Energy-efficient research of service function chain mapping [D ] . Chengdu:University of Electronic Science and Technology of China , 2018 .

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 .

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 .

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 .

汤红波 , 邱航 , 游伟 , 等 . 基于联合备份的服务功能链可靠性保障的部署方法 [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 .

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 .

孙士清 , 彭建华 , 游伟 , 等 . 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 .

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 .

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 .

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 .

程洪闪 , 孟欢 , 张晓辉 . 服务功能链的优化映射策略 [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 .

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 .

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 .

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 .

MIRJALILI S , MIRJALILI S S M , LEWIS A . Grey wolf optimizer [J ] . Advances in engineering software , 2014 ( 69 ): 46 - 61 .

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 .

GRANT M , BOYD S . CVX:MATLAB software for disciplined convex programming,version 2.1 [J ] . 2014 .

OPTIMIZATION G . Gurobi optimizer reference manual [Z ] . 2020 .

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 .

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 .

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 .

陈学松 , 杨宜民 . 强化学习研究综述 [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 .

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 .

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 .

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 .

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 .

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 .

朱国晖 , 景文焕 , 李世昌 . 基于改进麻雀搜索算法的服务功能链优化映射算法 [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 .

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 .

刘雪 , 田云娜 , 田园 . 群智能算法研究综述 [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 .

徐涛 , 丁晓璐 , 李建伏 . 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 .

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 .

GUPTA S , DEEP K . Cauchy grey wolf optimiser for continuous optimisation problems [J ] . Journal of Experimental ＆ Theoretical Artificial Intelligence , 2018 , 30 ( 6 ): 1051 - 1075 .

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 .

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 .

MARINI F , WALCZAK B . Particle swarm optimization (PSO).A tutorial [J ] . Chemometrics and Intelligent Laboratory Systems , 2015 , 149 : 153 - 165 .

刘昀 . 虚拟网络功能资源分配与服务功能链路由研究 [D ] . 合肥:中国科学技术大学 , 2020 .

LIU Y . Virtual network function resource allocation and service function chain routing [D ] . Hefei:University of Science and Technology of China , 2020 .

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 .

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 .

Views

465

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Variable granularity service function chain mapping algorithm based on microservice architecture

Research and practice of software-defined security technology architecture in the 5G+ era

User allocation technology for multi-dimensional resource optimization of LEO satellite

Overview of programmable data plane technology

Dynamic scheduling method of service function chain executors based on the mimic defense architecture

Related Author

Xiaochun WU

Chen HONG

Yue ZHANG

Junnan ZHANG

Jingjing ZHOU

Zeya ZHU

Xuliang WANG

Shuo QUAN

Related Institution

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

National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences

University of Chinese Academy of Sciences

Sichuan Communication Science Planning and Design Co.,Ltd.

University of Electronic Science and Technology of China

⁰