Συντάχθηκε 18-03-2015 11:30
από Vasiliki Grigoraki
Email συντάκτη: vgrigoraki<στο>tuc.gr
Ενημερώθηκε:
-
Κύρια: υπάλληλος ΗΜΜΥ.
Άλλες ιδιότητες: Unknown -#-@ΗΜΜΥ
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΓΕΩΡΓΙΟΥ ΚΩΣΤΟΥΛΑ
με θέμα
Τεχνικές Αποσύνθεσης για Μεγιστοποίηση Απόδοσης Δικτύου
Decomposition methods for Network Utility Maximization
Παρασκευή 20 Μαρτίου, 10πμ
Αίθουσα Συνεδριάσεων Σχολής ΗΜΜΥ, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Αθανάσιος Λιάβας (επιβλέπων)
Καθηγητής Μιχαήλ Πατεράκης
Αναπληρωτής Καθηγητής Πολυχρόνης Κουτσάκης
Περίληψη
Το πρόβλημα Μεγιστοποίησης Απόδοσης Δικτύου (NUM) είναι η κατανομή του κατάλληλου μεγέθους πόρων στους κόμβους του δικτύου, με σκοπό την μεγιστοποίηση μίας συνολικής συνάρτησης απόδοσης. Υπάρχουν πολλά εργαλεία βελτιστοποίησης για την λύση του προβλήματος με μη κατανεμημένο τρόπο. Σε αυτή τη διπλωματική, συζητάμε κατανεμημένους τρόπους για τη λύση διάφορων σχηματισμών NUM προβλημάτων. Διασπάμε το πρόβλημα σε υποπροβλήματα χρησιμοποιώντας Primal Decomposition, εφαρμόζοντας άμεση κατανομή πόρων και μετά ρυθμίζοντας την κατανομή με μικρά βήματα μέχρι να επιτύχουμε ισορροπία, και Dual Decomposition, κοστολογώντας τους πόρους κατά τέτοιο τρόπο ώστε κάθε κόμβος να επιτύχει βέλτιστη απόδοση. Πολλές εναλλακτικές μπορούν να προκύψουν από αυτές τις δύο μεθόδους, σε διαφορετικούς σχηματισμούς NUM, με τη χρήση πολυεπίπεδων αποσυνθέσεων. Αυτές οι τεχνικές μπορούν να οδηγήσουν σε καλύτερη κατανόηση των υπαρχόντων δικτύων, ανάλυση πρωτοκόλλων δικτύων όπως το TCP, καλύτερη διαχείριση των υπαρχόντων δικτύων και τρόπους σχεδίασης και λειτουργίας νέων δικτύων δημιουργώντας επίπεδα ως βελτιστοποίηση. Τέλος, πειραματιστήκαμε με τη διακίνηση μηνυμάτων αυτών των αλγορίθμων και προσπαθήσαμε να ελαττώσουμε το δεδομένα που αποστέλλονται κβαντίζοντας τις τιμές.
Abstract
Network Utility Maximization (NUM) is the problem of allocating the right amount of resources to the nodes of a network, in order to maximize an overall utility function. There are many optimization tools to solve this problem in a centralized manner. In this thesis, we discuss distributed ways to solve various formulations of NUM problems. We decompose the problems into subproblems using Primal Decomposition, by applying direct resource allocation and then adjust the resources by small steps until equilibrium, and Dual Decomposition by pricing the resource in such manner that each node achieves the optimal utility. Many alternatives can be derived from these two methods, in different NUM formulations, with the use of multilevel decompositions. These decompositions may lead to better understanding of existing networks, reverse engineering of network protocols like TCP, better management of existing networks, and ways to design and operate new networks by layering as optimization. Finally, we experiment with the message passing of these algorithms and try to minimize the data transferred by quantizing the values.
