An Optimized Algorithm with Low Latency for Virtual Network Function Mapping and Scheduling

LIU Guangyuan; CAO Jingyi; PANG Ziyuan; HUANG Shucui

doi:10.7652/xjtuxb202302013

您当前的位置：

首页 >

文章列表页 >

An Optimized Algorithm with Low Latency for Virtual Network Function Mapping and Scheduling

更新时间：2025-07-09

- An Optimized Algorithm with Low Latency for Virtual Network Function Mapping and Scheduling
- Vol. 57, Issue 2, Pages: 121-130(2023)
- 作者机构：
  
  1. 石家庄铁道大学信息科学与技术学院,石家庄,050043
  2. 河北省电磁环境效应与信息处理重点实验室,石家庄,050043
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb202302013
  CLC： TP393.01
- Online First：10 February 2023，
  
  Published：2023
- 稿件说明：
移动端阅览
LIU Guangyuan, CAO Jingyi, PANG Ziyuan, et al. An Optimized Algorithm with Low Latency for Virtual Network Function Mapping and Scheduling[J]. 2023, 57(2): 121-130.
DOI：

LIU Guangyuan, CAO Jingyi, PANG Ziyuan, et al. An Optimized Algorithm with Low Latency for Virtual Network Function Mapping and Scheduling[J]. 2023, 57(2): 121-130. DOI： 10.7652/xjtuxb202302013.

摘要

针对传统虚拟网络功能映射及调度服务时间长、不稳定的问题

提出了一种新的虚拟网络功能映射及调度优化算法。以虚拟网络功能链路传输时延与实例化时延整体最小化为目标

建立虚拟网络功能映射及调度模型

通过设计一种低时延映射及调度算法(GABL)

根据虚拟网络功能与虚拟机之间的映射集合

优化虚拟网络功能映射节点的选择问题及调度顺序问题

求解出最短时间的网络功能虚拟化映射及调度方案。GABL算法采用两段式初始化技术

将虚拟网络功能和虚拟机分别进行初始化

提高初始解的质量; 利用具有锦标赛策略的人工蜂群算法对问题进行求解

保留优秀基因与种群多样性

避免陷入局部最优; 采用局部搜索算法在可行解附近进行寻优

加快求最优解的速度。仿真实验结果表明:GABL算法具有稳定性强、收敛性快等特点

能够有效降低虚拟网络功能映射及调度服务时间; 与GATS算法相比

GABL算法的服务完成时间减少了15%。

Abstract

Traditional virtual network function mapping and scheduling services are usually time-consuming and unstable. To address this problem

an optimized new algorithm for virtual network function mapping and scheduling is proposed. Firstly

a virtual network function mapping and scheduling model is established to minimize the transmission latency and instantiation latency of virtual network function links as a whole. Then

a low-latency mapping and scheduling algorithm GABL

is designed. According to the mapping set between virtual network functions and virtual machines

the selection of virtual network function mapping nodes and scheduling sequence are optimized

and the virtual network function mapping and scheduling scheme with the least time consumption is concluded. GABL algorithm uses two-stage initialization technology to initialize virtual network functions and virtual machines separately to improve the quality of the initial solution. The artificial bee swarm algorithm with championship strategy is used to solve the problem

preserving excellent gene and population diversity

and avoiding local optimum. Local search algorithm is adopted to search for optimization near the feasible solution

thus speeding up the location of optimal solution. The simulation results show that the GABL algorithm has good stability and fast convergence

and effectively reduces the time of virtual network function mapping and scheduling service. The service completion time of GABL algorithm is reduced by 15% compared with GATS algorithm.

关键词

Keywords

references

LI Biyi, CHENG Bo, LIU Xuan, et al. Joint resource optimization and delay-aware virtual network function migration in data center networks [J]. IEEE Transactions on Network and Service Management, 2021, 18(3): 2960-2974.

HAKIRI A, GOKHALE A, BERTHOU P, et al. Software-defined networking: challenges and research opportunities for future internet [J]. Computer Networks, 2014, 75: 453-471.

王进文, 张晓丽, 李琦, 等. 网络功能虚拟化技术研究进展 [J]. 计算机学报, 2019, 42(2): 415-436.

WANG Jinwen, ZHANG Xiaoli, LI Qi, et al. Network function virtualization technology: a survey [J]. Chinese Journal of Computers, 2019, 42(2): 415-436.

JOSHI K, BENSON T. Network function virtualization [J]. IEEE Internet Computing, 2016, 20(6): 7-9.

孙士清, 彭建华, 游伟, 等. 5G网络下资源感知的服务功能链协同构建和映射算法 [J]. 西安交通大学学报, 2020, 54(8): 140-148.

SUN Shiqing, PENG Jianhua, YOU Wei, 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.

ZHANG Dong, ZHENG Zhifan, LIN Xiang, et al. Dynamic backup sharing scheme of service function chains in NFV [J]. China Communications, 2022, 19(5): 178-190.

王珂, 曲桦, 赵季红. 多域SFC部署中基于强化学习的多目标优化方法 [J]. 计算机科学, 2021, 48(12): 324-330.

WANG Ke, QU Hua, ZHAO Jihong. Multi-objective optimization method based on reinforcement learning in multi-domain SFC deployment [J]. Computer Science, 2021, 48(12): 324-330.

唐伦, 贺兰钦, 连沁怡, 等. 基于改进深度强化学习的虚拟网络功能部署优化算法 [J]. 电子与信息学报, 2021, 43(6): 1724-1732.

TANG Lun, HE Lanqin, LIAN Qinyi, et al. Virtual network function placement optimization algorithm based on improve deep reinforcement learning [J]. Journal of Electronics Information Technology, 2021, 43(6): 1724-1732.

