Η ανάθεση εικονικών μηχανών σε φυσικά μηχανήματα που απαρτίζουν υπολογιστικές δομές (σύννεφα) έχει καθοριστική επίδραση τόσο στο όφελος του παρόχου όσο και στην ικανοποίηση των αναγκών του πελάτη. Παρ' όλο που αυτές οι παράμετροι μπορούν να μεταβάλλονται με το χρόνο και τις περιστάσεις, οι τρέχουσες πρακτικές διαχείρισης των πόρων ενός datacenter δεν είναι ικανοποητικές, είτε διότι υλοποιούν πάγιες και στατικές πολιτικές είτε διότι φροντίζουν μονομερώς για το συμφέρον του διαχειριστή του σύννεφου. Σε αυτή την εργασία προτείνουμε ένα ευέλικτο και δημοκρατικό μηχανισμό αντιστοίχισης εικονικών μηχανών σε φυσικούς πόρους, ο οποίος αποσκοπεί στο να ικανοποιεί ισορροπημένα και τις δύο πλευρές του προβλήματος, πελάτες και παρόχους. Προς τούτο, η ανάθεση εικονικών μηχανών ανάγεται στο Πρόβλημα του Ισότιμου Σταθερού Ταιριάσματος (ESMP), αφού μετασχηματίσουμε τις πολιτικές κάθε πλευράς σε λίστες προτίμησης. Έπειτα, αναπτύσσουμε μια αποδοτική και κλιμακώσιμη ευριστική ώστε να αντλήσουμε προσεγγιστικές λύσεις-ταιριάσματα σε εύλογο χρονικό διάστημα, δεδομένου ότι το ESMP είναι ένα ΝP-Hard πρόβλημα. Η πειραματική αποτίμηση της προσέγγισής μας δείχνει ότι, χρησιμοποιώντας όχι περισσότερη μνήμη από όση διαθέτει ένας συνήθης προσωπικός υπολογιστής και γνωρίζοντας μόλις το άνω $20 \%$ των λιστών προτίμησης των αντιπροσώπων, μπορούμε να επιλύσουμε αποδοτικά άνω του $85 \%$ των παραγόμενων στιγμιοτύπων ESMP σε λιγότερο από $N \sqrt{N}$ γύρους ταιριάσματος.
(EL)
VM placement, be it in public or private clouds, has a decisive impact on the provider's interest and the customer's needs alike, both of which may vary over time and circumstances. However, current resource management practices are either statically bound to specific policies or unilaterally favor the needs of Cloud operators. In this work we argue for a flexible and democratic mechanism to map virtual to physical resources, trying to balance satisfaction on both sides of the involved stakeholders. To that end, VM placement is expressed as an Equitable Stable Matching Problem (ESMP), where each party's policy is translated to a preference list. A practical approximation for this NP-hard problem, modified accordingly to ensure efficiency and scalability, is applied to provide equitable matchings within a reasonable time frame. Our experimental evaluation shows that, requiring no more memory than what a high-end desktop PC provides and knowing no more than the top $20\%$ of the agent's preference lists, our solution can efficiently resolve more than $90\%$ of large-scale ESMP instances within $N \sqrt{N}$ rounds of matchmaking.
(EN)
Εθνικό Μετσόβιο Πολυτεχνείο
