- / -

Στόχος της εργασίας είναι να εμβαθύνει πάνω στο σημαντικό θέμα της ποιότητας υπηρεσίας, εξειδικεύοντας το θέμα για τα ATM switches. Μελετά τους αλγορίθμους που εφαρμόζονται ή λειτουργούν σε θεωρητικό επίπεδο για τα ATM switches και τον τρόπο που επηρεάζουν τις διάφορες παραμέτρους του QoS. Για το λόγο αυτό ορισμένοι αλγόριθμοι εφαρμόζονται σε εξομοιωτή δικτύων και με βάση τη συμπεριφορά τους εκτιμάται η επίδραση των διαφόρων αλγορίθμων στην απόδοση και τη συμπεριφορά των δικτύων. / This research examines closely the important issue of quality of service, specializing the issue on ATM switches. It examines the algorithms that are applied or used on theoretical level on ATM switches and the way they affect the QoS parameters. For this reason some algorithms are applied on a network simulator and according the network’s behavior we estimate the effect of different algorithms on networks’ performance and behavior.

Η ραγδαία ανάπτυξη του διαδικτύου και των τεχνολογιών που το υποστηρίζουν έχει οδηγήσει στην ραγδαία αύξηση των εφαρμογών διαμοίρασης δεδομένων. Ταυτόχρονα, οι ανάγκες για ταχεία μεταφορά δεδομένων γίνονται ολοένα και μεγαλύτερες. Μία από τις πιο απαιτητικές κατηγορίες εφαρμογών που διανέμουν πληροφορία είναι οι εφαρμογές πολλαπλής αποστολής δεδομένων. Σε αυτές τις εφαρμογές, ένας αποστολέας θέλει να στείλει δεδομένα σε μία ομάδα παραληπτών, οι οποίοι στη γενική περίπτωση είναι γεωγραφικά κατανεμημένοι. Είναι προφανές ότι ο αποστολέας δεν μπορεί να στείλει τα δεδομένα σε όλους τους παραλήπτες ταυτόχρονα, γιατί το έυρος ζώνης που διαθέτει είναι περιορισμένο, ενώ οι παραλήπτες μπορεί να είναι χιλιάδες. Έτσι, υιοθετείται συνήθως η τακτική δημιουργίας ενός δέντρου διανομής, όπου ο αρχικός κόμβος στέλνει σε μερικούς μόνο παραλήπτες, οι οπόιοι προωθούν το μήνυμα στα παιδιά τους κ.ο.κ. Το δέντρο διανομής συνήθως κατασκευάζεται πάνω από ένα δομημένο δίκτυο ομοτίμων (p2p networks) και πιο συγκεκριμένα πάνω από ένα δίκτυο βασισμένο σε Κατανεμημένους Πίνακες Κατακερματισμού (Distributed Hash Tables - DHT). Αυτή η τεχνική, αν και λύνει το πρόβλημα της πολλαπλής αποστολής, αντιμετωπίζει όμως κάποια προβλήματα. Πιο συγκεκριμένα, το δέντρο διανομής είναι στατικό, δηλαδή δεν μπορεί να μεταβληθούν οι συνδέσεις μεταξύ των κόμβων αν αλλάξουν οι συνθήκες του υφιστάμενου δικτύου. Ακόμα, δεν υπάρχει κάποιος έλεγχος για τις δυνατότητες των κόμβων που βρίσκονται στα υψηλότερα επίπεδα του δέντρου. Αυτό έχει σαν αποτέλεσμα το δέντρο να χάνει μεγάλο μέρος από την αποδοτικότητά του. Στα πλαίσια της εργασίας αυτής, μελετάμε τη δημιουργία ενός δυναμικού δέντρου διανομής, το οποίο μπορεί να αναπροσαρμόζεται στις εκάστοτε συνθήκες, αυξάνοντας έτσι σημαντικά τη συνολική αποδοτικότητα. Πιο συγκεκριμένα, η βασική μετρική είναι το εύρος ζώνης που παρατηρούν οι χρήστες κατα τη διάρκεια μιας αποστολής δεδομένων. Παρουσιάζουμε διάφορα στατιστικά στοιχεία που δείχνουν τη δραστική βελτίωση που επιτυγχάνουμε με τη χρήση του συγκεκριμένου αλγορίθμου. Ακόμα, μελετάμε τη δημιουργία ενός δέντρου διανομής που θα εκμεταλλεύεται τη δομή των DHT δίκτύων και θα μπορεί να διανέμει την πληροφορία αξιόπιστα (με χρήση erasure coding τεχνικών) ενώ θα εγγυάται ένα λογαριθμικό μέσο αριθμό βημάτων για την αποστολή των δεδομένων. Ταυτόχρονα, το σύστημα προσπαθεί να ισοκατανείμει το φόρτο προώθησης των μηνυμάτων σε όλους τους κόμβους του δικτύου. Και τα δύο συστήματα έχουν υλοποιηθέι και αξιολογηθεί χρησιμοποιώντας το DHT σύστημα Pastry και την υλοποίησή του σε Java (FreePastry). / The rapid evolution of the Internet and network technologies has led to an equally rapid increase in data dissemination applications. At the same time, the need for quick data transfer increase daily. One of the most demanding categories of information disseminating applications are file sharing applications. In these applications, one transmitter wants to send data to a group of receivers, that are geographically distributed. It is obvious that the transmitter can not send the data to all receivers simultaneously, because his bandwidth is limited , while the receivers may be hundreds or even thousands. Therefore, the most common method is that of the creation of a dissemination tree, where the initial node forwards the information to some recipients and they forward it to their children, etc. The dissemination tree is usually constructed over a peer-to-peer network, and specifically over a Distributed Hash Table (DHT) network. This method, although solves the problem of multicasting, faces some problems. First, the dissemination tree is static, which means that the connections between the nodes can not be rearranged, if the conditions of the underlying network change. Moreover, there is no control over the efficiency of the nodes in the highest levels of the tree. This leads to a significant drop in tree efficiency. In this thesis, we study the creation of a dynamic dissemination tree, which can adapt to the network conditions, thereby increasing the tree performance. Specifically, the basic evaluation metric is the bandwidth that end users perceive. We present evidence that shows the improvement that our algorithm imposes. We also study the creation of a dissemination tree that uses the existing DHT structure to efficiently and reliably (using erasure coding techniques) disseminate information and guarantees a logarithmic number of hops for message delivery. At the same time, the system tries to balance the load among all network nodes. Both systems were implemented and evaluated using the Pastry system and its implementation in Java (FreePastry).

