A pipeline-based approach for maximal-sized matching scheduling in input-buffered switches

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

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


This letter proposes an innovative pipeline-based maximal-sized matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the timing constraint for arbitration with a maximal matching scheme. In the PMM approach, arbitration operates in a pipelined manner. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides the matching result. The subscheduler can adopt a pre-existing efficient round-robin-based maximal matching algorithm. We show that PMM provides 100% throughput under uniform traffic since it preserves a desynchronization effect of the round-robin pointers as in the preexisting algorithm. In addition, PMM maintains fairness for best-effort traffic due to the round-robin-based arbitration.

Original languageEnglish (US)
Pages (from-to)263-265
Number of pages3
JournalIEEE Communications Letters
Issue number6
StatePublished - Jun 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • Input-buffered switch
  • Maximal-sized matching
  • Pipeline
  • Scheduling


Dive into the research topics of 'A pipeline-based approach for maximal-sized matching scheduling in input-buffered switches'. Together they form a unique fingerprint.

Cite this