Abstract

The 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.

Date

2023

Authors

Yi Zheng, Hang Ma, Sven Koenig, Erik Kline, TK Satish Kumar

Journal

Proceedings of the International Conference on Automated Planning and Scheduling

Volume

33

Pages

472-480