Enhanced Birkhoff–von Neumann decomposition algorithm for input queued switches
J. Li, Nirwan Ansari · IEE Proceedings - Communications · 2001
The enhanced Birkhoff–von Neumann decomposition (EBVND) algorithm, a new class of scheduling arbitrators for input queued (IQ) crossbar switches that is based on the Birkhoff–von Neumann decomposition algorithm, is introduced. Theoretical analysis shows that the performance of EBVND is better than the Birkhoff–von Neumann decomposition algorithm in terms of throughput and cell delay, and can also provide rate and cell delay guarantees. Also, the weighted rate filling algorithm (WRFA), a new algorithm that can be ueed to construct doubly stochastic matrices from doubly substochastic matrices with less complexity and better fairness, is proposed. The wave front Birkhoff–von Neumann decomposition (WFBVND) algorithm and its simplified version WFBVND with logN iterations (WFBVND-logN), the special cases of EBVND, are also introduced and evaluated. Simulations show that the WFBVND and WFBVND-logN algorithms have much lower average cell delay as compared to the Birkhoff–von Neumann decomposition algorithm.