Captured-frame matching schemes for scalable input-queued packet switches

Roberto Rojas-Cessa, Chuan Bi Lin

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Single-stage input-queued (IQ) switches are attractive for implementation of high performance routers because they require no speedup in the used memory. It has been shown that IQ switches can provide 100% throughput under admissible traffic when using maximum-weight matching schemes or iterative maximal-weight matching schemes with a speedup of two or more. These different approaches require either high computation complexity or high memory costs that can make them infeasible. Therefore, there is a need for low-complexity and fast matching schemes that provide high throughput under several admissible traffic patterns, including those with nonuniform distributions, without recurring to speedup nor multiple iterations. In this paper, we introduce the concept of captured frame and apply it to matching schemes. As a result, we propose two weightless matching schemes, one based on round-robin selection, called uFORM, and the other based on random selection, called uFPIM. We analyze the throughput improvement achieved by uFPIM, and show that these matching schemes provide high throughput under a variety of admissible traffic patterns, including those with nonuniform distributions, when using a single iteration and no speedup. Furthermore, we study the scalability of the captured-frame concept in matching schemes for memory-space-memory multiple-stage Clos-network switches, and show the achieved high switching performance and low implementation complexity.

Original languageEnglish (US)
Pages (from-to)2149-2161
Number of pages13
JournalComputer Communications
Issue number10
StatePublished - Jul 31 2007

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


  • Captured frame
  • Frame eligibility
  • Input-queued switch
  • Nonuniform traffic
  • Service frame


Dive into the research topics of 'Captured-frame matching schemes for scalable input-queued packet switches'. Together they form a unique fingerprint.

Cite this