Delay and effective throughput of wireless scheduling in heavy traffic regimes: vacation model for complexity

ABSTRACT

Distributed scheduling algorithms for wireless ad hoc networks have received substantial attention over the last decade. The complexity levels of these algorithms span a wide spectrum, ranging from no message passing to constant/polynomial time complexity, or even exponential complexity. However, by and large it remains open to quantify the impact of message passing complexity on throughput and delay. In this paper, we study the effective throughput and delay performance in wireless scheduling by explicitly considering complexity through a vacation model, where signaling complexity is treated as "vacations" and data transmissions as "services," with a focus on delay analysis in heavy traffic regimes. We analyze delay performance in two regimes of vacation models, depending on the relative lengths of data transmission and vacation periods. State space collapse properties proved here enable a significant dimensionality reduction in the challenging problem of delay characterization. We then explore engineering implications and quantify intuitions based on the heavy traffic analysis.

REFERENCES

• 1: Eitan Altman , Harold J. Kushner, Control of Polling in Presence of Vacations in Heavy Traffic with Applications to Satellite and Mobile Radio Systems, SIAM Journal on Control and Optimization, v.41 n.1, p.217-252, 2002 [doi>10.1137/S0363012999358464]
• 2: Maury Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing Systems: Theory and Applications, v.30 n.1/2, p.89-148, 1998 [doi>10.1023/A:1019160803783]
• 3: P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proceedings of Allerton, 2005.
• 4: H. Chen and W. Whitt. Diffusion approximations for open queueing networks with service interruptions. Queueing Systems, 13:335--359, 1993.
• 5: H. Chen and D. Yao. Fundamentals of Queueing Networks. Springer-Verlag, 2001.
• 6: J.G. Dai. On positive harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Annals of Applied Probability, 5:49--77, 1995.
• 7: J.G. Dai and W. Lin. Asymptotic optimality of maximum pressure policies in stochastic processing networks. Annals of Applied Probability, 18(6):2239--2299, 2008.
• 8: A. Eryilmaz, A. Ozdaglar, and E. Modiano. Polynomial complexity algorithms for full utilization of multi-hop wireless networks. In Proceedings of IEEE Infocom, 2007.
• 9: G.R. Gupta and N. Shroff. Delay analysis of multi-hop wireless networks. In Proceedings of IEEE Infocom, 2009.
• 10: C. Joo and N.B. Shroff. Performance of random access scheduling schemes in multi-hop wireless networks. In Proceedings of IEEE Infocom, 2007.
• 11: K. Jung and D. Shah. Low delay scheduling in wireless network. In Proceeding of ISIT, 2007.
• 12: O. Kella and W. Whitt. Diffusion approximations for queues with server vacations. Advances in Applied Probability, 22:706--729, 1990.
• 13: X. Lin and S. Rasool. Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of IEEE CDC, 2006.
• 14: X. Lin and N.B. Shroff. The impact of imperfect scheduling on cross-layer rate control in wireless networks. In Proceedings of IEEE Infocom, 2005.
• 15: 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
• 16: M.J. Neely, E. Modiano, and C.E. Rohrs. Tradeoffs in delay guarantees and computation complexity for nxn packet switches. In Proceedings of CISS, 2002.
• 17: S. Ray and S. Sarkar. Arbitrary throughput versus complexity tradeoffs in wireless networks using graph partitioning. In Proceedings of Information Theory and Applications Second Workshop, 2007.
• 18: 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
• 19: D. Shah and D.J. Wischik. Optimal scheduling algorithms for input-queued switches. In Proceedings of IEEE Infocom, 2006.
• 20: S. Shakkottai. Effective capacity and qos for wireless scheduling. IEEE Transactions on Automatic Control, 53(3):749--761, 2008.
• 21: S. Shakkottai, R. Srikant, and A. Stolyar. Pathwise optimality of the exponential scheduling rule for wireless channels. Advances in Applied Probability, 36(4):1021--1045, 2004.
• 22: A.L. Stolyar. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals in Applied Probability, 14(1):1--53, 2004.
• 23: A.L. Stolyar. Large deviations of queues under qos scheduling algorithms. In Proceedings of Allerton, 2006.
• 24: L. Tassiulas. Linear complexity algorithms for maximum throughput in radionetworks and input queued switches. In Proceedings of IEEE 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: V.J. Venkataramanan and X. Lin. Structural properties of ldp for queue-length based wireless scheduling algorithms. In Proceedings of Allerton, 2007.
• 27: W. Whitt. Stochastic-Process Limits. Springer-Verlag, 2001.
• 28: R. J. Williams, An invariance principle for semimartingale reflecting Brownian motions in an orthant, Queueing Systems: Theory and Applications, v.30 n.1/2, p.5-25, 1998 [doi>10.1023/A:1019156702875]
• 29: X. Wu and R. Srikant. Bounds on the capacity region of multi-hop wireless networks under distributed greedy scheduling. In Proceedings of IEEE Infocom, 2006.
• 30: Yung Yi , Alexandre Proutière , Mung Chiang, Complexity in wireless scheduling: impact and tradeoffs, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374624]
• 31: L. Ying, R. Srikant, A. Eryilmaz, and G.E. Dullerud. A large deviations analysis of scheduling in wireless networks. IEEE Transactions on Information Theory, 52(11):5088--5098, 2006.

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, heavy-traffic, scheduling, wireless networks