Linear complexity algorithms for QoS support in input-queued switches with no speedup

We present several fast, practical linear-complexity scheduling algorithms that enable provision of various quality-of-service (QoS) guarantees in an input-queued switch with no speedup. Specifically, our algorithms provide per-virtual-circuit transmission rate and cell delay guarantees using a credit-based bandwidth reservation scheme. Our algorithms also provide approximate max-min-fair sharing of unreserved switch capacity. The novelties of our algorithms derive from judicious choices of edge weights in a bipartite matching problem. The edge weights are certain functions of the amount and waiting times of queued cells and credits received by a virtual circuit. By using a linear-complexity variation of the well-known stable marriage matching algorithm, we present theoretical proofs and demonstrate by simulations that the edge weights are bounded. This implies various QoS guarantees or contracts about bandwidth allocations and cell delays. Network management can then provide these co..