Virtual network embedding : optimization models and heuristics for substrate network expansion

Network virtualization is one of the most promising future Internet technologies. The traditional role of the Internet Service Providers tends to be decoupled into two new figures: on the one hand there is the Infrastructure Provider, who maintains the physical structure (Substrate Network), while on the other hand there are the Service Providers (SPs), in charge of offering end-to-end services. These latter ones pay a certain amount in order to benefit from the Substrate Network resources. Virtual Networks are represented as graphs, with CPU demands associated to each node and bandwidth demands associated to each link. The Substrate Network is a graph whose nodes and links have corresponding CPU and bandwidth capacities. Virtual Network Embedding is the problem of performing an optimal mapping of the Virtual Networks onto the Substrate Network (virtual nodes onto substrate nodes and virtual links onto substrate paths connecting the substrate nodes on which the virtual extreme nodes are mapped). We propose and investigate new variants of the VNE problem, in which we consider the possibility of expanding the substrate links capacity and determine a fair price for the embedding. We have developed different Mixed Integer Linear Programming (MILP) models, adopting the point of view of either the InP or the SPs, depending on the field of application (telecommunications or data centers). After a first part on our general VNE variant for Substrate Network expansion, we focus on the Virtual Networks with star-shaped topology. We amend our exact general MILP models in order to tackle these special cases, by taking into account their specific features. We give 4-index and 3-index formulations and, with the aim of reducing computational time in case of star Virtual Networks, we also describe some heuristic methods based on MILP partial relaxations and greedy procedures. Computational results are reported and discussed to evaluate the performance of the MILP formulations and the heuristics.

La virtualizzazione delle reti rappresenta una delle più promettenti tecnologie nell’ambito delle telecomunicazioni e dei data centers. Vi è la tendenza a sostituire la figura tradizionale dell’Internet Service Provider in due nuovi ruoli: l’Infrastructure Provider (InP) e i Service Providers (SPs). Il primo si occupa della manutenzione fisica della rete, mentre i Service Providers forniscono servizi end-to-end, pagando una certa somma per poter beneficiare delle risorse messe a disposizione nella rete fisica (o di substrato). Le reti virtuali sono rappresentate da grafi, in cui ad ogni nodo è associata una domanda di CPU e ad ogni arco è associata una domanda di banda. La rete fisica è un grafo i cui nodi e archi hanno delle corrispondenti capacità di CPU e banda. Con Virtual Network Embedding viene indicato il processo di mappatura ottimale delle reti virtuali sulla rete di substrato (i nodi virtuali sono mappati su nodi del substrato, gli archi virtuali su cammini del substrato che connettono i nodi di substrato su cui sono mappati i corrispondenti estremi virtuali). Noi proponiamo e analizziamo nuove varianti al problema, in cui è possibile espandere la rete di substrato e introduciamo un problema di pricing per determinare il prezzo dell’embedding. Abbiamo sviluppato diversi modelli di programmazione lineare mista intera (MILP), adottando il punto di vista dell’InP o dei SPs a seconda delle applicazioni (telecomunicazioni o data centers). Dopo una prima parte relativa alla nostra variante generale del problema per l’espansione della rete di substrato, viene posta l’attenzione sulle reti virtuali con struttura a stella. I modelli MILP generali vengono quindi riadattati per questi tipi di reti. Proponiamo formulazioni alternative con 3 o 4 indici per il caso delle stelle e, nel tentativo di ridurre i tempi compuazionali, descriviamo anche metodi euristici basati su rilassamenti parziali delle formulazioni MILP o approcci di tipo greedy. I risultati computazionali sono illustrati e commentati per valutare le performance dei modelli MILP e delle euristiche.