A Mechanism Design and Deep Learning Approach for Revenue Maximization on Cloud Dynamic Resource Provisioning Systems

Abstract

Τα τελευταία χρόνια παρατηρείται σημαντική αύξηση στην ανάγκη για την επεξεργασία μεγάλου όγκου δεδομένων (Big Data). Για την επεξεργασία αυτών αναπτύχθηκαν νέες τεχνολογίες οι οποίες στις περισσότερες περιπτώσεις φιλοξενούνται σε διαμοιραζόμενους υπολογιστικούς πόρους, στα λεγόμενα υπολογιστικά νέφη.Οι περισσότεροι οργανισμοί που διαχειρίζονται μεγάλο όγκο δεδομένων επιλέγουν να μεταφέρουν τις εγκαταστάσεις τους από τοπικούς υπολογιστές και servers του οργανισμού, στα υπολογιστικά νέφη. Με τον τρόπο αυτό εξοικονομούν κέρδη, λαμβάνουν δυνατότητα κλιμάκωσης, διατηρούν τα δεδομένα τους ασφαλή και έχουν κάθε στιγμή την απαραίτητη τεχνική υποστήριξη από τον πάροχο. Μία υπηρεσία που παρουσίασε ραγδαία άνοδο τα τελευταία χρόνια είναι τα Spot Instances της Amazon. Με την υπηρεσία αυτή η Amazon θέτει σε χαμηλές τιμές αχρησιμοποίητες εικονικές μηχανές της. Οι χρήστες κάνουν τις προσφορές τους και λαμβάνουν τις μηχανές. Σε περίπτωση που προσφορά κάποιου νέου χρήστη είναι υψηλότερη από την τρέχουσα για τον ίδιο υπολογιστικό πόρο, τότε ο παλιός χρήστης ειδοποιείται και χάνει την εικονική μηχανή του. Μερικές εταιρείες που χρησιμοποιούν τη συγκεκριμένη υπηρεσία είναι: ΑOL, BloomReach, Mapbox, Moovit, Zillow, Novartis κ.α. Στο πλαίσιο της παρούσας διπλωματικής εργασίας μελετάμε το σύστημα κατανομής υπολογιστικών πόρων και καθορισμού τιμών για το σύστημα Spot Instances. Κύριος στόχος μας είναι να δημιουργήσουμε ένα σύστημα δυναμικής τιμολόγησης που θα μεγιστοποιεί τα έσοδα του παρόχου, ενώ παράλληλα θα δίνει κάποιες παραπάνω δυνατότητες στο χρήστη. Προκειμένου να λύσουμε το πρόβλημα βασιζόμαστε στην Αλγοριθμική Θεωρία Παιγνίων και πιο συγκεκριμένα στη Θεωρία του Σχεδιασμού Μηχανισμών και στις δημοπρασίες. Χρησιμοποιούμε προσεγγιστικούς αλγορίθμους, στοιχεία θεωρίας πιθανοτήτων για εκτιμήσεις παραμέτρων και νευρωνικά δίκτυα. Ελέγχουμε τις προσεγγίσεις τόσο σε συνθετικά δεδομένα όσο και σε πραγματικά. Στο τέλος καταλήγουμε σε μία πρόταση, η οποία δείχνει να είναι η πλέον συμφέρουσα με βάση πάντα τα αποτελέσματα των προσομοιώσεων, τα οποία παρουσιάζουμε αναλυτικά. Over the last years, we have witnessed a severe increment in the use and processing of Big Data. For the process of Big Data, several new technologies have emerged. The majority of these new technologies relies on shared computing resources, on the so called Cloud Services. The vast majority of corporations that manipulate Bid Data rely on shared computing resources instead of their own local servers and personal devices. This approach benefits modern enterprises due to the diminish of operational costs, the scalability of cloud systems, the safety of their private and critical data and the consistent customer support that they receive. One cloud service that has increased its popoularity over the years is Amazon Spot Instances. In this cloud service, Amazon sells unused virtual machines at low prices. Users that bid enough for these machines occupate them. In the case where, a new user bids a larger amount of money for the virtual machine of an old user, then the old user is warned about an interruption and its virtual machine is granted to the new user. Examples of modern enterprises that use Spot Instances are: ΑOL, BloomReach, Mapbox, Moovit, Zillow, Novartis and others. In this specific diploma thesis we study the allocation and pricing system for the system of Spot Instances. Our main goal is to create a new dynamic allocation and pricing system that maximizes profit for the cloud operator while it is fair and offers new capabilities to users. In order to solve this problem, our approach is based on Algorithmic Game Theory and specifically to Mechanism Design and Auction Theory. We use approximation algorithms, elements of probability theory for estimation of parameters and neural networks in order to solve the problem. Our approaches are tested both on synthetic and real data of cloud services. In the end of the thesis, we present our final proposition, which is the most efficient based on the simulation results.