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

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((n^{5 / 4}(1 - ρ) ^{- 1}) log max (1 / ρ, n)) for large n and ρ such that (1 - ρ) ^{- 1}≥ n^{3 / 4}. This result improves the previous best queue length bound in the regime n^{3 / 4}< (1 - ρ) ^{- 1}< n^{7 / 4}. Under same conditions, the algorithm has an amortized time complexity O(n+ (1 - ρ) ²n^{7 / 2}/ log max (1 / ρ, n)). The time complexity becomes O(n) when (1 - ρ) ^{- 1}≥ n^{5 / 4}.