Heuristic multicast routing and protection algorithms for optical WDM networks with arbitrary mesh topologies

Abstract

Κατά τα τελευταία χρόνια, το μέγεθος και η πολυπλοκότητα των τηλεπικοινωνιακών δικτύων αυξάνονται σταθερά και η τάση αυτή αναμένεται να συνεχιστεί και στα επόμενα χρόνια. Τα τηλεπικοινωνιακά συστήματα οπτικών ινών τα οποία παρέχουν τεράστια χωρητικότητα και χαμηλά ποσοστά σφάλματος, χρησιμοποιούνται ευρέως στα σημερινά τηλεπικοινωνιακά δίκτυα και παρέχουν αξιόπιστες επικοινωνίες υψηλής ταχύτητας. Τα αμιγώς οπτικά δίκτυα, όπου το σήμα παραμένει συνεχώς στο οπτικό επίπεδο, και οι λειτουργίες δρομολόγησης και αποκατάστασης βλαβών εκτελούνται στο φυσικό στρώμα, είναι στην πρώτη γραμμή της έρευνας τα τελευταία χρόνια, ειδικά για εφαρμογές μονοσημειακής σύνδεσης. Ωστόσο, υπάρχουν αρκετές νέες εφαρμογές (όπως βίντεο κατά απαίτηση, τηλεδιάσκεψη, εξ’ αποστάσεως μάθηση, εξ’ αποστάσεως εφαρμογές ιατρικής διάγνωσης, κλπ), οι οποίες απαιτούν πολυσημειακή σύνδεση στο φυσικό πεδίο. Επιπλέον, λόγω του ότι οι οπτικές ίνες μεταφέρουν πολύ μεγάλο όγκο πληροφορίας, το γεγονός ότι στις εφαρμογές πολυσημειακής σύνδεσης η βλάβη μιας μόνο οπτικής ίνας μπορεί να επηρεάσει τη μετάδοση της πληροφορίας σε μεγάλο αριθμό προορισμών, και το επίπεδο ποιότητας υπηρεσίας που προσφέρεται από τους παροχείς στους χρήστες, οδηγούν στην αναγκαιότητα ενσωμάτωσης μηχανισμών γρήγορης αποκατάστασης βλαβών στη λειτουργία των οπτικών δικτύων. Η παρούσα διατριβή ασχολείται ακριβώς με το πρόβλημα της δρομολόγησης και αποκατάστασης βλαβών σε εφαρμογές πολυσημειακής σύνδεσης, σε οπτικά δίκτυα με πολυπλεξία μήκους κύματος και αυθαίρετη τοπολογία πλέγματος. Η κύρια συνεισφορά της διατριβής είναι η ανάπτυξη καινοτόμων αλγορίθμων δρομολόγησης και προστασίας πολυσημειακών συνδέσεων, για δίκτυα μη κατευθυνόμενου και μικτού γραφήματος. Ένα μη κατευθυνόμενο γράφημα ορίζεται ως εκείνο που έχει μόνο αμφίδρομες συνδέσεις μεταξύ των κόμβων του, και ένα μικτό γράφημα ως εκείνο που έχει τόσο αμφίδρομες όσο και μονόδρομες συνδέσεις. Η μοντελοποίηση ενός δικτύου ως ένα μικτό γράφημα είναι πιο κοντά στην πραγματικότητα, δεδομένου ότι στην πράξη, ακόμα και αν το δίκτυο έχει σχεδιαστεί ως μη κατευθυνόμενο, οι συνδέσεις που έχουν ήδη υλοποιηθεί δεσμεύουν κάποιο μέρος της χωρητικότητας του, με αποτέλεσμα η εναπομένουσα χωρητικότητα να οδηγεί σε δίκτυο μικτού γραφήματος για τις επικείμενες συνδέσεις. Διάφορες αρχιτεκτονικές δικτύων ερευνήθηκαν στη παρούσα εργασία, όπως δίκτυα με οπτικούς διαχωριστές σε όλους τους κόμβους, δίκτυα με οπτικούς διαχωριστές σε μερικούς από τους κόμβους, και δίκτυα με κόμβους τερματισμού-και-συνέχειας και τερματισμού-ή-συνέχειας. Για αυτές τις κατηγορίες δικτύων, αναπτύχθηκαν αλγόριθμοι που δίνουν αποτελεσματικές λύσεις στα προβλήματα της κατανομής των οπτικών διαχωριστών στο δίκτυο και της δρομολόγησης πολυσημειακών συνδέσεων. Επιπλέον, παρουσιάζεται μια τεχνική εξισορρόπησης φορτίου, η οποία λαμβάνει υπόψη τις ήδη εγκατεστημένες εντολές πολυσημειακών συνδέσεων και τη συμφόρηση που προκαλούν σε κάθε σύνδεση του δικτύου, ώστε η δρομολόγηση των επερχόμενων συνδέσεων να γίνει με πιο αποτελεσματικό τρόπο. Παρά το γεγονός ότι οι προτεινόμενοι αλγόριθμοι αναπτύχθηκαν για την περίπτωση των αδόμητων οπτικών δικτύων, οι περισσότεροι από αυτούς, με ελάχιστες τροποποιήσεις, μπορούν να εφαρμοστούν και σε άλλους τύπους δικτύων. Όλοι οι προτεινόμενοι αλγόριθμοι αξιολογήθηκαν και συγκρίθηκαν με τους σχετικούς υφιστάμενους. Η βελτιωμένη τους απόδοση φαίνεται μέσα από παραδείγματα και προσομοιώσεις σε πραγματικά και τυχαία δημιουργημένα δίκτυα.