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

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}