Την τελευταία δεκαετία έχει παρατηρηθεί μια σημαντική διάδοση των συστημάτων πλοήγησης οχημάτων. Τα συστήματα αυτά συνδυάζοντας τις δυνατότητες που προσφέρει η τεχνολογία και χρησιμοποιώντας τη γεωγραφική αναπαράσταση του οδικού δικτύου, την τρέχουσα θέση του οχήματος και συχνά πληροφορίες για την κίνηση προτείνουν στους οδηγούς τη διαδρομή που πρέπει να ακολουθήσουν για να φτάσουν πιο γρήγορα στον προορισμό τους. Οι εφαρμογές πλοήγησης οχημάτων μπορούν να προσφέρουν τη δυνατότητα διαχείρισης της κυκλοφορίας με τέτοιο τρόπο που επιτρέπει την αύξηση της χωρητικότητας του οδικού δικτύου και επομένως τη μείωση της συμφόρησης, χωρίς να είναι απαραίτητη η υψηλού κόστους επέκταση της οδικής υποδομής. Σε αντίθεση με το βέλτιστο για το χρήστη μοντέλο που εφαρμόζεται στα κλασικά συστήματα πλοήγησης και που δεν παρέχει καμία εγγύηση βελτίωσης της κυκλοφοριακής κατάστασης, για το σκοπό αυτό έχει προταθεί το βέλτιστο για το σύστημα μοντέλο. Το μοντέλο προτείνει διαδρομές με στόχο τη βελτίωση της κυκλοφοριακής κατάστασης στο δίκτυο, αλλά η εφαρμογή του είναι μη ρεαλιστική καθώς οι προτεινόμενες διαδρομές μπορεί να είναι πολύ μακρύτερες από το αναμενόμενο. Στην παρούσα διπλωματική εργασία μελετάται μια τρίτη προσέγγιση: ένας βέλτιστος για το σύστημα υπό περιορισμούς αλγόριθμος. Πρόκειται για ένα συνδυασμό των δύο μοντέλων πλοήγησης με σκοπό τη μείωση της συμφόρησης και ταυτόχρονα τη διατήρηση της δικαιοσύνης στην επιλογή των προτεινόμενων διαδρομών για τους οδηγούς. Αφού γίνει θεωρητική μελέτη του προβλήματος παρουσιάζεται η υλοποίηση ενός συστήματος πρότασης διαδρομών που χρησιμοποιεί το βέλτιστο για το σύστημα υπό περιορισμούς αλγόριθμο. / During the last decade, vehicles' route guidance systems have known a significant spread. These systems, taking advantage of the available technological features and by using the geographical representation of the road network, the current position of a vehicle and often traffic data, propose to drivers the route they should follow in order to reach faster their destination. The applications of route guidance systems offer the chance to manage traffic in such a way that allows an increase in road network capacity and therefore a decrease in traffic congestion, without being necessary the high cost expansion of the road infrastructure. In contrast to the user optimal model that is followed by typical route guidance systems and provides no traffic improvement guarantees, the system optimal model has been proposed for this purpose. The model proposes paths with the goal of improving the traffic condition of the network, however its application is unrealistic since the proposed routes may be much longer than expected. In this thesis a third approach is studied: a constrained system optimal algorithm. The algorithm is a combination of the two navigation models with the goal of reducing congestion and at the same time remaining fair for drivers when selecting a route. After the theoretical study of the problem, the implementation of a route recommendation system that incorporates the constrained system optimal algorithm is presented.

Στην εργασία αυτή ασχολούμαστε με το πρόβλημα της δρομολόγησης ενός συνόλου αιτήσεων επικοινωνίας σε WDM (Wavelength Division Multiplexing) πλήρως οπτικά δίκτυα από την άποψη της θεωρίας παιγνίων. Αν θεωρήσουμε κάθε αίτηση δρομολόγησης (ζεύγος κόμβων αφετηρία-προορισμός) ως παίκτη, τότε μία στρατηγική περιλαμβάνει ένα μονοπάτι από τον κόμβο-αφετηρία στον κόμβο-προορισμό και μία συχνότητα (χρώμα). Λαμβάνοντας υπόψη τον περιορισμό ότι δύο παίκτες δεν μπορούν να χρησιμοποιήσουν την ίδια συχνότητα στην ίδια ακμή, θεωρούμε ότι το κόστος δύο αλληλοσυγκρουόμενων στρατηγικών είναι απαγορευτικά μεγάλο. Στο παραπάνω πλαίσιο, μελετάμε διάφορες φυσικές συναρτήσεις κόστους επικεντρώνοντας στην ύπαρξη αμιγών σημείων ισορροπίας Nash και στην υπολογιστική πολυπλοκότητα αναγνώρισης και υπολογισμού τους. / We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost. Under this formulation, we consider several natural cost functions focusing on the existence of Nash equilibria and on the complexity of recognizing and computing them.

