| Περίληψη: | Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικειμένων. Επιπλέον μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος. καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος σύγχρονου διαμοιρασμού αντικειμένων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν.
Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις:
• Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά, οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και, μάλιστα, με μεγάλη διασπορά.
• Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικειμένου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο.
• Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους.
• Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές.
• Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος.
• Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητά του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων.
• Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο.
Για τη λειτουργία του προτεινόμενου συστήματος απαιτείται η δημιουργία ενός γράφου διασύνδεσης. Ως γράφος διασύνδεσης ορίζεται ο γράφος που προκύπτει αν κάθε κόμβος συνδεθεί με ένα μικρό υποσύνολο των συμμετεχόντων κόμβων που ονομάζονται και γείτονες του κόμβου. Για την ικανοποίηση των προαναφερθεισών απαιτήσεων. μελετήθηκαν τα χαρακτηριστικά του γράφου διασύνδεσης και προέκυψε ότι κάθε κόμβος: α) πρέπει να έχει γείτονες με όσο το δυνατόν μικρότερη δικτυακή καθυστέρηση μεταξύ τους, β) πρέπει να έχει αριθμό εξερχόμενων συνδέσεων ανάλογο με το εύρος ζώνης του, γ) οι συνδέσεις αυτές πρέπει να κατανέμονται ομοιόμορφα στους συμμετέχοντες κόμβους για την ικανοποίηση των αναγκών όλων των κόμβων, δ) οι κόμβοι με σχετικά μεγάλο εύρος ζώνης πρέπει να ομαδοποιούνται στο γράφο με σκοπό την γρήγορη αρχικά διάχυση του αντικειμένου και ε) ο γράφος διασύνδεσης πρέπει να αναδιατάσσεται δυναμικά έτσι ώστε να διατηρεί τις ιδιότητες αυτές στο δυναμικό δικτυακό περιβάλλον που επικάθεται και για δυναμική συμπεριφορά των συμμετεχόντων κόμβων.
Για την ικανοποίηση αυτών των τεχνικών στόχων αναπτύχθηκε μία δομή του γράφου που ικανοποιεί αυτά τα χαρακτηριστικά. Η βελτιστοποίηση του γράφου γίνεται μέσω αλγορίθμων κατά την λειτουργία των οποίων κάθε κόμβος επιλέγει περιοδικά ένα τυχαίο κόμβο ο οποίος είναι γείτονάς του στον γράφο διασύνδεσης. Μεταξύ των δύο αυτών κόμβων εκτελείται ανακατανομή των γειτόνων τους με σκοπό την εξισορρόπηση του αριθμού των γειτόνων που κάθε ένας από αυτούς διαθέτει. αλλά και την ελαχιστοποίηση της μέσης καθυστέρησης που έχουν αθροιστικά οι κόμβοι από τους γείτονές τους. Οι αλλαγές στον γράφο διασύνδεσης που προκύπτουν από κάθε εκτέλεση του αλγορίθμου αυτού μεταβάλλουν και τους γείτονες ενός υποσυνόλου κόμβων εκτός των δύο συμμετεχόντων στον αλγόριθμο εναλλαγής. Οι αλλαγές αυτές επιφέρουν άλλες αλλαγές με την σειρά τους και έτσι προκύπτει τελικά ένας γράφος διασύνδεσης όπου κάθε κόμβος έχει τον προκαθορισμένο αριθμό γειτόνων και. παράλληλα. ελαχιστοποιείται το άθροισμα των μέσων δικτυακών καθυστερήσεων που έχουν οι συμμετέχοντες κόμβοι με τους γείτονές τους.
Για τον διαμοιρασμό του αντικειμένου ο δημιουργός του το τεμαχίζει σε τεμάχια (μπλοκ). Τα τεμάχια προωθούνται σε ένα πολύ μικρό σύνολο κόμβων και αποτελούν τις λογικές μονάδες δεδομένων που ανταλλάσσονται μεταξύ των κόμβων. Σκοπός είναι ο διαμοιρασμός του κάθε τεμαχίου σε κάθε κόμβο μέσα σε ένα προκαθορισμένο χρονικό διάστημα. Για την ανταλλαγή τεμαχίων μεταξύ των γειτόνων του γράφου διασύνδεσης του προς διαμοιρασμού αντικειμένου μεταξύ των συμμετεχόντων κόμβων αναπτύχθηκε ένας Κατανεμημένος Χρονοπρογραμματιστής Ανταλλαγής Τεμαχίων (ΚΧΑΤ).
Τεχνικοί στόχοι της ανάπτυξης του ΚΧΑΜ αποτέλεσαν α) ο χρονισμός διαπραγμάτευσης αποστολής τεμαχίων μεταξύ κάθε αποστολέα και παραλήπτη, β) η γρήγορη διάδοση πρόσφατα παραγόμενων τεμαχίων και σπάνιων σε μία γειτονία του γράφου διασύνδεσης (τεμάχια που δημιουργήθηκαν μεταγενέστερα από άλλα ευνοούνται από το χρονοπρογραμματιστή αρχικά για την επιτυχή και γρήγορη διάδοσή τους σε μία κρίσιμη μάζα από κόμβους), γ) η τροφοδότηση όλων των κόμβων με ομοιόμορφο και σταθερό ρυθμό, δ) η προτεραιότητα σε κόμβους με μεγάλο εύρος ζώνης, ε) η αποφυγή μετάδοσης του ίδιου τεμαχίου από δύο αποστολείς προς τον ίδιο παραλήπτη και στ) η αποφυγή μιας κατάστασης όπου αποστολέας και παραλήπτης δεν έχουν τεμάχια προς ανταλλαγή.
Ο χρονισμός του ΚΧΑΜ που αναπτύχθηκε αποτελείται από τρείς φάσεις. Στην πρώτη φάση που εκτελείται περιοδικά από κάθε αποστολέα εκδίδεται και αποστέλλεται στους πιθανούς παραλήπτες ένα σύνολο από «κουπόνια» μεγέθους ανάλογου με το εύρος ζώνης του αποστολέα. Στη δεύτερη φάση ο εκάστοτε παραλήπτης ζητά προκαταβολικά ένα τεμάχιο στην περίπτωση που επιλεγεί από τον αποστολέα για μετάδοση τεμαχίου. Στην τρίτη φάση ο αποστολέας επιλέγει τον παραλήπτη ακριβώς πριν την μετάδοση κάθε τεμαχίου και αποστέλλει το τεμάχιο που έχει ζητηθεί.
Ο αλγόριθμος ο οποίος προτείνεται για τη δημιουργία κουπονιών έχει ως στόχο τη μεγιστοποίηση της χρήσης του εύρους ζώνης όλων των κόμβων και την ικανοποίηση των αναγκών κάθε συμμετέχοντα κόμβου. Είναι αυτός που, στην ουσία, καθορίζει τις ροές δεδομένων μεταξύ των γειτόνων του γράφου διασύνδεσης. Η χρησιμότητά του αναδεικνύεται σε περιπτώσεις όπου ο ρυθμός αναπαραγωγής του προς διαμοιρασμό αντικειμένου είναι παρόμοιος με το μέσο εύρος ζώνης του συστήματος. Οι απαιτήσεις του αλγορίθμου ζήτησης τεμαχίων μοντελοποιούνται μέσω της γραμμικής βελτιστοποίησης και διασφαλίζεται η γρήγορη και αποτελεσματική διάχυση των τεμαχίων ελαχιστοποιώντας την ύπαρξη ανενεργών πόρων. Τέλος, ο αλγόριθμος επιλογής γείτονα είναι αυτός που ρυθμίζει την ομοιόμορφη κατανομή του εύρους ζώνης στους συμμετέχοντες κόμβους, αλλά και δίνει προτεραιότητα στους κόμβους με μεγάλο εύρος ζώνης έτσι ώστε να επιτευχθεί ο γρήγορος διαμοιρασμός κάθε τεμαχίου και η ελαχιστοποίηση της καθυστέρησης του συστήματος.
Η αξιολόγηση της προτεινόμενης αρχιτεκτονικής, της τοπολογίας του γράφου διασύνδεσης και του ΚΧΑΜ, έγινε μέσω προσομοίωσης σε προσομοιωτή δικτυακών συστημάτων. Μοντελοποιήθηκε το εύρος ζώνης των συμμετεχόντων κόμβων και δικτυακές καθυστερήσεις χρησιμοποιώντας πραγματικά δεδομένα από διομότιμα συστήματα.. Το σύστημα που αναπτύχθηκε μοντελοποιήθηκε πλήρως σε επίπεδο πακέτου. Εξετάστηκαν αρκετά σενάρια αξιολόγησης του συστήματος τα οποία, μεταξύ άλλων, περιλαμβάνουν, ευαισθησία του συστήματος σε παραμέτρους των προτεινόμενων αλγορίθμων, δυναμικά σενάρια όσον αφορά τη συμπεριφορά των χρηστών και του δικτύου και σενάρια εύρεσης των ορίων του προτεινόμενου συστήματος. Η αξιολόγηση των αποτελεσμάτων έδειξε ότι ικανοποιούνται οι απαιτήσεις που τέθηκαν για τη δημιουργία του συστήματος, καθώς και βελτίωση της συμπεριφοράς του συστήματος σε σχέση με αντίστοιχα συστήματα της διεθνούς βιβλιογραφίας με τα οποία συγκρίθηκε.
|
|---|
