Virtual Network Embedding with Opportunistic Resource Sharing
- 7 March 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 25 (3), 816-827
- https://doi.org/10.1109/tpds.2013.64
Abstract
Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NP-hardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators' sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes.Keywords
This publication has 27 references indexed in Scilit:
- The only constant is changePublished by Association for Computing Machinery (ACM) ,2012
- An Opportunistic Resource Sharing and Topology-Aware mapping framework for virtual networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- FELL: A Flexible Virtual Network Embedding Algorithm with Guaranteed Load BalancingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Adaptive virtual network provisioningPublished by Association for Computing Machinery (ACM) ,2010
- QoS Performance Analysis of Cognitive Radio-Based Virtual Wireless NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Diversifying the InternetPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Approximation AlgorithmsPublished by Springer Science and Business Media LLC ,2003
- Finding the k shortest pathsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Linear Programming Approach to the Cutting-Stock ProblemOperations Research, 1961
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952