2

A Clos-network switch architecture is attractive because of its scalability. Previously proposed implementable dispatching schemes from the rst stage to the second stage, such as random dis-patching (RD), are not able to achieve high throughput unless the internal bandwidth is expanded. This paper presents two round-robin-based dispatching schemes to overcome the throughput lim-itation of the RD scheme. First, we introduce a concurrent round-robin dispatching (CRRD) scheme for the Clos-network switch. The CRRD scheme provides high switch throughput without expanding internal bandwidth. CRRD implementation is very simple because only simple round-robin arbiters are adopted. We show via simulation that CRRD achieves 100 % throughput under uniform traÆc. When the oered load reaches 1.0, the pointers of round-robin arbiters at the rst-stage and second-stage modules are completely desynchronized and contention is avoided. Second, we introduce a concurrent master-slave round-robin dispatching (CMSD) scheme as an improved version of CRRD to make it more scalable. CMSD uses hierarchical round-robin arbitration. We show that CMSD preserves the advantages of CRRD, reduces the scheduling time by 30 % or more when arbitration time is signicant, and has a dramatically reduced number of crosspoints of the interconnection wires between round-robin arbiters in the dispatching scheduler with a ratio of 1