Στη μεταπτυχιακή αυτή εργασίας γίνεται μελέτη και υλοποίηση ενός αλγορίθμου χρονοπρογραμματισμού για μεταγωγέα ΑΤΜ της κατηγορίας αλγορίθμων ranking, ο οποίος χρησιμοποιεί μνήμη οργανωμένη σε πολλαπλές ουρές εισόδου για την αποθήκευση των πακέτων πριν την δρομολόγησή τους. O αλγόριθμος ROLM (Randomized On – Line Matching) επιτυγχάνει μέγιστο ταίριασμα εισόδων – εξόδων λόγω του permutation των εισόδων που γίνεται πριν την είσοδο των αιτήσεων. Επίσης, στοχεύει στη μείωση του latency που αφορά τη hardware υλοποίηση (χάρις στον υπολογισμό του τυχαίου permutation) και σε υψηλά ποσοστά δικαιοσύνης και throughput. Η υλοποίησηση του αλγορίθμου ROLM εκτελείται με δύο τρόπους: α) σε υλικό (FPGA) και β) σε λογισμικό (κώδικας C για AVR). Η πλατφόρμα FPSLIC μας επιτρέπει να αξιολογήσουμε και να συγκρίνουμε τις hardware και software υλοποιήσεις του αλγορίθμου κατά έναν ρεαλιστικό τρόπο, καθώς τόσο ο μικροελεγκτής ΑVR, όσο και η προγραμματιζόμενη λογική FPGA είναι κατασκευασμένα με την ίδια ακριβώς τεχνολογία, ενσωματωμένα σε μια μονολιθική συσκευή. Εξάγονται τα αποτελέσματα μετρήσεων της ταχύτητας και επιφάνειας του χρονοπρογραμματιστή και γίνεται σύγκριση για διαφορετικά μεγέθη μεταγωγέα στην απόδοση μεταξύ των δύο υλοποιήσεων του αλγορίθμου μεταξύ τους. Γίνεται επίσης σύγκριση μεταξύ αποτελεσμάτων του αλγόριθμου ROLM και του αλγορίθμου FIRM, που έχουν ληφθεί από παρεμφερή εργασία. / In this study the design and implementation of a scheduler ranking algorithm for ATM switches is presented. The algorithm employs a multiple-queue input memory for storing packets prior to sending them out. It is the ROLM (Randomized On-Line Matching) algorithm, which performs a high level of input-output matching due to pre-request input permutation. It also reduces hardware-related latency (due to the calculation of random permutation), and achieves fairness and high throughput. The ROLM algorithm was implemented in two ways: one implementation for hardware (FPGA) and one for software (using code C for AVR). The FPSLIC platform allowed for a reliable assessment of the algorithm's hardware and software implementation since the AVR microcontroller and the FGPA programming logic are technologically compatible and integrated on a single device. Measurement results are presented on the controller's surface and speed for different switch sizes as well as a performance comparison is conducted on published results between ROLM and FIRM algorithms.

To ATM είναι μια δικτυακή τεχνολογία μετάδοσης που υποστηρίζει την μεταφορά ετερογενούς κίνησης, δηλ πραγματικού χρόνου όπως ήχος, εικόνα και μη πραγματικού χρόνου όπως υπολογιστικά δεδομένα, χρησιμοποιώντας έναν μηχανισμό που διαβιβάζει μονάδες δεδομένων σταθερού μεγέθους, τα cells. Η απόδοση του δικτύου ΑΤΜ εξαρτάται σε μεγάλο βαθμό από την χαρακτηριστικά των μεταγωγέων πακέτων. Για την ανάπτυξη αποτελεσματικών μεταγωγέων χρειάζεται να αναπτύξουμε αποτελεσματικούς χρονοπρογραμματιστές υψηλής ταχύτητας που είναι απλοί στην υλοποίησή τους. Στα πλαίσια αυτής της μεταπτυχιακής εργασίας γίνεται η μελέτη και η υλοποίηση ενός νέου κατανεμημένου αλγορίθμου χρονοπρογραμματισμού για μεταγωγέα ΑΤΜ, που χρησιμοποιεί μνήμη οργανωμένη σε πολλαπλές ουρές εισόδου για την αποθήκευση των πακέτων πριν την δρομολόγησή τους. O αλγόριθμος Αμοιβαίας Προτεραιότητας (Mutual Priority) μπορεί να επιτύχει υψηλό throughput και βέλτιστη εγγύηση εξυπηρέτησης, ίση με Ν κύκλους. Επιπλέον προσφέρει πολύ υψηλή απόδοση ακόμα και με μια μόνο επανάληψη, υπερτερώντας έτσι των υπόλοιπων αλγορίθμων. Η υλοποίησηση του αλγορίθμου Αμοιβαίας Προτεραιότητας εκτελείται με 2 τρόπους: α) σε υλικό (FPGA) και β) σε λογισμικό (κώδικας C για AVR). Η πλατφόρμα FPSLIC μας επιτρέπει να αξιολογήσουμε και να συγκρίνουμε τις hardware και software υλοποιήσεις του αλγορίθμου κατά έναν ρεαλιστικό τρόπο, αφού τόσο ο μικροελεγκτής ΑVR, αλλά και η προγραμματιζόμενη λογική FPGA είναι κατασκευασμένα με την ίδια ακριβώς τεχνολογία, ενσωματωμένα σε μια μονολιθική συσκευή. Τέλος εξάγουμε αποτελέσματα μετρήσεων της ταχύτητας και επιφάνειας του χρονοπρογραμματιστή και εκπονούμε σύγκριση για διαφορετικά μεγέθη μεταγωγέα στην απόδοση μεταξύ των 2 υλοποιήσεων του αλγορίθμου μεταξύ τους, αλλά και σύγκριση μεταξύ αποτελεσμάτων, που έχουν ληφθεί από παρεμφερή εργασία, του αλγορίθμου FIRM και του αλγόριθμου Mutual Priority. Παρατηρούμε ότι ο αλγόριθμος Mutual Priority υπερέχει ξεκάθαρα, είτε για υλοποίηση σε υλικό είτε σε λογισμικό, έναντι του άλλου αλγορίθμου. / ATM is a network transmission technology that allows transfer of heterogeneous traffic, that is real-time like sound, image and non real-time like computer data, using a mechanism that delivers fixed size data units, the cells. The performance-efficiency of ATM network depends on a grate scale from the characteristics of packet switches. In order to develop efficient switches we need to design optimal high speed schedulers, which are easy to realize. In this master thesis, we present the study and realization of a new distributed scheduling algorithm for ATM switch, that uses memory organized according to the scheme of advanced input queuing. Mutual Priority Scheduler can achieve high throughput and optimum service guarentee, equal to N cycles. Furthermore it provides high performance, even with one iteration, exceeding all the other algoritms. The realization of the algorithm is performed with 2 ways: a)in hardware and b) in software. Fpslic platform let us evaluate and compare these 2 different realizations of Mutual Priority algorithm, as it contains an FPGA and a microcontroller embedded on the same chip. Finaly we present measurements for the speed and area of the scheduler, and make comparisons for different switch sizes. Moreover we compare the realization of Mutual Priority Scheduler and that of Firm scheduler. We take us an outcome that Mutual Priority scheduler surpass the other algorithm either in hardware, or in software.