Resolve the virtual network embedding problem: A column generation approach

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).