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

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

作者机构：National Digital Switching System Engineering and Technological Research Center 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2018年第61卷第9期

页      面：93-111页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：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 virtual network function scheduling genetic algorithm bandwidth allocation convex optimization 

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