Exhaustive service matching algorithms for input queued switches

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Virtual Output Queuing is widely used by fixed-length high-speed switches to overcome head-of-line blocking. This is done by means of matching algorithms. Maximum matching algorithms have good performance, but their implementation complexity is quite high. Maximal matching algorithms need speedup to guarantee good performance. Iterative matching schemes, such as iSLIP and DRRM, use multiple iterations to converge on a maximal match. The objective of matching algorithms is to reduce the matching overhead for each time slot. In this paper, Exhaustive Service Matching is presented as a way to amortize the cost of a match over multiple time slots, thus significantly improving switch performance. In an Exhaustive Service Matching switch, cells belonging to the same packet are transferred to the output continuously, which leads to good packet delay performance and simplifies the implementation of packet reassembly. To avoid unfairness under some extremely unbalanced traffic pattern, Limited Service Matching and Exhaustive Service Matching with Hamiltonian Walk (EMHW) are presented. We show that Limited Service Matching achieves better fairness under unbalanced traffic patterns, and in some cases improves the delay performance, while retaining low implementation complexity and a scalable architecture. We prove that EMHW is stable under all admissible traffic. All these schemes can be applied to existing matching algorithms, such as iSLIP and DRRM, to achieve high switching efficiency with low implementation complexities.

Original languageEnglish (US)
Title of host publication2004 Workshop on High Performance Switching and Routing, HPSR 2004
Number of pages6
StatePublished - 2004
Event2004 Workshop on High Perfomance Switching and Routing, HPSR 2004 - Phoenix, AZ, United States
Duration: Apr 19 2004Apr 20 2004

Publication series

NameIEEE Workshop on High Performance Switching and Routing, HPSR


Other2004 Workshop on High Perfomance Switching and Routing, HPSR 2004
Country/TerritoryUnited States
CityPhoenix, AZ


  • Exhaustive service
  • Hamiltonian walk
  • Limited service
  • Polling
  • Scheduling
  • Switching
  • Virtual Output Queueing

ASJC Scopus subject areas

  • General Engineering


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

Cite this