Please use this identifier to cite or link to this item:
For citation please use:
Main Title: On the Hardness and Inapproximability of Virtual Network Embeddings
Author(s): Rost, Matthias
Schmid, Stefan
Type: Article
Language Code: en
Abstract: 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, over the embedding of batch-processing workloads 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 and edge routing policies, and latency restrictions. While the VNEP 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 VNEP by systematically analyzing its hardness for any combination of the above stated node and edge mapping restrictions. For all studied variants the NPcompleteness of their respective decision problems is shown. Furthermore, NP-completeness 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 VNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P=NP holds. Secondly, we uncover structural hardness properties: the VNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.
Issue Date: 5-Mar-2020
Date Available: 19-May-2021
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): network virtualization
virtual network embeddings
computational complexity
Sponsor/Funder: BMBF, 01IS12056, Software Campus (TU Berlin)
EC/H2020/679158/EU/Resolving the Tussle in the Internet: Mapping, Architecture, and Policy Making/ResolutioNet
Journal Title: IEEE/ACM Transactions on Networking
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Publisher Place: New York, NY
Volume: 28
Issue: 2
Publisher DOI: 10.1109/TNET.2020.2975646
Page Start: 791
Page End: 803
EISSN: 1558-2566
ISSN: 1063-6692
Notes: © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Appears in Collections:FG Internet Network Architectures (INET) » Publications

Files in This Item:

Accepted manuscript

Format: Adobe PDF | Size: 919.75 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.