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.
Funding Information
  • BMBF Software Campus (01IS1205)
  • European Research Council (ERC-StG-679158, ERC-COG-864228)

This publication has 23 references indexed in Scilit: