Plan-Based Scalable Online Virtual Network Embedding

Edge computing offers a plethora of opportunities to improve quality of experience by placing applications close to the users. Typically, these applications are implemented as collections of inter-communicating micro-services. To deploy them on the shared edge infrastructure securely and cost-effectively, the micro-services are packaged as virtual functions having resource demands and communication requirements. Given a set of requests for virtualized applications, the edge provider has to deploy a maximum number of them to an underlying physical network, subject to capacity constraints. This is formalized as Virtual Network Embedding (VNE) problem that models applications as virtual networks, in which functions are nodes and communications beteen them are links. We focus on the online variant of VNE, in which deployment requests are not known in advance. This reflects the highly skewed and unanticipated demand intrinsic to the edge. All variants of VNE are known to be strongly NP-hard. Due to its centrality, VNE has been extensively studied. Unfortunately, the existing solutions have limited scalability with the number of requests per second and the physical topology size. We propose a scalable online approach in which an online algorithm uses a pre-computed nearly-optimal embedding for aggregated expected demand, as a blueprint to handle individual requests. We use LP relaxation to compute even very large plans very fast. Furthermore, the algorithm dynamically compensates for deviations from the plan. We show that thanks to combining pre-planning with dynamic handling of deviations, our approach produces nearly optimal results, and scales to a number of requests per time unit greater by an order of magnitude than those reported in the literature. This makes our proposition first of a kind in the sense that it combines scalability of a heuristic with particularly suitable for realistic edge environments.