Priority-Based Search for the Virtual Network Embedding Problem


  • Yi Zheng University of Southern California
  • Hang Ma Simon Fraser University
  • Sven Koenig University of Southern California
  • Erik Kline University of Southern California
  • T. K. Satish Kumar University of Southern California



Applications and case studies of plannin and scheduling techniques, Heuristic search


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.




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.