  Motivated by applications in data center networks, in this paper, we study
the problem of scheduling in an input queued switch. While throughput
maximizing algorithms in a switch are well-understood, delay analysis was
developed only recently. It was recently shown that the well-known MaxWeight
algorithm achieves optimal scaling of mean queue lengths in steady state in the
heavy-traffic regime, and is within a factor less than $2$ of a universal lower
bound. However, MaxWeight is not used in practice because of its high time
complexity. In this paper, we study several low complexity algorithms and show
that their heavy-traffic performance is identical to that of MaxWeight. We
first present a negative result that picking a random schedule does not have
optimal heavy-traffic scaling of queue lengths even under uniform traffic. We
then show that if one picks the best among two matchings or modifies a random
matching even a little, using the so-called flip operation, it leads to
MaxWeight like heavy-traffic performance under uniform traffic. We then focus
on the case of non-uniform traffic and show that a large class of low time
complexity algorithms have the same heavy-traffic performance as MaxWeight, as
long as it is ensured that a MaxWeight matching is picked often enough. We also
briefly discuss the performance of these algorithms in the large scale
heavy-traffic regime when the size of the switch increases simultaneously with
the load. Finally, we perform empirical study on a new algorithm to compare its
performance with some existing algorithms.
