Dichotomy slot allocation: A QoS guaranteed scheduling algorithm for input-queued switches

Jingjing Zhang, Nirwan Ansari, Yaohui Jin, Weisheng Hu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


With the rapid increase of real-time applications, jitter, delay, and throughput have become the three important QoS criteria in the scheduling of input-queued (IQ) switches with virtual output queues (VOQ). In this paper, we propose a novel frame-based scheduling algorithm, referred to as dichotomy slot allocation (DSA), to achieve high throughput, bounded delay, and bounded jitter. DSA possesses three major characteristics. First, DSA schedules the switch on a per-VOQ basis, and strives to provision QoS guarantees for each traffic stream corresponding to each VOQ. Second, DSA allocates the exact amount of slots to schedule the actual traffic of each VOQ, and decides the time slot for each packet. Third, DSA equally allocates the slots in a frame to each port pair, and then adjusts the scheduling to meet the actual traffic demand. The adjustment process employs a specially designed order named Dichotomy Order to guarantee QoS. Both analysis and simulation results demonstrate that DSA achieves good performance in jitter and throughput.

Original languageEnglish (US)
Article number5409505
Pages (from-to)74-83
Number of pages10
JournalIEEE Systems Journal
Issue number1
StatePublished - Mar 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Dichotomy slot allocation
  • Input-queued switch
  • Jitter
  • QoS
  • Throughput


Dive into the research topics of 'Dichotomy slot allocation: A QoS guaranteed scheduling algorithm for input-queued switches'. Together they form a unique fingerprint.

Cite this