Εγγυήσεις για ποιότητα εξυπηρέτησης (QoS) σε δίκτυα θα προσφέρονται σύντομα με τη χρήση ουρών και προηγμένης χρονοδρομολόγησης (scheduling). Οι περισσότεροι προηγμένοι αλγόριθμοι χρονοδρομολόγησης στηρίζονται σε ένα κοινό υπολογιστικό μέρος: τις ουρές προτεραιότητας. Μεγάλες ουρές προτεραιότητας φτιάχνονται με δομές δεδομένων όπως οι σωροί (heaps). Για να υποστηρίξουμε προηγμένη χρονοδρομολόγηση σε ρυθμούς OC-192 (10 Gbps) και πάνω, χρήση της τεχνικής της ομοχειρίας (pipelining) απαιτείται για τη διαχείριση της ουράς προτεραιότητας. Παρουσιάζουμε ένα διαχειριστή σωρού (heap) που κάνει χρήση της τεχνικής ομοχειρίας, τον οποίο έχομε σχεδιάσει σαν ένα πυρήνα (core) τοποθετίσιμο (integradable) κυκλώματα ASIC, και τον οποίο έχομε περιγράψει σε μορφή συνθέσιμης (synthesizable) Verilog. Συζητούμε πώς μπορεί να χρησιμοποιηθεί σε switches και routers, τα πλεονεκτήματά του σε σχέση με τις ουρές ημερολογίου (Calendar Queues), και αναλύουμε εναλλακτικές λύσεις για κόστος-απόδοση. Χρησιμοποιώντας δίπορτες και τετραπλού πλάτους μνήμες (SRAM) και οικουμενικά προσπεράσματα (global bypasses), οι εντολές-λειτουργίες μπορούν να ξεκινούν με ρυθμό μίας ανά κύκλο ρολογιού. Όταν μειώνεται το κόστος, ο ρυθμός αποδοχής εντολών ελλατώνεται σε μία ανά κάποιο μικρό αριθμό κύκλων. Το σύστημα μπορεί να τροποποιείται για οποιοδήποτε μέγεθος σωρού και υποστηρίζει έναρξη μιας εντολής ανά κύκλο ρολογιού, εκτός αν έχομε συνεχόμενες εντολές διαγραφής (delete), όπου χρειάζεται ένας κενός (idle) κύκλος ρολογιού για να τις διαχωρίζει. Έχομε επαληθεύσει (verified) το σύστημά μας, συν-προσομοιώνοντάς το με τρία μοντέλα σωρών διαφορετικής πολυπλοκότητας και αφαίρεσης. Έχομε επίσης εκτελέσει synthesis και παρουσιάζομε πληροφορίες για την ανάλυση κόστους.
(EL)
Quality-of-Service (QoS) guarantees in networks will soon be provided using per-flow queueing and sophisticated schedulers. Most advanced scheduling algorithms rely on a common computational primitive: priority queues. Large priority queues are built using calendar queue or heap data structures. To support advanced scheduling at OC-192 (10 Gbps) rates and above, pipelined management of the priority queue is needed. We present a pipelined heap manager that we have designed as a core integratable into ASIC's, in synthesizable Verilog form. We discuss how to use it in switches and routers, its advantages over calendar queues, and we analyze the cost-performance tradeoffs: using 2-port, 4-wide SRAM's and global bypasses, heap operations can be initiated at the rate of one per clock cycle; when reducing these costs, issue rates drop to one every few cycles. Our design can be configured to any heap size, and supports initiating operations on every clock cycle, except that one idle (bubble) cycle is needed between two successive delete operations. We have verified our design by co-simulating it with three heap models of varying abstraction. We have also performed synthesis, and are presenting cost analysis information.
(EN)
