Optimal weighted-delay scheduling in 2×2 input-queued switches

Motivated by few delay-optimal scheduling results, in comparison to results on throughput optimality, we investigate a canonical input-queued switch scheduling problem in which the objective is to minimize the discounted delay cost over an infinite time horizon. We derive an optimal scheduling policy and establish corresponding theoretical properties for the canonical switch, as well as establishing that some of these theoretical results additionally hold for the general switch. Our results provide important fundamental insights of interest to input-queued switches in general and are expected to be of interest more broadly than input-queued switches. Computational experiments demonstrate and quantify the benefits of our optimal scheduling policy over alternative policies such as variants of MaxWeight scheduling, well-known to be throughput optimal and more recently shown to be delay optimal in the heavy-traffic regime limit.