Στα ασύρματα αδόμητα δίκτυα, οι κόμβοι μπορούν να συνεργαστούν για τη μετάδοση δεδομένων σε απομακρυσμένουσ κόμβους. Συνήθως, η συνεργασία αυτή επιτυγχάνεται χρησιμοποιώντας βοηθητικούς ενδιάμεσους κόμβους για τη μετάδοση δεδομένων από ένα κόμβο πηγή σε ένα κόμβο προορισμό, μέσω point-to-point ή point-to-multipoint συνδέσμους. Πρόσφατα, μεγάλο ενδιαφέρον έχει αποκτήσει η τεχνική της συνεργατικής μετάδοσης, όπου περισσότεροι του ενός κόμβοι συμμετέχουν για τη μετάδοση του ίδιου σήματος σε έναν απομακρυσμένο κόμβο. Ο παραλήπτης ανακατασκευάζει το αρχικό σήμα συνδυάζωντας τα διαφορετικά σήματα που έφτασαν σε αυτόν. Εδώ, αναπτύσσεται και εκτιμάται ένας πολυ-κριτηριακός αλγόριθμος συνεργατικής δρομολόγησης που λαμβάνει υπόψην την εναπομένουσα ενέργεια και την απαιτούμενη ισχύ μετάδοσης των κόμβων. Ο αλγόριθμος για ένα ζευγάρι κόμβων πηγής – προορισμού ανακαλύπτει όλα τα δυνατά υποψήφια μονοπάτια λαμβάνοντας υπόψη και συνδέσμους με την δυνατότητα συνεργασίας των κόμβων για την αποστολή των δεδομένων. Τελικά επιλέγεται το μονοπάτι που βελτιστοποιεί μια συνάρτηση κόστους. Τα κριτήρια είναι η εναπομένουσα ενέργεια και η συνολική ισχύς μετάδοσης στους κόμβους του μονοπατιού. Εκτελούμε πειράματα προσομοίωσης σε δίκτυα με κόμβους που έχουν σταθερή ισχύ μετάδοσης και με κόμβους που μπορούν να προσαρμόσουν την ισχύ μετάδοσής τους. Τα αποτελέσματα δείχνουν ότι ο αλγόριθμός μας πετυχαίνει σημαντική εξοικονόμηση ενέργειας και μεγαλύτερο αριθμό επιτυχημένων αποστολών πακέτων σε σχέση με την περίπτωση που δεν χρησιμοποιείται συνεργασία. / In wireless ad-hoc networks, nodes cooperate to make possible the communication between otherwise distant nodes. Usually, this cooperation is in the form of nodes acting as intermediate relays that forward data from a source to a destination node using point-to-point or point-to-multipoint links. A technique that has gained considerable recent attention is cooperative diversity, where nodes are organized for transmitting the same signal to a given, often otherwise unreachable, node. The receiver combines the multiple receptions to reconstruct the original signal. In this work, we present and evaluate a multi-criteria cooperative routing algorithm that uses as parameters the nodes’ residual energy and their transmission power. This algorithm selects for each source-destination pair a path, in the form of a sequence of groups of cooperative nodes, and the nodes’ transmission powers. We perform a number of simulation experiments, assuming nodes with variable or fixed transmission power, evaluating the benefits of the proposed multi-criteria cooperative routing algorithm. The results show that our algorithm achieves significant energy savings and larger number of successfully delivered packets than the case where cooperation is not applied.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική προσέγγιση που αποτελείται από τρεις φάσεις: (i) συσταδοποίηση των πελατών με συμβατά παράθυρα χρόνου, (ii) συσταδοποίηση των πελατών που βρίσκονται γεωγραφικά κοντά χρησιμοποιώντας διάφορες μεθόδους (φυσικές αποκοπές, KaHIP, τετραδικά δένδρα), (iii) μια φάση εκλέπτυνσης που είτε χωρίζει μια συστάδα σε μικρότερες, είτε συγχωνεύει συστάδες δημιουργώντας μια συμπαγή μεγαλύτερη συστάδα. Η νέα προσέγγιση αποδίδει πολύ καλά όταν χρησιμοποιείται σε δυναμικά σενάρια στα οποία ζητούνται αλλαγές στην αρχικά υπολογισμένη διαδρομή (προσθήκη μιας νέας παραγγελίας ή ακύρωση κάποιας παραγγελίας). Η νέα μέθοδος αποτελεί ένα πολύ καλό σημείο εκκίνησης για επανεξέταση και περαιτέρω βελτιστοποίηση της λύσης του προβλήματος Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου. Πειράματα που έγιναν με πραγματικά σύνολα δεδομένων δείχνουν ότι η νέα προσέγγιση υπερέχει σε σχέση με τις συνήθεις προσεγγίσεις που ξεκινούν από μία βασική λύση. / We investigate the Vehicle Routing Problem with Time Windows (VRPTW) under a new approach, consisting of three major phases: (i) a first clustering of customers with compatible time windows; (ii) a second clustering of customers with close geographic proximity based on various methods (natural cuts, KaHIP, quad trees); (iii) a refinement phase that either splits a cluster into smaller ones, or merges clusters to form a bigger compact cluster. Our approach turns out to be beneficial when used in an on-line environment, where changes to the initial tour are requested (add a new customer to the tour or drop some customers). The new method serves as a warm starting point for re-evaluating and further optimizing the solution of VRPTW. Experiments with real data sets demonstrate that our approach compares favorably with standard approaches that start from a basic (cold) solution.

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

