Achieving stability in networks of input-queued switches using a local online scheduling policy

In recent years, several high-throughput low-delay scheduling algorithms have been designed for input-queued (IQ) switches. It has been shown however that scheduling policies such as maximum weight matching, that perform optimally for an isolated switch, fail to provide stability in a network of IQ switches (M. Andrews and L. Zhang, 2001). Although there exist algorithms that ensure stability in networks of switches (M. Andrews and L. Zhang, 2001) (M. Ajmone Marsan et al., 2003), they are either not fully local or require knowledge/estimation of rates, and are thus not desirable. Here we propose a local and online switch-scheduling algorithm and prove that it achieves stability in a network of single-server switches when arriving traffic is admissible and obeys the strong law of large numbers. We then propose its counterpart for networks of crossbar switches and conjecture that this too is stable. Additionally, we prove that our algorithms provide a max-min fair rate allocation for isolated switches even when arriving traffic is inadmissible. We believe that fairness is key to ensuring stability in networks.