Packet delay-aware scheduling in input queued switches

Yihan Li, Shivendra Panwar, H. Jonathan Chao, Jong Ha Lee

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


Virtual Output Queuing is widely used by high-speed packet switches to overcome head-of-line blocking. This is done by means of matching algorithms. In fixed-length VOQ switches, variable-length IP packets are segmented into fixedlength cells at the inputs. When a cell is transferred to its destination output, it will stay in the reassembly buffer and wait for the other cells of the same packet before the entire packet can depart the system. The delay a packet suffers in the system includes the waiting time in the VOQ, the widely studied cell delay, and the waiting time at the output reassembly buffer, the reassembly delay often ignored in many papers. Among all existing matching algorithms, Maximum Weight Matching (MWM) has the lowest average cell delay. In this paper, we investigate the average packet delay, one of the key performance measure for an input buffered packet switch. A new class of matching algorithms, PDA-MWM, is defined and proved to be stable under all admissible traffic. Three PDA-MWM matching algorithms are studied by simulation. We show that, in order to achieve low packet delay, there is a tradeoff between the cell delay performance and the reassembly delay performance. If both of them are carefully considered, a matching scheme can greatly reduce the packet delay as compared to MWM.

Original languageEnglish (US)
Title of host publicationIEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference
StatePublished - 2006
EventIEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference - San Francisco, CA, United States
Duration: Nov 27 2006Dec 1 2006

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference


OtherIEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference
Country/TerritoryUnited States
CitySan Francisco, CA


  • Delay performance
  • Scheduling
  • Stability
  • Switching
  • Virtual Output Queueing

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Packet delay-aware scheduling in input queued switches'. Together they form a unique fingerprint.

Cite this