Στην παρούσα διπλωματική εργασία παρουσιάζεται η ανάπτυξη μιας εφαρμογής σε περιβάλλον iPhone, η οποία έχει ως σκοπό την διευκόλυνση της πρόσβασης των φοιτητών στο χώρο του Πανεπιστημίου Πατρών. Πιο συγκεκριμένα, προσφέρει δεδομένα σχετικά με τον χώρο του Πανεπιστημίου και την αστική συγκοινωνία της Πάτρας και προσφέρει στον χρήστη την δυνατότητα της καθοδήγησης από ένα σημείο της πόλης σε άλλο. / This diploma dissertation concerns the development of an iPhone application, aiming to facilitate the access of the students to the University of Patras. It provides information over the University of Patras grounds and the traffic network of Patras, as well as the ability for the user to be navigated from one part of the city to another.

Η Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (OFDM) έχει προταθεί ως τεχνική διαμόρφωσης σε οπτικά δίκτυα, λόγω της καλής φασματικής απόδοσής της, της ευελιξίας και της ανοχής της σε βλάβες. Η διαμόρφωση OFDM επιτρέπει την ελαστική ανάθεση φάσματος, χρησιμοποιώντας μεταβλητό πλήθος υποφερουσών, καθώς και την επιλογή του κατάλληλου επιπέδου διαμόρφωσης με βάση την απόσταση της μετάδοσης. Το «Πρόβλημα Δρομολόγης και Ανάθεσης Φάσματος» (RSA) έχει αποδειχθεί ότι είναι ένα NP-πλήρες πρόβλημα, γεγονός που υποδηλώνει τη χρήση γραμμικού προγραμματισμού για τη λύση του. Στόχος της διπλωματικής εργασίας είναι η βελτίωση της απόδοσης του υπάρχοντος αλγορίθμου ακέραιου γραμμικού προγραμματισμού, με χρήση μεταευριστικών, έτσι ώστε στο ίδιο χρονικό διάστημα να υπολογίζεται αποδοτικότερη χρησιμοποίηση του συνολικού απαιτούμενου φάσματος, για το σύνολο των μεταδόσεων στο δίκτυο. / Orthogonal Frequency Division Multiplexing (OFDM) has been proposed as a modulation technique for optical networks, because of its good spectral efficiency, flexibility, and tolerance to impairments. OFDM modulation allows elastic spectrum allocation, using a variable number of subcarriers and choosing an appropriate modulation level, taking into account the transmission distance. The “Routing and Spectrum Allocation” (RSA) problem has been proved to be a NP-complete problem, which suggests the usage of linear programming in order to be solved. This diploma thesis aims to improve the efficiency of the existing integer linear programming algorithm, by using metaheuristics, so that at the same time period a more efficient utilization of the required spectrum is computed, for all network transmissions.

