Starvation prevention for arbiters of crossbars with multi-queue input buffers

Crossbars are key components of communication switches used to construct multiprocessor interconnection networks. Multi-queue input buffers have been shown to lead to high performance in such networks by allowing packets at an input port to be processed in non-FIFO order. Symmetric crossbar arbiters efficiently resolve conflicting requests in switches with multi-queue input buffers. While these arbiters lead to excellent performance in terms of throughput and average latency, they do not guarantee fairness. Hence, it is possible for an "unlucky" packet to be left in a switch buffer for a long time, potentially forever, while other packets are forwarded quickly through the switch. This paper introduces and evaluates a technique for preventing such starvation situations. The viability of the technique is demonstrated by implementing it in VLSI. Simulations show that the starvation-free arbiters may outperform arbiters that lack a starvation prevention mechanism for certain nonuniform traffic patterns at a cost of minor performance degradation for uniform traffic.<>