Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Virtual Network Embedding Approximations: Leveraging Randomized Rounding
Author(s): Rost, Matthias
Schmid, Stefan
Type: Article
Language Code: en
Abstract: The Virtual Network Embedding Problem (VNEP) captures the essence of many resource allocation problems. In the VNEP, customers request resources in the form of Virtual Networks. An embedding of a virtual network on a shared physical infrastructure is the joint mapping of (virtual) nodes to physical servers together with the mapping of (virtual) edges onto paths in the physical network connecting the respective servers. This work initiates the study of approximation algorithms for the VNEP for general request graphs. Concretely, we study the offline setting with admission control: given multiple requests, the task is to embed the most profitable subset while not exceeding resource capacities. Our approximation is based on the randomized rounding of Linear Programming (LP) solutions. Interestingly, we uncover that the standard LP formulation for the VNEP exhibits an inherent structural deficit when considering general virtual network topologies: its solutions cannot be decomposed into valid embeddings. In turn, focusing on the class of cactus request graphs, we devise a novel LP formulation, whose solutions can be decomposed. Proving performance guarantees of our rounding scheme, we obtain the first approximation algorithm for the VNEP in the resource augmentation model. We propose different types of rounding heuristics and evaluate their performance in an extensive computational study. Our results indicate that good solutions can be achieved even without resource augmentations. Specifically, heuristical rounding achieves 77.2% of the baseline’s profit on average while respecting capacities.
Issue Date: 23-Sep-2019
Date Available: 21-Jan-2020
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): network virtualization
virtual network embeddings
approximation algorithms
linear programming
lineare Programmierung
Einbettung virtueller Netze
Sponsor/Funder: BMBF, 01IS12056, Software Campus Grant
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: 27
Issue: 5
Publisher DOI: 10.1109/TNET.2019.2939950
Page Start: 2071
Page End: 2084
EISSN: 1558-2566
ISSN: 1063-6692
Notes: © 2019 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:
Format: Adobe PDF | Size: 2.64 MB
DownloadShow Preview

Item Export Bar

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