Τα τελευταία χρόνια η ραγδαία αύξηση της υπολογιστικής ισχύος, των αποθηκευτικών μέσων καθώς και των τηλεπικοινωνιών έχει δημιουργήσει γόνιμο έδαφος για την ανάπτυξη πολύπλοκων, απαιτητικών εφαρμογών, τόσο στον χώρο της επιστημονικής έρευνας, όσο και στα πλαίσια της παραγωγής εμπορικών λύσεων. Ως αποτέλεσμα αυτού, πραγματοποιείται μετάβαση από το μοντέλο των μεμονωμένων διακριτών πόρων στο μοντέλο της συνεργασίας κατανεμημένων πόρων το οποίο υλοποιείται από την τεχνολογία πλέγματος (Grid Computing). Ένα πολύ σημαντικό θέμα που επηρεάζει την συνολική απόδοση των δικτύων πλέγματος είναι η χρονοδρομολόγηση των εργασιών που υποβάλλουν οι χρήστες στους διαθέσιμους πόρους του δικτύου. Στόχος της παρούσας διπλωματικής εργασίας ήταν η μελέτη της χρονοδρομολόγησης στα δίκτυα πλέγματος όχι μέσω προγραμμάτων προσομοίωσης αλλά χρησιμοποιώντας το ενδιάμεσο λογισμικό gLite. Βασικό αντικείμενο μελέτης ήταν η υπηρεσία Workload Management System (WMS) στην οποία υλοποιούνται οι αλγόριθμοι χρονοπρογραμματισμού που παρέχει το gLite. Στόχος ήταν η ανάλυση της λειτουργίας των δύο αλγορίθμων χρονοπρογραμματισμού που παρέχει το ενδιάμεσο λογισμικό και η κατανόηση τόσο της αρχιτεκτονικής της WMS υπηρεσίας, που είναι μια από τις πιο σημαντικές για την λειτουργία ολόκληρου του δικτύου, αλλά και του τρόπου υλοποίησης των δύο αλγορίθμων του gLite. Στην συνέχεια προσθέσαμε στην υπηρεσία WMS ένα νέο δίκαιο αλγόριθμο ανάθεσης εργασιών στους διαθέσιμους πόρους του δικτύου πλέγματος. Τέλος αναπτύξαμε ένα μικρής κλίμακας δίκτυο πλέγματος για την πειραματική αξιολόγηση του νέου αλγορίθμου και την σύγκριση του με τους δύο βασικούς αλγορίθμους του gLite. Τα αποτελέσματα δείχνουν ότι ο αλγόριθμος μας παρέχει καλύτερη αξιοποίηση των πόρων του δικτύου, μειώνοντας παράλληλα το μέσο χρόνο εκτέλεσης μιας εργασίας στο δίκτυο. / The emergence of high speed optical networks is making the vision of Grids a reality. Grids consist of geographically distributed and heterogeneous computational and storage resources that may belong to different administrative domains, but can be shared among users by establishing global resource management architecture. An important issue in the performance of Grids is the scheduling of application tasks to the available resources. The Grid environment is quite dynamic, with resource availability and load varying rapidly with time, and application tasks have very different characteristics and requirements. Scheduling is a key to the success of Grid Networks, since it determines the efficiency in the use of the resources and the QoS provided to the users. In this work we present our experiences from implementing and integrating a new job scheduling algorithm in the gLite Grid middleware and present experimental results that compare it to the existing gLite scheduling algorithms. It is the first time that gLite scheduling algorithms are put under test and compared with a new algorithm under the same conditions. We describe the problems that were encountered and solved, going from theory and simulations to practice and the actual implementation of our fair scheduling algorithm. In this work we also describe the steps one needs to follow in order to develop and test a new scheduling algorithm in gLite. We present the methodology followed and the testbed set up for the comparisons. Our research sheds light on some of the problems of the existing gLite scheduling algorithms and makes clear the need for the development of new.

Τα δίκτυα πλέγματος (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.

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