Charting the Complexity Landscape of Virtual Network Embeddings
Charting the Complexity Landscape of Virtual Network Embeddings
复制标题
DOI：
10.23919/ifipnetworking.2018.8696604
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Matthias Rost;S. Schmid
中科院分区：
文献类型：
--
作者：
Matthias Rost;S. Schmid
Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): 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 (from where the problem originated), over the embedding of batch-processing workloads (virtual clusters) to the embedding of service function chains. The different applications come with their own specific requirements and constraints, including node mapping constraints, routing policies, and latency constraints. While the VNEP has been studied intensively over the last years, complexity results are only known for specific models and we lack a comprehensive understanding of its hardness.This paper charts the complexity landscape of the VNEP by providing a systematic analysis of the hardness of a wide range of VNEP variants, using a unifying and rigorous proof framework. In particular, we show that the problem of finding a feasible embedding is ${{\mathcal{N}}}{{\mathcal{P}}}$-complete in general, and, hence, the VNEP cannot be approximated under any objective, unless ${{\mathcal{P}}} = {{\mathcal{N}}}{{\mathcal{P}}}$ holds. Importantly, we derive ${{\mathcal{N}}}{{\mathcal{P}}}$-completeness results also for finding approximate embeddings, which may violate, e.g., capacity constraints by certain factors. Lastly, we prove that our results still pertain when restricting the request graphs to planar or degree-bounded graphs.
Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): 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 (from where the problem originated), over the embedding of batch-processing workloads (virtual clusters) to the embedding of service function chains. The different applications come with their own specific requirements and constraints, including node mapping constraints, routing policies, and latency constraints. While the VNEP has been studied intensively over the last years, complexity results are only known for specific models and we lack a comprehensive understanding of its hardness.This paper charts the complexity landscape of the VNEP by providing a systematic analysis of the hardness of a wide range of VNEP variants, using a unifying and rigorous proof framework. In particular, we show that the problem of finding a feasible embedding is ${{\mathcal{N}}}{{\mathcal{P}}}$-complete in general, and, hence, the VNEP cannot be approximated under any objective, unless ${{\mathcal{P}}} = {{\mathcal{N}}}{{\mathcal{P}}}$ holds. Importantly, we derive ${{\mathcal{N}}}{{\mathcal{P}}}$-completeness results also for finding approximate embeddings, which may violate, e.g., capacity constraints by certain factors. Lastly, we prove that our results still pertain when restricting the request graphs to planar or degree-bounded graphs.