Resolve the virtual network embedding problem: A column generation approach
- 1 April 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, we study the virtual network embedding (VNE) problem in the network virtualization context, which aims at mapping the virtual network requests of the service providers (SPs) to the substrate networks managed by the infrastructure providers (InPs). Given the NP-Completeness of the VNE problem, prior approaches primarily rely on solving/relaxing the link-based Integer Linear Programming (ILP) formulations, which lead to either extensive computational time, or non-optimal solutions. In this paper, for the first time, we present a path-based model for the VNE problem, namely P-VNE. By analyzing the dual formulation of the P-VNE model, we propose a column generation process, with which an optimal solution to the VNE problem can be found efficiently (when embedded into a branch-and-bound framework).Keywords
This publication has 12 references indexed in Scilit:
- Virtual network embedding through topology-aware node rankingACM SIGCOMM Computer Communication Review, 2011
- A virtual network mapping algorithm based on subgraph isomorphism detectionPublished by Association for Computing Machinery (ACM) ,2009
- Network virtualization: state of the art and research challengesIEEE Communications Magazine, 2009
- Rethinking virtual network embeddingACM SIGCOMM Computer Communication Review, 2008
- How to lease the internet in your spare timeACM SIGCOMM Computer Communication Review, 2007
- Algorithms for Assigning Substrate Network Resources to Virtual Network ComponentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Selected Topics in Column GenerationOperations Research, 2005
- Overcoming the Internet impasse through virtualizationComputer, 2005
- Diversifying the InternetPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Corrigendum to our paper “the ellipsoid method and its consequences in combinatorial optimization”Combinatorica, 1984