Efficient heuristics for virtual network embedding with substrate network expansion

Network virtualization is an important paradigm for future Internet and telecommunication systems. Virtualization enables to manage the networks' resources in a highly flexible and dynamic way. In most of the new proposed business models, the figure of the Internet Service Provider is decoupled into two new figures: the Service Provider, whose aim is to offer customized services modeled as virtual networks (VNs), and the Infrastructure Provider, that is in charge to mantain the physical substrate network (SN). Determine how to map virtual network requests on a physical shared substrate network, is the well known Virtual Network Embedding problem. In this work, we investigate a VNE variant arising in the field of telecommunications where the point of view of the Infrastructure Provider is adopted. The goal is to determine how to (eventually) expand the substrate network capacities in order to be able to accept all the available star-shaped virtual network requests and to determine fair prices for the VNs in order to cover the total expansion cost. After showing that this VNE problem with substrate network expansion is NP-hard, we present a Mixed Integer Linear Programming (MILP) formulation and we report and discuss some computational results for some realistic instances. Since this problem turns out to be challenging from the computational point of view even for small size instances, we present several MILP-based and greedy heuristics to tackle larger size instances. To evaluate the quality of the solutions provided by the heuristics, we propose a column generation method to yield tighter dual bounds. The reported computational results show that the best MILP-based proposed heuristic provides close to optimal solutions even for the more challenging considered instances. To further improve the performance of the proposed algorithms, we also investigate the benefits that can provide different solver's tunings and some advanced search strategies like proximity search and local branching. To conclude, in the last part of the thesis we describe some algorithms to tackle the interesting variant of the VNE with substrate network expansion, whose aim is to minimize the number of substrate nodes used during the embedding process while leaving unchanged a certain maximum bandwidth unit price.

La virtualizzazione di reti è uno dei nuovi paradigmi per l'Internet del futuro e per i sistemi di telecomunicazioni. La virtualizzazione permette di gestire le risorse delle reti in maniera altamente flessibile e dinamica. Nella maggior parte dei nuovi modelli di business proposti, la figura dell' Internet Service Provider è suddivisa in due nuove figure: il Service Provider, il cui obiettivo è quello di offrire servizi personalizzati modellati come reti virtuali (VNs), e l'Infrastructure Provider, che è incaricato di mantenere la rete fisica di substrato. Determinare come mappare le richieste virtuali di rete sulla rete di substrato, corrisponde al ben noto problema del Virtual Network Embedding. In questo lavoro consideriamo una variante del VNE per il campo delle delle telecomunicazioni dove viene adottato il punto di vista dell'Infrastructure Provider. L'obiettivo è quello di determinare come (eventualmente) espandere le capacità della rete di substrato in modo da essere in grado di accettare tutte le richieste di rete virtuali a forma di stella disponibili e di determinare prezzi equi per le VNs in modo tale da coprire il costo di espansione. Dopo aver mostrato che questa variante del VNE è un problema NP-hard, presentiamo una formulazione MILP e riportiamo i risultati per alcune istanze realistiche. Dato che il problema risulta essere difficile dal punto di vista computazionale anche per le istanze più piccole, presentiamo diversi algoritmi basati o su euristiche di tipo MILP-based o su euristiche di tipo greedy per affrontare le instanze più grandi. Al fine di valutare la qualità delle soluzioni fornite dalle euristiche, proponiamo un approccio di tipo column generation per fornire bounds duali più stringenti. I risultati computazionali che vengono riportati, mostrano che la migliore euristica MILP-based tra quelle proposte fornisce soluzioni che sono vicine all'ottimo anche per le istanze più difficili tra quelle considerate. Per migliorare ulteriormente le prestazioni degli algoritmi proposti, indaghiamo sui benefici che possono fornire un certo setup dei paremetri del solver e l'applicazione di strategie di ricerca avanzate come la proximity search ed il local branching. Nella parte conclusiva del nostro lavoro, descriviamo alcuni algoritmi per poter affrontare una variante interessante del problema di VNE in cui è ammessa l'espansione della rete fisica, il cui obiettivo è quello di minimizzare il numero di nodi di substrato che vengono usati durante il processo di mappatura lasciando invariato un certo prezzo massimo di unità di banda.