Ο πιο σύγχρονος και περισσότερα υποσχόμενος τύπος οπτικών δικτύων, είναι τα οπτικά δίκτυα πολυπλεξίας διαίρεσης μήκους κύματος (Wavelength Division Multiplexing – WDM). Τα δίκτυα αυτά διαθέτουν τεράστια χωρητικότητα και αναμένεται να αποτελέσουν τα μελλοντικά δίκτυα κορμού για τη μεταφορά μεγάλου όγκου δεδομένων. Η πλήρης αξιοποίηση της χωρητικότητας των WDM δικτύων, όμως, απαιτεί την επίλυση ειδικών θεμάτων που σχετίζονται µε τις ιδιαιτερότητες και τη φύση των WDM οπτικών δικτύων. Το σημαντικότερο ίσως από αυτά είναι το πρόβλημα της δρομολόγησης και ανάθεσης μήκους κύματος (Routing and Wavelength Assignment – RWA), πάνω στο οποίο έχει αναπτυχθεί έντονη ερευνητική δραστηριότητα τα τελευταία χρόνια, το οποίο είναι NP-πλήρες. Ένα άλλο θέμα που χρήζει ιδιαίτερης προσοχής είναι οι εξασθενήσεις που υφίσταται ένα σήμα μέσα στο οπτικό δίκτυο. Όταν λοιπόν κάποιο σήμα διαδίδεται κατά μήκος ενός οπτικού μονοπατιού πέφτει η ποιότητα του εξαιτίας των φυσικών επιδράσεων που δέχεται. Οι φυσικές επιδράσεις κατά κανόνα μειώνουν τον λόγο σήματος προς θόρυβο (SNR), με αποτέλεσμα να αυξηθεί σημαντικά και η συχνότητα εμφάνισης λαθών (BER) στον κόμβο προορισμού. Αν η παραπάνω συχνότητα εμφάνισης λαθών είναι μεγαλύτερη από ένα καθορισμένο όριο, τότε το αίτημα δρομολόγησης θα πρέπει να απορριφθεί. Επομένως κατά την επίλυση του RWA προβλήματος θα πρέπει να ληφθούν υπόψη οι επιδράσεις που προκαλούνται στο σήμα λόγω των φυσικών χαρακτηριστικών του δικτύου. Στην παρούσα διπλωματική εργασία έχει υλοποιηθεί ένας αλγόριθμος για την επίλυση του στατικού RWA, που βασίζεται στην μοντελοποίηση ενός γραμμικού προβλήματος (Linear Programming – LP). Κατά την μοντελοποίηση λαμβάνονται υπόψη οι πιο σημαντικές επιδράσεις, όπως η χρωματική διασπορά (Chromatic Dispersion – CD), η διασπορά τρόπου πόλωσης (Polarization Mode Dispersion – PMD), η ενισχυμένη αυθόρμητη εκπομπή (Amplifier Spontaneous Emission – ASE) και η αλληλεπίδραση γειτονικών καναλιών (crosstalk). Η επίδραση των τριών πρώτων παραμέτρων εξαρτάται αποκλειστικά από τα χαρακτηριστικά των συνδέσμων και μοντελοποιούνται σύμφωνα με αναλυτικούς τύπους, ενώ η επίδραση του crosstalk εξαρτάται από τον αριθμό των οπτικών μονοπατιών που διατρέχουν ένα σύνδεσμο. Προτείνεται επίσης μία συνάρτηση βελτιστοποίησης ώστε να προκύπτουν ακέραιες λύσεις με πολύ μεγάλη πιθανότητα από την επίλυση του LP (Linear Program) προβλήματος. Αυτός ο αλγόριθμος εφαρμόζεται σε ένα μητροπολιτικό δίκτυο και λαμβάνονται συγκριτικά αποτελέσματα για διάφορες παραμέτρους των φυσικών στοιχείων του δικτύου. / Wavelength division multiplexing (WDM) is a promising technology for faster and more reliable data communication networks. In a WDM network several optical signals are sent on the same fiber using different wavelength channels. Multiple WDM channels from different end users may be multiplexed on the same fiber. Traditionally only a small fraction of the fiber capacity is in use, but by using WDM it is possible to exploit this huge capacity more efficiently. Under WDM, the optical transmission spectrum is curved up into a number of non-overlapping wavelength bands, with each wavelength supporting a single communication channel operating at whatever rate one desires. WDM technology has been recognized as one of the key components of the future networks. Routing and wavelength assignment (RWA) is a crucial issue for WDM optical network designers. In wavelength routed WDM optical networks connections between terminal stations are established through the use of lightpaths. Given a WDM optical topology and a set of connection requests between pairs of source-destination terminal nodes, the problem of how to route all the lightpaths simultaneously, one per connection, and which wavelength should be assigned to each one of them, subject to minimizing network resources or maximizing traffic characteristics, arises; this is known as the Routing and Wavelength Assignment problem RWA. In transparent networks, the signal quality is subject to a variety of physical impairments, such as polarization mode dispersion (PMD), amplified spontaneous emission (ASE) noise and chromatic dispersion (CD) and crosstalk. These impairments are linearly modeled and handled effectively by a set of analytical formulas as additional constraints on RWA. We apply our algorithm to perform impairment-constraint based RWA, in order to obtain comparative results of a typical metropolitan network's performance under various network and impairment parameters, such as bit rate, amplifier gain and type, modulation format used, etc.

