Abstract
Based on a decomposition result by Birkhoff and von Neumann for a doubly substochastic 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 4.5 ) for an N × 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 3 log N).