Virtual Network Embedding With Guaranteed Connectivity Under Multiple Substrate Link Failures

This paper addresses Connectivity-aware Virtual Network Embedding (CoViNE) problem, which consists in embedding a virtual network (VN) on a substrate network while ensuring VN connectivity (without any bandwidth guarantee) against multiple substrate link failures. CoViNE provides a weaker form of survivability incurring less resource overhead than traditional VN survivability models. To optimally solve CoViNE, we present an Integer Linear Program (ILP), namely CoViNE-opt. CoViNE-opt enumerates an exponential number of edge-cuts in a VN severely limiting its scalability. Therefore, we decompose CoViNE into three sub-problems: i) augmenting a VN with virtual links to provide necessary connectivity, ii) identifying the virtual links that should be embedded disjointly, and iii) computing a VN embedding while satisfying the disjointness constraints. We introduce conflicting set abstraction that allows to address sub-problems (i) and (ii) without enumerating all the edge-cuts of a VN. We propose two novel solutions to CoViNE leveraging conflicting set, namely CoViNE-ILP and CoViNE-fast. CoViNE-ILP uses a heuristic algorithm to address sub-problems (i) and (ii), while an ILP is used for sub-problem (iii). In contrast, CoViNE-fast uses heuristics for solving all three sub-problems. Through simulation, we evaluate the optimality and scalability of our solutions and demonstrate a failure restoration use-case enabled by CoViNE.