On distributed virtual network embedding with guarantees
Files
Accepted manuscript
Date
2016-02
Authors
Esposito, Flavio
Di Paola, Donato
Matta, Ibrahim
Version
OA Version
Accepted manuscript
Citation
Flavio Esposito, Donato Di Paola, Ibrahim Matta. 2016. "On Distributed Virtual Network Embedding With Guarantees." IEEE/ACM Transactions on Networking, v. 24, Issue 1, pp. 569 - 582. https://doi.org/10.1109/TNET.2014.2375826
Abstract
To provide wide-area network services, resources from different infrastructure providers are needed. Leveraging the consensus-based resource allocation literature, we propose a general distributed auction mechanism for the (NP-hard) virtual network (VNET) embedding problem. Under reasonable assumptions on the bidding scheme, the proposed mechanism is proven to converge, and it is shown that the solutions guarantee a worst-case efficiency of (1-(1/e)) relative to the optimal node embedding, or VNET embedding if virtual links are mapped to exactly one physical link. This bound is optimal, that is, no better polynomial-time approximation algorithm exists, unless P=NP. Using extensive simulations, we confirm superior convergence properties and resource utilization when compared to existing distributed VNET embedding solutions, and we show how by appropriate policy design, our mechanism can be instantiated to accommodate the embedding goals of different service and infrastructure providers, resulting in an attractive and flexible resource allocation solution.
Description
License
Copyright notice: "© 2018 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."