Virtual Network Embedding with Survivable Routing

Abstract

In this paper, we address the problem of embedding a Virtual Network (VN) on a substrate network in such a way that the VN remains connected in the event of single substrate link failure, which is called the Survivable Routing of VN Embedding (SRVNE) problem. We first establish an Integer Linear Programming (ILP) for the SRVNE problem. Then we put forward a heuristic algorithm called Cut-set Aware VN Embedding (CA-VNE) to solve this ILP problem. CA-VNE consists of a breadth-first node mapping strategy to reduce the substrate resource cost of VN embedding and a novel cut-set aware link mapping strategy to guarantee the routing survivability of the VN. Simulation results show that CA-VNE can effectively obtain the VN embedding solution with survivable routing while achieving almost the same revenue for the Infrastructure Provider (InP) as the existing approach without providing routing survivability guarantee.