Improved Conflict-Based Search for the Virtual Network Embedding Problem
- Resource Type
- Conference
- Authors
- Zheng, Yi; Ravi, Srivatsan; Kline, Erik; Thurlow, Lincoln; Koenig, Sven; Kumar, T. K. Satish
- Source
- 2023 32nd International Conference on Computer Communications and Networks (ICCCN) Computer Communications and Networks (ICCCN), 2023 32nd International Conference on. :1-10 Jul, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
Data centers
Runtime
Costs
Heuristic algorithms
Quality of service
Search problems
Distance measurement
network virtualization
virtual network embedding
conflict-based heuristic search
- Language
- ISSN
- 2637-9430
Virtualization is the mechanism of creating virtual representations of physical resources. It is now integrated into almost every facet of computing and is pervasive on the Internet: ranging from data center services and cloud computing services to services on our phones. The common goal for virtualization providers is to ensure that the physical resources are managed efficiently and effectively. This goal induces the Virtual Network Embedding (VNE) problem: the task of properly allocating the physical resources of a network to satisfy virtual requests for resources under various constraints while ensuring the quality of service and maximizing resource utilization. The VNE problem captures many resource allocation tasks arising in computer systems and computer networks. In this paper, we present Improved VNE-CBS (iVNE-CBS) as an efficient and effective algorithm for solving the VNE problem. iVNE-CBS builds on Conflict-Based Search (CBS), a heuristic search framework borrowed from the Multi-Agent Path Finding literature. We show that iVNECBS significantly outperforms popular baseline VNE algorithms: it scales to networks with several hundreds of vertices and thousands of edges, while also producing better-quality solutions.