Ανάπτυξη αλγορίθμων χρονοπρογραμματισμού σε οπτικά εκτεταμένα δίκτυα πρόσβασης

Abstract

Η ραγδαία αύξηση της κίνησης δεδομένων και η απαίτηση για ευέλικτες, ενεργειακά αποδοτικές και χαμηλού κόστους αρχιτεκτονικές δικτύων καθιστούν αναγκαία την επανεξέταση του τρόπου με τον οποίο πραγματοποιείται η συγκέντρωση και η μεταφορά της κίνησης στα οπτικά δίκτυα. Η εργασία αυτή εστιάζει στην ανάπτυξη και αξιολόγηση αλγορίθμων χρονοπρογραμματισμού σε οπτικά εκτεταμένες υποδομές που βασίζονται στη χρήση συνεκτικών point-to-multipoint (P2MP) πομποδεκτών και στη δημιουργία δέντρων φωτός (light-trees) για αποδοτικότερη κατανομή πόρων. Αρχικά παρουσιάζεται αναλυτικά το θεωρητικό υπόβαθρο και το σχετικό έργο, εστιάζοντας στις τεχνολογίες Digital Subcarrier Multiplexing (DSCM) και στα πλεονεκτήματα των συνεκτικών P2MP διατάξεων έναντι των κλασικών point-to-point (P2P) λύσεων. Στη συνέχεια, διατυπώνεται ένα μεικτό ακέραιο γραμμικό μοντέλο (MILP) για τη βέλτιστη τοποθέτηση και κατανομή πομποδεκτών, το οποίο λαμβάνει υπόψη φυσικούς περιορισμούς. Παράλληλα, αναπτύσσεται ένας ευριστικός αλγόριθμος (heuristic) βασισμένος στη μεθοδολογία Best-Fit Decreasing, που παρέχει προσεγγιστικές λύσεις με σημαντικά μικρότερο χρόνο εκτέλεσης. Οι δύο προσεγγίσεις εφαρμόζονται σε δύο διαφορετικά σενάρια: σε offline σενάριο, όπου η συνολική ζήτηση είναι εκ των προτέρων γνωστή και αναζητείται η βέλτιστη κατανομή πόρων του συστήματος, και σε online, όπου οι αφίξεις μεταβάλλονται χρονικά και λαμβάνονται υπόψη κόστη επαναδιαμόρφωσης και μη εξυπηρετούμενης κίνησης.