Τα δίκτυα πλέγματος (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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/4010 |
| Date | 05 January 2011 |
| Creators | Κόκκινος, Παναγιώτης |
| Contributors | Βαρβαρίγος, Εμμανουήλ, Kokkinos, Panagiotis, Βαρβαρίγος, Εμμανουήλ, Γαλλόπουλος, Ευστράτιος, Σπυράκης, Παύλος, Βέργαδος, Δημήτρης, Δενάζης, Σπύρος, Ζαρολιάγκης, Χρήστος, Μπούρας, Χρήστος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0042 seconds