Since Tassiulas and Ephremides proposed the maximum weight scheduling algorithm of throughput-optimality for constrained queueing networks in 1992, extensive research efforts have been made for resolving its high complexity issue under various directions. In this paper, we resolve the issue by developing a generic framework for designing throughput-optimal and low-complexity scheduling algorithms. Under the framework, an algorithm updates current schedules via an interaction with a given oracle system that can generate a solution of a certain discrete optimization problem in a finite number of interactive queries. Therefore, one can design a variety of scheduling algorithms under this framework by choosing different oracles, e.g., the exhaustive search (ES), the markov chain monte carlo (MCMC), the belief propagation (BP) and the cutting-plane (CP) algorithms. The complexity of the resulting algorithm is decided by the number of operations required for an oracle processing a single query, which is typically very small. Somewhat surprisingly, we prove that an algorithm using any such oracle is throughput-optimal for general constrained queueing network models that arise in the context of emerging large-scale communication networks. In particular, the pick-and-compare' algorithms developed by Tassiulas in 1998 and recently developed queue-based CSMA algorithms can be also understood as special cases of such algorithms using ES and MCMC oracles, respectively. To our best knowledge, our result is the first that establishes a rigorous connection between iterative optimization methods and low-complexity scheduling algorithms, which we believe provides various future directions and new insights in both areas.
Design and analysis of resource allocation algorithms in constrained queueing networks have been of great interest for last four decades across various research communities, where the contention resolution protocols in multiple-access broadcast channels have been studied since the mid-1970s @cite_23 . The broadcast channels induce a special constraint in resources usages among queues (i.e., every queue contend with all other queues), and simple distributed contention resolution protocols gained much attention in the ages. It is the year 1992 that the seminal work by Tassiulas and Ephremides proposed a throughput-optimal algorithm, referred to as MW, for general resource constraints. Its main appeal is that it does require only information on the current queue lengths (and instantaneous service rates) and does not rely on the knowledge of underlying system parameters. However, as we mentioned earlier, the MW algorithm suffers from the high implementation complexity, and a huge array of subsequent research has been made to develop algorithms with high performance guarantees and low-complexity.
@cite_23
2076915000
The popularity of Aloha-like algorithms for resolution of contention between multiple entities accessing common resources is due to their extreme simplicity and distributed nature. Example applications of such algorithms include Ethernet and recently emerging wireless multi-access networks. Despite a long and exciting history of more than four decades, the question of designing an algorithm that is essentially as simple and distributed as Aloha while being efficient has remained unresolved. In this paper, we resolve this question successfully for a network of queues where contention is modeled through independent-set constraints over the network graph. The work by Tassiulas and Ephremides (1992) suggests that an algorithm that schedules queues so that the summation of weight' of scheduled queues is maximized, subject to constraints, is efficient. However, implementing such an algorithm using Aloha-like mechanism has remained a mystery. We design such an algorithm building upon a Metropolis-Hastings sampling mechanism along with selection of weight' as an appropriate function of the queue-size. The key ingredient in establishing the efficiency of the algorithm is a novel adiabatic-like theorem for the underlying queueing network, which may be of general interest in the context of dynamical systems.