A branch‐and‐price algorithm for the single‐path virtual network embedding problem
Abstract
Network virtualization is a growing trend in the implementation of Internet infrastructures. The Virtual Network Embedding problem is one of the challenges in the virtualization of physical networks. This work shows that finding a feasible solution to this problem is NP‐Hard. However, in practice, it can be solved to optimality by exploiting the problem structure. We propose a new branch‐and‐price algorithm applied to a flow‐based formulation of the problem, and present an extensive computational study performed for instances of distinct topologies and sizes. The results presented attest the efficiency of the branch‐and‐price algorithm in solving the problem.Keywords
Funding Information
- CNPq (462425/2014-2)
This publication has 23 references indexed in Scilit:
- A branch-and-price framework for optimal virtual network embeddingComputer Networks, 2016
- On orchestrating virtual network functions2015
- A novel approach to virtual networks embedding for SDN management and orchestration2014
- Virtual network provisioning across multiple substrate networksComputer Networks, 2011
- A survey of network virtualizationComputer Networks, 2010
- Efficient and dependable overlay networks2008
- Rethinking virtual network embeddingACM SIGCOMM Computer Communication Review, 2008
- How to lease the internet in your spare timeACM SIGCOMM Computer Communication Review, 2007
- Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow ProblemsOperations Research, 2000
- Decomposition Principle for Linear ProgramsOperations Research, 1960