Birkhoff-von Neumann input-buffered crossbar switches for guaranteed-rate services. - Cheng-Shang Chang
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(N4.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(N3 log N)
Keywords: Birkhoff-von Neumann input-buffered crossbar switches; N×N switch; Doubly sub-stochastic matrix decomposition; Guaranteed-rate services; Nonuniform traffic; On-line computational complexity; On-line memory complexity; Scheduling algorithm