Δρομολόγηση και ανάθεση μήκους κύματος σε οπτικά δίκτυα

Abstract

We study models for routing and wavelength assignment in optical networks, aiming at showing properties of these models that must be taken into consideration when optical networks are deployed in practice. More specifically, we propose approximation algorithms for maximizing the number of satisfied requests in optical ring networks where the number of available wavelengths per fiber is given as part of the input. The proposed algorithms, which all possess a bounded approximation ratio, are also compared experimentally with other algorithms already known from the literature. From the comparison, we conclude that the algorithm with the theoretically best approximation ratio produces the best solutions but consumes too much running time. On the contrary, one of the proposed algorithms produces very satisfactory solutions with a running time several orders of magnitude faster than the time of the better algorithm. Moreover, we study a generalization of the problem where every communication request is associated with a given profit, and we seek to maximize the total profit of satisfied requests. We propose an extremely fast, purely combinatorial, and easily implemented algorithm for this problem, which has worse approximation ratio them an already known algorithm, but manages to produce competitive solutions—in some cases, it produces better solutions than all the other algorithms included in the study. From the experimental comparison, we conclude that the proposed algorithm is a decent choice whenever we require decent solutions in limited running time. We also study game-theoretic models for routing and wavelength assignment in multifiber optical networks. We present a full analysis of the price of anarchy when players selfishly choose the wavelength of already routed communication requests, they are charged according to the maximum fiber multiplicity incurred by their choice of wavelength, and the social cost is determined by the maximum wavelength multiplicity that appears at any edge of the network. We prove that the game thus defined always converges to a Nash equilibrium in a finite number of moves, and also propose algorithms for efficiently computing socially optimal and approximate Nash equilibria in specific network topologies. The price of anarchy can grow unbounded even in tree networks with maximum degree three. However, in the case of chains and rings, the price of anarchy is bounded by a constant when the number of available wavelengths is not too large compared to the load of the network—an assumption which covers most cases that can appear in practice. Extending the previous model, we propose a general framework for studying selfish routing and wavelength assignment games in multifiber optical networks, under player cost and social cost functions. We prove upper and lower bounds on the price of anarchy of these games. Finally, we study the complexity of scheduling a set of routes that must be executed periodically in a transportation network with a given period, so that the safety distance between successive vehicles that use the same portion of the network is maximized. For solving this problem, we prove and utilize its connection with a path coloring problem which has been used extensively for modeling routing and wavelength assignment problems in optical networks. Thus, we show the generality of the graph theoretic path coloring models which we studied in the thesis.

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