Two-Dimensional Round-Robin Schedulers for Packet Switches with Multiple Input Queues

We present a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N x N switch, our scheduler determines which of the queues in the total of N2input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components thereby allowing a very high-speed implementation. © 1994 IEEE