A branch-and-price framework for optimal virtual network embedding

Network virtualization promises a future Internet that can facilitate technology revolutions via decoupling the traditional Internet Service Providers (ISPs) into the infrastructure providers (InPs), and the service providers (SPs). This separation introduces an extra layer of abstraction, thus allowing independent innovations at both the hardware level and service level. In this paper, we study the fundamental virtual network embedding (VNE) problem in network virtualization, which aims at mapping the virtual network request of the SPs to the substrate networks managed by the InPs. Given the NP-Completeness of the VNE problem, prior approaches primarily rely on the solving of the link-based Integer Linear Programming (ILP) formulations, relaxations, and heuristics. In this study, we first present a compact path-based ILP model. Moreover, we present a branch-and-price framework that embeds a column generation process to solve the proposed ILP model. Our framework can lead to optimal solution to the VNE problem, or near optimal solution with per-instance guarantee on its closeness to the optimal solution.