Concurrent round-robin-based dispatching schemes for clos-network switches

Eiji Oki, Zhigang Jing, Roberto Rojas-Cessa, H. Jonathan Chao

Research output: Contribution to journalArticlepeer-review

122 Scopus citations


A Clos-network switch architecture is attractive because of its scalability. Previously proposed implementable dispatching schemes from the first stage to the second stage, such as random dispatching (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 limitation 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 traffic. When the offered load reaches 1.0, the pointers of round-robin arbiters at the first- 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 significant 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/√N, where N is the switch size. This makes CMSD easier to implement than CRRD when the switch size becomes large.

Original languageEnglish (US)
Pages (from-to)830-844
Number of pages15
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2002

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Arbitration
  • Clos-network switch
  • Dispatching
  • Packet switch
  • Throughput


Dive into the research topics of 'Concurrent round-robin-based dispatching schemes for clos-network switches'. Together they form a unique fingerprint.

Cite this