Scheduling in multi-channel wireless networks: rate function optimality in the small-buffer regime

ABSTRACT

We consider the problem of designing scheduling algorithms for the downlink of cellular wireless networks where bandwidth is partitioned into tens to hundreds of parallel channels, each of which can be allocated to a possibly different user in each time slot. We prove that a class of algorithms called Iterated Longest Queues First (iLQF) algorithms achieves the smallest buffer overflow probability in an appropriate large deviations sense. The class of iLQF algorithms is quite different from the class of max-weight policies which have been studied extensively in the literature, and it achieves much better performance in the regimes studied in this paper.

REFERENCES

• 1: 3GPP TR 25.913. Requirements for Evolved UTRA (E-UTRA) and Evolved UTRAN (E-UTRAN). March 2006.
• 2: M. Andrews, K. Kumaran, K. Ramanan, A.L. Stolyar, R. Vijayakumar, and P. Whiting. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Tech. Memo, April 2000.
• 3: S. Bodas, S. Shakkottai, L. Ying, and R. Srikant. Scheduling in multi-channel wireless networks: Rate function optimality in the small-buffer regime. Technical report, The University of Texas at Austin, WNCG, 2009.
• 4: A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Springer-Verlag New York, Inc., second edition, 1998.
• 5: Atilla Eryilmaz , R. Srikant , James R. Perkins, Stable scheduling policies for fading wireless channels, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.411-424, April 2005 [doi>10.1109/TNET.2004.842226]
• 6: WiMax Forum. Mobile WiMAX Part I: A technical overview and performance evaluation. March 2006. White Paper.
• 7: A. Ganti, E. Modiano, and J. Tsitsiklis. Optimal transmission scheduling in symmetric communication models with intermittent connectivity. IEEE Trans. Inform. Theory, 53:998--1008, March 2007.
• 8: S. Kittipiyakul and T. Javidi. Delay-Optimal Server Allocation in Multi-Queue Multi-Server Systems with Time-Varying Connectivities. Technical Report, UCSD, 2008.
• 9: Jon Kleinberg and Èva Tardos. Algorithm Design. Pearson Education, 2006.
• 10: S.P. Meyn. Stability and asymptotic optimality of generalized maxweight policies. SIAM J. Control and Optimization, 2008. to appear.
• 11: M.J. Neely. Delay Analysis for Max Weight Opportunistic Scheduling in Wireless Systems. In Forty-Sixth Annual Allerton Conference On Communication, Control, and Computing, Sep. 2008.
• 12: M.J. Neely, E. Modiano, and C.E. Rohrs. Power and server allocation in a multi-beam satellite with time varying channels. In Proc. IEEE Infocom, volume 3, pages 1451--1460, New York, NY, June 2002.
• 13: S. Shakkottai. Effective capacity and QoS for wireless scheduling. IEEE Trans. Automat. Contr., 53(3):749--761, February 2008.
• 14: S. Shakkottai, R. Srikant, and A. Stolyar. Pathwise optimality of the exponential scheduling rule for wireless channels. Ann. Appl. Prob., 36(4):1021--1045, December 2004.
• 15: S. Shakkottai and A. Stolyar. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. Ann. Math. Statist., 207:185--202, 2002.
• 16: A. Stolyar. MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Prob., 14(1), 2004.
• 17: Alexander L. Stolyar, Large Deviations of Queues Sharing a Randomly Time-Varying Server, Queueing Systems: Theory and Applications, v.59 n.1, p.1-35, May 2008 [doi>10.1007/s11134-008-9072-y]
• 18: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automat. Contr., 4:1936--1948, December 1992.
• 19: L. Tassiulas and A. Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inform. Theory, 39:466--478, March 1993.
• 20: V.J. Venkataramanan and X. Lin. Structural properties of LDP for queue-length based wireless scheduling algorithms. In Proc. Ann. Allerton Conf. Communication, Control and Computing, Monticello, Illinois, September 2007.
• 21: L. Ying, R. Srikant, A. Eryilmaz, and G. Dullerud. A large deviations analysis of scheduling in wireless networks. IEEE Trans. Inform. Theory, 52(11):5088--5098, November 2006.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
delay optimality, large deviations, scheduling algorithm