text: 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.
  @cite_27: 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.
  @cite_14: Current technology trends make it possible to build communication networks that can support high-performance distributed computing. This paper describes issues in the design of a prototype switch for an arbitrary topology point-to-point network with link speeds of up to 1 Gbit s. The switch deals in fixed-length ATM-style cells, which it can process at a rate of 37 million cells per second. It provides high bandwidth and low latency for datagram traffic. In addition, it supports real-time traffic by providing bandwidth reservations with guaranteed latency bounds. The key to the switch's operation is a technique called parallel iterative matching , which can quickly identify a set of conflict-free cells for transmission in a time slot. Bandwidth reservations are accommodated in the switch by building a fixed schedule for transporting cells from reserved flows across the switch; parallel iterative matching can fill unused slots with datagram traffic. Finally, we note that parallel iterative matching may not allocate bandwidth fairly among flows of datagram traffic. We describe a technique called statistical matching , which can be used to ensure fairness at the switch and to support applications with rapidly changing needs for guaranteed bandwidth.
  @cite_21: In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multi-hop wireless networks. While a lower bound on the throughput performance of GMS is relatively well-known in the simple node-exclusive interference model, it has not been thoroughly explored in the more general K-hop interference model. Moreover, empirical observations suggest that the known bounds are quite loose, and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. First, we show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Second, we show that the worst-case efficiency ratio of GMS in geometric network graphs is between 1 6 and 1 3.
  @cite_7: 
summary: 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.