Performance of exhaustive matching algorithms for input-queued switches

Yoohwan Kim, H. Jonathan Chao

Research output: Contribution to journalConference articlepeer-review


Virtual output queue (VOQ) architecture is commonly used for avoiding head-of-line blocking in input-queued switches. Many algorithms have been developed for transferring the cells from the VOQs to the output ports. Traditional iterative algorithms such as iSLIP and DRRM, achieve 100% throughput under uniform traffic. But under non-uniform traffic, throughput drops significantly. Recently, a new paradigm of exhaustive matching (EM) has been introduced for handling non-uniform traffic while preserving the complexity of traditional iterative algorithms. In EM, a VOQ is served continuously until it becomes empty. Only the input ports that have finished serving a VOQ look for a new match. This strategy produces very good throughput and delay performance in uniform and non-uniform traffic. However under some traffic patterns, there is a starvation problem when a VOQ occupies an output port for an extended period of time. This problem can be eliminated by providing a priority service for a VOQ that has waited an excessively long time. The resulting algorithm, prioritized EM (PEM), eliminates starvation and achieves very high throughput for many traffic patterns.

Original languageEnglish (US)
Pages (from-to)1817-1822
Number of pages6
JournalIEEE International Conference on Communications
StatePublished - 2003
Event2003 International Conference on Communications (ICC 2003) - Anchorage, AK, United States
Duration: May 11 2003May 15 2003


  • Exhaustive service
  • Matching
  • Scheduling
  • Switch
  • Virtual Output Queueing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Performance of exhaustive matching algorithms for input-queued switches'. Together they form a unique fingerprint.

Cite this