Η εργασία αυτή επικεντρώνεται στη σχεδίαση και υλοποίηση αλγορίθμων scheduling εργασιών σε κατανεμημένο περιβάλλον (Grid Computing, HPC), οι οποίοι μπορούν να προσφέρουν δίκαιο καταμερισμό των υπολογιστικών πόρων, ενώ διατηρούν τον βαθμό της ποιότητας υπηρεσίας που απαιτούν κάποιες κατηγορίες χρηστών. Οι αλγόριθμοι που αναλύονται και υλοποιούνται βασίζονται στις τεχνικές του περιορισμού των χρηστών από μια γραμμική σχέση, καθώς και την ομαδοποίηση των πόρων σε αφιερωμένες ομάδες, οι οποίες εξυπηρετούν συγκεκριμένες κατηγορίες χρηστών. Οι τεχνικές συνδυάζονται για την επίτευξη μεγαλύτερης απόδοσης, καλύτερης ποιότητας υπηρεσίας και δικαιότερης κατανομής των υπολογιστικών πόρων. Παράλληλα αναπτύχθηκε και ένα ευέλικτο και αποδοτικό περιβάλλον προσομοίωσης, το οποίο χρησιμοποιείται για τον πειραματικό έλεγχο της απόδοσης των αλγορίθμων. Περιγράφεται αναλυτικά το μοντέλο προσομοίωσης, του οποίου η απλότητα, σε συνδυασμό με την ευελιξία της υλοποίησης του προσομοιωτή και τον έλεγχο πάνω σε οποιαδήποτε παράμετρο των προσομοιωμένων συστημάτων, επιτρέπει τον ταχύ σχεδιασμό και υλοποίηση πειραματικών προσομοιώσεων, καθώς και την άμεση σύγκριση των αποτελεσμάτων, με την αυτόματη παραγωγή συγκριτικών γραφικών παραστάσεων. / This thesis addresses the design and implementation of algorithms for task (job) scheduling in distributed computational enviroments (Grid Computing, HPC). These algorithms provide fair resource usage while preserving the provided QoS for user types that demand it. The algorithms that are being developed utilize linear bounds in order to keep under control workload submission rates, while dedicated node sets are used to handle jobs submitted from QoS-demanding users. In order to test the behavior of the proposed algorithms, a new simulation application was designed and developed. The simulator uses a simple, but powerful model of simulation, is extremely extendible and flexible in reusing components and developing new ones, allows execution of a series of the same experiments over the values of a single parameter (e.g. arrival rate λ) and incorporates graph creation utilities, making it a valuable tool for engineers, administrators and scientists trying to choose an optimal scheduling policy for their distributed systems.

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

Οι οικονομικές και τεχνολογικές εξελίξεις των τελευταίων ετών, η απελευθέρωση της αγοράς, οι ισχυρές κατά απαίτηση πολυμεσικές υπηρεσίες καθώς και ο αυξημένος αριθμός χρηστών των κινητών δικτύων υποδεικνύουν την αναγκαιότητα της σύγκλισης των δύο δικτυακών τεχνολογιών (κινητή τηλεφωνία και internet) με στόχο την παροχή υπηρεσιών Internet στο περιβάλλον των κινητών επικοινωνιών. Η παραπάνω απαίτηση οδήγησε στην δημιουργία του δικτύου επόμενης γενιάς NGN. Η διπλωματική αυτή εργασία ασχολείται με την μελέτη της αρχιτεκτονικής του επιπέδου υπηρεσιών και την υποστήριξη Ποιότητας Υπηρεσίας (QoS) σε δίκτυα Νέας Γενιάς. Συγκεκριμένα δίνεται έμφαση στις λειτουργίες ελέγχου, σηματοδοσίας και λειτουργιών αρχιτεκτονικής του QoS σε επίπεδο υπηρεσιών. Αρχικά, ορίζουμε την έννοια “QoS” όσον αφορά την οπτική του δικτύου και το χρήστη. Περιγράφονται η αρχιτεκτονική του στρώματος υπηρεσιών του δικτύου καθώς και οι λειτουργίες ελέγχου πόρου και αποδοχής των κλήσεων, που αποτελούν σημαντικό μέρος της αρχιτεκτονικής του NGN. Στη συνέχεια παρουσιάζονται αρχιτεκτονικές που προορίζονται για την παροχή του QoS (IntServ, DiffServ), στη Συμφωνία Στάθμης Παρεχόμενης Υπηρεσίας (SLA), το πρωτόκολλο σηματοδοσίας COPS. Επίσης, δίνουμε έμφαση σε ορισμένες πτυχές (χρονοδρομολόγηση, διαχείριση ουρών) μίας QoS αρχιτεκτονικής, οι οποίες είναι ζωτικής σημασίας όσον αφορά την αποδοτική παροχή Ποιότητας Υπηρεσίας. Στη συνέχεια, με τη χρήση του εργαλείου προσομοίωσης OPNET, διεξάγουμε μια σειρά προσομοιώσεων σε ένα ATM και σε ένα NGN δίκτυο. Τέλος, παραθέτουμε και αναλύουμε τα αποτελέσματα των προαναφερθέντων πειραμάτων. / The concept of an NGN (Next Generation Network) has been introduced to take into consideration the new realities in the telecommunications industry, characterized by factors such as: competition among operators due to ongoing deregulation of markets, explosion of digital traffic, e.g.,increasing use of "the Internet", increasing demand for new multimedia services, increasing demand for a general mobility, convergence of networks and services, etc. This thesis has as subject the architecture of service stratum and presents an overview of standards functions defining the Quality of Service (QoS) in Next Generation Networks (NGNs). Several standards bodies define the QoS control architectures based on their scope of work. Specifically, emphasis is given to control functions, signalling and functional architecture of QoS in service stratum. Firstly, we define the meaning of QoS according to the view of the operator’s network and terminal users. The functional architecture of service stratum and especially the part of resource and admission control functions are described in the main body. Furthermore, architectures as IntServ and DiffServ, SLAs and COPS protocol are used as providers of the QoS. Scheduling and queuing management are necessary to optimize the QoS in NGN networks. In this project, we use OPNET simulator in two scenarios to determine construct and control ATM and NGN networks. Finally, collect the results of the experiments and analyze them.