text: The Virtual Network Embedding Problem (VNEP) captures the essence of many resource allocation problems of today’s infrastructure providers, which offer their physical computation and networking resources to customers. Customers request resources in the form of Virtual Networks, i.e. as a directed graph which specifies computational requirements at the nodes and communication requirements on the edges. An embedding of a Virtual Network on the shared physical infrastructure is the joint mapping of (virtual) nodes to physical servers together with the mapping of (virtual) edges onto paths in the physical network connecting the respective servers.This work initiates the study of approximation algorithms for the VNEP. Concretely, we study the offline setting with admission control: given multiple request graphs the task is to embed the most profitable subset while not exceeding resource capacities. Our approximation is based on the randomized rounding of Linear Programming (LP) solutions. Interestingly, we uncover that the standard LP formulation exhibits an inherent structural deficit when considering general virtual networks: its solutions cannot be decomposed into valid embeddings. In turn, focusing on the class of cactus request graphs, we devise a novel LP formulation, whose solutions can be decomposed into convex combinations of valid embedding. Proving performance guarantees of our rounding scheme, we obtain the first approximation algorithm for the VNEP in the resource augmentation model.We propose two rounding heuristics and evaluate their performance in an extensive computational study, showing that these consistently yield good solutions (even without augmentations).
  @cite_2: Network virtualization is a promising new resource management approach that allows customized virtual networks (VNs) to be multiplexed on a shared physical infrastructure. In this paper, our focus is on the embedding of VN resources onto this infrastructure. Since this problem is known to be NP-hard, embedding proposals in literature are heuristic-based approaches that restrict the problem space in different dimensions. Limitations of these proposals are: 1) as embedding of VN links and nodes is performed in two separate stages, it may ensue in a high blocking of VN requests and a less efficient usage of substrate resources; and 2) as pricing of embedding resources is based on linear functions, it triggers no competition among VN users in order to maximize infrastructure provider profits. These drawbacks motivate us to propose a mathematical model that makes use of large-scale optimization tools and proposes a Column Generation (CG) formulation of the problem, coupled with branch-and-bound technique or rounding-off heuristic. We also propose a periodical planning of embedding process where profitable VN requests are selected through an auction mechanism. In our experiments with different substrate network topologies and many different VN request patterns, we show a clear advantage of auction-based CG models over present benchmarks .
summary: A column generation approach was proposed by in @cite_2 to efficiently compute solutions to the VNEP by generating feasible mappings on-the-fly subject to a specific cost measure. In particular, compute feasible mappings by relying on heuristics and, if no feasible heuristical solution was found, rely on Mixed-Integer Programming to compute a cost optimal feasible embedding in non-polynomial time. We believe that our work can bridge the gap between the heuristic generation of feasible mappings and the optimal generation of feasible mappings as our approach can be used to compute mappings.