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. Designing scheduling algorithms that work in synergy with TCP is a challenging problem in wireless networks. Extensive research on scheduling algorithms has focused on inelastic traffic, where there is no correlation between traffic dynamics and scheduling decisions. In this work, we study the performance of several scheduling algorithms in LTE networks, where the scheduling decisions are intertwined with wireless channel fluctuations to improve the system throughput. We use ns-3 simulations to study the performance of several scheduling algorithms with a specific focus on Max Weight (MW) schedulers with both UDP and TCP traffic, while considering the detailed behavior of OFDMA-based resource allocation in LTE networks. We show that, contrary to its performance with inelastic traffic, MW schedulers may not perform well in LTE networks in the presence of TCP traffic, as they are agnostic to the TCP congestion control mechanism. We then design a new scheduler called “Queue MW” (Q-MW) which is tailored specifically to TCP dynamics by giving higher priority to TCP flows whose queue at the base station is very small in order to encourage them to send more data at a faster rate. We have implemented Q-MW in ns-3 and studied its performance in a wide range of network scenarios in terms of queue size at the base station and round-trip delay. Our simulation results show that Q-MW achieves peak and average throughput gains of 37 and 10 compared to MW schedulers if tuned properly. We consider a cognitive radio network where multiple secondary users (SUs) contend for spectrum usage, using random access, over available primary user (PU) channels. Our focus is on SUs' queueing delay performance, for which a systematic understanding is lacking. We take a fluid queue approximation approach to study the steady-state delay performance of SUs, for cases with a single PU channel and multiple PU channels. Using stochastic fluid models, we represent the queue dynamics as Poisson driven stochastic differential equations, and characterize the moments of the SUs' queue lengths accordingly. Since in practical systems, a secondary user would have no knowledge of other users' activities, its contention probability has to be set based on local information. With this observation, we develop adaptive algorithms to find the optimal contention probability that minimizes the mean queue lengths. Moreover, we study the impact of multiple channels and multiple interfaces, on SUs' delay performance. As expected, the use of multiple channels and or multiple interfaces leads to significant delay reduction. We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently served. Whenever a queue is served, the system receives a certain reward. Different rewards are obtained for serving different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing the throughput is no longer equivalent to maximizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.