Αποδοτικοί, Κλιμακώσιμοι Και Δίκαιοι Αλγόριθμοι Αντιστοίχισης Για Ανάθεση Εικονικών Μηχανών Σε Υποδομή Υπολογιστικού Νέφους

Abstract

Η ανάθεση εικονικών μηχανών σε φυσικά μηχανήματα που απαρτίζουν υπολογιστικές δομές (σύννεφα) έχει καθοριστική επίδραση τόσο στο όφελος του παρόχου όσο και στην ικανοποίηση των αναγκών του πελάτη. Παρ' όλο που αυτές οι παράμετροι μπορούν να μεταβάλλονται με το χρόνο και τις περιστάσεις, οι τρέχουσες πρακτικές διαχείρισης των πόρων ενός datacenter δεν είναι ικανοποητικές, είτε διότι υλοποιούν πάγιες και στατικές πολιτικές είτε διότι φροντίζουν μονομερώς για το συμφέρον του διαχειριστή του σύννεφου. Σε αυτή την εργασία προτείνουμε ένα ευέλικτο και δημοκρατικό μηχανισμό αντιστοίχισης εικονικών μηχανών σε φυσικούς πόρους, ο οποίος αποσκοπεί στο να ικανοποιεί ισορροπημένα και τις δύο πλευρές του προβλήματος, πελάτες και παρόχους. Προς τούτο, η ανάθεση εικονικών μηχανών ανάγεται στο Πρόβλημα του Ισότιμου Σταθερού Ταιριάσματος (ESMP), αφού μετασχηματίσουμε τις πολιτικές κάθε πλευράς σε λίστες προτίμησης. Έπειτα, αναπτύσσουμε μια αποδοτική και κλιμακώσιμη ευριστική ώστε να αντλήσουμε προσεγγιστικές λύσεις-ταιριάσματα σε εύλογο χρονικό διάστημα, δεδομένου ότι το ESMP είναι ένα ΝP-Hard πρόβλημα. Η πειραματική αποτίμηση της προσέγγισής μας δείχνει ότι, χρησιμοποιώντας όχι περισσότερη μνήμη από όση διαθέτει ένας συνήθης προσωπικός υπολογιστής και γνωρίζοντας μόλις το άνω 20% των λιστών προτίμησης των αντιπροσώπων, μπορούμε να επιλύσουμε αποδοτικά άνω του 85% των παραγόμενων στιγμιοτύπων ESMP σε λιγότερο από N \sqrt{N} γύρους ταιριάσματος.