Η οπτική μεταγωγή καταιγισμών (Optical Burst Switching) είναι ένα ελπιδοφόρο παράδειγμα μεταγωγής για την επόμενη γενεά του Διαδικτύου. Ένα βασικό πρόβλημα στα δίκτυα OBS είναι η δρομολόγηση και ο χρονοπρογραμματισμός των καταιγισμών στους συνδέσμους του δικτύου, ώστε να μειωθεί η απώλεια και η καθυστέρηση τους. Εδώ παρουσιάζουμε έναν βασισμένο στην πηγή αλγόριθμο δρομολόγησης και χρονοπρογραμματισμού πολλαπλών κριτηρίων για την επιλογή μονοπατιών (διαδρομών) που ακολουθούνται από τους καταιγισμούς. Ο αλγόριθμος επιπλέον υπολογίζει και το χρόνο στον οποίο πρέπει να αρχίσει η μετάδοση των καταιγισμών ώστε να φθάσουν στον προορισμό με την ελάχιστη καθυστέρηση. Τα διαγράμματα χρησιμοποίησης (utilization profiles) των συνδέσμων του δικτύου, η καθυστέρηση διάδοσης των συνδέσμων και οι παράμετροι των καταιγισμών (μέγεθος, offset time κ.α.) διαμορφώνουν τα δεδομένα εισόδου του αλγορίθμου. Το προτεινόμενο σχήμα εκμεταλλεύεται τα κενά (void filling) που προκύπτουν από τη χρήση του bandwidth σε κάθε σύνδεσμο ώστε να βρεθεί η καλύτερη διαθέσιμη διαδρομή. Όταν δεν υπάρχει καμία κατάλληλη διαδρομή τη χρονική στιγμή που ζητείται από τον καταιγισμό, ο αλγόριθμος καθορίζει επίσης το χρονικό διάστημα (Time Offset) που πρέπει να καθυστερήσουμε τον καταιγισμό στην πηγή έως ότου γίνει διαθέσιμη η καλύτερη δυνατή διαδρομή. / Optical burst switching (OBS) is considered a promising switching paradigm for the next generation Internet. A key problem in OBS networks is the routing and scheduling of the bursts on the network links, so as to reduce burst loss and delay. In this paper we present a source-based multicost routing and scheduling algorithm to select the paths to be followed by the bursts and the times when the bursts should start transmission from their source so as to arrive at their destination with minimum delay. The utilization profiles of the network links, the link propagation delays, and the parameters of the bursts that have to be scheduled form the inputs to the algorithm. The proposed scheme exploits gaps in capacity utilization so as to find the best available path. When there is no suitable path at the time it is requested, the algorithm also determines the amount of time the burst must be delayed at the source for the best path to become available.