Μέχρι σήμερα στη δρομολόγηση στα ασύρματα αδόμητα δίκτυα λαμβάνεται ως κριτήριο ένα μοναδιαίο μέγεθος για κάθε σύνδεσμο του δικτύου, το οποίο αναπαριστά το κόστος της μετάδοσης πάνω στον συγκεκριμένο σύνδεσμο. Στη δρομολόγηση με βάση πολλαπλά κριτήρια η βασική ιδέα είναι ότι σε κάθε σύνδεσμο ανατίθεται ένα διάνυσμα από παραμέτρους-κόστη με βάση το οποίο προκύπτει και ένα αντίστοιχο διάνυσμα για κάθε μονοπάτι. Για κάθε ζευγάρι κόμβων αποστολέα-παραλήπτη γίνεται καταρχήν η εύρεση όλων των υποψήφιων για χρήση μονοπατιών. Τα υποψήφια μονοπάτια, που λαμβάνονται υπόψη κατά τη διαδικασία επιλογής, έχουν την ιδιότητα να είναι μη-κυριαρχημένα μεταξύ τους. Στη συνέχεια εφαρμόζεται στο σύνολο των μη-κυριαρχημένων μονοπατιών μια συνάρτηση που συνδυάζοντας τις συνιστώσες του κάθε διανύσματος παράγει το κόστος χρήσης κάθε μονοπατιού και έτσι το μονοπάτι με το ελάχιστο κόστος επιλέγεται για χρήση. Στα πλαίσια της εργασίας, καταρχήν μελετήθηκε ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη χρησιμοποιώντας παραμέτρους-κόστη σχετικές με την ενέργεια, όπως η τρέχουσα διαθέσιμη ενέργεια στους κόμβους και η ισχύς μετάδοσής τους. Στη συνέχεια στις παραμέτρους προστέθηκε και η παρεμβολή που δημιουργείται από τη μετάδοση πάνω σε ένα σύνδεσμο. Τα αποτελέσματα των προσομοιώσεων έδειξαν ότι ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη, σε σχέση με τον ελάχιστου μήκους διαδρομής, κατανέμει πιο ομοιόμορφα την κίνηση στο δίκτυο, επιμηκύνει τον χρόνο ζωής του δικτύου και αυξάνει το ποσοστό των παραδιδόμενων πακέτων. Στο επόμενο στάδιο της εργασίας έγινε μια κατανεμημένη υλοποίηση του αλγορίθμου δρομολόγησης με πολλαπλά κόστη, που επιπλέον λαμβάνει υπόψη την κινητικότητα των κόμβων του δικτύου, η οποία και πάλι φάνηκε να υπερέχει έναντι πιο παραδοσιακών πρακτικών. Τέλος η ιδέα της δρομολόγησης με πολλαπλά κόστη εφαρμόστηκε για τη λύση του προβλήματος ενεργο-αποδοτικής πολλαπλής ή ολικής εκπομπής (multicasting ή broadcasting, αντίστοιχα). Στόχος ήταν να βρεθεί η βέλτιστη ενεργο-αποδοτικά ακολουθία συνδέσμων πάνω στους οποίους πρέπει να γίνει μετάδοση ενός πακέτου προκειμένου να υλοποιηθεί η επιθυμητή εκπομπή. Σαν παράμετροι-κόστη χρησιμοποιήθηκαν η τρέχουσα διαθέσιμη ενέργεια και η ισχύς μετάδοσης των κόμβων. Τα αποτελέσματα δείχνουν σαφή υπεροχή του αλγορίθμου με πολλαπλά κόστη έναντι παραδοσιακών λύσεων τόσο για πολλαπλή εκπομπή όσο και για ολική εκπομπή. / Until now, routing in wireless ad hoc networks has been studied by taking into account a single scalar metric for every network link, representing the cost of transmitting through this link. In multicost routing a vector of cost parameters is assigned to each link, based on which a respective cost vector is produced for every path in the network. For every source-destination pair all the candidate paths are initially calculated that are non-dominated to each other. At the cost vectors of the candidate paths, an optimization function is applied in order to produce a cost for each path based on which the selection of the optimal one is made. In the present thesis multicost routing in wireless ad hoc networks was studied initially using as cost parameters the node residual energy and transmission power. As a next step the interference cause by the transmission of each link was added to the cost vectors assigned to each network link. The simulation results showed that multicost routing in comparison to traditional routing practices achieves more uniform traffic distribution and energy consumption in the network, prolongs the network lifetime and increases the percentage of the packets that are successfully delivered to their destinations. Expanding these ideas, the multicost routing algorithm was next implemented in a fully distributed fashion in which additionally the node mobility was taken into account. The results again proved that a significant improvement was accomplished compared to minimum-hop routing. Finally, multicost routing was applied in the field of multicasting and broadcasting in wireless ad hoc networks. The emphasis was again on energy-efficiency by incorporating energy-related cost parameters like node residual energy and transmission power. The multicost algorithm calculates the optimal energy-efficient sequence of nodes that by transmitting implement the desired communication task (multicasting or broadcasting). Simulation results illustrate a clear advantage of our algorithm over established solutions for energy-efficient multicasting and broadcasting.

