Complexity in wireless scheduling: impact and tradeoffs

ABSTRACT

It has been an important research topic since 1992 to maximize stability region in constrained queueing systems, which includes the study of scheduling over wireless ad hoc networks. In this paper, we propose a framework to study a wide range of existing and future scheduling algorithms and characterize the achieved tradeoffs in stability, delay, and complexity. These characterizations reveal interesting properties hidden in the study of any one or two dimensions in isolation. For example, decreasing complexity from exponential to polynomial, while keeping stability region the same, generally comes at the expense of exponential growth of delays. Investigating trade-offs in the 3-dimensional space allows a designer to fix one dimension and vary the other two jointly. For example, incentives for using scheduling algorithms with only partial throughput-guarantee can be quantified with regards to delay and complexity. Trade-off analysis is then extended to systems with congestion control through utility maximization for non-stabilizable arrival inputs, where the complexity-utility-delay trade-off is shown to be different from the complexity-stability-delay tradeoff. Finally, we analyze more practical models with bounded message size, and consider "effective throughput" which reflects resource occupied by control messages. We show that effective throughput may degrade significantly in certain scheduling algorithms, and suggest a mechanism to avoid this problem in light of the 3D tradeoff framework.

REFERENCES

• 1: P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proc. of Allerton, 2005.
• 2: P. Chaporkar and S. Sarkar. Stable scheduling policies for maximizing throughput in generalized constrained queueing. In Proc. of Infocom, 2006.
• 3: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, Joint optimal congestion control, routing, and scheduling in wireless ad hoc networks, In Proc. of Infocom, 2006.
• 4: A. Eryilmaz, A. Ozdaglar, and E. Modiano. Polynomial complexity algorithms for full utilization of multi-hop wireless networks. In Proc. of Infocom, 2007.
• 5: Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, On the distributed complexity of computing maximal matchings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 25-27, 1998, San Francisco, California, United States
• 6: C. Joo and N. B. Shroff. Performance of random access scheduling schemes in multi-hop wireless networks. In Proc. of Infocom, 2007.
• 7: K. Jung and D. Shah. Low delay scheduling in wireless network. In Proc. of ISIT, 2007.
• 8: A. Kabbani, T. Salonidis, and E. W. Knightly. Distributed low-complexity maximum-throughput scheduling for wireless backhaul networks. In Proc. of Infocom, 2007.
• 9: K. Kar, S. Sarkar, and L. Tassiulas. Achieving proportional fairness using local information in aloha networks. IEEE Transactions on Automatic Control, 49:1858--1863, 2004.
• 10: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, Bounds on delays and queue lengths in input-queued cell switches, Journal of the ACM (JACM), v.50 n.4, p.520-550, July 2003 [doi>10.1145/792538.792544]
• 11: X. Lin and S. Rasool. Constant-time distributed scheduling policies for ad hoc wireless networks. In Proc. of CDC, 2006.
• 12: X. Lin and N. B. Shroff. The impact of imperfect scheduling on cross-layer rate control in wireless networks. In Proc. of Infocom, 2005.
• 13: S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer-Verlag, 1993.
• 14: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 15: M. J. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In Proc. of IEEE INFOCOM, 2005.
• 16: M. J. Neely, E. Modiano, and C. E. Rohrs. Tradeoffs in delay guarantees and computation complexity for nxn packet switches. In Proc. of CISS, 2002.
• 17: M. J. Neely, E. Modiano, and C. E. Rohrs. Dynamic power allocation and routing for time varying wireless networks. In Proc. of Infocom, 2003.
• 18: R. Preis. Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In Proc. of STOC, 1999.
• 19: S. Ray and S. Sarkar. Arbitrary throughput versus complexity tradeoffs in wireless networks using graph partitioning. In Proc. of Information Theory and Applications Second Workshop, 2007.
• 20: Sujay Sanghavi , Loc Bui , R. Srikant, Distributed link scheduling with constant overhead, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 21: S. Sarkar and K. Kar. Achieving 2/3 throughput approximation with sequential maximal scheduling under primary internference constraints. In Proc. of Allerton, 2006.
• 22: D. Shah and M. Kopikare. Delay bounds for approximate maximum weight matching algorithms for input queued switches. In Proc. of Infocom, 2002.
• 23: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 24: L. Tassiulas. Linear complexity algorithms for maximum throughput in radionetworks and input queued switches. In Proc. of Infocom, 1998.
• 25: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936--1949, December 1992.
• 26: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 27: X. Wu and R. Srikant. Bounds on the capacity region of multi-hop wireless networks under distributed greedy scheduling. In Proc. of Infocom, 2006.
• 28: Y. Yi and M. Chiang. Stochastic network utility maximization. European Transactions on Telecommunications, March, 2008.
• 29: Y. Yi and M. Chiang. Wireless scheduling with O(1) complexity for m-hop interference model. In Proc. of ICC, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Performance, Theory

Keywords:
complexity, scheduling, tradeoff, wireless networks