Virtual network embedding: An optimal decomposition approach

In network virtualization, a traditional ISP collapses into two independent tiers, where the infrastructure provider (InP) manages the physical (or substrate) networks and the service provider (SP) operates the service (or virtual) networks. In this work, we investigate the virtual network embedding (VNE) problem, which bridges above two tiers by mapping the virtual network request to the substrate networks. Existing VNE approaches are either optimal Integer Linear Programming formulations that suffer from extensive computational time, or relaxation/heuristics (mostly decompose the VNE problem into link mapping (LM) and node assignment (NA) sub-problems) that are unable to provide an optimal solution or near-optimal solution with guaranteed quality. In this paper, we attempt to fill this gap with a new VNE solution, which relies on an iterative process enabling feedbacks between the NA, and LM sub-problems (obtained based on the Primal-dual analysis of the VNE problem). With our approach, one can reach either an optimal solution or a near optimal solution with a per-instance guarantee on its closeness to the optimal solution.