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 cred...

Full description

Bibliographic Details
Published in:	IEEE Journal on selected areas in communications 17, 6 (1999).
Main Author:	Kam, A.C
Format:	Article
Language:	English
Subjects:	QoS guarantees. QoS support. Approximate max-min fair sharing. Bandwidth allocations. Bipartite matching problem. Bounded edge weights. Buffer overflow prevention. Cell delay guarantees. Cell delays. Contracts. Credit-based bandwidth reservation. Credits. Hard guarantees. Input-queued switches. Linear-complexity scheduling algorithms. Minimal buffer requirement. Network management. Output queues. Packet switching. Per-virtual-circuit transmission rate. Performance. Performance bounds. Quality-of-service. Queued cells. Simulations. Soft guarantees. Stable-marriage matching algorithm. Unreserved switch capacity. Upper bounds. Virtual circuit. Waiting times.