Optimization models and heuristics for virtual machine placement and migration

Resource management and traffic congestion are two major concerns in modern data centers. The tools currently available to cloud providers are limited to first-principle solutions that do not lead to a proper utilization of resources. In this work, we consider two variants of two problems arising in the context of short-term Virtual Machine placement and longterm resource management of the data center. The short-term problem consists in determining the best allocation of a set of new Virtual Machines on some servers, while the long-term problem consists in periodically updating the placement of already running Virtual Machines. We propose two novel Mixed Integer Linear Programming (MILP) formulations to solve instances of the two problems with up to 128 and 54 servers respectively, for which we are able to obtain the optimal solutions. Then, we develop two Greedy Randomized Adaptive Search Procedures (GRASP) to tackle larger instances with up to 10000 servers. Our two heuristics are able to achieve an average relative gap of approximately 0% and 8% respectively on the instances for which we know the optimal solution. The heuristics have also been tested on the larger instances. The instances are generated using data and parameters derived from real sources.

La gestione delle risorse e la congestione di traffico costituiscono due preoccupazioni rilevanti per i moderni data center. Gli strumenti attualmente disponibili ai cloud provider si limitano a soluzioni di primo principio che non garantiscono on corretto utilizzo delle risorse. In questo lavoro, consideriamo due varianti di due problemi che si presentano nel contesto del collocamento di Virtual Machine nel breve periodo e della gestione di risorse del data center nel lungo periodo. Il problema nel breve periodo consiste nel determinare la migliore allocazione di un insieme di nuove Virtual Machine su alcuni server, mentre il problema nel lungo periodo consiste nell'aggiornare periodicamente il collocamento di Virtual Machine già in esecuzione. Proponiamo due nuove formulazioni di Programmazione Lineare Misto-Intera (MILP) per risolvere istanze dei due problemi fino a 128 e 54 server rispettivamente, per le quali siamo in grado di ottenere le soluzioni ottime. In seguito, sviluppiamo due algoritmi di tipo Greedy Randomized Adaptive Search Procedure (GRASP) per affrontare istanze più grandi fino a 10000 server. Le nostre due euristiche sono in grado di ottenere, in media, un gap relativo di circa 0% e 8% rispettivamente sulle istanze per le quali conosciamo la soluzione ottimale. Le euristiche sono anche state testate sulle istanze di dimensione maggiore. Le istanze sono state generate usando dati e parametri ricavati da fonti reali.