Paper Info
Title
Backlog-Aware Crossbar Schedulers: A New Algorithm and its Efficient Hardware Implementation
Abstract
Crossbars switches with input queues are the common building blocks of high-speed networks, while their speed and performance critically depend on their scheduler. In this paper we combine ideas from randomized backlog-aware schedulers, and their round-robin (RR) counterparts, to propose a practical, deterministic crossbar scheduler, that: (i) achieves almost full throughput under the many adverse traffic patterns tested, using just 1 Mbyte buffer memory per input, (ii) provides deterministic delay service guarantees, (Hi) yields low delays under both uniform and non-uniform load, and (iv) achieves these performances with a single iteration of an iSLIP-like algorithm. With simple extensions, the proposed crossbar scheduler is shown to distribute the bandwidth of congested links in a fair RR or WRR manner. In order to prove the efficiency of the new scheduling algorithm, we implemented in hardware a 32times32 scheduler, using a novel design for programmable-priority RR arbiters, that is significantly more area-speed efficient than present state-of-the- art. The scheduler's ASIC occupies roughly 3 mm2, when implemented at 130 nm, and gives a new crossbar match every 3.2 ns as needed for above hundred Gb/s line rates, and short packet lengths.
Year
DOI
Venue
2008
10.1109/HOTI.2008.18
Hot Interconnects
Keywords
Field
DocType
deterministic algorithms,scheduling,switching networks,backlog-aware crossbar schedulers,buffer memory,crossbar match,crossbars switches,deterministic crossbar scheduler,deterministic delay service,randomized backlog-aware schedulers,scheduling algorithm,ASIC design,VOQ crossbar scheduler,backlog-aware,deterministic service guarantees,round-robin arbiters
Computer science,Scheduling (computing),Computer network,Throughput,Computer hardware,Crossbar switch,Algorithm design,Parallel computing,Queue,Network packet,Algorithm,Application-specific integrated circuit,Bandwidth (signal processing)
Conference
ISSN
ISBN
Citations 
1550-4794
978-0-7695-3380-3
0
PageRank 
References 
Authors
0.34
7
2
Name
Order
Citations
PageRank
Nikos Chrysos100.34
Giorgos Dimitrakopoulos221527.31