Conflict-Based Search for the Virtual Network Embedding Problem

Abstract

In emerging network virtualization architectures, service providers will be able to create many heterogeneous virtual networks and offer customized end-to-end services by leasing shared resources from infrastructure providers. The Virtual Network Embedding (VNE) problem is central to such technology. It involves the proper allocation of CPU and bandwidth resources available in a physical substrate network to meet the demands of multiple virtual networks. Combinatorially, the VNE problem is a problem in resource management that is NP-hard to solve. In this paper, we present a novel version of the Conflict-Based Search (CBS) algorithm for solving the VNE problem. Our approach, called VNE-CBS, is inspired by the success of the CBS framework in the Multi-Agent Path Finding domain. We successfully address the unique challenges in applying the CBS framework to the VNE problem, and, in doing so, we pave the way for overcoming a crucial issue in Internet ossification via heuristic search methods. On the theoretical front, we show that, unlike many existing algorithms, our algorithm is complete and optimal. On the experimental front, we show that our algorithm significantly outperforms other state-of-the-art methods on various benchmark instances for both the offline and online versions of the VNE problem.