N. McKeown, J. Walrand, and P. Varaiya, “Scheduling cells in an input-queued switch,” IEE Electronics Letters, Vol. 29, No. 25, pp. 2174–2175, December 1993.

has been cited by the following article:

• TITLE: Fast and Noniterative Scheduling in Input-Queued Switches

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

  KEYWORDS: Switch Architecture, Switch Fabric, Fabric Scheduling, SRA

  JOURNAL NAME: International Journal of Communications, Network and System Sciences, Vol.2 No.3, June 21, 2009

  ABSTRACT: 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.