Adapting the Conflict-Based Search Framework for the Virtual Network Embedding Problem

Abstract

Virtualization is the mechanism of creating virtual representations of physical resources. It is ubiquitously used in data centers and cloud computing services. The objective of virtualization is to ensure that the physical resources are managed efficiently and effectively. This goal induces the Virtual Network Embedding (VNE) problem: the cornerstone task of properly allocating the physical resources of a network to satisfy requests for resources under various constraints while ensuring the quality of service and maximizing resource utilization. Combinatorially, the VNE problem is a problem in resource management that is NP-hard to solve optimally. In this article, we adapt the Conflict-Based Search (CBS) framework for solving the VNE problem, inspired by its success in the Multi-Agent Path Finding (MAPF) domain. We create two algorithms: VNE-CBS and its improved version Improved VNE-CBS (iVNE-CBS). These algorithms not only successfully address the unique challenges in applying the CBS framework to the VNE problem but also import powerful algorithmic techniques, such as disjoint splitting, bypassing conflicts, and conflict avoidance tables, from the MAPF domain. We show that iVNE-CBS significantly outperforms popular baseline VNE algorithms: It scales to networks with several hundred vertices and thousands of edges—significantly larger than the scale of the networks previously used in the VNE literature—while also producing better-quality solutions. The success of our approach might pave the way for overcoming a crucial issue in Internet ossification via heuristic search methods.