On the Hardness and Inapproximability of Virtual Network Embeddings
- 5 March 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 28 (2) , 791-803
Abstract
Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (NP-hardVNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds, over the embedding of batch-processing tasks to the embedding of service function chains and come with different mapping restrictions for nodes and edges. The restrictions studied most often are node and edge capacities, node mapping, edge routing and latency restrictions. While the NP-hardVNEP has been studied intensively, complexity results are only known for specific models and this paper provides a first comprehensive study of the computational complexity of the NP-hardVNEP by systematically analyzing its hardness for any combination of the above stated mapping restrictions. For all studied variants the NP-hardNPcompleteness of the respective decision problems is shown. Furthermore, NP-hardNPcompleteness results for finding approximate embeddings, which may, e.g., violate capacity constraints by certain factors, are derived. Lastly, it is also shown that all these results pertain when restricting the request graphs to planar and degree-bounded graphs. While theoretic in nature, our results have severe practical implications. Firstly, any optimization variant of the NP-hardVNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P=NP. Secondly, we uncover structural hardness properties: the NP-hardVNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.Keywords
Funding Information
- BMBF Software Campus (01IS1205)
- European Research Council (ERC-StG-679158, ERC-COG-864228)
This publication has 23 references indexed in Scilit:
- Beyond the StarsACM SIGCOMM Computer Communication Review, 2015
- It's About Time: On Optimal Virtual Network Embeddings under Temporal Flexibilities2014
- Competitive and deterministic embeddings of virtual networksTheoretical Computer Science, 2013
- What we talk about when we talk about cloud network performanceACM SIGCOMM Computer Communication Review, 2012
- Towards predictable datacenter networks2011
- Introducing the Virtual Network Mapping Problem with Delay, Routing and Location ConstraintsLecture Notes in Computer Science, 2011
- A survey of graph layout problemsACM Computing Surveys, 2002
- Subgraph Isomorphism in Planar Graphs and Related Problems2002
- The complexity of induced minors and related problemsAlgorithmica, 1995
- On the complexity of integer programmingJournal of the ACM, 1981