An algorithm for improved delay-scaling in input-queued switches

Wentao Weng, R. Srikant

Research output: Contribution to journalArticlepeer-review


We consider an n× n input-queued switch with uniform Bernoulli traffic and study the delay (or equivalently, the queue length) in the regime where the size of the switch n and the load (denoted by ρ) simultaneously become large. We devise an algorithm with expected total queue length equal to O((n5 / 4(1 - ρ) - 1) log max (1 / ρ, n)) for large n and ρ such that (1 - ρ) - 1≥ n3 / 4. This result improves the previous best queue length bound in the regime n3 / 4< (1 - ρ) - 1< n7 / 4. Under same conditions, the algorithm has an amortized time complexity O(n+ (1 - ρ) 2n7 / 2/ log max (1 / ρ, n)). The time complexity becomes O(n) when (1 - ρ) - 1≥ n5 / 4.

Original languageEnglish (US)
Pages (from-to)135-166
Number of pages32
JournalQueueing Systems
Issue number1-2
StatePublished - Feb 2022


  • Input-queued switch
  • Large systems
  • Queue-size scaling
  • Stochastic network

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics


Dive into the research topics of 'An algorithm for improved delay-scaling in input-queued switches'. Together they form a unique fingerprint.

Cite this