We address the virtual network embedding problem (VNE) which, given a physical (substrate) network and a collection of virtual networks (VNs), calls for an embedding of the most profitable subset of VNs onto the physical substrate, subject to capacity constraints. In practical applications, node and link demands of the different VNs are, typically, uncertain and difficult to know a priori. To face this issue, we first model VNE as a chance-constrained Mixed-Integer Linear Program (MILP) where the uncertain demands are assumed to be random variables. We then propose a -robust optimization approach to approximate the original chance-constrained formulation, capable of yielding solutions with a large profit that are feasible for almost all the possible realizations of the uncertain demands. To solve larger scale instances, for which the exact approach is computationally too demanding, we propose two MILP-based heuristics: a parametric one, which relies on a parameter setting chosen a priori, and an adaptive one, which does not. We conclude by reporting on extensive computational experiments where the different methods and approaches are compared.

(2016). Data Uncertainty in Virtual Network Embedding: Robust Optimization and Protection Levels [journal article - articolo]. In JOURNAL OF NETWORK AND SYSTEMS MANAGEMENT. Retrieved from http://hdl.handle.net/10446/229297

Data Uncertainty in Virtual Network Embedding: Robust Optimization and Protection Levels

Coniglio, Stefano;
2016

Abstract

We address the virtual network embedding problem (VNE) which, given a physical (substrate) network and a collection of virtual networks (VNs), calls for an embedding of the most profitable subset of VNs onto the physical substrate, subject to capacity constraints. In practical applications, node and link demands of the different VNs are, typically, uncertain and difficult to know a priori. To face this issue, we first model VNE as a chance-constrained Mixed-Integer Linear Program (MILP) where the uncertain demands are assumed to be random variables. We then propose a -robust optimization approach to approximate the original chance-constrained formulation, capable of yielding solutions with a large profit that are feasible for almost all the possible realizations of the uncertain demands. To solve larger scale instances, for which the exact approach is computationally too demanding, we propose two MILP-based heuristics: a parametric one, which relies on a parameter setting chosen a priori, and an adaptive one, which does not. We conclude by reporting on extensive computational experiments where the different methods and approaches are compared.
articolo
Coniglio, Stefano; Koster, Arie M. C. A.; Tieves, Martin
(2016). Data Uncertainty in Virtual Network Embedding: Robust Optimization and Protection Levels [journal article - articolo]. In JOURNAL OF NETWORK AND SYSTEMS MANAGEMENT. Retrieved from http://hdl.handle.net/10446/229297
File allegato/i alla scheda:
File Dimensione del file Formato  
2016-JONS.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 2.59 MB
Formato Adobe PDF
2.59 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229297
Citazioni
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 14
social impact