Virtual network function scheduling via multilayer encoding genetic algorithm with distributed bandwidth allocation

• 来源期刊: 中国科学（信息科学）
• 关键词: network function virtualization virtual network function scheduling genetic algorithm bandwidth allocation convex optimization
• 年，卷（期）: 2018,（9）
• 页码范围: 87-105
• 页数: 19页
• 语种: 中文

摘要

Network function virtualization represents a revolutionary approach to network service deployment.This software-oriented approach for virtual network functions (VNFs) deployment enables more flexible and dynamic network services to meet diversified demands.To minimize the execution time of all VNFs in service function chains,VNF scheduling must be addressed.In this paper,we improve upon the flexible job-shop model by introducing the process of bandwidth allocation.First,we propose a multilayer encoding genetic algorithm to solve the VNF scheduling model.In addition,we design a distributed method for bandwidth allocation based on the Nash bargaining solution.Finally,by combining the genetic algorithm with distributed bandwidth allocation,we present a heuristic algorithm that solves the VNF scheduling problem in one stage.Using a multilayer encoding genetic algorithm,we simplify the constraints of the VNF scheduling problem and reduce its time complexity.At the same time,our Nash game solution refines the granularity of bandwidth allocation to further reduce the transmission delay between VNFs.The effectiveness of our proposed heuristic algorithm is verified through numerical evaluation.Compared with existing approaches,our method exhibits shorter scheduling time and reduces CPU time by 45％ in simulated scenarios.