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.
Maximal scheduling or Longest-Queue-First algorithm are low-complexity alternatives to MW, but they achieve only some fraction of the maximal throughput region. Parallel Iterative Matching @cite_14 and iSLIP @cite_7 were shown to be 50 sufficient conditions on the network topology for throughput-optimality. Those conditions were further analyzed to obtain fractional throughput results about a class of wireless networks by @cite_21 and @cite_27 . These algorithms are generally not throughput-optimal and require multiple rounds of message exchanges between nodes.
@cite_27 @cite_14 @cite_21 @cite_7
2099797040 2126169247 2148282413 37309325
Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50 throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100 throughput. Moreover, in networks in which the σ-Local Pooling conditions hold, GMS achieves σ throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100 throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 × n, GMS is guaranteed to achieve 66 throughput, thereby improving upon the previously known 50 lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. A major challenge in the design and operation of wireless networks is to jointly route packets and schedule transmissions to efficiently share the common spectrum among links in the same area. Due to the lack of central control in wireless networks, these algorithms have to be decentralized. It was recently shown that distributed (greedy) algorithms can usually guarantee only fractional throughput. It was also recently shown that if a set of conditions regarding the network topology (known as Local Pooling) is satisfied, simple distributed maximal weight (greedy) scheduling algorithms achieve 100 throughput. In this paper, we focus on networks in which packets have to undergo multihop routing and derive multihop local pooling conditions for that setting. In networks satisfying these conditions, a backpressure-based joint routing and scheduling algorithm employing maximal weight scheduling achieves 100 throughput. Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this paper, we prove that GMS achieves 100 throughput in all networks with eight nodes or less, under the two-hop interference model. Further, we obtain performance bounds that improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size. A major challenge in the design of wireless networks is the need for distributed scheduling algorithms that will efficiently share the common spectrum. Recently, a few distributed algorithms for networks in which a node can converse with at most a single neighbor at a time have been presented. These algorithms guarantee 50 of the maximum possible throughput. We present the first distributed scheduling framework that guarantees maximum throughput. It is based on a combination of a distributed matching algorithm and an algorithm that compares and merges successive matching solutions. The comparison can be done by a deterministic algorithm or by randomized gossip algorithms. In the latter case, the comparison may be inaccurate. Yet, we show that if the matching and gossip algorithms satisfy simple conditions related to their performance and to the inaccuracy of the comparison (respectively), the framework attains the desired throughput.It is shown that the complexities of our algorithms, that achieve nearly 100 throughput, are comparable to those of the algorithms that achieve 50 throughput. Finally, we discuss extensions to general interference models. Even for such models, the framework provides a simple distributed throughput optimal algorithm.