Κατά την διάδοση του σήματος στα οπτικά δίκτυα η ποιότητα του λαμβανόμενου σήματος εξασθενεί λόγω των διαφόρων ειδών απωλειών που υπεισέρχονται κατά τη μετάδοση. Οι κυριότερες εξ’ αυτών είναι: ο θόρυβος λόγω των οπτικών ενισχυτών, η διαφωνία, η χρωματική διασπορά, η διασπορά τρόπων πόλωσης, η μείξη τεσσάρων κυμάτων, η αυτοδιαμόρφωση φάσης κτλ. Προκειμένου να επιτευχθεί αποδεκτή ποιότητα λαμβανόμενου σήματος στον δέκτη είναι απαραίτητη, ιδιαίτερα για μεγάλα μονοπάτια, η χρήση οπτικών 3R αναγεννητών σε κάποιους ενδιάμεσους κόμβους για την περιοδική αναμετάδοση του σήματος. Στην παρούσα διπλωματική εργασία σχεδιάζονται και υλοποιούνται στατικοί αλγόριθμοι δρομολόγησης και ανάθεσης μηκών κύματος για ημιδιαφανή οπτικά δίκτυα. Συγκεκριμένα, θεωρώντας μια δικτυακή τοπολογία, έναν αριθμό διαθέσιμων μηκών κύματος, μια μήτρα κίνησης και μια (αραιή) τοπολογία 3R αναγεννητών για το εξεταζόμενο δίκτυο (ή εκφράζοντάς το διαφορετικά έναν αριθμό ελεύθερων πομποδεκτών για κάθε κόμβο του δικτύου) επιχειρείται η μεγιστοποίηση του αριθμού των συνδέσεων που μπορούν να επιτευχθούν, διατηρώντας παράλληλα την επιθυμητή ποιότητα μετάδοσης. Έτσι, το πρόβλημα της επιλογής της ακολουθίας των αναγεννητών μέσα από τους οποίους θα δρομολογηθεί η κάθε αδιαφανής αίτηση σύνδεσης, μοντελοποιείται σαν ένα πρόβλημα εικονικής τοπολογίας (virtual topology problem). Στην συνέχεια το πρόβλημα αυτό επιλύεται με τη βοήθεια μιας σειράς αλγορίθμων από πολύπλοκους που βασίζονται σε σχηματισμούς ακέραιου γραμμικού προγραμματισμού (Integer Linear Programming – ILP) έως απλούστερους αλλά πάντα πρακτικούς ως προς την εύρεση λύσης, ευριστικούς αλγόριθμους. Ύστερα από την επιλογή της ακολουθίας των χρησιμοποιούμενων αναγεννητών για κάθε αδιαφανή αίτηση σύνδεσης, η μήτρα κίνησης μετασχηματίζεται σε μια ισοδύναμη διαφανή, όπου κάθε αδιαφανής αίτηση έχει αντικατασταθεί από μια σειρά διαφανών συνδέσεων που τερματίζουν και ξεκινούν από τους συγκεκριμένους 3R κόμβους αναγέννησης. Ακολούθως, εφαρμόζεται ένας διαφανής IA-RWA αλγόριθμος για τη μετασχηματισμένη μήτρα κίνησης, ενώ τυχόν συνδέσεις που μποκάρονται ύστερα από την εφαρμογή του διαφανή αλγορίθμου επαναδρομολογούνται χρησιμοποιώντας τους υπολοιπόμενους αναγεννητές. Η Ποιότητα Μετάδοσης (Quality of Transmission QoT) των δημιουργουμένων lightpaths υπολογίζεται με τη βοήθεια ενός εκτιμητή της παραμέτρου Q του κάθε lightpath. Για την μοντελοποίηση των φυσικών περιορισμών του δικτύου χρησιμοποιούνται αναλυτικές φόρμουλες. Η απόδοση του προτεινόμενου αλγορίθμου υπολογίστηκε διεξάγοντας εξομοιώσεις για μια παραλλαγή του DTnet δικτύου εισάγοντας τη μοναδιαία μήτρα κίνησης. Η απόδοση του αλγορίθμου κρίνεται ικανοποιητική όχι μόνο για μεσαία, αλλά και για μεγάλης κλίμακας δίκτυα παρέχοντας βέλτιστες λύσεις. Το μεγαλύτερο μέρος του χρόνου εκτέλεσης του αλγορίθμου, οφείλεται στον υπολογισμό του διαφανούς IA-RWA αλγόριθμου της δεύτερης φάσης. Σχετικά με την απόδοση των εξεταζόμενων αλγορίθμων της πρώτης φάσης, φαίνεται ότι ο αλγόριθμος που παρουσιάζει τα καλύτερα αποτελέσματα είναι αυτός που ελαχιστοποιεί τον μέγιστο αριθμό των χρησιμοποιούμενων αναγεννητών μεταξύ των διαφορετικών κόμβων αναγέννησης του σήματος. / Physical impairments in optical fiber transmission necessitate the use of regeneration at certain intermediate nodes, at least for certain lengthy lightpaths. We design and implement impairment-aware algorithms for routing and wavelength assignment (IA-RWA) in translucent optical networks. We focus on the offline version of the problem, where we are given a network topology, the available wavelengths, a traffic matrix and a (sparse) placement of 3R regenerators in the network (or, in a slightly different setting, the number of available transceivers at each network switch), and we aim at maximizing the number of connections served with adequate quality of transmission. We formulate the problem of choosing the sequence of regenerators to be used by non-transparent connections as a virtual topology design problem, and address it using various algorithms, ranging from an integer linear program (ILP) to simple heuristic algorithms. Once the sequence of regenerators to be used has been determined, we transform the traffic matrix by replacing non-transparent connections with a sequence of transparent connections that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix we then apply an IA-RWA algorithm designed for transparent (as opposed to translucent) networks to route the traffic. Connections that are blocked are re-routed using any remaining regenerator(s).

