  Ever since Tassiulas and Ephremides (1992) proposed the maximum weight
scheduling algorithm of throughput-optimality for constrained queueing networks
that arise in the context of communication networks, extensive efforts have
been devoted to resolving its most important drawback: high complexity. This
paper proposes a generic framework for designing throughput- optimal and
low-complexity scheduling algorithms for constrained queueing networks. Under
our framework, a scheduling algorithm updates current schedules by interacting
with a given oracle system that generates an approximate solution to a related
optimization task. One can utilize our framework to design a variety of
scheduling algorithms by choosing an oracle system such as random search,
Markov chain, belief propagation, and primal-dual methods. The complexity of
the resulting scheduling algorithm is determined by the number of operations
required for an oracle to process a single query, which is typically small. We
provide sufficient conditions for throughput-optimality of the scheduling
algorithm in general constrained queueing network models. The linear-time
algorithm of Tassiulas (1998) and the random access algorithm of Shah and Shin
(2012) correspond to special cases of our framework using random search and
Markov chain oracles, respectively. Our generic framework, however, provides a
unified proof with milder assumptions.