GIL HERRERA J, BOTERO J F. Resource allocation in NFV: a comprehensive survey [J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 518-532.

马景奕, 隋兵, 舒万能. 基于Min-Min遗传算法的网格任务调度方法 [J]. 计算机工程与应用, 2008, 44(23): 102-104.

MA Jingyi, SUI Bing, SHU Wanneng. Task scheduling based on Min-Min genetic algorithm in grid [J]. Computer Engineering and Applications, 2008, 44(23): 102-104.

RIERA J F, HESSELBACH X, ESCALONA E, et al. On the complex scheduling formulation of virtual network functions over optical networks[C]//2014 16th International Conference on Transparent Optical Networks. Piscataway, NJ, USA: IEEE, 2014: 1-5.

RIERA J F, ESCALONA E, BATALLÉ J, et al. Virtual network function scheduling: concept and challenges[C]//2014 International Conference on Smart Communications in Network Technologies. Piscataway, NJ, USA: IEEE, 2014: 1-5.

BECK M T, BOTERO J F. Coordinated allocation of service function chains [C]//2015 IEEE Global Communications Conference. Piscataway, NJ, USA: IEEE, 2015: 1-6.

ZHANG Qixia, XIAO Yikai, LIU Fangming, et al. Joint optimization of chain placement and request scheduling for network function virtualization [C]//2017 IEEE 37th International Conference on Distributed Computing Systems. Piscataway, NJ, USA: IEEE, 2017: 731-741.

王琛, 游伟, 袁泉, 等. 一种基于多层编码遗传算法的虚拟网络功能调度方法 [J]. 信息工程大学学报, 2018, 19(3): 275-281.

WANG Chen, YOU Wei, YUAN Quan, et al. Virtualized network function scheduling method based on multi-layer encoding genetic algorithm [J]. Journal of Information Engineering University, 2018, 19(3): 275-281.

王琛, 汤红波, 游伟, 等. 一种5G网络低时延资源调度算法 [J]. 西安交通大学学报, 2018, 52(4): 117-124.

WANG Chen, TANG Hongbo, YOU Wei, et al. A resource scheduling algorithm with low latency for 5G networks based on effective hybrid genetic algorithm and Tabu search [J]. Journal of Xi'an Jiaotong University, 2018, 52(4): 117-124.

黄睿, 张红旗. 安全服务链中虚拟网络功能分配与调度算法研究 [J]. 计算机应用研究, 2019, 36(3): 890-895.

HUANG Rui, ZHANG Hongqi. Research on algorithm of VNF allocation and scheduling problems in security service chain [J]. Application Research of Computers, 2019, 36(3): 890-895.

史久根, 张径, 徐皓, 等. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略 [J]. 电子与信息学报, 2019, 41(4): 973-979.

SHI Jiugen, ZHANG Jing, XU Hao, et al. Joint optimization of virtualized network function placement and routing allocation for operational expenditure [J]. Journal of Electronics Information Technology, 2019, 41(4): 973-979.

祖家琛, 胡谷雨, 严佳洁, 等. 网络功能虚拟化下服务功能链的资源管理研究综述 [J]. 计算机研究与发展, 2021, 58(1): 137-152.

ZU Jiachen, HU Guyu, YAN Jiajie, et al. Resource management of service function chain in NFV enabled network: a survey [J]. Journal of Computer Research and Development, 2021, 58(1): 137-152.

YAO Hong, XIONG Muzhou, LI Hui, et al. Joint optimization of function mapping and preemptive scheduling for service chains in network function virtualization [J]. Future Generation Computer Systems, 2020, 108: 1112-1118.

KANG Rui, HE Fujun, SATO T, et al. Virtual network function allocation to maximize continuous available time of service function chains with availability schedule [J]. IEEE Transactions on Network and Service Management, 2021, 18(2): 1556-1570.

GIANNOULAKIS I, KAFETZAKIS E, XYLOURIS G, et al. On the applications of efficient NFV management towards 5G networking[C]//1st International Conference on 5G for Ubiquitous Connectivity. Piscataway, NJ, USA: IEEE, 2014: 1-5.

贺桂娇, 周树亮, 冯冬青. 求解高维复杂优化问题的改进人工蜂群算法 [J]. 计算机工程与应用, 2018, 54(12): 126-132.

HE Guijiao, ZHOU Shuliang, FENG Dongqing. Improved artificial bee algorithm for high dimensional complex optimization problems [J]. Computer Engineering and Applications, 2018, 54(12): 126-132.

黄歆雨. 基于混合遗传算法的柔性作业车间动态调度问题研究 [D]. 福州: 福州大学, 2016.

季少梅. 柔性路径下基于混合粒子群算法的跨单元调度方法 [D]. 北京: 北京理工大学, 2011.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Function Mapping and Scheduling Method of Virtual Network Combining Genetic Algorithm and Reinforcement Learning

A Multi-Member Artificial Bee Colony Algorithm for Constrained Optimization Problems

Integrated Intelligent Algorithms for Global Optimization

A Resource Scheduling Algorithm with Low Latency for 5G Networks Based on Effective Hybrid Genetic Algorithm and Tabu Search

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Related Author

LIU Guangyuan

CAO Jingyi

DU Jie

王翔 1

郑建国 1

魏平

徐成贤

Related Institution

Glorious Sun School of Business and Management, Donghua University

School of Civil Engineering, Zhengzhou Institute of Aeronautical Industry Management

School of Sciences, Xi'an Jiaotong University

National Digital Switching System Engineering and Technological Research Center

National Engineering Laboratory for Mobile Network Security

⁰