Πολλά συστήματα πολλαπλών διαμεσολαβητών είναι εμπνευσμένα από διάφορες κοινωνίες εντόμων, τα οποία συλλογικά πετυχαίνουν διάφορους στόχους οι οποίοι είναι αδύνατο να επιτευχθούν σε ατομικό επίπεδο. Στις περισσότερες περιπτώσεις, κινητήρια δύναμη στην «συνεργασία» και τη συλλογικότητα των εντόμων είναι η στιγματική συμπεριφορά (stigmergy). Ο όρος αυτός χρησιμοποιείται στη βιολογία για να περιγράψει τον τρόπο επίδρασης αλλαγών στο περιβάλλον που προέκυψαν από μια παρελθοντική συμπεριφορά κάποιων κοινωνικών εντόμων στην συμπεριφορά ατόμων της ίδιας ομάδας. Χαρακτηριστικά παραδείγματα από τη φύση βρίσκουμε σε κάποια είδη μυρμηγκιών με τον τρόπο αναζήτησης τροφής και τη δημιουργία διαδρομών μεταξύ φωλιάς και πηγών τροφής ή την κατασκευαστική διαδικασία των τερμιτών. Αν και η έννοια αυτή είναι άρρητα συνδεδεμένη με την έκκριση μιας η περισσοτέρων χημικών ουσιών (στίγματα) για την έμμεση επικοινωνία μεταξύ ατόμων μιας κοινωνίας εντόμων, έχει εφαρμοστεί σε διαφορετικούς τομείς της επιστήμης των υπολογιστών. Αν και ένα μέρος του κλάδου της τεχνητής ζωής ασχολείται με μια ένα- προς -ένα αντιστοίχηση του έμμεσου αυτού τρόπου επικοινωνίας σε ομάδες ρομπότ που λειτουργούν στον πραγματικό κόσμο με την έκκριση κάποιας αντίστοιχης ουσίας, μεγάλο επιστημονικό ενδιαφέρον υπάρχει για την αναγωγή της έννοιας και της λειτουργίας της στιγματικής συμπεριφοράς στον ψηφιακό κόσμο: Η έννοια των ψηφιακών φερορμονών ή των στιγματικών πακέτων συναντάται, κυρίως σε αντίστοιχους αλγορίθμους δρομολόγησης πακέτων σε ένα δίκτυο κόμβων. Όσο αφορά στην ένα -προς- ένα αντιστοίχηση μηχανισμών σε συστήματα διαμεσολαβητών που λειτουργούν αναλογικά (αισθητήρες) στον πραγματικό κόσμο υπάρχουν περιπτώσεις όπου ενώ ένας στιγματικός μηχανισμός που εμφανίζεται στη φύση φαινομενικά βοηθά στην αντιμετώπιση του προβλήματος που το σύστημα καλείται να αντιμετωπίσει. Η υλοποίηση όμως ενός τέτοιου μηχανισμού μπορεί να είναι ανέφικτη λόγω τεχνικών ή / και οικονομικών λόγων. Ένας προτεινόμενος τρόπος αντιμετώπισης του προβλήματος αυτού είναι η αντιστοίχηση (προσέγγιση) ενός τέτοιου μηχανισμού με ένα μηχανισμό επικοινωνίας ο οποίος θα προσφέρει αντίστοιχα αποτελέσματα χωρίς επιπλέον ή με το μικρότερο κόστος. Για το σκοπό αυτό μπορεί να γίνει χρήση της τεχνολογίας μεταφοράς αναλογικών (π.χ ήχος, φως) ή ψηφιακών σημάτων (π.χ πακέτα δεδομένων). Πόσο στιγματικός όμως είναι μια ένας τρόπος επικοινωνίας μέσω μηνυμάτων, και ποιες είναι οι παραδοχές για κάτι τέτοιο; Μπορεί να υπάρξει αντιστοίχηση της επικοινωνίας (μέσω φερορμονών) που εμφανίζεται στη φύση με κάποιο τρόπο (ασύρματης) επικοινωνίας ο οποίος να μπορεί να εφαρμοστεί σε διαμεσολαβητές περιορισμένων δυνατοτήτων? Η αντιστοίχηση μπορεί να αξιολογηθεί με ποιοτικά κριτήρια όπως η εμφάνιση ή όχι μιας επιθυμητής συμπεριφοράς του συστήματος. Στη διπλωματική αυτή διατριβή παρουσιάζεται ένα μοντέλο ψηφιακής επικοινωνίας το οποίο θεωρητικά αντιστοιχεί στην ποιοτική στιγματική συμπεριφορά ενός συστήματος διαμεσολαβητών. Επιπλέον, εισάγονται δυο μετρήσιμα κριτήρια αξιολόγησης βάση των οποίων μπορεί να γίνει σύγκριση διαφορετικών τρόπων επικοινωνίας. Τα κριτήρια αυτά προκύπτουν από τη μοντελοποίηση μιας κοινής πλατφόρμας – συστήματος διαμεσολαβητών για ένα συγκεκριμένο σενάριο λειτουργίας. Αφού πραγματοποιήθηκαν τρεις σειρές εξομοιώσεων, προέκυψε ότι το σύστημα με χρήση ψηφιακής επικοινωνίας μπορεί να επιτύχει αυτοοργανωτική συμπεριφορά αντίστοιχη με τη συμπεριφορά όταν χρησιμοποιείται στιγματική επικοινωνία ή καμία επικοινωνία. Παρόλα αυτά, η απόδοση του συστήματος βάση των κριτηρίων αξιολόγησης δεν ήταν καλύτερη για τις περισσότερες εξομοιώσεις, κάτι που δεν ήταν θεωρητικά αναμενόμενο. Τέλος, τα αποτελέσματα των εξομοιώσεων οδηγούν σε διάφορα συμπεράσματα τα οποία πρέπει να λαμβάνονται υπόψη στη μελέτη τέτοιων συστημάτων. / Multiagent systems are inspired from insect societies, which collectively achieve different targets, each of is impossible to complete by an individual. In most cases, the driving force to insect “cooperation” and collectiveness is stigmergic behavior. This concept is used in biology to describe the way that environmental changes that occur as a result of a behavior of some social insects, affects the behavior of individuals of the same species. A prominent nature –based example is found in some ant species, where individuals use pheromones during food acquisition, creating different routes between the nest and several food sources. Another example is the termite nest building process. Stigmergy is associated to the emission of one or several chemical substances (stigmata), so as to achieve forms of indirect communication between individuals of a society, although, this concept has been used in different sections of the Computer Science. While much effort is done from the Artificial Life discipline to achieve a one-to-one equivalence of this indirect form of communication into groups of robots that operate in the real world by emitting a pheromone-alike substance, there is much interest in converting this stigmergic behavior to the digital world. The concept of digital pheromones (or stigmergic packets) is met in relative network routing algorithms. Staying on the one-to-one equivalence, there are cases and situations where a proposed stigmergic mechanism can be applied in a multiagent system, where each individual is operating using sensors and actuators inside the real world. However, the implementation of such a mechanism may be unfeasible because of technical, technological or economic reasons. A suggestion to counterattack this limitation is to approximate the stigmergic solution using a different communication mechanism, which may combine feasible, low cost implementation with corresponding to the stigmergic mechanism results. To achieve that, analog (eg light, sound) or digital (data packets) signals may be used. The question is, by using these new concepts, the mechanism of communication is classified as stigmergic and, if yes, are there any admissions? Is there any digital communication analog to the stigmergic communication which may be used to robotic and limited agents? This hypothetical equivalent can be evaluated using qualitative measures like the relevance (or absence) of a desired system behavior In this master thesis, I use a digital communication model which is theoretically assumed to be relative to the quantitative stigmergic behavior of a multiagent system. Additionally, two measurable evaluation criteria are introduced. By using these criteria, different mechanisms of communication may be compared to each other. These criteria result from the modeling of the common platform-multiagent system for a particular scenario of operation. By performing three different series of simulation, there was demonstrated that by using digital communication, the system achieves self organizing behavior relative to the behavior of the same system, using stigmergic or no form of communication. Still, the system performance (according to the introduced evaluation criteria) was not better for most cases of simulations, as it may be expected. Finally, the results lead to several conclusions that must be taken under consideration and further attention for the study of swarm intelligence based systems.

