Author(s)

Kevin F. CHEN, Edwin H.-M. SHA, S. Q. ZHENG

Department of Computer Science, University of Texas at Dallas, Richardson, Texas, USA.

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.

Switch Architecture, Switch Fabric, Fabric Scheduling, SRA

K. CHEN, E. SHA and S. ZHENG, "Fast and Noniterative Scheduling in Input-Queued Switches," International Journal of Communications, Network and System Sciences, Vol. 2 No. 3, 2009, pp. 185-202. doi: 10.4236/ijcns.2009.23021.