ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping
Top Cited Papers
- 14 July 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 20 (1), 206-219
- https://doi.org/10.1109/tnet.2011.2159308
Abstract
Network virtualization allows multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. Efficient mapping of virtual nodes and virtual links of a VN request onto substrate network resources, also known as the VN embedding problem, is the first step toward enabling such multiplicity. Since this problem is known to be NP-hard, previous research focused on designing heuristic-based algorithms that had clear separation between the node mapping and the link mapping phases. In this paper, we present ViNEYard-a collection of VN embedding algorithms that leverage better coordination between the two phases. We formulate the VN embedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to obtain a linear program and devise two online VN embedding algorithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. We also present a generalized window-based VN embedding algorithm (WiNE) to evaluate the effect of lookahead on VN embedding. Our simulation experiments on a large mix of VN requests show that the proposed algorithms increase the acceptance ratio and the revenue while decreasing the cost incurred by the substrate network in the long run.Keywords
This publication has 27 references indexed in Scilit:
- PolyViNEPublished by Association for Computing Machinery (ACM) ,2010
- Designing and embedding reliable virtual infrastructuresPublished by Association for Computing Machinery (ACM) ,2010
- A virtual network mapping algorithm based on subgraph isomorphism detectionPublished by Association for Computing Machinery (ACM) ,2009
- A Distributed Virtual Network Mapping AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Algorithms for Assigning Substrate Network Resources to Virtual Network ComponentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Dynamic Topology Configuration in Service Overlay Networks: A Study of Reconfiguration PoliciesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Improved approximation algorithms for unsplittable flow problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Algorithms for provisioning virtual private networks in the hose modelIEEE/ACM Transactions on Networking, 2002
- A competitive analysis of the list update problem with lookaheadTheoretical Computer Science, 1998
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987