An efficient round-robin algorithm for combined input-crosspoint-queued switches

The combined input-crosspoint-queued (CICQ) crossbar switch is becoming attractive because of the simplicity of scheduling. Although the previously proposed round-robin algorithms achieves 100% throughput asymptotically under unijbrm Bernoulli i.i.d. traffic, these algorithms do not have a satisfactory performance under nonuniform traffic. In this paper, we propose a dual round-robin algorithm for a CICQ switch with one-cell crosspoint buffers. With our algorithm, each input arbiter is associated with dual round-robin pointers. Unlike the previously proposed algorithms, the new algorithm has distinctive round-robin pointer updating rules which are efficient to cope with nonuniform traffic patterns. Extensive simulations show that our algorithm achieves nearly 100% throughput and low average delay under uniform and a broad class of nonuniform traffic patterns.