| Περίληψη |
Τα συστήματα μεταγωγέων πακέτων παίζουν κρίσιμο ρόλο στη σχεδίαση δικτύων υψηλών επιδόσεων και για αυτό πρέπει να κατασκευαστούν έτσι ώστε να είναι αποτελεσματικά και χαμηλού κόστους. Οι μεταγωγείς με ουρές αποθήκευσης στις εισόδους, λειτουργούν με μνήμες με ταχύτητα μόλις διπλάσια της ταχύτητας των γραμμών μεταφοράς, επιδεικνύοντας έτσι πολύ καλές ιδιότητες κλιμάκωσης. Εν τούτοις, αυτά τα συστήματα επίσης απαιτούν ένα κεντρικό χρoνοπρογραμματιστή, που θα να επιλέγει, ανά πάσα στιγμή, πακέτα με προορισμούς μη αλληλοσυγκρουόμενους: η πολυπλοκότητα αυτού του χρονοπρογραμματιστή αυξάνει σημαντικά με το μέγεθος του μεταγωγέα. Επιπλέον, είναι ακόμα αμφισβητούμενο αν αυτή η αρχιτεκτονική μπορεί να προσφέρει σύνθετη ποιότητα υπηρεσίας, χωρίς να χρησιμοποιεί υποβαθμισμένα τη χωρητικότητα μετάδοσης του συστήματος. Σε αυτή τη μεταπτυχιακή εργασία, προτείνουμε και αναλύουμε μία αρχιτεκτονική για την τοπολογία crossbar με εσωτερική μνήμη, που ανήκει στην κατηγορία των παραπάνω μεταγωγέων και λύνει το πρόβλημα του εσωτερικού χρονόπρογραμματισμού με τρόπο απλό και αποδοτικό. Χρησιμοποιούμε εσωτερική αποθήκευση στο crossbar, που επιτρέπει σε ξεχωριστούς σε κάθε είσοδο και έξοδο χρόνοπρογραμματιστές, συλλογικά αλλά ταυτόχρονα και ο καθένας αυτόνομα, να επιλέγουν το σύνολο των πακέτων που θα προωθηθούν στις εξόδους. Στο σχήμα που εξετάζουμε σε αυτή την εργασία, οι χρονοπρογραμματιστές στις εισόδους και στις εξόδους υλοποιούν την αρχή της σταθμισμένης-κυκλικής δρομολόγησης (WRR) και ασθενώς συγχρονίζονται, μέσω των σημάτων οπισθοδρομικής πίεσης (backpressure) που διαχειρίζονται την εσωτερική μνήμη. Αυτή η αρχιτεκτονική διακρίνεται από υψηλή, επαναλαμβανόμενη, δομική οργάνωση και απλότητα, που επιτρέπει χαμηλού κόστους, γρήγορη και αποτελεσματική υλοποίηση, κατάλληλη για ένα φάσμα από κλίμακες. Μελετούμε το κατά πόσον η παροχή που διανέμει το προτεινόμενο σύστημα στις "ανταγωνιζόμενες" ροές πλησιάζει την ιδεατή δίκαιη κατανομή του μεγίστου-σταθμισμένου-ελαχίστου (Weighted Max-Min Fairness). Παρέχουμε εκτεταμένες προσομοιώσεις και προκαταρτικές αναλυτικές μαρτυρίες ότι το σύστημα συγκλίνει πολύ κοντά στον προαναφερθέντα στόχο δικαιοσύνης. Επιπρόσθετα, μελετάμε το χρόνο που χρειάζεται το σύστημα για να φτάσει στη κατάσταση ισορροπίας, και τις επιδόσεις παροχής του συστήματος, υπό διαφορετικές υποθέσεις για την φύση της εισερχόμενης κίνησης. Αν και χώρος για ένα μόλις πακέτο θα αρκούσε για την λειτουργικότητα του χρονοπρογραμματισμού, προσομοιώσεις και αναλυτικές ενδείξεις φανερώνουν ότι χώρος 4-5 πακέτων ανά crosspoint, μας επιτρέπει να πλησιάσουμε πολύ κοντά στα προαναφερθέντα χαρακτηριστικά αποτελεσματικότητας, τουλάχιστον για συστήματα μέχρι και 32x32.
|
Δίκαιος χρονοπρογραμματισμός μεγίστου-σταθμισμένου-ελαχίστου, για ένα με ουρές αποθήκευσης στις εισόδους και μικρούς εσωτερικούς ενταμιευτές
