Μελέτη Οικονομικών Αλγορίθμων για Κατανομή Φόρτου Εργασιών
και Διαχείριση Δεδομένων σε Κατανεμημένα Συστήματα
Αναστασία Αναστασιάδη
Μεταπτυχιακή Εργασία
Τμήμα Επιστήμης Υπολογιστών
Πανεπιστήμιο Κρήτης
ΠΕΡΙΛΗΨΗ
Οι πρόσφατες εξελίξεις στην τεχνολογία υπολογιστών και δικτύων επιτρέπουν την διασύνδεση μεγάλου αριθμού ετερογενών υπολογιστών και τη δημιουργία μεγάλων συλλογών από υπολογιστικούς και επικοινωνιακούς πόρους. Τα συστήματα αυτά παρουσιάζουν μεγάλη πολυπλοκότητα στην οργάνωση και διαχείριση των πόρων και των υπηρεσιών που διαθέτουν. Η αυξημένη πολυπλοκότητα οφείλεται κυρίως στο μέγεθος (αριθμός συστημάτων, αριθμός χρηστών) και στην ετερογένεια των πόρων και των εφαρμογών και καθιστά τις παραδοσιακές μεθόδους κατανομής πόρων μη αποδοτικές.
Στόχος αυτής της εργασίας είναι να επιδείξει πως ανταγωνιστικά, οικονομικά μοντέλα μπορούν να παρέχουν αποδοτικούς αλγόριθμους για την κατανομή πόρων σε ένα κατανεμημένο υπολογιστικό σύστημα περιορίζοντας σημαντικά την πολυπλοκότητα σε σχέση με τις παραδοσιακές μεθόδους.
Εχουν σχεδιαστεί αλγόριθμοι κατανομής φόρτου εργασιών και διαχείρισης δεδομένων που στηρίζονται στην οικονομία τιμών. Καταναλωτές αυτής της οικονομίας θεωρούνται οι δοσοληψίες οι οποίες εκμεταλλεύονταιτο κεφάλαιο που διαθέτουν για την αγορα πόρων (υπολογιστικός χρόνος, εύρος επικοινωνίας, δεδομένα). Στόχος των δοσοληψιών είναι η ικανοποίηση των αναγκών τους με τη μικρότερη δυνατή χρέωση. Προμηθευτές της οικονομίας θεωρούνται οι κόμβοι του συστήματος οι οποίοι εμπορεύονται τα τοπικά τους αγαθά και στοχεύουν στη μεγιστοποίηση των κερδών τους.
Η μελέτη της συμπεριφοράς των οικονομικών αλγορίθμων κατανομής φόρτου εργασιών και διαχείρισης δεδομένων έγινε με την διεξαγωγή πλήθους πειραμάτων προσομοίωσης στον προσομοιωτή TPsim. Τα πειράματα πιστοποίησαν οτι οι οικονομικές μέθοδοι επιλύουν αποδοτικά το πρόβλημα της κατανομής πόρων σε κάθε κατανεμημένο συστήμα και περιορίζουν την πολυπλοκότητα της διαδικασίας σε σχέση με τις παραδοσιακές μεθόδους.
A study of Microeconomic Algorithms for Load Balancing and
Data Replication in Distributed Computer Systems
Anastasia Anastasiadi
Master of Science Thesis
Department of Computer Science
University of Crete
ABSTRACT
With the recent advances in computer and networking technology thousands of heterogeneous computers can be interconnected to provide a large collection of computing and communication resources. A macroscopic view of these systems reveals the complexity of the organization and management of the resources and services they provide. This complexity arises from size (no of systems, no of users) and heterogeneity of applications and resources and makes the traditional approaches to resource allocation impractical in modern distributed systems.
The goal of this work is to demonstrade how competitive ecomonic models provide efficient algorithms and tools for allocating resources in distributed computer systems and manage to limit the complexity of resource allocation.
In this work we model the distributed system as a competitive society of microeconomic agents (price based economy) and we apply this model to the problem of load balancing and managing distributed replicated data objects. The consumers of the economy are the transactions which are endowed with some wealth (budget). Each transaction is using its budget to purchase resources (CPU time, communication bandwidth, data objects) with the minimum cost. The nodes of the system are the suppliers of the economy. A supplier's sole goal is to optimize its individual satisfaction (profit) derived from its choice of resource allocation to consumers.
We evaluate the load balancing economy and the data replication economy through a simulation study on TPsim. Our experiments show that the microeconomic algorithms can substantially improve the performance and reduce the complexity of resource allocation relative to traditional approaches.
