Αλγόριθμοι δρομολόγησης και δέσμευσης φάσματος σε ελαστικά οπτικά δίκτυα

Abstract

The continuous growth of consumers’ IP traffic, fed by the generalization of broadband access through digital subscriber lines (DSL) and fiber to the home (FTTH) and the emerging rich- content high-rate and burst applications, such as video-on-demand, HDTV, and cloud computing, can be met only with the abundant capacity provided by optical core and metro networks. For the future, it is expected that the traffic will not only increase in volume (traffic increases by 34% on average per year) but will also exhibit high burstiness, resulting in large variations over time and direction. To cope with the increasing capacity requirements, WDM systems target the employment of higher rate and improved distance transmissions. However, the rigid granularity of WDM systems leads to inefficient capacity usage, a problem expected to become more significant with the deployment of the higher channel rate systems. To improve system efficiency, recent research efforts have focused on architectures that support variable spectrum connections. Typically, wavelength routed WDM networks operate over the ITU-T grid, that is, connections are established over a 100 or 50 GHz frequency spaced grid. Elastic optical networks assume the use of tunable transponders and a flexible spectrum grid or flex-grid. Flex-grid’s granularity is much finer than that of standard WDM systems: the spectrum is divided into spectrum slots (12.5 GHz) that can be combined to create channels that are as wide as needed. Tunable optical transponders, also called bandwidth variable transponders (BVTs) or software defined transponders, have been proposed. The key difference to standard transponders is that they can adapt several transmission parameters, such as the baudrate, the modulation format, the spectrum, the launch power or even the Forward Error Connection (FEC) code that they use. In a flexible network, a BVT uses just enough spectrum to serve the demand and every bandwidth-variable Optical Cross-Connect (OXC) on the path establishes a cross-connection with sufficient spectrum to create an appropriately sized end-to-end connection. we propose impairment-aware RSA (IARSA) algorithms for planning transparent and translucent flexible optical networks under physical layer impairments. Although core networks offer high capacities, they consume a non-negligible amount of energy. If the corresponding energy requirements grow analogously with the traffic volume in metro and core networks, they will sooner rather than later form a bottleneck for network communications. Thus, energy efficiency in optical networks is mandatory for the sustainability of the future Internet. The objectives of the current work are to identify the main causes of energy consumption for current fixedgrid wavelength division multiplexing and future flex-grid optical networks, and to propose and compare techniques for improving their energy efficiency. Toward this end, we carried out a comparative study of energy efficiency of elastic networks and fixed-grid single- line-rate and mixed-line-rate networks. Under realistic network scenarios, we calculated the energy consumption of the different components of the optical layer and demonstrated that by using energy-aware techniques in planning such networks, we can achieve significant power savings. Since energy prices are location dependent, especially in large networks, e.g., over continents, we show that accounting. We also consider the problem of dynamic connection establishment and spectrum defragmentation in flexible optical networks. During the operation phase, new connections are established and torn down dynamically with time. In contrast to traditional WDM networks, where spectrum assignment is uniform in the form of wavelengths, in flexible networks the spectrum eventually becomes fragmented, a problem that becomes more severe as time progresses. Thus, after a point the available spectrum is inefficiently utilized, the network serves fewer demands than one would expect at its actual load level, and connections are blocked even though there is enough spectrum on the links that could be used to serve them. The proposed algorithm reactively re-optimizes the network by shifting (“pushing”) in the spectrum domain and/or rerouting existing connections. We present an algorithm based on Integer Linear Programming (ILP) formulation that searches among all combinations of shiftings and reroutings and selects the one that minimizes the changes in existing connections. We also present a heuristic algorithm that recursively shifts/reroutes connections around a void. Our simulation results show that the blocking probability can be substantially reduced using the proposed techniques as opposed to a network that does not reactively defragments the spectrum. Next, we considered the problem of multi-period planning in optical transport networks. The common practice to ensure uninterrupted communication, is to over-provision lightpaths in terms of capacity and physical layer performance. Overprovisioning at the physical layer is achieved using worst-case assumptions and high margins in the estimation of the Quality of Transmission (QoT) when provisioning lightpaths. End-of-Life (EOL) system margins are used to anticipate performance deteriorations due to additional future interference, ageing and maintenance operations, while the design margin is used to account for inaccuracies in the QoT estimation. Such assumptions decrease network efficiency and increase the network cost. The advent of Elastic optical networks (EON) and software defined networking (SDN) will enable a dynamically and adaptably operated optical network. We envision an optical network that continuously senses the physical layer and optimizes connections accordingly. This enables static (e.g. worst case) physical information to be replaced by real-time (and accurate) information. We propose an algorithm that takes into account the actual physical layer performance to provision the lightpaths with actual (just enough) margins, optimizing the decisions regarding the placement and transmission parameters of transponders and regenerators including their launch powers. Using this algorithm in a multi-period planning scenario, we quantify the cost benefits of provisioning with actual margins as opposed to planning with worst case margins. Finally, we present an approach based on admission control and solution validation, for the embedding of virtual network requests in elastic optical networks. This makes use of an optimal offline VNE mechanism for parameterizing the way the online VNE algorithm will operate. To do so, it blocks virtual network requests that if served would negatively affect the performance of the network in the future (waste of network resources, increasing the fragmentation of the network, etc). For the same reason, the presented approach also rejects candidate reservation solutions for accepted (non-blocked) requests, calculated by the online allocation mechanism, and leads to their recalculation. We show through simulations that this optimally-driven approach, for online time-varying virtual network embedding in the elastic optical network, can improve network performance regarding accepted Virtual Network (VN) requests, with similar execution time as the respective (non-optimally-driven) heuristic.

Η συνεχής αύξηση της 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) αλγόριθμοι, η απόδοση των οποίων αρκετά συχνά υστερεί σημαντικά σε σύγκριση με τη βέλτιστη. Για την αποδοτική επίλυση δυναμικών προβλημάτων προτείνουμε μία τεχνική που κάνει χρήση ενός βέλτιστου αλγορίθμου που εκτελείται περιοδικά, από τη λύση του οποίου εξάγονται οι παράμετροι που χρησιμοποιούνται για την καθοδήγηση των αποφάσεων πραγματικού χρόνου.