Σε ένα δίκτυο πολυπλεξίας διαίρεσης μήκους κύματος (Wavelength Division Multiplexing - WDM), κάθε οπτική ίνα μεταφέρει κίνηση υψηλού ρυθμού σε διαφορετικά μήκη κύματος δημιουργώντας έναν αριθμό από µη επικαλυπτόμενα κανάλια μέσα σε μία μόνο ίνα. Η πιο κοινή αρχιτεκτονική που χρησιμοποιείται για την επικοινωνία σε WDM οπτικά δίκτυα είναι η δρομολόγηση μηκών κύματος, όπου οπτικοί παλμοί μεταδίδονται μέσω οπτικών μονοπατιών, δηλαδή αμιγώς WDM κανάλια που μπορεί να διατρέχουν έναν αριθμό από συνεχόμενες ίνες. Τα σημερινά οπτικά δίκτυα κορμού είναι κυρίως δίκτυα από σημείο σε σημείο (αδιαφανή), όπου το σήμα αναγεννάται σε κάθε ενδιάμεσο κόμβο μέσω οπτο-ηλεκτρο-οπτικής (ΟΕΟ) μετατροπής. Η τάση που επικράτησε τα προηγούμενα χρόνια δείχνει μία εξέλιξη σε δίκτυα χαμηλού κόστους και υψηλής χωρητικότητας που δεν χρησιμοποιούν OEO μετατροπή. Αρχικά, το κόστος ενός αδιαφανούς δικτύου μπορεί να μειωθεί με την μετακίνηση σε ένα δίκτυο όπου η OEO μετατροπή γίνεται μόνο σε ορισμένους κόμβους, το οποίο συνήθως αναφέρεται ως ημιδιαφανές δίκτυο. Ο στόχος είναι η ανάπτυξη ενός αμιγώς διάφανου οπτικού δικτύου όπου το σήμα θα παραμένει σε οπτική μορφή κατά μήκος ολόκληρου του οπτικού μονοπατιού. Δεδομένου ότι τα οπτικά μονοπάτια είναι οι βασικές οντότητες μεταγωγής ενός WDM δικτύου δρομολόγησης μήκους κύματος, η αποτελεσματική εγκατάσταση τους είναι υψηλής σημασίας. Επομένως, είναι σημαντικό να προτείνουμε αποδοτικούς αλγορίθμους για την επιλογή των μονοπατιών των αιτήσεων σύνδεσης και να αναθέσουμε μήκη κύματος σε κάθε ένα σύνδεσμο κατά μήκος αυτών των μονοπατιών. Αυτό το πρόβλημα είναι γνωστό ως πρόβλημα δρομολόγησης και ανάθεσης μήκους κύματος (Routing and Wavelength Assignment - RWA). Στα διαφανή και ημιδιαφανή οπτικά δίκτυα, η ποιότητα της μετάδοσης του σήματος (QoT) επηρεάζεται σημαντικά από τις φυσικές εξασθενήσεις. Το RWA πρόβλημα με την παρουσία φυσικών εξασθενήσεων αναφέρεται ως Impairment aware (ΙΑ-) RWA πρόβλημα. Στην παρούσα διδακτορική έρευνα αρχικά ασχοληθήκαμε με την ανάπτυξη και την αξιολόγηση αλγορίθμων δρομολόγησης και ανάθεσης μήκους κύματος σε διαφανή και ημιδιαφανή οπτικά WDM δίκτυα θεωρώντας ότι οι αιτήσεις σύνδεσης είναι γνωστές εκ των προτέρων (φάση σχεδιασμού δικτύων θεωρώντας στατική κίνηση). Εξαιτίας των φυσικών φαινομένων, η επιλογή του κάθε οπτικού μονοπατιού επηρεάζει και επηρεάζεται από τις επιλογές των άλλων οπτικών μονοπατιών. Η αλληλεπίδραση μεταξύ των οπτικών μονοπατιών στο στατικό πρόβλημα είναι δύσκολο να μοντελοποιηθεί καθώς η χρησιμοποίηση των οπτικών μονοπατιών αποτελούν μεταβλητές του προβλήματος. Αρχικά προτείνουμε RWA αλγορίθμους, χωρίς να λαμβάνουμε υπόψη τις φυσικές εξασθενήσεις, οι οποίοι βασίζονται σε μοντελοποιήσεις γραμμικού προγραμματισμού (Linear Programming - LP) και τείνουν να δίνουν ακέραιες λύσεις. Στην συνέχεια επεκτείνουμε τις μοντελοποιήσεις αυτές και παρουσιάζουμε δύο αλγορίθμους οι οποίοι λαμβάνουν υπόψη τις φυσικές εξασθενήσεις (IA-RWA). Στην πρώτη μοντελοποίηση οι φυσικές εξασθενήσεις λαμβάνονται υπόψη έμμεσα με βάση τις πηγές που προκαλούν τις εξασθενήσεις, ενώ στην δεύτερη μοντελοποίηση οι φυσικές εξασθενήσεις λαμβάνονται υπόψη άμεσα συνδυάζοντας τις παραμέτρους οι οποίες σχετίζονται με την διασπορά του θορύβου. Ο στόχος των IA-RWA αλγορίθμων είναι η ελαχιστοποίηση του αριθμού των μηκών κύματος που χρειάζονται για να εγκατασταθούν όλα τα οπτικά μονοπάτια και ταυτόχρονα η ελαχιστοποίηση της εξασθένησης του σήματος του κάθε οπτικού μονοπατιού. Αναπτύχθηκαν επίσης δύο IA-RWA αλγόριθμοι πολλαπλών κριτηρίων για δυναμική κίνηση (online αλγόριθμοι, που χρησιμοποιούνται κυρίως στην φάση λειτουργίας του δικτύου) για διαφανή δίκτυα. Οι αλγόριθμοι αυτοί λαμβάνουν υπόψη τους συνδυαστικά τις παραμέτρους του φυσικού επιπέδου και του επιπέδου δικτύου, ορίζοντας διανύσματα κόστους για κάθε συνδέσμου και για κάθε μονοπάτι. Ο ένας αλγόριθμος λαμβάνει τις φυσικές εξασθενήσεις έμμεσα, ενώ ο άλλος έμμεσα. Με βάση τους αλγορίθμους πολλαπλών κριτηρίων, προτείναμε διάφορες τεχνικές προστασίας των μονοπατιών για την αντιμετώπιση βλαβών στο δίκτυο λαμβάνοντας υπόψη τους περιορισμούς εξασθένησης του φυσικού επιπέδου. Ο αλγόριθμος που λαμβάνει άμεσα υπόψη τις φυσικές εξασθενήσεις, επεκτάθηκε ώστε να λαμβάνει υπόψη την ύπαρξη αναγεννητών σε συγκεκριμένους κόμβους του δικτύου καθιστώντας τον ικανό κατ’ αυτόν τον τρόπο να λειτουργεί σε ημιδιαφανή δίκτυα. Μελετήσαμε επιπλέον RWA αλγορίθμους σε WDM δίκτυα τα οποία περιλαμβάνουν κόμβους με περιορισμούς χρώματος (colored) και κατεύθυνσης (direction). Ειδικότερα, επικεντρωθήκαμε σε τέσσερις αρχιτεκτονικές κόμβων που χρησιμοποιούν add/drop ports με τις ακόλουθες ρυθμίσεις i) colored/directed, ii) colored/directionless, iii) colorless/ directed, και iv) colorless/directionless. Αυτές οι αρχιτεκτονικές έχουν διαφορετικό κόστος υλοποίησης, δηλαδή η πιο ευέλικτη αρχιτεκτονική είναι και η πιο ακριβή. Παράλληλα ασχοληθήκαμε με την μελέτη RWA αλγορίθμων σε ευέλικτα οπτικά δίκτυα όπου υπάρχει η επιπλέον δυνατότητα επιλογής του ρυθμού μετάδοσης (και του είδους διαμόρφωσης) που θα χρησιμοποιηθεί στο οπτικό μονοπάτι. Η δυνατότητα αυτή επιτρέπει στα κυκλώματα συνδέσεων, σε μελλοντικά οπτικά δίκτυα κορμού, να μην είναι πλέον στατικά και μονολιθικά, αλλά να μπορούν να αναπροσαρμόζονται δυναμικά στην ζήτηση, τόσο ως προς τον ρυθμό τους όσο και ως προς τον τρόπο διαμόρφωσης. Στα δίκτυα πολλαπλών ρυθμών δεν αρκεί να θεωρήσουμε μία συγκεκριμένη μέγιστη απόσταση μετάδοσης για κάθε τεχνική διαμόρφωσης/ρυθμό μετάδοσης, αλλά θα πρέπει να λάβουμε υπόψη τις αλληλεπιδράσεις μεταξύ των συνδέσεων που μεταδίδονται με διαφορετικό ρυθμό μετάδοσης. Οι προτεινόμενοι αλγόριθμοι προσαρμόζουν την απόσταση μετάδοσης των συνδέσεων ανάλογα με την κατάσταση χρησιμοποίησης του δικτύου, έτσι ώστε να αποφευχθούν τα φαινόμενα παρεμβολών πολλαπλών ρυθμών, παρέχοντας τη δυνατότητα να εγκατασταθούν συνδέσεις με αποδεκτή ποιότητα μετάδοσης. Τέλος, μελετήσαμε RWA αλγορίθμους που έχουν ως στόχο την μείωση της κατανάλωσης της ενέργειας σε WDM οπτικά δίκτυα, για την περίπτωση της στατικής κίνησης. Η μείωση της ενέργειας επιτυγχάνεται μέσω της μείωσης του αριθμού των συσκευών του δικτύου που είναι ιδιαίτερα δαπανηρές σε ενέργεια. Αναπτύξαμε ενεργοαποδοτικούς αλγορίθμους για διαφανή και ημιδιαφανή δίκτυα με την χρήση ILP μοντελοποιήσεων. / Ιn a wavelength division multiplexing (WDM) network, each fiber link carries high-rate traffic at several different wavelengths, thus creating multiple channels within a single fiber. The most common architecture utilized for establishing communication in WDM optical networks is wavelength routing, where optical pulse-trains are transmitted through lightpaths, that is, all-optical WDM channels that may span multiple consecutive fibers. Current optical core networks are mainly point-to-point (opaque) networks, where the signal is regenerated at every intermediate node via optical-electronic-optical (OEO) conversion. The trend in recent years shows an evolution toward low-cost and high-capacity all-optical networks that do not utilize OEO. Initially, the cost of an opaque network can be reduced by moving toward a network where OEO conversion is employed only at some nodes, which is usually referred to as a translucent network. The ultimate goal is the development of an all-optical transparent network, where the data signal remains in the optical domain for the entire lightpath. Since the lightpaths are the basic switched entities of a wavelength routed WDM network, their effective establishment and usage are crucial. Thus, it is important to propose efficient algorithms to select the routes for the requested connections and to assign wavelengths on each of the links along these routes. This is known as the routing and wavelength assignment (abbreviated RWA) problem. In a transparent or translucent network, where the signal on a lightpath remains in the optical domain, the quality of transmission (QoT) is significantly affected by physical limitations of fibers and optical components. The RWA problem in the presence of physical layer impairments is referred as Impairment aware (IA-) RWA. We first consider the offline version (network planning phase assuming static traffic) of the RWA problem in transparent and translucent optical networks. In such networks, the signal quality of transmission degrades due to physical layer impairments. Because of certain physical effects, routing choices made for one lightpath affect and are affected by the choices made for the other lightpaths. This interference among the lightpaths is particularly difficult to formulate in an offline algorithm since, in this version of the problem, we start without any established connections and the utilization of lightpaths are the variables of the problem. We initially present algorithms for solving the pure (without impairments) RWA problem based on a Linear Programming (LP)-relaxation formulation that tends to yield integer solutions. Then, we extend these algorithms and present two IA-RWA algorithms for transparent networks that account for the interference among lightpaths in their formulation. The first algorithm takes the physical layer indirectly into account by limiting the impairment-generating sources. The second algorithm uses noise variance-related parameters to directly account for the most important physical impairments. The objective of the resulting cross-layer optimization problem is not only to serve the connections using a small number of wavelengths (network layer objective), but also to select lightpaths that have acceptable quality of transmission (physical layer objective). We propose an algorithm for translucent networks that decomposes the problem into two sub-problems. Initially, we formulate the problem of choosing the sequence of regenerators to be used by the so called “non-transparent connections” as a virtual topology problem and propose various offline IA-RWA algorithms, ranging from integer linear programs (ILP) to simple heuristic algorithms, to solve it. We then transform the initial traffic matrix so as to obtain a traffic matrix that consists only of connections that can be served transparently and apply an IA-RWA algorithm developed for transparent networks. Next, we present two algorithms, for the online version (network operation phase assuming dynamic traffic) of the RWA problem, which are based on the multicost concept and use multiple cost parameters (that is, a cost vector, as opposed to a single scalar cost) for characterizing a link and handle the impairments directly and indirectly, respectively. We show that the use of the multicost approach to solve the online IA-RWA problem can be quite beneficial, both in terms of performance (blocking probability, execution time) and it terms of functionality. Multiple candidate lightpaths are calculated that have, by construction, good QoT performance, making also fault tolerance provisioning easy. We also present an IA-RWA algorithm for translucent WDM networks. We extend an algorithm developed for transparent networks, to obtain a number of IA-RWA algorithms that work in translucent networks and make use of the regenerators that are present at certain network locations when necessary. We also consider RWA in a WDM network consisting of optical cross-connect (OXC) nodes that have color and direction constraints. These restricted node architectures have a smaller cost than the more flexible (and best performing) ones usually assumed in the RWA problem. In particular, we concentrate on four node architectures that use add/drop ports with the following configurations: i) colored/directed, ii) colored/directionless, iii) colorless/ directed, and iv) colorless/directionless. We consider the problem of planning a mixed line rates (MLR) WDM transport optical network. In such networks, different modulation formats are usually employed to support the transmission at different line rates. Previously proposed planning algorithms have used a transmission reach bound for each modulation format/line rate, mainly driven by single line rate systems. However, transmission experiments in MLR networks have shown that physical layer interference phenomena are more severe between among transmissions that utilize different modulation formats. Thus, the transmission reach of a connection with a specific modulation format/line rate depends also on the other connections that co-propagate with it in the network. To plan a MLR WDM network, we present RWA algorithms that adapt the transmission reach of each connection according to the use of the modulation formats/line rates in the network. The proposed algorithms are able to plan the network so as to alleviate cross-rate interference effects, enabling the establishment of connections of acceptable quality over paths that would otherwise be prohibited. Finally, we consider the energy minimization problem in optical networks from an algorithmic perspective. The objective of our proposed algorithms is to plan optical WDM networks so as to minimize the energy consumed, by minimizing the number of the most energy-consuming components. Such components can be amplifiers, regenerators, add/drop terminals, optical fibers, etc. We present algorithms for solving the Energy-Aware Routing and Wavelength Assignment (EA-RWA) problem based on ILP formulations that incorporates energy consuming modules.

