UNIVERSIT`
A DI PISA
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE
Dottorato di Ricerca in Ingegneria dell’Informazione
Relazione dell’Allievo Giuseppe PORTALURI sull’attivit`
a svolta
nell’ambito del I, II e III anno del Corso di Dottorato, ciclo XXX
Tutori: Prof. Stefano Giordano,
Attivit`a di ricerca
Primo anno
L’attivit`a di ricerca affrontata durante il primo anno di Dottorato ha riguardato l’allocazione di risorse computazionali e di rete all’interno del Cloud Data Center (DC). Il DC modellato `e composto da un insieme di server e di switch collegati tra loro secondo una topologia Three-Tier Fat Tree; switch e server nel DC adottano uno specifico modello di consumo di potenza. Il problema in esame appartiene alla classe dei problemi di ottimizzazione multi-obiettivo nel quale si cerca di migliorare le prestazioni del DC in termini di tempo di completamento e di numero di risorse allocate, minimizzando contemporaneamente il consumo di potenza di tutti i server e gli switch.
Il problema in esame `e una variante multi-obiettivo del problema del Bin Packaging che appartiene alla classe dei problemi NP-Hard. Pertanto, al fine di ricercare efficientemente soluzioni al problema che consentano una rapida allocazione delle risorse, sono stati adoperati gli Algoritmi Genetici Multi-obiettivo (MOGA), un particolare tipo di euristiche che si ispirano al naturale processo evolutivo. Nei MOGA, le soluzioni vengono cercate a partire da un insieme di soluzioni iniziali (detto popolazione) che evolvono tramite ricombinazione ed alterazione delle soluzioni di partenza. Ad ogni iterazione vengono generate nuove soluzioni e, poich´e il numero di elementi nella popolazione deve essere mantenuto costante, le migliori vengono selezionate e mantenute per le iterazioni successive.
Inizialmente l’attivit`a di ricerca si `e concentrata sull’allocazione di task sui server del DC; i task devono eseguire un certo numero di istruzioni e necessitano di un bit-rate medio per poter comunicare verso l’esterno. L’applicazione dei MOGA su questo caso di studio ha consentito di ottenere un fronte di Pareto di soluzioni possibili, garantendo tempi di esecuzione rapidi, mostrando una complessit`a computazionale quadratica nel numero dei task e riuscendo ad allocare su un DC di 1536 server, 20.000 task in 60 secondi. In seguito, `e stato ulteriormente potenziato il modello in modo tale da consentire l’allocazione di Macchine Virtuali (VM) all’interno del DC. Ogni VM ha quattro diversi requisiti: CPU, RAM, Disco fisso e un bit-rate medio garantito per comunicare con l’esterno del DC. La formulazione del problema prevede sempre l’ottimizzazione degli obiettivi considerati in precedenza e vincola le VM ad essere allocate in modo tale da non consentire la congestione sui link di rete.
Sono stati utilizzati due diversi approcci per risolvere il problema dell’allocazione: MOGA combinato con Simulated Annealing (SA) per effettuare un’allocazione statica e la logica Fuzzy per eseguire un’allocazione dinamica delle VM. SA `e un’euristica di ricerca locale delle soluzioni, simile alla discesa del gradiente, che utilizza un parametro detto temperatura per evitare gli ottimi locali. La temperatura assume all’inizio della ricerca assume valori pi`u alti, decrescendo monotonicamente fino al termine della computazione. Questo parametro `e correlato con la probabilit`a di accettare anche soluzioni che non migliorano quella precedentemente trovata in modo tale da evadare dagli ottimi (massimi o minimi) locali. Tale probabilit`a diminuisce insieme alla temperatura nel corso delle iterazioni. La logica fuzzy `e una logica in cui si pu`o
-attribuire ad una qualsiasi proposizione un grado di verit`a compreso tra 0 e 1 tramite particolari funzioni dette funzioni di appartenenza.
Il primo dei due approcci `e stato confrontato con una formalizzazione ridotta a singolo obiettivo del problema risolto tramite CPLEX. I risultati ottenuti mostrano come sia possibile allocare efficacemente fino a 2.000 VM tramite l’approccio MOGA mentre CPLEX limita la sua esecuzione ad un numero massimo di VM pari a 100 e, nel caso in esame, la ricerca della soluzione ottimale richiede ore mentre la ricerca delle soluzioni tramite le due euristiche ha permesso di ottenere gli stessi risultati (per quanto riguarda il singolo obiettivo considerato) in pochi secondi. Il secondo approccio `e stato paragonato con altri tre metodi analitici con l’obiettivo di allocare dinamicamente il maggior numero di nuove VM. L’allocatore basato sulla logica Fuzzy utilizza due metodi, quelli di Mandami e Sugeno, e ciascuno di essi `e stato confrontato con gli altri tre metodi seguendo tre euristiche di allocazione, First Fit (FF), Best Fit (BF) e Worst Fit (WF). L’approccio Fuzzy ha consentito di allocare un numero maggiore di VM rispetto a tutti gli altri.
Secondo anno
L’attivit`a di ricerca affrontata durante il secondo anno di Dottorato ha riguardato l’allocazione di risorse computazionali e di rete all’interno del DC. Il modello del DC `e rappresentato da un insieme di server e di switch collegati tra loro secondo una topologia Three-Tier Fat Tree; ogni switch e server ha un proprio consumo di potenza.
Sono stati affrontati due problemi diversi riguardanti il contemporaneo miglioramento delle performance e la riduzione del consumo di potenza elettrica:
1. l’allocazione di un gruppo di VM come problema di ottimizzazione globale, risolto tramite l’uso di MOGA;
2. l’allocazione di singole VM in base allo stato corrente del DC per attuare un’ottimizzazione locale effettuata utilizzando diversi approcci tra cui uno analitico mono-dimensionale, due varianti della Fuzzy Logic e due varianti di un’euristica multi-obiettivo.
In entrambi casi, sono stati considerate come risorse per ogni VM la quantit`a necessaria di CPU, RAM, e disco insieme con la banda di rete necessaria per comunicare con il gateway esterno.
Nel primo caso, rispetto all’anno precedente, `e stata svolta un’analisi pi`u accurata dell’approccio MOGA ed in particolare `e stata verificata la qualit`a delle soluzioni calcolate utilizzando appropriati indicatori facendo variare alcuni dei parametri di base dell’euristica. In seconda istanza, `e stato effettuato un confronto con una formalizzazione ridotta a singolo obiettivo del problema risolto tramite CPLEX.
Nel secondo caso, si `e proceduto a potenziare il modello gi`a adottato introducendo l’allocazione della parte di rete ed ottenendo informazioni statistiche sulla distribuzione delle richieste accettate/rifiutatee delle risorse residue. I percorsi di rete sono stati allocati utilizzando una variante dell’algoritmo di Dijkstra che attribuisce ai pesi dei link di rete il relativo consumo energetico in modo tale da scegliere il percorso che garantisca il minor consumo.
Terzo anno
Durante l’ultimo anno di Dottorato, la precendete attivit`a di ricerca ha incluso un nuovo argomento di ricerca riguardante il Mobile Edge Computing e la schedulazione di comunicazioni tra dispositivi che fanno parte del paradigma dell’Internet of Things (IoT). `E stato ottimizzato un sistema di trasmissione basato su Time-slotted Channel Hopping (TSCH) in uno scenario con comunicazioni a tempo reale utilizzando i MOGA al fine di ottimizzare il consumo di potenza delle trasmissioni minimizzando la violazione di deadline nelle trasmissioni.
L’attivit`a di ricerca dell’anno precedente `e stata ulteriormente estesa concentrandosi sull’allocazione dinamica delle VM tramite la modellazione di una nuova euristica chiamata Enhanced Worst Fit (EWF) che unisce gli aspetti positivi del BF e del WF multi-dimensionali. Tramite l’utilizzo di EWF nell’allocazione dinamica di VM si ottengono risultati migliori in termini di numero di VM allocate rispetto a BF e WF che sono stati utilizzati come termini di paragone.
-Durante quest’anno, inoltre, `e stata ultimata la ricerca intrapresa all’estero, con la presentazione di una nuova euristica per la schedulazione di comunicazioni collettiva basate su Message Passing Interface (MPI) in un DC con infrastruttura SDN.
Attivit`a di ricerca all’estero
ETH Zurich, Ambito di ricerca:“Cooperation between MPI and SDN in Cloud DC”, Settembre - Dicembre 2015.
Pubblicazioni
Riviste scientifiche di rilevanza internazionale:
[ J1 ] G. Portaluri, D. Adami, A. Gabbrielli, S. Giordano, M. Pagano: “Power Consumption-Aware Vir-tual Machine Placement in Cloud Data Center”, IEEE Transactions on Green Communications and Networking.
Conferenze/Workshop di rilevanza internazionale:
[ C10 ] M. Ojo, S. Giordano, G. Portaluri, D. Adami: “Throughput Maximization Scheduling Algorithm in TSCH Networks with Deadline Constraints”. Globecom Workshops (GC Wkshps), December 2017. [ C9 ] G. Portaluri, D. Adami, S. Giordano, M. Pagano: “A Novel Allocation Strategy for Virtual Machines
in Software Defined Data Center”, NFV-SDN Workshops, November 2017.
[ C8 ] A. S. Pinna, G. Portaluri, S. Giordano: “Shooter localization in wireless acoustic sensor networks”, Computers and Communications (ISCC) IEEE Symposium on, May 2017, (pp. 473-476).
[ C7 ] M. Ojo, S. Giordano, G. Portaluri, D. Adami, M. Pagano: “An energy efficient centralized scheduling scheme in TSCH networks” Communications Workshops (ICC Workshops), May 2017 IEEE Interna-tional Conference on (pp. 570-575).
[ C6 ] G. Portaluri, D. Adami, A. Gabbrielli, S. Giordano, M. Pagano: “Power Consumption-Aware Virtual Machine Allocation in Cloud Data Center”, 2016 IEEE Global Communications Conference: Work-shops: Fifth International Workshop on Cloud Computing Systems, Networks, and Applications, December 2016.
[ C5 ] D. Adami, S. Giordano, M. Pagano , G. Portaluri: “A Novel SDN Controller for Traffic Recovery and Load Balancing in Data Centers”, IEEE 21st International Workshop on Computer Aided Modelling and Design of Communication Links and Networks (CAMAD), October 2016.
[ C4 ] G. Portaluri, S. Giordano: “Multi Objective Virtual Machine Allocation in Cloud Data Centers”, 2016 IEEE 5th International Conference on Cloud Networking (CloudNet), October 2016.
[ C3 ] D. Adami, A. Gabrielli, S. Giordano, M. Pagano, G. Portaluri: “A Fuzzy Logic approach for Re-sources Allocation in Cloud Data Center”, IEEE Globecom Workshop on Cloud Computing Systems, December 2015.
[ C2 ] G. Portaluri, S. Giordano: “Power Efficient Resource Allocation in Cloud Computing Data Cen-ters using Multi-Objective Genetic Algorithms and Simulated Annealing”, 4th IEEE International Conference on Cloud Networking, October 2015.
[ C1 ] G. Portaluri, S. Giordano, D. Kliazovich and B. Dorronsoro, “A power efficient genetic algorithm for resource allocation in cloud computing data centers,” Cloud Networking (CloudNet), 2014 IEEE 3rd International Conference on, Luxembourg, 2014, pp. 58-63.
Altro:
[ O1 ] G. Portaluri, S. Giordano: “A Topology-Aware Scheduler for MPI Collectives in Software Defined Data Centers”, Italian Networking Workshop, January 2017.
-Attivit`a di formazione
• CLI, “Academic Writing and Presentation Skills for Engineering PhD Students C1+”, 4 CFU. • IEEE ComSoc Summer School, Trento, 20 – 23 Giugno 2016.
• Kishor Trivedi, Duke University, “Reliability, Availability and Performance of Data Centers and Clouds”, 14 - 18 Marzo 2016, 5 CFU.
• CLI, “Academic Writing and Presentation Skills for Engineering PhD Students C1”, 4 CFU. • M. Luise, L. Sanguinetti, Univ. Pisa: “Game Theory and Optimization in communications and
Networking”, 1-4 Febbraio 2016, 4 CFU.
• Ph.D. Summer School, “Graph Data Management”, 31 Agosto – 4 Settembre 2015, Palam`os (Spagna), 4 CFU.
• Rainer Leupers, “Design Technologies for Embedded Multiprocessor Systems-on-Chip”, 14- 17 Luglio 2015, 5 CFU.
• Claudio Lucchese, Franco Maria Nardini, Nicola Tonellotto, “Cloud Computing for Big Data Analy-sis”, 8 - 22 Giugno 2015, 5 CFU.
• Giovanni Neglia, “Network Science”, 23-27 Marzo 2015, 5 CFU. • Dmitry G. Korzun, “Smart Spaces”, 1 - 5 Dicembre 2014, 5 CFU.
• Michal Pioro “Optimization models for communication network design”, Novembre 10-14, 2014 Politecnico di Milano, DEIB, 6 CFU.
