Network Function Virtualization (NFV) has been emerging as an appealing solution that transforms complex network functions from dedicated hardware implementations to software instances running in a virtualized environment. In this survey, we provide an overview of recent advances of resource allocation in NFV. We generalize and analyze four representative resource allocation problems, namely, (1) the VNF Placement and Traffic Routing problem, (2) VNF Placement problem, (3) Traffic Routing problem in NFV, and (4) the VNF Redeployment and Consolidation problem. After that, we study the delay calculation models and VNF protection (availability) models in NFV resource allocation, which are two important Quality of Service (QoS) parameters. Subsequently, we classify and summarize the representative work for solving the VPTR problem and the VRC problem by considering various QoS parameters (e.g., cost, delay, reliability and energy) and different scenarios (e.g., edge cloud, online provisioning and distributed provisioning). Finally, we conclude our survey with a short discussion on the state-of-the-art of literatures and emerging topics in the related field, and highlight areas where we expect high potential for future research.

Mobile Edge Computing (MEC) offers a way to shorten the cloud servicing delay by building the small-scale cloud infrastructures at the network edge, which are in close proximity to the end users. Moreover, Network Function Virtualization (NFV) has been an emerging technology that transforms from traditional dedicated hardware implementations to software instances running in a virtualized environment. In NFV, the requested service is implemented by a sequence of Virtual Network Functions (VNF) that can run on generic servers by leveraging the virtualization technology. Service Function Chaining (SFC) is defined as a chain-ordered set of placed VNFs that handles the traffic of the delivery and control of a specific application. NFV therefore allows to allocate network resources in a more scalable and elastic manner, offer a more efficient and agile management and operation mechanism for network functions and hence can largely reduce the overall costs in MEC. In this paper, we study the problem of how to place VNFs on edge and public clouds and route the traffic among adjacent VNF pairs, such that the maximum link load ratio is minimized and each user's requested delay is satisfied. We consider this problem for both totally ordered SFCs and partially ordered SFCs. We prove that this problem is NP-hard, even for the special case when only one VNF is requested. We subsequently propose an efficient randomized rounding approximation algorithm to solve this problem. Extensive simulation results show that the proposed approximation algorithm can achieve close-to-optimal performance in terms of acceptance ratio and maximum link load ratio.

Mobile Edge Computing (MEC) offers a way to shorten the cloud servicing delay by building the small-scale cloud infrastructures such as cloudlets at the network edge, which are in close proximity to end users. On one hand, it is energy consuming and costly to place each cloudlet on each Access Point (AP) to process the requested tasks. On the other hand, the service provider should provide delay-guaranteed service to end users, otherwise they may get revenue loss. In this paper, we first model how to calculate the task completion delay in MEC and mathematically analyze the energy consumption of different equipments in MEC. Subsequently, we study how to place cloudlets on the network and allocate each requested task to cloudlets and public cloud with the minimum total energy consumption without violating each task’s delay requirement. We prove that this problem is NP-hard and propose a Benders Decomposition-based algorithm to solve it. We also present a Software-Defined Network (SDN)-based framework to deploy the proposed algorithm. Extensive simulations reveal that the proposed algorithm can achieve an (close-to-)optimal performance in terms of energy consumption and acceptance ratio compared with two benchmark heuristics.

The efficacy of Network Function Virtualization (NFV) depends critically on (1) where the virtual network functions (VNFs) are placed and (2) how the traffic is routed. Unfortunately, these aspects are not easily optimized, especially under time-varying network states with different QoS requirements. Given the importance of NFV, many approaches have been proposed to solve the VNF placement and Service Function Chaining (SFC) routing problem. However, those prior approaches mainly assume that the network state is static and known, disregarding dynamic network variations. To bridge that gap, we leverage Markov Decision Process (MDP) to model the dynamic network state transitions. To jointly minimize the delay and cost of NFV providers and maximize the revenue, we first devise a customized Deep Reinforcement Learning (DRL) algorithm for the VNF placement problem. The algorithm uses the attention mechanism to ascertain smooth network behavior within the general framework of network utility maximization (NUM). We then propose attention mechanism-based DRL algorithm for the SFC routing problem, which is to find the path to deliver traffic for the VNFs placed on different nodes. The simulation results show that our proposed algorithms outperform the state-of-the-art algorithms in terms of network utility, delay, cost, and acceptance ratio.

With the proliferation of Internet-of-Things (IoT), zillions of bytes of data are generated at the network edge, incurring an urgent need to push the frontiers of artificial intelligence (AI) to network edge so as to fully unleash the potential of the IoT big data. To materialize such a vision which is known as edge intelligence, federated learning is emerging as a promising solution to enable edge nodes to collaboratively learn a shared model in a privacy-preserving and communication-efficient manner, by keeping the data at the edge nodes. While pilot efforts on federated learning have mostly focused on reducing the communication overhead, the computation efficiency of those resource-constrained edge nodes has been largely overlooked. To bridge this gap, in this paper, we investigate how to coordinate the edge and the cloud to optimize the system-wide cost-efficiency of federated learning. Leveraging Lyapunov optimization theory, we design and analyze a cost-efficient optimization framework CEFL to make online yet near-optimal control decisions on admission control, load balancing, data scheduling and accuracy tuning for the dynamically arrived training data samples, reducing both computation and communication cost. In particular, our control framework CEFL can be flexibly extended to incorporate various design choices and practical requirements of federated learning, such as exploiting the cheaper cloud resource for model training with better cost-efficiency yet still facilitating on-demand privacy preservation. Via both rigorous theoretical analysis and extensive trace-driven evaluations, we verify the cost-efficiency of our proposed CEFL framework.

Network Function Virtualization (NFV) has been emerging as an appealing solution that transforms from dedicated hardware implementations to software instances running in a virtualized environment. In NFV, the requested service is implemented by a sequence of Virtual Network Functions (VNF) that can run on generic servers by leveraging the virtualization technology. These VNFs are pitched with a predefined order, and it is also known as the Service Function Chaining (SFC). Considering that the delay and resiliency are two important Service Level Agreements (SLA) in a NFV service, in this paper, we first investigate how to quantitatively model the traversing delay of a flow in both totally ordered and partially ordered SFCs. Subsequently, we study how to calculate the VNF placement availability mathematically for both unprotected and protected SFCs. After that, we study the delay-sensitive Virtual Network Function (VNF) placement and routing problem with and without resiliency concerns. We prove that this problem is NP-hard under two cases. We subsequently propose an exact Integer Nonlinear Programming formulation and an efficient heuristic for this problem in each case. Finally, we evaluate the proposed algorithms in terms of acceptance ratio, average number of used nodes and total running time via extensive simulations.