Δρομολόγηση Και Ανάθεση Μήκους Κύματος Σε Οπτικά Δίκτυα

Abstract

Μελετάμε μοντέλα για δρομολόγηση και ανάθεση μήκους κύματος σε οπτικά δίκτυα, με στόχο να καταδειχθούν ιδιότητες των εν λόγω μοντέλων που πρέπει να λαμβάνονται υπόψιν κατά την υλοποίηση και ανάπτυξη οπτικών δικτύων στην πράξη. Πιο συγκεκριμένα, προτείνονται προσεγγιστικοί αλγόριθμοι για τη μεγιστοποίηση του πλήθους των ικανοποιούμενων αιτήσεων σε οπτικά δίκτυα τοπολογίας δακτυλίου όπου ο αριθμός των μηκών κύματος ανά ίνα δίδεται ως μέρος της εισόδου. Οι προτεινόμενοι αλγόριθμοι, οι οποίοι έχουν όλοι φράγμενο λόγο προσέγγισης στη χειρότερη περίπτωση, συγκρίνονται και πειραματικά με ήδη γνωστούς από τη βιβλιογραφία αλγορίθμους. Από τη σύγκριση προκύπτει ότι ο αλγόριθμος με τον θεωρητικά καλύτερο λόγο προσέγγισης αποδίδει μεν καλύτερα από τους υπόλοιπους αλλά καταναλώνει υπερβολικά πολύ χρόνο. Αντίθετα, ένας από τους προτεινόμενους αλγόριθμους παράγει πολύ ικανοποιητικές λύσεις σε χρόνο που είναι αρκετές τάξεις μεγέθους μικρότερος από τον χρόνο του καλύτερου αλγορίθμου.Επιπλέον, μελετάται μία γενίκευση του προβλήματος όπου κάθε αίτηση επικοινωνίας έχει ένα δεδομένο κέρδος, και ζητείται η μεγιστοποίηση του συνολικού κέρδους των ικανοποιούμενων αιτήσεων. Προτείνεται ένας εξαιρετικά γρήγορος, καθαρά συνδυαστικός και εύκολος στην υλοποίηση αλγόριθμος για το πρόβλημα αυτό, ο οποίος έχει χειρότερο λόγο προσέγγισης από έναν ήδη γνωστό αλγόριθμο, όμως καταφέρνει να παράγει ανταγωνιστικές λύσεις και μάλιστα σε ορισμένες περιπτώσεις καλύτερες από όλους τους άλλους αλγορίθμους που συμπεριλαμβάνονται στη μελέτη. Από την πειραματική σύγκριση προκύπτει το συμπέρασμα ότι ο προτεινόμενος αλγόριθμος αποτελεί ιδανική επιλογή όταν απαιτούνται λύσεις στο πρόβλημα σε σύντομο χρονικό διάστημα.Μελετώνται παιγνιοθεωρητικά μοντέλα για τη δρομολόγηση και την ανάθεση μηκών κύματος σε οπτικά δίκτυα πολλαπλών ινών. Ειδικότερα, παρουσιάζεται μια πλήρης ανάλυση του κόστους της αναρχίας όταν οι παίκτες επιλέγουν εγωιστικά το μήκος κύματος ήδη δρομολογημένων αιτήσεων επικοινωνίας, χρεώνονται με βάση την μέγιστη πολλαπλότητα του μήκους κύματος που επέλεξαν κατά μήκος του μονοπατιού στο οποίο έχει δρομολογηθεί η αίτηση, και το κοινωνικό κόστος καθορίζεται από την μέγιστη πολλαπλότητα μήκους κύματος που εμφανίζεται σε ολόκληρο το δίκτυο. Αποδεικνύεται ότι το παίγνιο που ορίζεται με αυτόν τον τρόπο συγκλίνει πάντοτε σε ισορροπία Nash σε πεπερασμένο αριθμό κινήσεων, ενώ προτείνονται αλγόριθμοι για τον υπολογισμό κοινωνικά βέλτιστης ισορροπίας Nash και προσεγγιστικά βέλτιστης ισορροπίας Nash σε συγκεκριμένες τοπολογίες. Αποδεικνύεται ότι το κόστος της αναρχίας μπορεί να γίνει αυθαίρετα μεγάλο ακόμη και σε δενδρικές τοπολογίες δικτύων με μέγιστο βαθμό τρία. 'Ομως, στην περίπτωση του δακτυλίου και της αλυσίδας, το κόστος της αναρχίας φράσσεται από μία σταθερά αν το πλήθος των διαθέσιμων μηκών κύματος δεν είναι πολύ μεγάλο σε σχέση με το φορτίο του δικτύου, υπόθεση που καλύπτει ουσιαστικά την πλειοψηφία των περιπτώσεων που μπορεί να εμφανιστούν στην πράξη.Προς επέκταση του προηγούμενου μοντέλου, προτείνεται ένα γενικότερο πλαίσιο μελέτης των παιγνίων εγωιστικής δρομολόγησης και ανάθεσης μηκών κύματος σε οπτικά δίκτυα πολλαπλών ινών, υπό διάφορες συναρτήσεις κόστους των παικτών και υπό διάφορες συναρτήσεις κοινωνικού κόστους. Αποδεικνύονται άνω και κάτω φράγματα για το κόστος της αναρχίας των εν λόγω παιγνίων.Τέλος, μελετάται η πολυπλοκότητα του προβλήματος χρονικού προγραμματισμού ενός συνόλου δρομολογίων που πρέπει να εκτελούνται περιοδικά με δοσμένη συχνότητα σε ένα δίκτυο μεταφορών, έτσι ώστε να μεγιστοποιούνται οι αποστάσεις ασφαλείας μεταξύ διαδοχικών οχημάτων που χρησιμοποιούν το ίδιο τμήμα του δικτύου. Για την επίλυση αυτού του προβλήματος αποδεικνύεται και αξιοποιείται η σύνδεσή του με ένα πρόβλημα χρωματισμού μονοπατιών που έχει χρησιμοποιηθεί κατά κόρον για τη μοντελοποίηση προβλημάτων δρομολόγησης και ανάθεσης μηκών κύματος σε οπτικά δίκτυα. Έτσι, καταδεικνύεται η γενικότητα των γραφοθεωρητικών μοντέλων χρωματισμού μονοπατιών που μελετήθηκαν στη διατριβή.