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

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