Στα πλαίσια της συγκεκριμένης μεταπτυχιακής εργασίας εξετάζονται διάφορες τεχνικές βελτίωσης των modems που χρησιμοποιούνται στους δέκτες των xDSL συστημάτων, προκειμένου να επιτευχθεί μεγιστοποίηση της ταχύτητας μετάδοσης. Τα xDSL συστήματα είναι συστήματα που χρησιμοποιούν διαμόρφωση πολλαπλών φερουσών (Discrete Multitone – DMT). Η συμβατική μορφή ισοστάθμισης που απαντάται στα συστήματα αυτά, αποτελείται από έναν ισοσταθμιστή Τ-συντελεστών (Τ-tap) που ενεργεί στο πεδίο του χρόνου (TEQ) ακολουθούμενο από Ν ισοσταθμιστές 1-tap που δρουν στο πεδίο της συχνότητας (FEQ) σε κάθε τόνο ξεχωριστά. Η πρόταση που εξετάζεται σε αυτή τη διπλωματική εργασία είναι η μεταφορά του ισοσταθμιστή από το πεδίο του χρόνου στο πεδίο της συχνότητας και ο κατάλληλος συνδυασμός του με τον FEQ. Επομένως, θα προκύψει ένα σύστημα που θα αποτελείται από Ν παράλληλους ισοσταθμιστές T-tap ο κάθε ένας από τους οποίους θα λειτουργεί σε κάθε τόνο ξεχωριστά (Ισοστάθμιση ανά τόνο – PTEQ) . Με τον τρόπο αυτό επιτυγχάνεται η μεγιστοποίηση του ρυθμού μετάδοσης και ελαττώνεται η ευαισθησία του δέκτη στις παραμέτρους του καναλιού. Τα δύο προαναφερθέντα μοντέλα ισοστάθμισης, ο βέλτιστος PTEQ (MMSE PTEQ) και ο συνδυασμός ΤΕQ/FEQ συγκρίνονται μεταξύ τους. Ο βέλτιστος PTEQ παρουσιάζει μεγάλη πολυπλοκότητα κατά τον υπολογισμό των συντελεστών του. Για να γίνει αποδοτικά η αξιοποίηση των θετικών του στοιχείων, εξετάζονται διάφοροι προσαρμοστικοί τρόποι υπολογισμού του, με χρήση των αλγορίθμων RLS και LMS κατάλληλα ενταγμένων στο MMSE σύστημα. / This postgraduate thesis is about improvement techniques for modems which are used at the xDSL systems’ receivers, in order to maximize bit rate. xDSL systems are using multiple carrier modulation (Discrete Multitone – DMT). The conventional equalization scheme for these systems consists of one T-taps time domain equalizer (TEQ) followed by N 1-tap frequency domain equalizers (FEQ) per tone. In this thesis is proposed a modified scheme where the time domain equalizer is replaced by a frequency domain one, properly combined with the 1-tap FEQs. The resulting structure consists of N T-taps frequency domain equalizers per tone (Per Tone Equalizer – PTEQ). The outcome is a larger bit rate while the per tone receiver has reduced sensitivity to the channel’s parameters. The aforesaid equalization models, the optimal PTEQ (MMSE PTEQ) and the combined TEQ/FEQ, are compared. The optimal PTEQ structure presents great complexity during the calculation of its coefficients. In order to efficiently exploit its advantages, adaptive methods, using RLS and LMS algorithms properly imported at the MMSE system, are examined.

Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση. Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων. Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα, προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης, χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά. Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def- inition of which is: We are given a sequence of tasks that are to be processed on a set of machines. Each task is characterized by its running time and has to be scheduled on a machine, for at least its running time. In addition, there are speedup requests from a subset of tasks. The scheduling algorithm is asked to produce a schedule that minimizes an objective function in par- allel with serving as many as possible speedup requests. The introduction gives a theoretical background concerning scheduling prob- lems and algorithms, with an emphasis on the di_erence between static and dynamic algorithms. The objective of the second chapter, is to study the problem above, in its many variations, with a reference to parameters like the number of the machines, deadlines etc. The result of this study, is the development and the evaluation of two algorithms, using objective functions like makespan, and also some new ones that arise in the essay and their need is analyzed. The thesis closes with a consideration of already known schedul- ing problems and its variants, that have been proved to be NP-complete.

