Αλγόριθμοι δρομολόγησης και δέσμευσης φάσματος σε ελαστικά οπτικά δίκτυα
Authors: Σούμπλης Πολυζώης 
Published: April 2024

Η συνεχής αύξηση της IP κίνησης λόγω της όλο και πιο συχνής χρήσης broadband και Fiber Τo Τhe Ηome υπηρεσιών καθώς και η ύπαρξη όλο και περισσότερων υπηρεσιών υψηλού ρυθμού μετάδοσης καθιστούν επιτακτική την αξιοποίηση της χωρητικότητας των οπτικών δικτύων. Η κίνηση αυτή χαρακτηρίζεται από υψηλές διακυμάνσεις τόσο ως προς το χρόνο όσο και ως προς την κατεύθυνση και αναμένεται η αύξηση της να συνεχιστεί με υψηλό ρυθμό (34% ανά έτος) και τα επόμενα χρόνια. Σε ένα δίκτυο πολυπλεξίας διαίρεσης μήκους κύματος (Wavelength Division Multiplexing - WDM), η οπτική ίνα χρησιμοποιείται για τη μεταφορά κίνησης υψηλού ρυθμού δημιουργώντας έναν αριθμό από μη επικαλυπτόμενα κανάλια μέσα σε μόνο μία ίνα. Η πιο κοινή αρχιτεκτονική που χρησιμοποιείται για την επικοινωνία σε WDM οπτικά δίκτυα είναι η δρομολόγηση μηκών κύματος, όπου οπτικοί παλμοί μεταδίδονται μέσω οπτικών μονοπατιών, δηλαδή αμιγώς WDM κανάλια που μπορεί να διατρέχουν έναν αριθμό από συνεχόμενες ίνες. Τα σημερινά οπτικά δίκτυα κορμού είναι κυρίως δίκτυα από σημείο σε σημείο (αδιαφανή), όπου το σήμα αναγεννάται σε κάθε ενδιάμεσο κόμβο μέσω οπτο-ηλεκτρο-οπτικής (ΟΕΟ) μετατροπής. Τα ελαστικά οπτικά δίκτυα, ως συνέχεια των WDM δικτύων σταθερού πλέγματος, θεωρούνται η καταλληλότερη αρχιτεκτονική για τα δίκτυα κορμού και τα μητροπολιτικά δίκτυα επόμενης γενιάς καθώς χαρακτηρίζονται από υψηλή φασματική αποδοτικότητα και προσαρμοστικότητα. Τα ελαστικά δίκτυα αξιοποιούν την τεχνολογία του ελαστικού πλέγματος, όπου το φάσμα χωρίζεται σε σχισμές φάσματος των 12.5 GHz, έναντι των 50 GHz των παραδοσιακών δικτύων πολυπλεξίας μήκους κύματος WDM και οι σχισμές συνδυάζονται για να δημιουργηθούν κανάλια επιθυμητού μεγέθους κάνοντας χρήση του απολύτως απαραίτητου για τη μετάδοση φάσματος. Από τη μετατόπιση του ερευνητικού ενδιαφέροντος στα ελαστικά οπτικά δίκτυα προέκυψε η ανάγκη ανάπτυξης αλγορίθμων δρομολόγησης και δέσμευσης φάσματος (Routing and Spectrum Allocation - RSA) που διαφέρουν από τους υπάρχοντες αλγόριθμους δρομολόγησης και ανάθεσης μήκους κύματος (Routing and Wavelength Assignment - RWA) λόγω των επιπλέων περιορισμών που εισάγουν. Στην παρούσα διδακτορική έρευνα αρχικά ασχοληθήκαμε με την ανάπτυξη και την αξιολόγηση αλγορίθμων δρομολόγησης και δέσμευσης φάσματος σε διαφανή και ημιδιαφανή οπτικά WDM δίκτυα θεωρώντας ότι οι αιτήσεις σύνδεσης είναι γνωστές εκ των προτέρων (φάση σχεδιασμού δικτύων θεωρώντας στατική κίνηση). Εξαιτίας των φυσικών φαινομένων, η επιλογή ενός οπτικού μονοπατιού επηρεάζει και επηρεάζεται από τις επιλογές των άλλων οπτικών μονοπατιών. Για το λόγο αυτό αναπτύξαμε στατικούς αλγορίθμους δρομολόγησης και δέσμευσης φάσματος που βελτιστοποιούν την χρήση των δικτυακών πόρων.Επίσης, η ενεργειακή αποδοτικότητα αποτελεί πλέον ένα από τα πιο σημαντικά κριτήρια σε κάθε πτυχή της καθημερινής μας ζωής. H κατανάλωση ενέργειας για τον κλάδο Τεχνολογιών Πληροφορίας και Επικοινωνιών αποτελεί ένα σημαντικό ποσοστό της παγκόσμιας κατανάλωσης (~10%) με συνεχείς αυξητικές τάσεις. Η προσπάθεια για περιορισμό της κατανάλωσης ενέργειας και την δημιουργία “πράσινων δικτύων” δεν έχει μόνο οικονομικά ή περιβαλλοντικά κίνητρα, αλλά συχνά αποτελεί και ένα ζήτημα για την περαιτέρω ανάπτυξη των δραστηριοτήτων του κλάδου των Επικοινωνιών, καθώς πλέον λειτουργεί ως παράγοντας ανάσχεσης υλοποίησης νέων τεχνολογιών. Για το λόγο αυτό αναπτύξαμε επίσης αλγορίθμους δρομολόγησης και δέσμευσης φάσματος που βελτιστοποιούν την καταναλισκόμενη από το δίκτυο ενέργεια.Κατά τη διάρκεια λειτουργίας ενός οπτικού δικτύου μπορεί να χρειαστεί η εγκατάσταση νέων συνδέσεων ή ο τερματισμός ήδη υπαρχόντων. Σε αντίθεση με τα παραδοσιακά δίκτυα WDM, όπου η δέσμευση φάσματος είναι ομοιόμορφη με τη μορφή μηκών κύματος, στα ελαστικά δίκτυα το φάσμα κατακερματίζεται λόγω της μη ομοιόμορφης δέσμευσης του, ένα πρόβλημα που γίνεται πιο έντονο με την πάροδο του χρόνου. Ένα πρόβλημα που έχει ως αποτέλεσμα την εξυπηρέτηση όλο και λιγότερων αιτήσεων παρά την ύπαρξη των απαραίτητων πόρων για την εξυπηρέτησή τους. Οι δυναμικοί αλγόριθμοι που αναπτύξαμε αντιμετωπίζουν αποδοτικά το πρόβλημα της λειτουργίας του δικτύου με την άμεση λήψη αποφάσεων και τη χρήση κατάλληλων τεχνικών ανασυγκρότησης του δικτύου. Επιπλέον μελετήσαμε το πρόβλημα σχεδιασμού δικτύων πολλαπλών περιόδων. Η συνήθης πρακτική που ακολουθείται σε αυτήν την περίπτωση είναι η χρήση περιθωρίων χειρότερης περίπτωσης που εξασφαλίζουν την απρόσκοπτη λειτουργία κατά το σύνολο της διάρκειας ζωής του δικτύου. Τα ελαστικά οπτικά δίκτυα σε συνδυασμό με τα προγραμματιζόμενα δίκτυα επιτρέπουν τη δυναμική λειτουργία του, κάνοντας παράλληλα δυνατή τη μετάδοση με τη χρήση των απολύτως απαραίτητων περιθωρίων. Οι αλγόριθμοι που αναπτύξαμε προς αυτήν την κατεύθυνση κάνουν χρήση των απολύτως απαραίτητων περιθωρίων ενώ παράλληλα στοχεύουν στην επαναχρησιμοποίηση του υπάρχοντος εξοπλισμού, μια στρατηγική που προσφέρει σημαντικά οικονομικά οφέλη στους διαχειριστές των δικτύων. Τέλος, προτείναμε μια τεχνική για τη λειτουργία δυναμικών δικτύων. Μια σημαντική απαίτηση κατά τη φάση λειτουργίας των δικτύων είναι η ελαχιστοποίηση του χρόνου που απαιτείται για την εξυπηρέτηση των αιτήσεων από τη στιγμή της άφιξής τους με παράλληλη βελτιστοποίηση των αποφάσεων που λαμβάνονται για τη δέσμευση των πόρων του δικτύου. Η συνήθης πρακτική που ακολουθείται για την επίλυση αυτών των προβλημάτων είναι η χρήση αλγορίθμων ακέραιου γραμμικού προγραμματισμού (Integer Linear Programming). Επειδή όμως ο υψηλός χρόνος εκτέλεσης τα καθιστά μη αποδοτικά για την επίλυση προβλημάτων πραγματικού μεγέθους χρησιμοποιούνται τελικά ευριστικοί (heuristic) αλγόριθμοι, η απόδοση των οποίων αρκετά συχνά υστερεί σημαντικά σε σύγκριση με τη βέλτιστη. Για την αποδοτική επίλυση δυναμικών προβλημάτων προτείνουμε μία τεχνική που κάνει χρήση ενός βέλτιστου αλγορίθμου που εκτελείται περιοδικά, από τη λύση του οποίου εξάγονται οι παράμετροι που χρησιμοποιούνται για την καθοδήγηση των αποφάσεων πραγματικού χρόνου.