Abstract

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.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.