Achieving 100% throughput in an input-queued switch
- 1 January 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 47 (8) , 1260-1267
- https://doi.org/10.1109/26.780463
Abstract
It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to approximately 58%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm.Keywords
This publication has 16 references indexed in Scilit:
- High-performance multiqueue buffers for VLSI communication switchesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Stability of queueing networks and scheduling policiesIEEE Transactions on Automatic Control, 1995
- Scheduling cells in an input-queued switchElectronics Letters, 1993
- Parallel contention resolution control for input queueing ATM switchesElectronics Letters, 1992
- Input and output queueing ATM switch architecture with spatial and temporal slot reservation controlElectronics Letters, 1992
- Optimum architecture for input queuing ATM switchesElectronics Letters, 1991
- Neural network design of a banyan network controllerIEEE Journal on Selected Areas in Communications, 1990
- Queueing in high-performance packet switchingIEEE Journal on Selected Areas in Communications, 1988
- Input Versus Output Queueing on a Space-Division Packet SwitchIEEE Transactions on Communications, 1987
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973