Research On Resource Allocation In Network Function Virtualization

Traditional telecommunication networks are built from proprietary devices,and network functions of network services are proprietary devices.Service provisioning in these networks has long product cycles,low service agility,and heavy dependency on proprietary hardware.These drawbacks make it extremely difficult to provide agile and diverse services in traditional networks.Network Function Virtualization(NFV)has been proposed to address these issues,which uses virtualization technology to implement hardwarebased network functions as software-based Virtualized Network Functions(VNFs)and instantiates these VNFs on common servers without purchasing new hardware.NFV provides a new paradigm for designing,deploying,and managing network services.NFV improves the network flexibility while reducing the Capital Expense(CAPEX)and Operating Expense(OPEX).Although NFV offers many benefits,many challenges need to be addressed to adopt NFV.In this dissertation,we study the resource allocation problem in NFV in dynamic scenarios,including VNF placing problem and NFV provisioning problem in the cloud.The main contributions are as follows:1.Research on performance guaranteed VNF placing algorithm based on online primal-dual algorithm.Considering the dynamics in NFV networks,we propose a performance provable algorithm DAFT,based on an online primal-dual framework and transforms the subproblem into a problem that can be solved by the Dijkstra's algorithm.This makes DAFT achieve provable performance while maintaining low computation complexity.The theoretical analysis shows that the competitive ratio of DAFT is(1-1/e),where e ? 2.7183.Besides,we propose an improved algorithm,called FDAFT,to resolve the problem that DAFT may violate the capacity.The simulation results show that DAFT and FDAFT outperform the compared algorithm in terms of competitive ratio.2.Research on buffer-aware VNF placing algorithm based on Lyapunov optimization.Considering the stability of buffers(queues),we study the VNF placing problem in dynamic networks.We propose an online algorithm to solve this problem,called MACRO.Besides,to bound the worst-case delay encountered by service requests,we propose an improved algorithm,called WEB-MACRO.Both algorithms achieve an optimality gap of O(1/V),where V is a tunable parameter that controls the tradeoff between cost and backlogs.The backlogs maintained by MACRO are bounded by O(V)and the backlogs maintained by WEB-MACRO are upper bounded which accordingly bounds the worstcase delay encountered by service requests.The simulation results suggest that MACRO and WEB-MACRO achieve queue stability and reduce the total cost compared with the state-of-the-art method.3.Research on VNF-FG placing algorithm based on GNN and DRL.Complex network services are represented as Virtual Network Function Forwarding Graphs(VNFFGs)which are Directed Acyclic Graphs(DAGs).We study the VNF-FG placing problem in dynamic scenarios.To fully exploit the special graph structures of services and handle the complexity of dynamic networks,we combine Graph Neural Network(GNN)with Deep Reinforcement Learning(DRL)and propose an efficient algorithm for VNF-FG placing,called Kolin.The simulation results suggest that Kolin outperforms the state-ofthe-art solutions in terms of system cost,acceptance ratio,and computation complexity.4.Research on VNF migrations constrained VNF placing algorithm based on combinational algorithm.We study how to restrict VNF migrations while reducing servers for placing VNFs.We propose a VNF placing algorithm,called SIVA,based on a combinational algorithm that solves the online bin packing problem.The theoretical analysis shows that SIVA migrates at most ? VNFs at each step,and achieves an Asymptotic Competitive Ratio(ACR)of 3/2 if k ? ?,where ? = k · |N|,k is a tunable parameter,and |N|is the number of VNF types.The simulation results show that SIVA reduces servers by leveraging small amounts of VNF migrations,and outperforms the compared algorithms.5.Research on VNF provisioning algorithm in stochastic cloud environment based on MPC.Due to the advantages of NFV,Network Function Virtualization Providers(NFVPs)are trying to offer NFV services by deploying VNFs in the cloud.However,existing VNF provisioning solutions ignored the dynamics of the cloud environment,which may lead to high cost.Considering both the fluctuation of the cloud price and service traffic rates,we study how NFVPs should purchase the cloud resources to reduce cost.We propose an algorithm,called VINOS,based on Model Predictive Control(MPC),where the Long Short Term Memory(LSTM)networks are used to predict the cloud price and service traffic rates.The simulation results suggest that VINOS achieves near-optimal performance,and outperforms the benchmark algorithms.