Τα δίκτυα πλέγματος (grid networks) αποτελούνται από ένα σύνολο ισχυρών υπολογιστικών, αποθηκευτικών και άλλων πόρων. Οι πόροι αυτοί είναι συνήθως γεωγραφικά αλλά και διοικητικά διασκορπισμένοι και συνδέονται με ένα δίκτυο δεδομένων. Τα δίκτυα πλέγματος το τελευταίο καιρό έχουν αποκτήσει μία δυναμική, η οποία εντάσσεται μέσα σε ένα γενικότερο πλαίσιο, αυτό της κατανεμημένης επεξεργασίας και αποθήκευσης δεδομένων. Επιστήμονες, ερευνητές αλλά και απλοί χρήστες χρησιμοποιούν από κοινού τους κατανεμημένους πόρους για την εκτέλεση διεργασιών ή τη χρήση εφαρμογών, για τις οποίες δεν μπορούν να χρησιμοποιήσουν τους τοπικά διαθέσιμους υπολογιστές τους λόγω των περιορισμένων δυνατοτήτων τους. Στην παρούσα διδακτορική διατριβή εξετάζουμε ζητήματα που σχετίζονται με το χρονοπρογραμματισμό (scheduling) των διεργασιών στους διαθέσιμους πόρους, καθώς και με τη δρομολόγηση (routing) των δεδομένων που οι διεργασίες χρειάζονται. Εξετάζουμε τα ζητήματα αυτά είτε χωριστά, είτε σε συνδυασμό, μελετώντας έτσι τις αλληλεπιδράσεις τους. Αρχικά, προτείνουμε ένα πλαίσιο παροχής ποιότητας υπηρεσιών στα δίκτυα πλέγματος, το οποίο μπορεί να εγγυηθεί σε ένα χρήστη μία μέγιστη χρονική καθυστέρηση εκτέλεσης των διεργασιών του. Με τον τρόπο αυτό, ένας χρήστης μπορεί να επιλέξει με απόλυτη βεβαιότητα εκείνον τον υπολογιστικό πόρο που μπορεί να εκτελέσει τη διεργασία του πριν τη λήξη της προθεσμίας της. Το προτεινόμενο πλαίσιο δεν στηρίζεται στην εκ των προτέρων δέσμευση των υπολογιστικών πόρων, αλλά στο ότι οι χρήστες μπορούν να αυτό-περιορίσουν το ρυθμό δημιουργίας διεργασιών τους, ο οποίος συμφωνείται ξεχωριστά με κάθε πόρο κατά τη διάρκεια μίας φάσης εγγραφής τους. Πραγματοποιούμε έναν αριθμό πειραμάτων προσομοίωσης που αποδεικνύουν ότι το προτεινόμενο πλαίσιο μπορεί πράγματι να παρέχει στους χρήστες εγγυημένο μέγιστο χρόνο καθυστέρησης εκτέλεσης των διεργασιών τους, ενώ με τις κατάλληλες επεκτάσεις το πλαίσιο μπορεί να χρησιμοποιηθεί ακόμα και όταν το φορτίο των διεργασιών δεν είναι εκ των προτέρων γνωστό. Στη συνέχεια εξετάζουμε το πρόβλημα της ``Συγκέντρωσης Δεδομένων'' (ΣΔ), που εμφανίζεται όταν μία διεργασία χρειάζεται περισσότερα του ενός τμήματα δεδομένων να μεταφερθούν σε έναν υπολογιστικό πόρο, πριν η διεργασία ξεκινήσει την εκτέλεσή της σε αυτόν. Μελετάμε τα υπό-προβλήματα της επιλογής των αντιγράφων των δεδομένων, του χρονοπρογραμματισμού της διεργασίας και της δρομολόγησης των δεδομένων της και προτείνουμε έναν αριθμό πλαισίων ``Συγκέντρωσης Δεδομένων''. Μερικά πλαίσια εξετάζουν μόνο τις υπολογιστικές ή μόνο τις επικοινωνιακές απαιτήσεις των διεργασιών, ενώ άλλα εξετάζουν και τα δύο είδη απαιτήσεων. Επιπλέον, προτείνονται πλαίσια ``Συγκέντρωσης Δεδομένων'' τα οποία βασίζονται στην κατασκευή ελαχίστων γεννητικών δέντρων(Minimum Spanning Tree - MST), με σκοπό τη μείωση της συμφόρησης στο δίκτυο δεδομένων, που εμφανίζεται κατά την ταυτόχρονη μεταφορά των δεδομένων μίας διεργασίας. Στα πειράματα προσομοίωσης μας αξιολογούμε τα προτεινόμενα πλαίσια και δείχνουμε ότι αν η διαδικασία της ``Συγκέντρωση Δεδομένων'' πραγματοποιηθεί σωστά, τότε η απόδοση του δικτύου πλέγματος, όσον αφορά τη χρήση των πόρων και την εκτέλεση των διεργασιών, μπορεί να βελτιωθεί. Επιπλέον, ερευνούμε την εφαρμογή τεχνικών σύνοψης της πληροφορίας των χαρακτηριστικών των πόρων στα δίκτυα πλέγματος. Προτείνουμε ένα σύνολο μεθόδων και τελεστών σύνοψης, προσπαθώντας να μειώσουμε τον όγκο των πληροφοριών πόρων που μεταφέρονται πάνω από το δίκτυο, ενώ παράλληλα επιθυμούμε οι συνοπτικές πληροφορίες που παράγονται να βοηθούν το χρονοπρογραμματιστή να παίρνει αποδοτικές αποφάσεις ανάθεσης διεργασιών στους διαθέσιμους πόρους. Οι τεχνικές αυτές μπορούν να συνδυαστούν και με τις αντίστοιχες τεχνικές που εφαρμόζονται στα ιεραρχικά δίκτυα δεδομένων για τη δρομολόγηση, εξασφαλίζοντας έτσι τη διαλειτουργικότητα μεταξύ διαφορετικών δικτύων πλέγματος καθώς και το απόρρητο των πληροφοριών που ανήκουν σε διαφορετικούς παρόχους πόρων. Στα πειράματα προσομοίωσης μας χρησιμοποιούμε σαν μετρική της ποιότητας / αποδοτικότητας των αποφάσεων του χρονοπρογραμματιστή τον Stretch Factor (SF), που ορίζεται ως ο λόγος της μέσης καθυστέρησης εκτέλεσης των διεργασιών όταν αυτές χρονοπρογραμματίζονται με βάση ακριβείς πληροφορίες πόρων, προς τη μέση καθυστέρηση τους όταν χρησιμοποιούνται συνοπτικές πληροφορίες. Ακόμα, μετράμε τη συχνότητα με την οποία ο χρονοπρογραμματιστής ενημερώνεται για τις αλλαγές στην κατάσταση των πόρων καθώς και τον όγκο των πληροφοριών πόρων που μεταφέρονται. Μελετάμε, ακόμα, ζητήματα που προκύπτουν από την υλοποίηση αλγορίθμων χρονοπρογραμματισμού που έχουν αρχικά μελετηθεί σε περιβάλλοντα προσομοίωσης, σε πραγματικά συστήματα ενδιάμεσου λογισμικού (middleware) για δίκτυα πλέγματος, όπως το gLite. Το πρώτο ζήτημα που εξετάζουμε είναι το γεγονός ότι οι πληροφορίες που παρέχονται στους αλγορίθμους χρονοπρογραμματισμού στα συστήματα αυτά δεν είναι πάντα έγκυρες, ενώ το δεύτερο ζήτημα είναι ότι δεν υπάρχει ευελιξία στο διαμοιρασμό των πόρων μεταξύ διαφορετικών διεργασιών. Η μελέτη μας δείχνει ότι με απλές αλλαγές στους μηχανισμούς διαχείρισης διεργασιών ενός συστήματος ενδιάμεσου λογισμικού, αυτά αλλά και άλλα ζητήματα μπορούν να αντιμετωπιστούν, επιτυγχάνοντας σημαντικές βελτιώσεις στην απόδοση των δικτύων πλέγματος. Στα πλαίσια αυτά μάλιστα, εξετάζουμε τη χρήση της τεχνολογίας της εικονικοποίησης (virtualization). Υλοποιούμε και αξιολογούμε τους προτεινόμενους μηχανισμούς σε ένα μικρό δοκιμαστικό δίκτυο πλέγματος. Τέλος, προτείνουμε έναν αλγόριθμο πολλαπλών κριτηρίων για τη δρομολόγηση και ανάθεση μήκους κύματος υπό την παρουσία φυσικών εξασθενήσεων (Impairment-Aware Routing and Wavelength Assignment, IA-RWA) για οπτικά δίκτυα δεδομένων. Τα οπτικά δίκτυα είναι η δικτυακή τεχνολογία που χρησιμοποιείται σήμερα για τη διασύνδεση των υπολογιστικών και αποθηκευτικών πόρων των δικτύων πλέγματος, ενώ οι διάφορες φυσικές εξασθενήσεις τείνουν να μειώνουν την ποιότητα μετάδοσης (Quality of Transmission - QoT) των οπτικών σημάτων. Κύριο χαρακτηριστικό του προτεινόμενου αλγορίθμου είναι ότι υπολογίζει την ποιότητα μετάδοσης (Quality of Transmission - QoT) ενός υποψήφιου οπτικού μονοπατιού (lightpath) μη βασιζόμενο σε πραγματικές μετρήσεις ή εκτιμήσεις μέσω αναλυτικών μοντέλων των διαφόρων φυσικών εξασθενήσεων, αλλά μετρώντας τις αιτίες στις οποίες αυτά οφείλονται. Με τον τρόπο αυτό ο αλγόριθμος γίνεται πιο γενικός και εφαρμόσιμος σε διαφορετικές συνθήκες (μέθοδοι διαμόρφωσης του οπτικού σήματος, ρυθμοί μετάδοσης, τιμές διαφόρων φυσικών παραμέτρων, κ.α.). Τα πειράματα προσομοίωσης μας δείχνουν ότι ο προτεινόμενος αλγόριθμος μπορεί να εξυπηρετήσει τις περισσότερες δυναμικές αιτήσεις σύνδεσης, υπολογίζοντας γρήγορα, μονοπάτια με καλή ποιότητα μετάδοσης σήματος. Γενικά, η παρούσα διδακτορική διατριβή παρουσιάζει έναν αριθμό σημαντικών και καινοτόμων μεθόδων, πλαισίων και αλγορίθμων που αφορούν τα δίκτυα πλέγματος. Παράλληλα ωστόσο αποκαλύπτει το εύρος των ζητημάτων και ως ένα βαθμό και τις αλληλεπιδράσεις τους, που σχετίζονται με την αποδοτική λειτουργία των δικτύων πλέγματος, τα οποία απαιτούν τη σύνθεση και τη συνεργασία ερευνητών, μηχανικών και επιστημόνων από διάφορα πεδία. / Grid networks consist of several high capacity, computational, storage and other resources, which are geographically distributed and may belong to different administrative domains. These resources are usually connected through high capacity optical networks. The grid networks evolution follows the current trend of distributedly performed computation and storage. This trend provides several new possibilities to scientists, researchers and to simple users around the world, so as to use the shared resources for executing their tasks and running their applications. These operations are not always possible to perform in local, limited capacity, resources. In this thesis we study issues related to the scheduling of tasks and the routing of their datasets. We study these issues both separately and jointly, along with their interactions. Initially, we present a Quality of Service (QoS) framework for grids that guarantees to users an upper bound on the execution delay of their submitted tasks. Such delay guarantees imply that a user can choose, with absolute certainty, a resource to execute a task before its deadline expires. Our framework is not based on the advance reservation of resources, instead, the users follow a self constrained task generation pattern, which is agreed separately with each resource during a registration phase. We validate experimentally the proposed Quality of Service (QoS) framework for grids, verifying that it satisfies the delay guarantees promised to users. In addition, when the proposed extensions are used, the framework also provides delay guarantees without exact a-priori knowledge of the task workloads. Next, we examine a task scheduling and data migration problem for grid networks, which we refer to as the Data Consolidation (DC) problem. Data Consolidation arises when a task requests concurrently multiple pieces of data, possibly scattered throughout the grid network that have to be present at a selected site before the task's execution starts. In such a case, the scheduler must select the data replicas to be used, the site where these data will be gathered for the task to be executed, and the routing paths to be followed. We propose and experimentally evaluate several Data Consolidation schemes. Some consider only the computational or only the communication requirements of the tasks, while others consider both kinds of requirements. We also propose Data Consolidation (DC) schemes, which are based on Minimum Spanning Trees (MST) that route concurrently the datasets so as to reduce the congestion that may appear in the future, due to these transfers. In our simulation experiments we validate the proposed schemes and show that if the Data Consolidation operation is performed efficiently, then significant benefits can be achieved, in terms of the resources' utilization and task delay. We also consider the use of resource information aggregation in grid networks. We propose a number of aggregation schemes and operators for reducing the information exchanged in a grid network and used by the resource manager in order to make efficient scheduling decisions. These schemes can be integrated with the schemes utilized in hierarchical data networks for data routing, providing interoperability between different grid networks, while the sensitive or detailed information of resource providers is kept private. We perform a large number of experiments to evaluate the proposed aggregation schemes and the used operators. As a metric of the quality of the aggregated information we introduce the Stretch Factor (SF), defined as the ratio of the task delay when the task is scheduled using complete resource information over the task delay when an aggregation scheme is used. We also measure the number of resource information updates triggered by each aggregation scheme and the amount of resource information transferred. In addition, we are interested in the difficulties encountered and the solutions provided in order to develop and evaluate scheduling policies, initially implemented in a simulation environment, in the gLite grid middleware. We identify two important such implementation issues, namely the inaccuracy of the information provided to the scheduler by the information system, and the inflexibility in the sharing of a resource among different jobs. Our study indicates that simple changes in the gLite's scheduling procedures can solve these and other similar issues, yielding significant performance gains. We also investigate the use of the virtualization technology in the gLite middleware. We implement and evaluate the proposed mechanisms in a small gLite testbed. Finally, we propose a multicost impairment-aware routing and wavelength assignment (IA-RWA) algorithm in optical networks. In general, physical impairments tend to degrade the optical signal quality. Also, optical networks is the main networking technology used today for the interconnection of the grid's, computational and storage, resources around the world. The main characteristic of the proposed algorithm is that it calculates the quality of transmission (QoT) of a candidate lightpath by measuring several impairment-generating source parameters and not by using complex formulas to directly account for the effects of physical impairments. In this way, this approach is more generic and more easily applicable to different conditions (modulation formats, bit rates). Our results indicate that the proposed impairment-aware routing and wavelength assignment (IA-RWA) algorithm can efficiently serve the online traffic in an optical network and to guarantee the transmission quality of the found lightpaths, with low running times. In general, in this thesis we present several novel mechanisms and algorithms for grid networks. At the same time, this Thesis reveals the variety of the issues that relate to the efficient operation of the grid networks and their interdependencies. For handling all these issues the cooperation of researches, scientists and engineers from various fields, is required.

