%0 Journal Article
%T Fast and Noniterative Scheduling in Input-Queued Switches
%A Kevin F. CHEN
%A Edwin H.-M. SHA
%A S. Q. ZHENG
%J Int'l J. of Communications, Network and System Sciences
%P 185-202
%@ 1913-3723
%D 2009
%I Scientific Research Publishing
%R 10.4236/ijcns.2009.23021
%X Most high-end switches use an input-queued or a combined input- and output-queued architecture. The switch fabrics of these architectures commonly use an iterative scheduling system such as iSLIP. Iterative schedulers are not very scalable and can be slow. We propose a new scheduling algorithm that finds a maximum matching of a modified I/O mapping graph in a single iteration (hence noniterative). Analytically and experimentally, we show that it provides full throughput and incurs very low delay; it is fair and of low complexity; and it outperforms traditional iterative schedulers. We also propose two switch architectures suited for this scheduling scheme and analyze their hardware implementations. The arbiter circuit is simple, implementing only a FIFO queue. Only half as many arbiters for an iterative scheme are needed. The arbiters operate in complete parallel. They work for both architectures and make the hardware implementations sim-ple. The first architecture uses conventional queuing structure and crossbar. The second one uses separate memories for each queue at an input port and a special crossbar. This crossbar is simple and also has a re-duced diameter and distributed structure. We also show that the architectures have good scalability and re-quire almost no speedup.
%K Switch Architecture
%K Switch Fabric
%K Fabric Scheduling
%K SRA
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=468