Bifurcated Queueing for Throughput Enhancement in Input-Queued Switches

In this letter we propose a bifurcated queueing approach to breaking the well-known 0.586 barrier for the throughput of input queued switches with head-of-line blocking. Each input line maintains a small number k of parallel queues, one for each of a set of k mutually exclusive subsets of the set of output-port addresses. We generalize the analysis of Karol et al. and show that the upper bound on throughput is (1 + k) root 1 + k(2); k = 1, 2, 3, ... . We point out that even for k = 2, there is a significant improvement in throughput and that as k increases, the throughput approaches one.