PCRRD: a pipeline-based concurrent round-robin dispatching scheme for Clos-network switches

This paper proposes a pipeline-based concurrent round-robin dispatching scheme, called PCRRD, for Clos-network switches. Our previously proposed concurrent round-robin dispatching (CRRD) scheme provides 100% throughput under uniform traffic by using simple round-robin arbiters, but it has the strict timing constraint that the dispatching scheduling has to be completed within one cell time slot. This is a bottleneck in building high-performance switching systems. To relax the strict timing constraint of CRRD, we propose to use more than one scheduler engine, up to P, so called subschedulers. Each subscheduler is allowed to take more than one time slot for dispatching. Every time slot, one out of P subschedulers provides the dispatching result. The subschedulers adopt our original CRRD algorithm. We show that PCRRD preserves 100% throughput under uniform traffic of our original CRRD algorithm, while ensuring the cell-sequence order. Since the constraint of the scheduling timing is dramatically relaxed, it is suitable for high-performance switching systems even when the switch size increases and port speed is high (e.g., 40 Gbit/s).