A Decomposition Approach for Large Virtual Network Embedding
Abstract
ABSTRACT Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service‐dedicated virtual networks, embedded onto a common substrate network. VNE asks for a minimum‐cost mapping of a virtual network on a substrate network, encompassing simultaneous node placement and edge routing decisions. On a benchmark of large virtual networks with realistic topologies we compiled, the state‐of‐the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse. We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network. This results in a column generation approach whose pricing problems are also VNE problems. This method allows us to compute better lower bounds than state‐of‐the‐art methods. Finally, we devise an efficient Price‐and‐Branch heuristic for large instances.