On a network function virtualization orchestration problem with uniform chain allocation and simple path routing : properties and formulation

In traditional telecommunication networks, network services are provided by a variety of expensive commercial hardware appliances that must be installed on network nodes. Therefore, it becomes more and more difficult to integrate and operate the complex hardware based appliances while keeping reasonable costs. Network Functions Virtualization has been recently proposed and is expected to overcome this issue by replacing hardware appliances with Virtual Network Functions (VNF) running on generic servers. The key problem in Network Functions Virtualization is the location and management of cost-efficient VNFs. The VNF Chaining Problem is to locate VNFs and to route a set of demands so as to guarantee that each demand passes through a chain of VNF types that provide the services it needs. In this work we focus on a version of the VNF Chaining Problem that we define as VNF Problem with Uniform Chain Allocation and Simple Path Routing (VNFP-UCSP), where several constraints are taken into account such as the service order constraints, the VNF capacity constraints, the link capacity constraints, and the demand routing constraints including the simple path constraints. The aim of the thesis is to study the VNFP-UCSP properties and computational complexity focusing on the impact of the considered assumptions, and then to derive two formulations based on two modelling strategies proposed in the literature (placement and routing and virtual embedding). The formulations are tested on a set of real life based instances in order to analyse and compare them.

Nelle reti di telecomunicazione tradizionali, i servizi di rete sono forniti da network functions che sono eseguite da una crescente varietà di costosi dispositivi. Pertanto, diventa sempre più difficile integrare e far funzionare i servizi complessi mantenendo costi ragionevoli. Recentemente, una nuova innovazione tecnologica, Network Function Virtualization, è stata proposta per ovviare a questo problema sostituendo i dispositivi con Virtual Network Functions (VNF) che vengono eseguiti su server generici. Il problema chiave nella Network Function Virtualization è il posizionamento delle funzioni virtualizzate sui nodi della rete e la gestione dei costi e dell'efficienza delle VNF. Il VNF Chaining Problem consiste nell'installare le VNF e nell'instradare un insieme di domande in modo da garantire che ogni domanda passi attraverso una catena di tipi di VNF che forniscono i servizi richiesti. In questo lavoro ci concentriamo su una particolare versione del VNF Chaining Problem che definiamo come VNF Problem con posizionamento di una Catena Uniforme e Cammino Semplice (VNFP-UCSP), in cui sono presi in considerazione i seguenti vincoli: ordine dei servizi , capacità dei servizi, capacità degli archi e instradamento della domanda su cammino semplice. Lo scopo della tesi è in primo luogo studiare le proprietà e la complessità computazionale del VNFP-UCSP concentrandosi sull'importanza delle assunzioni considerate, e in secondo luogo sviluppare due formulazioni basate su due strategie di modellazione proposte in letteratura (placement and routing and virtual embedding), analizzarle e confrontarle.