Στα δίκτυα επικοινωνιών, η δρομολόγηση περιλαμβάνει τον προσδιορισμό μιας πορείας μεταξύ των κόμβων της πηγής και του προορισμού για κάθε αίτημα σύνδεσης. Στρέφουμε την προσοχή μας στην κατηγορία των διαφανών (transparent) οπτικών δικτύων όπου, σε απάντηση σε ένα δεδομένο αίτημα κλήσης, εγκαθιδρύεται μια circuit-switched σύνδεση μεταξύ του κόμβου που έχει την απαίτηση κλήσης (πηγή) και του κόμβου που λαμβάνει αυτή την κλήση (προορισμός) σε ένα ενιαίο μήκος κύματος, υπό τον όρο ότι ένα ελεύθερο μήκος κύματος είναι διαθέσιμο σε όλους τους ενδιάμεσου συνδέσμους. Σε ένα διαφανές οπτικό δίκτυο που δρομολογείται βάσει του μήκους κύματος (wavelength routed), η πληροφορία μιας σύνδεσης μεταδίδεται πάνω από αμιγώς οπτικά μονοπάτια (lightpaths) στα οποία το μεταδιδόμενο σήμα παραμένει στο οπτικό πεδίο καθ’ όλη τη διάρκεια της διαδρομής που ορίζεται ανάμεσα στην πηγή και τον προορισμό. Οι παραδοσιακές προσεγγίσεις δρομολόγησης βρίσκουν μια πορεία που είτε ελαχιστοποιεί μια ορισμένη παράμετρο κόστους - όπως το μήκος της σύνδεσης ή των πόρων του δικτύων που χρησιμοποιούνται - ή μεγιστοποιούν την κυκλοφορία που εξυπηρετείται και καλούνται αλγόριθμοι Δρομολόγησης και Ανάθεσης Μήκους Κύματος (Routing and Wavelength Assignment - RWA). Το RWA πρόβλημα εξετάζεται συνήθως κάτω από δύο εναλλακτικές τοποθετήσεις. Η Στατική ή Offline εγκαθίδρυση lightpath που εξετάζει την περίπτωση όπου το σύνολο των συνδέσεων είναι γνωστό εκ των προτέρων και εξυπηρετείται από κοινού. Η Δυναμική ή Online εγκαθίδρυση lightpath εξετάζει την περίπτωση όπου τα αιτήματα σύνδεσης φθάνουν τυχαία χρονικές περιπτώσεις και εξυπηρετούνται ένα προς ένα. Σε αυτήν την μελέτη θα εστιάσουμε στο Online RWA πρόβλημα. Οι περισσότεροι από τους RWA αλγορίθμους υποθέτουν λειτουργία σε ιδανικό φυσικό επίπεδο μετάδοσης όπου μόλις προσδιοριστεί μια διαθέσιμη πορεία και ένα μήκος κύματος, η σύνδεση είναι εφικτή. Όμως στα διαφανή οπτικά δίκτυα, η ποιότητα του σήματος υποβαθμίζεται λόγω εξασθενίσεων (impairments) στο φυσικό επίπεδο που κάνει αδύνατη τη δρομολόγηση (physical-layer blocking). Ως εκ τούτου, απαιτούνται αλγόριθμοι δρομολόγησης που να λαμβάνουν υπ’ όψιν τους περιορισμούς εξασθένισης (impairment aware RWA) προκειμένου να εξασφαλιστεί το γεγονός ότι οι συνδέσεις είναι εφικτές αλλά και με ικανοποιητική ποιότητα μετάδοσης (Quality of Transmission - QoT). Για να γίνει αυτό, είναι απαραίτητο να συνυπολογιστούν τόσο η κατάσταση του δικτύου όσο και η φυσική απόδοση της σύνδεσης. Σε ένα οπτικό δίκτυο που δρομολογείται βάσει του μήκους κύματος το οποίο εκτείνεται σε μεγάλη γεωγραφική περιοχή, ένα οπτικό σήμα μπορεί να μεταβεί σε διάφορους ενδιάμεσους κόμβους και μεγάλα τμήματα ινών. Οι προοδευτικά αυξανόμενες απώλειες του σήματος σε όλους τους ενδιάμεσους κόμβους και τα μεγάλα τμήματα ινών απαιτούν τη χρήση οπτικών ενισχυτών σε στρατηγικές θέσεις στο δίκτυο, ενδεχομένως σε κάθε κόμβο και μέσα στις ίνες, αλλά και Optical Cross Connect Switches (OXC). Δυστυχώς, οι ενισχυτές και οι OXC μπορεί να εισάγουν σημαντικές εξασθενίσεις στη μετάδοση, όπως η παραγωγή crosstalk, ενισχυμένου αυθόρμητου θορύβου (Amplified Spontaneous Emission - ASE), κορεσμού και εξάρτησης από το μήκος κύματος του κέρδους των ενισχυτών, που κάνει το κέρδος μια ποσότητα μη ντετερμινιστική και εξαρτώμενη από την κυκλοφορία της πληροφορίας. Σκοπός της συγκεκριμένης εργασίας είναι να προσδιοριστεί αυτή η σχέση εξάρτησης μεταξύ του κέρδους των ενισχυτών και του μήκους κύματος που χρησιμοποιείται για την εξυπηρέτηση της απαίτησης από τον κόμβο πηγής στον κόμβο προορισμού. Πιο συγκεκριμένα, το κέρδος, με το οποίο ενισχύεται το σήμα κατά τη μετάδοσή του, εξαρτάται από το την ισχύ εισόδου του ενισχυτή, δηλαδή το πλήθος των μηκών κύματος που μπορεί να ενισχύσει ο εκάστοτε ενισχυτής. Επομένως, θέλουμε οι αλλαγές στα κέρδη των ενισχυτών ανάλογα με τo πλήθος των μηκών κύματος που χρησιμοποιούνται σε κάθε κόμβο να συνυπολογίζονται κατά τη διάρκεια εύρεσης των μονοπατιών και της δρομολόγησης των αιτήσεων. Για την επίτευξη αυτού δημιουργήθηκε μια επέκταση ενός ήδη υπάρχοντος αλγορίθμου δρομολόγησης και ανάθεσης μήκους κύματος πολλαπλών κριτηρίων (Multicost Impairment Aware Routing and Wavelength Assignment – IA-RWA) που λαμβάνει υπ’ όψιν του εκτός από τις εξασθενίσεις από το φυσικό επίπεδο κατά τη μετάδοση και τις αλλαγές στα κέρδη των ενισχυτών. Ο προτεινόμενος αλγόριθμος ονομάζεται αλγόριθμος δρομολόγησης και ανάθεσης μήκους κύματος πολλαπλών κριτηρίων με περιορισμούς ισχύος (Multicost Impairment Aware Routing and Wavelength Assignment with Power Constraints – IA-RWA with Power Constraints). Για την εξυπηρέτηση μιας σύνδεσης, βρίσκει μια πορεία και ένα ελεύθερο μήκος κύματος, που να μην επηρεάζει αρνητικά το κέρδος των ενισχυτών της πορείας αυτής, ώστε να έχει αποδεκτή ποιότητα μετάδοσης, βάσει του τρέχοντος βαθμού χρήσης (utilization) του δικτύου, που αλλάζει όσο νέες συνδέσεις εγκαθιδρύονται ή απελευθερώνονται. Ο IA-RWA with Power Constraints αλγόριθμος ακολουθεί τις ίδιες δυο φάσεις ανάπτυξης για την ανάθεση και δρομολόγηση με τον IA-RWA αλγόριθμο. Στην πρώτη φάση, ο αλγόριθμος βρίσκει το σύνολο των επιτρεπτών για την απαιτούμενη QoT πορειών από τη δεδομένη πηγή σε όλους τους κόμβους του δικτύου, συμπεριλαμβανομένου και του προορισμού. Στη δεύτερη φάση, εφαρμόζεται μια συνάρτηση βελτιστοποίησης στο διάνυσμα δαπανών (cost vector) των πορειών, που είναι αυτό που θα πρέπει να κρατά πληροφορίες σχετικές με τις αλλαγές στα κέρδη των ενισχυτών, προκειμένου να βρεθεί η βέλτιστη λύση. Η προσθήκη που επιτυγχάνει το σκοπό μας είναι ο υπολογισμός του κέρδους των ενισχυτών σε όλους τους συνδέσμου του δικτύου πριν την πρώτη φάση του αλγορίθμου αλλά στο τέλος της δεύτερης, όπου εκεί γίνεται ουσιαστικά ένας έλεγχος για τον τρόπο με τον οποίο επηρεάζει η εγκαθίδρυση της νέας αίτησης τις ήδη υπάρχουσες. Με απώτερο στόχο στην περίπτωση της μείωσης του QoT τη φραγή (blocking) ή την επαναδρομολόγηση (rerouting) της αίτησης. Στα Κεφάλαια που θα ακολουθήσουν θα γίνει μια εκτενής παρουσίαση όλων των στοιχείων που συνθέτουν το Online RWA πρόβλημα. Στο Κεφάλαιο 1 θα αναπτυχθεί η τεχνική της Πολυπλεξίας με Διαίρεση Μήκους Κύματος (Wavelength Division Multiplexing - WDM), στο Κεφάλαιο 2 θα περιγραφούν οι φυσικές εξασθενίσεις που συνυπολογίζονται κατά τη διαδικασία της δρομολόγηση και ανάθεσης μήκους κύματος. Στο Κεφάλαιο 3 παρουσιάζονται οι οπτικοί ενισχυτές και ο τρόπος λειτουργίας τους. Στο Κεφάλαιο 4 αναλύουμε τους παράγοντες που βοηθούν στον υπολογισμό της ποιότητας μετάδοσης της πληροφορίας. Τέλος, στα Κεφάλαια 5 και 6 γίνεται η ανάλυση του RWA προβλήματος, του αλγορίθμου που αναπτύχθηκε αλλά και ανάπτυξη των πειραματικών αποτελεσμάτων. / In communication networks, routing involves the identification of a path between the source and destination nodes for each connection request. We focus our attention on the class of transparent optical networks wherein, in response to a given call request, a circuit-switched connection is established between the calling (source) and the called (destination) nodes on a single wavelength, provided a free wavelength is available over the desired lightpath. In a transparent wavelength-routed optical network, the information of connection is transmitted above purely optical paths (lightpaths) in which any transmitted signal remains in the optical domain over the entire route assigned to it between its source and destination nodes. Traditional routing approaches find a path that either minimizes a certain cost parameter - such as the length of the connection or the network resources used – or maximize the traffic served and are called Routing and Wavelength Assignment (RWA) algorithms. The RWA problem is usually considered under two alternative settings. Static or Offline lightpath establishment addresses the case where the set of connections is known in advance and are jointly served. Dynamic or Online lightpath establishment considers the case where connection requests arrive at random time instances and are served on a one-by-one basis. In this study we will focus on the online RWA problem. Most of the RWA algorithms assume an ideal physical layer transmission that once an available path and wavelength have been identified, the connection is feasible. However, in all-optical transparent network, the quality of the signal degrades due to physical layer impairments which make routing unfeasible (physical-layer blocking). Hence, impairment-constraint-based routing is needed in order to ensure that the connections are feasible with acceptable Quality of Transmission (QoT). To do this, it is necessary to consider not only the network-level conditions but also the equally important physical performance of the connection. In a wavelength-routed optical network spanning a large geographical area, an optical signal may traverse a number of intermediate nodes and long fibre segments. The progressive losses incurred by the signal in all intermediate nodes and long fibre segments necessitate the use of optical amplifiers at strategic locations in the network, possibly at each node and within the fibre segments, and optical cross connect switch (XCS). Unfortunately, the XCS and the amplifiers may introduce significant transmission impairments, such as crosstalk generation, generation of amplified spontaneous emission (ASE) noise, saturation and wavelength dependence of amplifiers gain, making the gain a traffic-dependent nondeterministic quantity. Aim of particular work is to determine this relation of dependence between the amplifiers’ gain and the wavelength that is used to serve the request from the source node to the destination node. More concretely, this gain, with which is amplifies the transmission signal, depends on the input power of the amplifiers. Consequently, we want the changes of the amplifiers’ gain, which depend on the number of wavelengths that are used in each node, to be taken into account when requests are routed. For the achievement of this, we created an extension of the Multicost Impairment-Aware Routing and Wavelength Assignment algorithm (IA-RWA) that takes under consideration, apart from the impairments on the physical layer during transmission, the changes of the amplifiers’ gain. The proposed algorithm is called Multicost Impairment Aware Routing and Wavelength Assignment with Power Constraints (IA-RWA with Power Constraints). To serve a connection, the algorithm finds a path and a free wavelength, which does not degrade the amplifier gain of the chosen path, so as to have acceptable quality of transmission (QoT) performance according to the current utilization of the network, which changes as new connections are established or released. The IA-RWA with Power Constraints algorithm follows the same two phases for the routing and wavelength assignment with the IA-RWA algorithm. In the first phase, the algorithm finds the total number of paths with the required QoT, from the given source to all nodes of the network, included the destination. In the second phase, is applied an optimization function in the cost vector of the paths so as to find the most optimal solution. The addition that achieves our aim is the calculation of amplifiers’ gain in all nodes of the network before the first phase of algorithm but also and at the end of the second phase, where substantially checks the way that the establishment of new request influences the already existing. With final objective the blocking of the new connection in the case where the QoT is reduced or the rerouting of the request. In the following Chapters there will be an extensive presentation of all elements that compose Online RWA problem. In Chapter 1 will be developed the technique of Wavelength Division Multiplexing (WDM), in Chapter 2 will be described the physical impairments that are taken under consideration in routing and wavelength assignment procedure. In Chapter 3 are presented the optical amplifiers and their operation. In Chapter 4 we analyze the factors that are used in order to calculate the quality of transmission of a signal. Finally, in Chapter 5 and 6 we analyze the RWA problem, the algorithm that was developed but also the presentation of the experimental results.