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.

We study the task of scheduling in a multi-source system where sources report their time-varying information to a central monitoring station via multiple orthogonal channels. The Age-of-Information of a source is defined as the amount of time elapsed since the latest update from that source was received at the monitoring station. At each time instant, the system pays a cost that is a function of the current Ages-of-Information of the sources. Our goal is to design scheduling policies to minimize this cost. We draw a novel parallel between our scheduling problem and the minimum mean cost cycle problem in weighted graphs and use this insight to design optimal scheduling policies for a very general class of cost functions. In addition, we compare the performance of our policy with naive greedy policies. We show that while greedy policies can be optimal if the cost function is symmetric with respect to the sources, our policy strictly outperforms greedy policies when the cost function is asymmetric across sources.