Novel Location-Constrained Virtual Network Embedding LC-VNE Algorithms Towards Integrated Node and Link Mapping
- 11 March 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 24 (6), 3648-3661
- https://doi.org/10.1109/tnet.2016.2533625
Abstract
This paper tries to solve the location-constrained virtual network embedding (LC-VNE) problem efficiently. We first investigate the complexity of LC-VNE, and by leveraging the graph bisection problem, we provide the first formal proof of the NP-completeness and inapproximability result of LC-VNE. Then, we propose two novel LC-VNE algorithms based on a compatibility graph (CG) to achieve integrated node and link mapping. In particular, in the CG, each node represents a candidate substrate path for a virtual link, and each link indicates the compatible relation between its two endnodes. Our theoretical analysis proves that the maximal clique in the CG is also the maximum one when the substrate network has sufficient resources. With CG, we reduce LC-VNE to the minimumcost maximum clique problem, which inspires us to propose two efficient LC-VNE heuristics. Extensive numerical simulations demonstrate that compared with the existing ones, our proposed LC-VNE algorithms have significantly reduced time complexity and can provide smaller gaps to the optimal solutions, lower blocking probabilities, and higher time-average revenue as well.Keywords
Funding Information
- NCET Project (NCET-11-0884)
- National Natural Science Foundation of China (61371117)
- Fundamental Research Funds for the Central Universities (WK2100060010)
- Natural Science Research Project for Universities in Anhui Province (KJ2014ZD38)
- Strategic Priority Research Program of the Chinese Academy of Sciences (XDA06011202)
This publication has 31 references indexed in Scilit:
- Demonstration of Online Spectrum Defragmentation Enabled by OpenFlow in Software-Defined Elastic Optical NetworksPublished by Optica Publishing Group ,2014
- Resolve the virtual network embedding problem: A column generation approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Virtual Network Embedding with Opportunistic Resource SharingIEEE Transactions on Parallel and Distributed Systems, 2013
- Resource Discovery and Allocation in Network VirtualizationIEEE Communications Surveys & Tutorials, 2012
- ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link MappingIEEE/ACM Transactions on Networking, 2011
- Virtual network embedding through topology-aware node rankingACM SIGCOMM Computer Communication Review, 2011
- Rethinking virtual network embeddingACM SIGCOMM Computer Communication Review, 2008
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Centrality in social networks conceptual clarificationSocial Networks, 1979
- A Fast Merging AlgorithmJournal of the ACM, 1979