Priority-Based Search for the Virtual Network Embedding Problem

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.

Authors

• Yi Zheng 0010
• Hang Ma 0001
• Sven Koenig
• Erik Kline
• T. K. Satish Kumar

Keywords

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