Τα οπτικά δίκτυα αποτελούν την αποδοτικότερη επιλογή όσον αφορά την εγκατάσταση ευρυζωνικών δικτύων κορμού, καθώς παρουσιάζουν μοναδικά χαρακτηριστικά μετάδοσης. Διαθέτουν τεράστιο εύρος ζώνης, υψηλή αξιοπιστία, ενώ επίσης έχουν μειωμένο κόστος μετάδοσης ανά bit πληροφορίας σε σχέση με τα υπόλοιπα ενσύρματα δίκτυα. Σημαντικές ερευνητικές προσπάθειες έχουν επικεντρωθεί στις προοπτικές μετάβασης από τα παραδοσιακά στατικά δίκτυα κυκλωμάτων, στα οποία χρησιμοποιείται από-σημείο-σε-σημείο οπτική μετάδοση, σε δίκτυα μετάδοσης δεδομένων που προσφέρουν δυναμική και γρήγορη επαναρύθμιση των οπτικών μονοπατιών και πρόσβαση σε χωρητικότητες κάτω του ενός μήκους κύματος, ανάλογα με τις απαιτήσεις των χρηστών και των εκάστοτε εφαρμογών. Τα τελευταία χρόνια υπάρχει η τάση για δημιουργία δυναμικών και επαναρυθμιζόμενων οπτικών δικτύων μεταγωγής κυκλώματος (Optical Circuit Switching), τα οποία θα βασίζονται σε διαφανείς κόμβους μεταγωγής. Η μονάδα μεταγωγής των δικτύων οπτικής μεταγωγής κυκλώματος είναι τα οπτικά μονοπάτια (lightpaths) και το βασικό πρόβλημα βελτιστοποίησης που σχετίζεται με την αποδοτική εκμετάλλευση της χωρητικότητας τέτοιων δικτύων είναι το πρόβλημα της δρομολόγησης και ανάθεσης μήκους κύματος (Routing and Wavelength Assignment - RWA). Στα αμιγώς διαφανή (transparent) οπτικά δίκτυα κυκλώματος η μετάδοση του σήματος υποβαθμίζεται από μια σειρά φυσικών εξασθενήσεων (physical impairments), σε σημείο που η εγκατάσταση ενός οπτικού μονοπατιού να μην είναι αποδεκτή. Για την αντιμετώπιση αυτού του προβλήματος στην παρούσα διατριβή προτείνουμε αλγόριθμους οι οποίοι λαμβάνουν υπόψη τους τις φυσικές εξασθενήσεις (Impairment Aware RWA ή ΙΑ-RWA algorithms) τόσο για στατική όσο και για δυναμική κίνηση. Συγκεκριμένα, παρουσιάζουμε έναν IA-RWA αλγόριθμο για στατική κίνηση, ο οποίος βασίζεται στην τεχνική της LP-χαλάρωσης και χρησιμοποιεί αποδοτικές μεθόδους για την παραγωγή ακεραίων λύσεων. Εκφράζουμε τις φυσικές εξασθενήσεις μέσω επιπλέον περιορισμών στην LP μοντελοποίηση του RWA προβλήματος, επιτυγχάνοντας την διαστρωματική βελτιστοποίηση (cross-layer optimization) πάνω στο φυσικό επίπεδο και στο επίπεδο δικτύου. Στη συνέχεια, προτείνουμε έναν IA-RWA αλγόριθμο πολλαπλών κριτηρίων (multi-cost) για δυναμική κίνηση. Ορίζουμε ένα διάνυσμα από κόστη για κάθε σύνδεσμο και τις πράξεις συσχέτισης αυτών, ώστε να μπορούμε να υπολογίσουμε το διάνυσμα από κόστη ενός μονοπατιού και μέσω αυτού να αξιολογήσουμε την ποιότητα μετάδοσης των διαθέσιμων μηκών κύματος του μονοπατιού. Για την εξυπηρέτηση μιας νέας αίτησης σύνδεσης, ο αλγόριθμος πολλαπλών κριτηρίων υπολογίζει το σύνολο των μη κυριαρχούμενων μονοπατιών, από την πηγή στο ζητούμενο προορισμό, και μετά εφαρμόζει μια πολιτική για να επιλέξει το βέλτιστο οπτικό μονοπάτι. Προτείνουμε και αξιολογούμε την απόδοση μιας σειράς από πολιτικές επιλογής, η κάθε μια από τις οποίες ουσιαστικά αντιστοιχεί σε έναν διαφορετικό δυναμικό IA-RWA αλγόριθμο. Στη συνέχεια, στρέφουμε την προσοχή μας στα δίκτυα οπτικής μεταγωγής καταιγισμών (Optical Burst Switching – OBS), τα οποία θεωρούνται ότι αποτελούν το επόμενο στάδιο των δικτύων οπτικής μεταγωγής κυκλώματος, όπου η δέσμευση της χωρητικότητας γίνεται για μικρότερο χρονικό διάστημα. Στα OBS δίκτυα, τα πακέτα που έχουν τον ίδιο προορισμό και παρόμοιες απαιτήσεις ποιότητας υπηρεσίας συναθροίζονται σε καταιγισμούς (bursts). Οι καταιγισμοί μεταδίδονται πάνω από αμιγώς οπτικά μονοπάτια, τα οποία ρυθμίζονται με τη χρήση πακέτων ελέγχου που μεταδίδονται πριν από τους αντίστοιχους καταιγισμούς και τα οποία επεξεργάζονται ηλεκτρονικά οι ενδιάμεσοι κόμβοι. Επικεντρώνουμε την προσοχή μας σε δυο βασικά στοιχεία ενός δικτύου οπτικής μεταγωγής καταιγισμών, την διαδικασία συναρμολόγησης καταιγισμών και τα πρωτόκολλα σηματοδοσίας, και παραθέτουμε δύο προτάσεις για την αποδοτική ανάθεσης χωρητικότητας σε αυτά τα δίκτυα. Συγκεκριμένα, προτείνουμε και αξιολογούμε ένα νέο αλγόριθμο συναρμολόγησης καταιγισμών που βασίζεται στη μέση καθυστέρηση των πακέτων που αποτελούν έναν καταιγισμό. Δείχνουμε ότι ο προτεινόμενος αλγόριθμος συναρμολόγησης καταιγισμών μειώνει την διασπορά της καθυστέρησης των πακέτων (packet delay jitter), η οποία είναι σημαντική για μια σειρά από εφαρμογές. Στην συνέχεια προτείνουμε ένα νέο αμφίδρομο (two-way) πρωτόκολλο σηματοδοσίας που βασίζεται στις μελλοντικές (in-advance) και χαλαρωμένες χρονικά (relaxed timed) δεσμεύσεις χωρητικότητας. Στο προτεινόμενο πρωτόκολλο, κατά τη φάση εγκατάστασης της σύνδεσης οι δεσμεύσεις χωρητικότητας γίνονται για χρονικό διάστημα μεγαλύτερο από το χρόνο μετάδοσης του καταιγισμού, ώστε να αυξηθεί η πιθανότητα επιτυχούς εγκατάστασης στους επόμενους συνδέσμους του μονοπατιού. Συγκρίνουμε το προτεινόμενο πρωτόκολλο με τυπικά πρωτόκολλα που έχουν προταθεί στη βιβλιογραφία και δείχνουμε οτι μπορεί να χρησιμοποιηθεί για την παροχή διαφοροποιημένης ποιότητα υπηρεσιών (QoS differentiation) στους χρήστες του OBS δικτύου. Στη συνέχεια, εξετάζουμε το πρόβλημα της δρομολόγησης και του χρονοπρογραμματισμού συνδέσεων με χαλαρό - μη συγκεκριμένο χρόνο εκκίνησης, πρόβλημα που εμφανίζεται υπό ελαφρώς διαφορετική μορφή σε δίκτυα οπτικής μεταγωγής κυκλώματος, οπτικής μεταγωγής καταιγισμών αλλά και μεταγωγής πακέτου. Η εξυπηρέτηση αυτών των συνδέσεων γίνεται μέσω μελλοντικών δεσμεύσεων χωρητικότητας, τρόπος ο οποίος είναι τυπικός για να παρεχθεί εγγυημένη ποιότητα υπηρεσίας (QoS) στους χρήστες ενός δικτύου. Θεωρούμε ότι μας δίνεται μια σύνδεση με γνωστή πηγή και προορισμό, γνωστό ή άγνωστο όγκο δεδομένων και γνωστό ρυθμό μετάδοσης και ζητείται να αποφασίσουμε το μονοπάτι που θα ακολουθήσουν τα δεδομένα και το χρόνο που θα αρχίσει η μετάδοση. Διακριτοποιούμε το χρόνο και χρησιμοποιούμε κατάλληλα διανύσματα ως δομές δεδομένων για να αναπαραστήσουμε τη διαθεσιμότητα των συνδέσμων του δικτύου ως συνάρτηση του χρόνου. Χρησιμοποιούμε αυτά τα διανύσματα σε ένα αλγόριθμο πολλαπλών κριτηρίων για τη δρομολόγηση και το χρονοπρογραμματισμό των συνδέσεων. Αρχικά, παρουσιάζουμε έναν αλγόριθμο πολλαπλών κριτηρίων μη πολυωνυμικής πολυπλοκότητας, ο οποίος βασίζεται στην έννοια των μη-κυριαρχούμενων μονοπατιών. Μετά προτείνουμε δύο ευριστικούς αλγορίθμους πολυωνυμικής πολυπλοκότητας, ορίζοντας κατάλληλες σχέσεις ψευδο-κυριαρχίας οι οποίες μειώνουν το χώρο των λύσεων. Επίσης, προτείνουμε ένα μηχανισμό branch-and-bound, ο οποίος μπορεί να μειώσει το χώρο λύσεων στην περίπτωση που χρησιμοποιούμε μια συγκεκριμένη συνάρτηση βελτιστοποίησης για όλες τις συνδέσεις. Η απόδοση των προτεινόμενων αλγορίθμων αξιολογήθηκε σε ένα δίκτυο οπτικής μεταγωγής καταιγισμών, ωστόσο τα συμπεράσματα και η εφαρμοσιμότητα του προτεινόμενου αλγόριθμου επεκτείνεται και σε άλλου είδους οπτικά δίκτυα. Τέλος, εξετάζουμε το πρόβλημα του συνδυασμένου χρονοπρογραμματισμού των δικτυακών και υπολογιστικών πόρων που απαιτούνται για την εκτέλεση μιας διεργασίας σε ένα Δίκτυο Πλέγματος (Grid Network). Τα Δίκτυα Πλέγματος θεωρούνται το επόμενο βήμα στον τομέα των κατανεμημένων συστημάτων, εισάγοντας την έννοια της “κοινής” χρήσης γεωγραφικά κατανεμημένων και ετερογενών πόρων (υπολογιστικών, αποθηκευτικών, δικτυακών, κλπ.). Υποθέτουμε ότι η εκτέλεση μιας διεργασίας αποτελείται από δύο διαδοχικά στάδια: (α) Τη μεταφορά των δεδομένων εισόδου της διεργασίας από μια αποθηκευτική μονάδα σε μια συστοιχία υπολογιστών (cluster), (β) την εκτέλεση της διεργασίας στη συστοιχία υπολογιστών. Επεκτείνουμε τον αλγόριθμο πολλαπλών κριτηρίων για τη δρομολόγηση και το χρονοπρογραμματισμό συνδέσεων που περιγράφηκε προηγουμένως, έτσι ώστε να χειρίζεται με ένα συνδυασμένο τρόπο δικτυακούς και υπολογιστικούς πόρους για την εκτέλεση των διεργασιών. Ο προτεινόμενος αλγόριθμος επιστρέφει: (i) τη συστοιχία υπολογιστών όπου θα εκτελεστεί η διεργασία, (ii) το μονοπάτι το οποίο θα ακολουθήσουν τα δεδομένα εισόδου, (iii) τη χρονική στιγμή εκκίνησης μετάδοσης και (iv) τη χρονική στιγμή εκκίνησης εκτέλεσης της διεργασίας στη συστοιχία υπολογιστών. Ξεκινάμε παρουσιάζοντας έναν αλγόριθμο μη πολυωνυμικού χρόνου και μετά, αφού μειώσουμε κατάλληλα το χώρο λύσεων, δίνουμε έναν ευριστικό αλγόριθμο πολυωνυμικής πολυπλοκότητας. / Optical networks have developed rapidly over the last ten years and are widely used in core networks due to their superior transmission characteristics. Optical networks provide huge available capacity that can be efficiently utilized using wavelength division multiplexing (WDM) and high reliability at the lowest cost per bit ratio when compared to the other wired and wireless networking solutions. Much research has focused on ways to evolve from the typical point-to-point opaque WDM networks that are currently employed in the core to optical networks that are dynamically and quickly reconfigurable and can provide on-demand services to users at subwavelength granularity according to users’ requirements. The most common architecture utilized for establishing communication in WDM optical networks is wavelength routing that fall in the general category of Optical Circuit Switched (OCS) networks. The switched entities in OCS networks are the lightpaths and the basic optimization problem that is related to the efficient allocation of bandwidth is the routing and wavelength assignment problem (RWA). The current optical technology employed in core networks is point-to-point transmission, where the signal is regenerated at every intermediate node via optical-electronic-optical (OEO) conversion. During the recent few years, the trend clearly shows an evolution towards low-cost and high capacity all-optical transparent networks that do not utilize OEO. In transparent OCS networks the signal of a lightpath remains in the optical domain and its quality deteriorates due to a series of physical layer impairments (PLIs). These PLIs may degrade the received signal quality to the extent that the bit-error rate (BER) at the receiver may be so high that signal detection may be infeasible for some lightpaths. To address this problem we proposed algorithms that take into account the PLIs, usually referred in the literature as Impairment Aware RWA or ΙΑ-RWA algorithms, for both offline (static) and online (dynamic) traffic. In particular we propose an IA-RWA algorithm for static traffic that is based on an LP-relaxation formulation and use various efficient methods to obtain integer solutions. The physical layer impairments are included as additional constraint in the LP formulation of the RWA problem, yielding a cross-layer optimization solution between the network and the physical layers. We then proceed and propose a multi-cost IA-RWA algorithm for dynamic traffic. We define a cost vector per link and associative operators to combine these vectors so as to calculate the cost vector of a path. The parameters of these cost vectors are chosen so as to enable the quick and efficient calculation of the quality of transmission of candidate lightpaths. To serve a connection request, the proposed multi-cost algorithm calculates the set of so called non-dominated paths from the given source to the given destination, and then applies an optimization policy to choose the optimal lightpath. We propose and evaluate various optimization policies that correspond to different online IA-RWA algorithms. We then turn our attention to Optical Burst Switched (OBS) networks, which are regarded as the next step from the OCS paradigm towards a more dynamic core network that can provide on demand subwavelength services to users. In OBS networks, the packets that have the same destination and similar quality of service requirements are aggregated into bursts at the ingress nodes. When a burst is aggregated, a control packet is transmitted and is electronically processed at intermediate nodes so as to configure them for the burst that will pass transparently afterwards. We focus on two key elements of an OBS network, and in particular the burst aggregation (or burstification) process and the signaling protocol, and we propose two solutions for the efficient allocation of bandwidth in OBS networks. We propose and evaluate a novel burst assembly algorithm that is based on the average delay of the packets that comprise a burst. We show that the proposed algorithm decreases the packet delay jitter among the packets, which is important for a number of applications, including real-time, video and audio streaming, and TCP applications. Next we propose a two-way reservation signaling protocol that utilizes in-advance and relaxed timed reservation of the bandwidth. In the connection establishment phase of the proposed protocol, bandwidth reservations can exceed the duration of burst transmission (thus, relaxing the timed reservations), so as to increase the acceptance probability for the rest of the path. By controlling the degree of the relaxed timed reservations the protocol can also provide service differentiation to the users. Next we examine the problem of routing and scheduling of connections with flexible starting time in networks that support advance reservations. This problem can arise in slightly different settings in Optical Circuit Switched, Optical Burst Switched, and Optical Packet Switched networks. Such connection requests are served through advanced reservations, a process which is used to provide quality of service to users. We assume that for a connection request we are given the source, the destination, and the size of the data to be transferred with a given rate, and we are asked to provide the path and the time that the transmission should start so as to optimize a certain performance metric. We discretize the time and we use appropriate data structures (in the form of vectors) to map the utilization of the links as a function of time. We use these vectors as cost parameters in a multi-cost algorithm. We initially present a multicost algorithm of non-polynomial complexity that uses a full domination relation between paths. We then propose two mechanisms to prune the solution space in order to obtain polynomial complexity algorithms. In the first mechanism we define pseudo-domination relations that are weaker than the full domination relation. We also propose a branch-and-bound extension to the optimum algorithm that can be used for a given specific optimization function. The performance of the multicost algorithm and its variations are evaluated in an OBS network, but this does not limit the applicability of the algorithm and the conclusions can be extended in the other optical networking paradigms. Finally, we examine the problem of joint reservation of communication and computation resources that are required by a task in a Grid Network. Grid Networks are considered as the next step in distributed systems, introducing the concept of shared usage of geographically distributed and heterogeneous resources (computation, storage, communication, etc.). We assume that the task execution consists of two phases: (a) the transfer of the input data from a data storage resource, or the scheduler to a computation resource (cluster), (b) the execution of a program at the cluster. We extend the multicost algorithm for the routing and scheduling of connections, outlined above, so as to handle the reservation of computation resources as its last leg. In this way the proposed algorithm performs a joint optimization for the communication and computation part required by a task and returns: (i) the cluster to the execute the task, (ii) the path to route the input data, (iii) the time to start the transmission of data, and (iv) the time to start the execution of the task. We start by presenting an algorithm of non-polynomial complexity and then by appropriately pruning the solution space, we give a heuristic algorithm of polynomial complexity. We show that in a Grid network where the tasks are cpu- and data-intensive important performance benefits can be obtained by jointly optimizing the use of the communication and computation resources.