Η παρούσα εργασία ασχολείται με κινητά Ασύρματα Δίκτυα Αισθητήρων και προτείνεται ένα αποδοτικό πρωτόκολλο διάδοσης για κινητά Δίκτυα Αισθητήρων με σταθερό σταθμό Κόμβο-Πηγή. Επίσης, υλοποιούνται σε πραγματικό πειραματικό δίκτυο ασύρματων αισθητήρων και μελετάται πειραματικά η απόδοση πρωτοκόλλων εξισορρόπησης ενέργειας. Τα Ασύρματα Δίκτυα Αισθητήρων αποτελούνται από μεγάλο αριθμό αυτόνομων συσκευών με περιορισμένες δυνατότητες επικοινωνίας, αποθήκευσης, επεξεργασίας και ενέργειας, που τοποθετούνται σε μια συγκεκριμένη περιοχή ενδιαφέροντος στην οποία δεν υπάρχει καμία εκ των προτέρων εγκατεστημένη δικτυακή υποδομή και γνώση της τοπολογίας. Οι κόμβοι επικοινωνούν και συνεργάζονται μεταξύ τους και ακροάζονται το περιβάλλον με τη χρήση αισθητήρων με στόχο να φέρουν σε πέρας εφαρμογές όπως είναι, ο έλεγχος κυκλοφορίας, η συλλογή μετεωρολογικών δεδομένων, η παρακολούθηση του περιβάλλοντος καθώς και εφαρμογές ασφαλείας. Η δρομολόγηση δεδομένων στα ασύρματα δίκτυα αισθητήρων γίνεται ως εξής, οι αισθητήρες-κόμβοι συλλέγουν δεδομένα από το περιβάλλον που ακροάζονται και τα προωθούν σε γειτονικούς κόμβους με στόχο να φτάσουν κάποια στιγμή (multi-hop routing) σε ένα κόμβο-πηγή (sink) ο οποίος έχει απεριόριστο αποθηκευτικό χώρο και ενέργεια. Για την αύξηση της διάρκειας ζωής ενός ασύρματου δικτύου αισθητήρων έχουν αναπτυχθεί διάφορες τεχνικές όπως είναι οι τεχνικές εξισορρόπησης ενέργειας. Στόχος στο πρόβλημα της εξισορρόπησης κατανάλωσης ενέργειας σε ένα ασύρματο δίκτυο αισθητήρων είναι να επιτύχουμε ίση κατανάλωση ενέργειας ανά κόμβο του δικτύου ώστε να μεγιστοποιήσουμε τη διάρκεια ζωής του δικτύου αποφεύγοντας την πρόωρη αποσύνδεση του δικτύου. Τα προτεινόμενα πρωτόκολλα για κινητά δίκτυα αισθητήρων αξιολογήθηκαν πειραματικά μέσω διεξοδικής προσομοίωσης, χρησιμοποιώντας ποικίλες τιμές για βασικές παραμέτρους του δικτύου και συγκρίθηκαν με υπάρχουσες ευρέως αποδεκτές μεθόδους. Τα αποτελέσματα δείχνουν ότι τόσο ο χρόνος παράδοσης των μηνυμάτων, όσο και η ενέργεια που απαιτείται διατηρούνται σε χαμηλά επίπεδα, βελτιώνοντας σημαντικά την προηγούμενη σχετική έρευνα. Όσον αφορά τα πρωτόκολλα εξισορρόπησης ενέργειας, υλοποιήθηκαν σε πραγματικό πειραματικό δίκτυο και αξιολογήθηκαν πειραματικά μέσω πραγματικών πειραμάτων. Τα πειραματικά αποτελέσματα επιβεβαιώνουν τα θεωρητικά αποτελέσματα των μελετώμενων πρωτοκόλλων. / In this thesis we study Sensor Networks that are highly dynamic and mobile, and we propose a new efficient routing protocol for mobile Sensor Networks with a static base-station/sink. Moreover, we implement energy balancing data propagation protocols in a wireless sensor network test-bed and we investigate their performance. Wireless Sensor Networks consist of a large number of small, autonomous devices, that have limited communication, storage, computational and energy resources, that are deployed in a specific area of interest where there is no prior established network infrastructure and knowledge of topology. The nodes communicate and cooperate with each other and sense the environment by using sensors to carry out applications such as control traffic, weather monitoring, environmental monitoring and security applications. The routing of data in wireless sensor network is done as follows, the sensor-nodes sense the environment, collect data and relay the data to adjacent nodes in order to reach in a multi-hop way to a base station (sink) which has unlimited storage and energy resources. There have been developed various techniques to increase the lifetime of a wireless sensor network such as energy balancing propagation techniques. The goal of the energy balancing propagation schemes is to achieve equal energy consumption per node in order to maximize the lifetime of the network by avoiding early disconnection of the network. An extensive performance comparison of the protocols for mobile sensor networks proposed in this study to relevant methods from the state of the art demonstrates significant improvements i.e. latency is reduced by even four times while keeping energy dissipation and delivery success at very satisfactory levels. Regarding the energy balancing protocols, we have implemented them in a real experimental testbed and evaluated them experimentally via real experiments. The experimental results confirm the theoretical results of the studied protocols.

