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

Wentao Weng () and R. Srikant ()
Additional contact information
Wentao Weng: Massachusetts Institute of Technology
R. Srikant: University of Illinois at Urbana-Champaign

Queueing Systems: Theory and Applications, 2022, vol. 100, issue 1, No 9, 135-166

Abstract: Abstract We consider an $$n\times n$$ 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 $$\rho $$ ρ ) simultaneously become large. We devise an algorithm with expected total queue length equal to $$O((n^{5/4}(1-\rho )^{-1})\log \max (1/\rho ,n))$$ O ( ( n 5 / 4 ( 1 - ρ ) - 1 ) log max ( 1 / ρ , n ) ) for large n and $$\rho $$ ρ such that $$(1-\rho )^{-1} \ge n^{3/4}$$ ( 1 - ρ ) - 1 ≥ n 3 / 4 . This result improves the previous best queue length bound in the regime $$n^{3/4}

Keywords: Input-queued switch; Queue-size scaling; Stochastic network; Large systems; 68M20; 60K25; 60C05; 90B15 (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-021-09726-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:100:y:2022:i:1:d:10.1007_s11134-021-09726-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-021-09726-7

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().