Priority-Based Search for the Virtual Network Embedding Problem
Keywords:Applications and case studies of plannin and scheduling techniques, Heuristic search
AbstractThe Virtual Network Embedding (VNE) problem is a constrained optimization problem. It arises in the context of allocating resources on heterogeneous physical networks to provide end-to-end computing services. In this paper, we introduce a new solver, called VNE-PBS, that uses priority-based search (PBS) for solving the VNE problem. VNE-PBS uses a prioritized heuristic search algorithm that explores the space of all possible priority orderings using a systematic depth-first search. The solver is inspired by the success of PBS for the Multi-Agent Path Finding (MAPF) problem and the similarities between the VNE and MAPF problems. We show that VNE-PBS significantly outperforms competing methods on various benchmark instances for both the offline and online versions of the VNE problem.
How to Cite
Zheng, Y., Ma, H., Koenig, S., Kline, E., & Kumar, T. K. S. (2023). Priority-Based Search for the Virtual Network Embedding Problem. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 472-480. https://doi.org/10.1609/icaps.v33i1.27227