Σε ένα δίκτυο πολυπλεξίας διαίρεσης μήκους κύματος (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.

Η δρομολόγηση και ανάθεση μηκών κύματος (routing and wavelength assignment - RWA) αποτελεί ένα πολύ σημαντικό πρόβλημα, που απασχολεί τους σχεδιαστές WDM οπτικών δικτύων και είναι γνωστό, πως είναι NP-πλήρες. Στην εργασία αυτή σχεδιάζουμε και υλοποιούμε έναν αλγόριθμο για το στατικό RWA, που βασίζεται σε έναν προτεινόμενο σχηματισμό (μη ακέραιου) γραμμικού προγραμματισμού (linear programming - LP). Ισχυριζόμαστε, πως ο σχηματισμός αυτός είναι σε θέση να παρέχει ακέραιες βέλτιστες λύσεις (παρά την εν γένει μη ακέραια φύση του) για ένα μεγάλο ποσοστό στιγμιότυπων εισόδου, οδηγώντας έτσι σε αντίστοιχες ακριβείς λύσεις του RWA. Η πολυπλοκότητα του αλγόριθμου κυριαρχείται από το χρόνο εκτέλεσης του αλγόριθμου Simplex, ο οποίος θεωρείται αποδοτικός για μια μεγάλη πλειοψηφία στιγμιότυπων εισόδου. Στα διαφανή (πλήρως οπτικά) δίκτυα, η ποιότητα του σήματος υπόκειται σε μια ποικιλία από φυσικές εξασθενήσεις, όπως είναι η διασπορά λειτουργίας πόλωσης (polarization mode dispersion - PMD), ο θόρυβος αυθόρμητης εκπομπής ενισχυτή (amplified spontaneous emission - ASE - noise) και η χρωματική διασπορά (chromatic dispersion - CD). Αυτές οι εξασθενήσεις μοντελοποιούνται γραμμικά και μπορούν να αντιμετωπιστούν αποτελεσματικά από ένα σύνολο αναλυτικών τύπων ως επιπρόσθετοι περιορισμοί στο RWA. Εφαρμόζουμε τον αλγόριθμό μας και εκτελούμε RWA βασισμένο σε περιορισμούς εξασθένησης, με σκοπό να παρατηρήσουμε συγκριτικά αποτελέσματα στην απόδοση ενός τυπικού μητροπολιτικού δικτύου υπό διάφορες παραμέτρους του δικτύου και των εξασθενήσεων, όπως είναι ο ρυθμός bit, ο τύπος και το κέρδος των ενισχυτών, η χρησιμοποιούμενη διάταξη διαμόρφωσης, κλπ. / Routing and wavelength assignment (RWA) is a very important problem concerning WDM optical network designers and is known to be NP-complete. In this work, we design and implement an algorithm for the static RWA, that is based on a proposed (not integer) linear programming formulation. We claim, that this formulation is able to provide integer optimal solutions (despite its non integral nature) for a large fraction of input instances, yielding thus to corresponding exact RWA solutions. The algorithm's complexity is dominated by the execution time of Simplex LP-solver, that is considered efficient in the great majority of all possible input instances. In transparent (all-optical) 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). Those impairments are linearly modeled and are handled effectively by a set of analytical formulae 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.

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

Η πρόσφατη τεχνολογική ανάπτυξη των οπτικών ενισχυτών, πολυπλεκτών/αποπλεκτών, οπτικών διακοπτών καθώς και άλλων οπτικών συσκευών μας οδηγεί στο να ελπίζουμε ότι σύντομα στο μέλλον θα υλοποιηθεί ένα πλήρες οπτικό (all optical), WDM (wavelength division multiplexing) δίκτυο που να ικανοποιεί και την ανάγκη για μεγάλα μεγέθη χωρητικότητας. Σε ένα τέτοιο δίκτυο η μετατροπή του οπτικού σήματος σε ηλεκτρονικό και εκ νέου στο οπτικό (ΟΕΟ) δεν θα χρησιμοποιείται στους ενδιάμεσους κόμβους, και αυτό συμβάλει σε οικονομικότερες υλοποιήσεις των οπτικών δικτύων. Σε ένα WDM δρομολογούμενο δίκτυο, τα δεδομένα μεταφέρονται μέσω ενός οπτικού καναλιού, lightpath, στους κόμβους του δικτύου που συνδέονται με οπτικές ίνες. Στις πλείστες των περιπτώσεων, κατά την άφιξη ενός lightpath σε κάποιο κόμβο, εφαρμόζεται σε αυτό οπτικό-ηλεκτρονική μετατροπή και αντίστροφα, ούτως ώστε το σήμα να αναδημιουργηθεί λόγω των απωλειών που υπέστη κατά την μεταφορά, ή ακόμη για να αναλυθεί από ενδιάμεσες ηλεκτρονικές συσκευές. Στα μη πλήρη οπτικά δίκτυα, η μεταφορά των δεδομένων γίνεται από κόμβο σε κόμβο κατά μήκος του δικτύου, ούτως ώστε το οπτικό σήμα να ενισχύεται και να αναγεννάτε μέσω της OEO επεξεργασίας. Παρ’ όλα αυτά, η κάθε ενδιάμεση ανάλυση του θέματος σε ένα τέτοιο δίκτυο προϋποθέτει πολύ μεγάλα κόστη λόγω των πολλών συσκευών που απαιτούνται για τη OEO επεξεργασία. Το γεγονός αυτό μας οδηγεί στα ημί-πλήρη δίκτυα όπου η ενίσχυση και αναγέννηση του θέματος δε γίνεται σε όλους τους ενδιάμεσους κόμβους αλλά σε μερικούς από αυτούς. Ο τελικός στόχος όμως είναι η απαλοιφή της ηλεκτρονικής μετατροπής και αυτό οδηγεί στην υλοποίηση των πλήρως οπτικών δικτύων. Στα πλήρη οπτικά δίκτυα, ένα σήμα που μεταδίδεται παραμένει, για όλο το lightpath, στο οπτικό επίπεδο. Έτσι, το πλήρες οπτικό δίκτυο μπορεί να απαλείψει την ασύμφορη OEO μετατροπή. Η αναζήτηση των κατάλληλων μονοπατιών με τα κατάλληλα μήκη κύματος που θα ικανοποιούσε ένα πλήρες οπτικό δίκτυο το οποίο δρομολογείται από ligthpaths, ονομάζεται Routing and Wavelength Assignment (RWA) και αποτελεί ένα από τα σημαντικότερα ζητήματα για το σωστό σχεδιασμό των οπτικών δικτύων τέτοιου είδους. Το πρόβλημα γίνεται ιδιαίτερα πολύπλοκο όταν στην τελική απόφαση θα πρέπει να συμπεριληφθούν και τα χαρακτηριστικά του φυσικού επιπέδου του δικτύου, όπως εξασθένιση του σήματος, μη γραμμικά φαινόμενα, διασπορά κ.ά, η συμβολή των οποίων στην τελική δρομολόγηση δεν θεωρείται αμελητέα (Impairment Aware Routing and Wavelength Assignment, ΙΑ-RWA). Σε αυτή την εργασία μελετάται το RWA πρόβλημα και προτείνεται ένας μονού στόχου γενετικός αλγόριθμος (Single Objective Genetic Algorithm - SOGA), ο οποίος επιλύει ικανοποιητικά το πρόβλημα θεωρώντας στατική κίνηση. Επιπλέον τονίζεται η σημασία των φυσικών παραμέτρων του προβλήματος και πως αυτές επηρεάζουν την απόδοση του πλήρους οπτικού δικτυου. Στη συνέχεια προτείνεται ένας νέος, πολλαπλών στόχων γενετικός αλγόριθμος (multi objective genetic algorithm – MOGA) ο οποίος βελτιστοποιεί τις λύσεις του προβλήματος ικανοποιητικά λαμβάνοντας ταυτόχρονα υπόψη, με έμμεσο τρόπο, και τις φυσικές παραμέτρους. Επίσης προτείνεται και ένας μονού στόχου γενετικός αλγόριθμος οποίος χρησιμοποιεί ένα εργαλείο αποτίμηση της ποιότητας μετάδοσης (Q-TOOL) σαν μέτρο κατά τη διαδικασία εύρεσης ικανοποιητικής λύσης. Το υπόλοιπο της εργασίας οργανώνεται ως ακολούθως: Στην ενότητα 2 παρουσιάζεται μια σύντομη αναφορά στα WDM δίκτυα καθώς και η περιγραφή του RWA και IA-RWA προβλήματος, ενώ στην ενότητα 3 παρουσιάζεται η πρόταση επίλυσης του RWA προβληματος με τη χρήση γενετικών αλγορίθμων. Ακολουθεί στην ενότητα 4 η πρότασή μας για επίλυση του IA-RWA προβλήματος με τη χρήση Multi-objective διαδικασιών βελτιστοποίησης, καθώς και η βελτιστοποίηση του προβλήματος με τη χρήση του Q-TOOL. Τέλος στην ενότητα 5 συνοψίζουμε την εργασία και παρουσιάζουμε τα συμπεράσματα. / The recent development of optical amplifiers, multiplexers / de-multiplexers, optical switches and other optical devices leads us to hope that soon in future all optical, WDM (wavelength division multiplexing) networks will be implemented which that will satisfy the needs for large capacity. In such networks a viable conversion of the optical -> Electronic and back to optical (OEO) will not be used at intermediate nodes, and this will contribute to efficient and economical implementation. The search for the appropriate paths with the appropriate wavelengths that meet the requirement in all optical networks is called Routing and Wavelength Assignment (RWA) and is one of the most important issues for proper design of such optical networks. The problem becomes particularly complex when the final decision should include the characteristics of the physical layer of the network, such as attenuation of the signal, nonlinear effects, dispersion, etc., whose contribution to the final result is not considered negligible (Impairment Aware Routing and Wavelength Assignment,IA-RWA). This work studies the RWA problem considering static traffic, and proposes a single-objective genetic algorithm (Single Objective Genetic Algorithm - SOGA), which resolves the problem satisfactorily. Furthermore the work stresses the importance of physical parameters of the problem and how these affect the performance of the all optical networks, and proposes a new, multi-objective genetic algorithm (MOGA) which optimizes the solution of IA-RWA problem adequately taking into account indirectly, and the physical impairments that affect the quality of the signal. In addition, a single objective genetic algorithm is proposed that uses a tool to assess the quality of the transmission signal (Q-TOOL), as a benchmark, in the process of optimization of the solution to the IA-RWA problem.

Τα οπτικά δίκτυα αποτελούν την αποδοτικότερη επιλογή όσον αφορά την εγκατάσταση ευρυζωνικών δικτύων κορμού, καθώς παρουσιάζουν μοναδικά χαρακτηριστικά μετάδοσης. Διαθέτουν τεράστιο εύρος ζώνης, υψηλή αξιοπιστία, ενώ επίσης έχουν μειωμένο κόστος μετάδοσης ανά bit πληροφορίας σε σχέση με τα υπόλοιπα ενσύρματα δίκτυα. Τις τελευταίες δεκαετίες διατυπώθηκαν οι αρχές μίας τεχνολογίας μετάδοσης πολλαπλών φερουσών, γνωστής ως Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (Orthogonal Frequency Division Multiplexing - OFDM), η οποία στηρίζεται στην πολυπλεξία διαίρεσης συχνότητας, αλλά πετυχαίνει πολύ καλύτερη χρησιμοποίηση του διαθέσιμου εύρους ζώνης. Πρόσφατα και στις οπτικές επικοινωνίες άρχισε να μετατοπίζεται το ενδιαφέρον στην Οπτική Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (O-OFDM), λόγω της προόδου στην κωδικοποίηση και στην ηλεκτρονική ψηφιακή επεξεργασία σήματος (DSP). Οι εξελίξεις αυτές μπορούν να αλλάξουν ριζικά τα οπτικά δίκτυα. Μέσω της πολυπλεξίας υποφερουσών και της δέσμευση μεταβλητού φάσματος, που είναι χαρακτηριστικά της O-OFDM τεχνολογίας, ένα οπτικό μονοπάτι μπορεί να χρησιμοποιεί το απολύτως απαραίτητο φάσμα (αριθμό υποφερουσών) ανάλογα με το μεταδιδόμενο ρυθμό δεδομένων. Με τον τρόπο αυτό επιτυγχάνεται καλύτερη χρησιμοποίηση φάσματος αναιρόντας τον περιορισμό σταθερού πλέγματος των δικτύων πολυπλεξίας μήκους κύματος (WDM). Παράλληλα η αρχιτεκτονική αυτή υποστηρίζει τη δέσμευση χωρητικότητας μικρότερης ή μεγαλύτερης από αυτή ενός μήκους κύματος μέσω της δέσμευσης κατάλληλου αριθμού υποφερουσών από κατάλληλους transponders και μεταγωγείς WXCs. Στην παρούσα διπλωματική εργασία αντιμετωπίζεται το πρόβλημα της σχεδίασης ευέλικτων OFDM οπτικών δικτύων, όπου οι αιτήσεις εξυπηρετούνται από κατάλληλους transponders όσον αφορά την επιλογή του χρησιμοποιούμενου φάσματος και του επίπεδου διαμόρφωσης. Με δεδομένη την τοπολογίας του δικτύου, τον πίνακα αιτήσεων και των χαρακτηριστικών των transponders, παρουσιάζονται οι μοντελοποιήσεις γραμμικού ακέραιου προγραμματισμού (Integer Linear Programming) για την επίλυση του προβλήματος σχεδίασης διαφανών (transparent) και ημι-διαφανών (translucent) οπτικών OFDM δικτύων λαμβάμνοντας υπόψη τους υπαρκτούς περιορισμούς φυσικού επιπέδου. Σχεδιάζεται λοιπόν, ένα πρόβλημα βελτιστοποίησης που λαμβάνει υπόψη του τόσο το εύρος ζώνης που χρησιμοποιείται όσο και τον αριθμό των transponders. Από τη στιγμή που το πρόβλημα της δρομολόγησης και δέσμευσης φάσματος (Routing and Spectrum Allocation RSA) είναι ΝP πλήρες (NP-complete), η λύση του προβλήματος γραμμικού ακέραιου προγραμματισμού (ILP) δεν είναι αποδοτική για μεγάλα στιγμιότυπα του προβλήματος. Για το λόγο αυτό, παρουσιάζονται ευριστικοί αλγόριθμοι (heuristic algorithms) για την επίλυση του προβλήματος σχεδίασης διαφανών και ημι-διαφανών οπτικών δικτύων. / We consider the planning problem of a spectrum flexible optical network where traffic is served by flexible transponders that can be tuned in both the spectrum and the modulation format that they utilize. We assume that physical layer impairments are incorporated in the definition of the feasible transmission configurations for the transponders, described by capacity-reach-spectrum-guardband tuples. Given the feasible configurations (tuples) of the transponders and the traffic matrix, we formulate the planning problem of a spectrum flexible optical network considering both the use or not of regenerators in the network. Demands are served for their requested rates by choosing the route, breaking the transmission in more than one connection if needed, placing regenerators if needed, and allocating spectrum to the connections. The connections are separated by appropriate spectrum guardbands so that physical layer interference is kept at acceptable levels. The objective is to serve the traffic and find a solution that is Pareto optimal with respect to the total amount of spectrum utilized and the number of transponders used. We start by presenting algorithms that are based on integer linear programming (ILP) formulations for planning both transparent (without regenerators) and translucent (with regenerators) networks and then we continue by presenting heuristic algorithms. Our heuristic algorithms utilize simulated annealing to tradeoff performance with running time. We use transmission tuples based on studies on OFDM-based networks in our simulation experiments. We initially examine the optimality performance of the heuristic algorithms in small scale experiments. Then we use the heuristic algorithms to study realistic network planning problems and evaluate the spectrum and transponder cost savings that can be obtained by an OFDM-based network as compared to a mixed line rate (MLR) fixed-grid WDM optical network.

H διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων, προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείρισή τους και, τέλος, δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισo-προσανατολισμένων ορθογωνίων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο-προσανατολισμένο ορθογώνιο είτε σημείο ή κάθετο / οριζόντιο ευθύγραμμο τμήμα. Για την επίλυσή του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγούμενων καλύτερων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. H προτεινόμενη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δύο βιομηχανικά προβλήματα. Το πρώτο αφορά στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION-FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγόριθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων, έλεγχος polygon inclusion, κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κύρια μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παραγωγής και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on-line έλεγχο προκειμένου να υποστηρίξει το διευθυντή παραγωγής στη λήψη αποφάσεων. / Τhe dissertation examines problems of efficient organization of spatial data, proposes specific tree structures for their management, and finally, gives examples of their use in specific application areas. The first chapter is about the problem of finding the iso-oriented rectangles that enclose a query object which can be an iso-oriented rectangle either a point or a vertical / horizontal line segment. A multilevel tree structure is proposed to solve the problem which improves the complexities of the best previous known solutions. The second chapter examines the problem of point retrieval on polygons. The proposed geometric structure is also multileveled and efficient when the query polygon has specific properties. The third chapter is about the application of tree structures in two manufacturing problems. The first one concerns the reduction in the complexity of collision detection as a robotic arm moves on a planar scene with obstacles. For the solution a priority queue and a UNION-FIND structure are used, whereas known data structures and algorithms of Computational Geometry such as construction of convex hulls, polygon inclusion testing, etc. are applied. The second problem is about material requirements planning (MRP) in a manufacturing production system. To this end an MRP processor was developed, which uses linked lists and runs in main memory to retain efficiency. The last chapter examines the production control problem, and more specifically the job scheduling problem. In this context, an intelligent scheduling system was designed and developed for flow shop production control which combines knowledge-based technology and simulation with on-line control in order to support the production manager in decision making.