Στη μεταπτυχιακή αυτή εργασίας γίνεται μελέτη και υλοποίηση ενός αλγορίθμου χρονοπρογραμματισμού για μεταγωγέα ΑΤΜ της κατηγορίας αλγορίθμων 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.

Το αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μελέτη της αρχιτεκτονικής των Δικτύων Νέας Γενιάς (Next Generation Networks-NGN) με εστίαση στους μηχανισμούς του Επιπέδου Μετάδοσης και τις Λειτουργίες Τελικού Χρήστη. Συγκεκριμένα, περιγράφεται η αρχιτεκτονική IMS (IP Multimedia Subsystem) με τις αντίστοιχες λειτουργικές συνιστώσες και διεπαφές, ενώ στη συνέχεια παρατίθενται τα βήματα μετάβασης προς δίκτυα και προσβάσεις νέας γενιάς επιλεγμένων μεγάλων τηλεπικοινωνιακών Οργανισμών. Ακολούθως, γίνεται μια συνοπτική αναφορά στις λειτουργίες του επιπέδου μετάδοσης, ελέγχου μεταφοράς και διαχείρισης δικτύου και στη συνέχεια περιγράφεται λεπτομερώς η λειτουργική αρχιτεκτονική των κύριων λειτουργικών οντοτήτων του επιπέδου μετάδοσης (λειτουργίες ελέγχου προσάρτησης δικτύου-NACF, λειτουργίες ελέγχου διαχείρισης φορητότητας-MMCF, λειτουργίες ελέγχου πόρων –RACF, λειτουργίες μετάδοσης κορμού) και τα μοντέλα πληροφόρησης (ένδειξη δέσμευσης, πληροφορία απόκρισης πόρων μετάδοσης κ.α.) των επιμέρους στοιχείων των προαναφερθέντων δομικών οντοτήτων. Σε κάθε δομικό μοντέλο πληροφόρησης υπάρχει αναλυτική παρουσίαση των σημείων αναφοράς και ροών πληροφορίας που εμπλέκονται στη διαχείριση και έλεγχο φορητότητας, προσάρτησης δικτύου, διεργασίας μετάδοσης κορμού και πρόσβασης, αντιστοίχως. Στη συνέχεια, αναλύονται οι λειτουργίες τελικού χρήστη με ειδικότερη αναφορά στις λειτουργίες πύλης δικτύου (CPN) με τα επιμέρους λειτουργικά στοιχεία της, και τα δίκτυα που θα αποτελέσουν τον κορμό πάνω στον οποίο θα στηριχθεί η υλοποίηση της πρόσβασης των δικτύων νέας γενιάς. Πιο συγκεκριμένα, περιγράφονται οι τεχνολογίες πρόσβασης DSL (ADSL, ADSL2 και VDSL2) με τους υποκείμενους περιορισμούς του ρυθμού μετάδοσης (διαφωνία, εξασθένηση), Ethernet (EPON, P2P πάνω από χαλκό και οπτική ίνα), και PON (διασύνδεση P2MP με οπτικό διαμεριστή οπτικής ισχύος, GPON). Τέλος, αναλύονται οι καλωδιακές υποδομές που απαιτούνται για την ανάπτυξη των προσβάσεων νέας γενιάς (εύρος, διάρθρωση, πυκνότητα οπτικών ινών). / The theme of this particular thesis is the study of the Next Generation Networks –NGN architecture focusing on the functionalities of the Transport Stratum and the End User Functions. Specifically, it is described the IMS architecture (IP Multimedia Subsystem) and the related functional components, and then, it is listed the transition steps towards the next generation networks and access of selected Telecommunications Providers. Following, it is briefly outlined the functionalities of transport level, transport control and network management, as well, and subsequently, the functional architecture of the main entities of transport level (network attachment control functions –NACF, Mobility Management and Control Functions- MMCF, Resource and Admission Control Functions- RACF, Transport processing entities) and the information models (event registration reply, resource selection information reply etc) of the aforementioned functional components are being described, in detail. Each structural component is analytically presented with its reference points and information flows that are involved in the management as well as the control of mobility, network admission, transport core and access processing, respectively. Additionally, the end user functions are described, giving weighted reference to the customer premises gateway functions (CGF) and their individual entities, and the networks that will compose the core upon which the implementation of next generation access will be established. That is, different access types are presented such as DSL network (ADSL, ADSL2, VDSL2) with its transfer rate restrictions (i.e. attenuation), Ethernet network (EPON, P2P over copper and optical fiber) and PON (P2MP interconnection using optical power splitter ,GPON). Finally, it is analyzed the cable infrastructure needed for the development of the new generation access (optical fiber rate, structure, density).