Based on a decomposition result by Birkhoff (1946) and von Neumann (1953) for a doubly sub-stochastic matrix, in this letter we propose a scheduling algorithm that is capable of providing guaranteed-rate services for input-buffered crossbar switches. Our guarantees are uniformly good for all nonuniform traffic. The computational complexity to identify the scheduling algorithm is O(N/sup 4.5/) for an N/spl times/N switch. Once the algorithm is identified, its on-line computational complexity is O(log N) and its on-line memory complexity is O(N/sup 3/ log N).

Previously, we proposed a scheduling algorithm that is capable of providing rate guarantees for input-buffered crossbar switches. The algorithm is based on a decomposition result by Birkhoff (1945) and von Neumann (1953) for a doubly substochastic matrix. An input buffered crossbar switch that uses such an algorithm is called the Birkhoff-von Neumann switch in this paper. For the Birkhoff-von Neumann switch, the rate guarantees are uniformly good for all non-uniform traffic, and it does not require framing or internal speedup. Our objective of this paper is to make the Birkhoff-von Neumann switch more complete and practical. We do so by addressing three topics: providing best-effort services in the Birkhoff-von Neumann switch, hardware implementation of the switch fabric, and multistage Birkhoff-von Neumann switches.