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

作　　者：Quan YUAN Hongbo TANG Wei YOU Xiaolei WANG Yu ZHAO 

机构地区：[1]National Digital Switching System Engineering and Technological Research Center, Zhengzhou 450002, china

出　　处：《Science China(Information Sciences)》2018年第9期87-105,共19页中国科学（信息科学）（英文版）

基　　金：supported by Foundation for Innovative Research Groups of National Natural Science Foundation of China(Grant No.61521003);National Key Research and Development Program of China(Grant No.2016YFB0801605)

摘　　要：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.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.

关 键 词：network function virtualization virtual network function scheduling genetic algorithm band-width allocation convex optimization 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP393.0[自动化与计算机技术—控制科学与工程]