Stability of multi-class queueing systems with state-dependent service rates

ABSTRACT

We examine the stability of multi-class queueing systems with the special feature that the service rates of the various classes depend on the number of users present of each of the classes. As a result, the various classes interact in a complex dynamic fashion. Such models arise in several contexts, especially in wireless networks, as resource sharing algorithms become increasingly elaborate, giving rise to scaling efficiencies and complicated interdependencies among traffic classes. Under certain monotonicity assumptions we provide an exact characterization of stability region. We also discuss how some of the results extend to weaker notions of monotonicity. The results are illustrated for simple examples of wireless networks with two or three interfering base stations.

REFERENCES

• 1: Agrawal, R., Bedekar, A., La, R. J., Subramanian, V. (2001). Class and channel condition based weighted proportional fair scheduler. In: Teletraffic Engineering in the Internet Era, Proc. ITC-17, Salvador da Bahia, eds. J. M. de Souza, N. L. S. da Fonseca, E. A. de Souza e Silva (North-Holland, Amsterdam), 553--565.
• 2: Matthew Andrews , Krishnan Kumaran , Kavita Ramanan , Alexander Stolyar , Rajiv Vijayakumar , Phil Whiting, SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES, Probability in the Engineering and Informational Sciences, v.18 n.2, p.191-217, April 2004 [doi>10.1017/S0269964804182041]
• 3: Armony, M., Bambos, N. (1999). Queueing networks with interacting service resources. In: Proc. 37th Annual Allerton Conf. Commun., Control, Comp., 42--51.
• 4: Bambos, N., Michailidis, G. (2004). Queueing and scheduling in random environments. Adv. Appl. Prob.36, 293--317.
• 5: T. Bonald , S. Borst , N. Hegde , A. Proutiére, Wireless data performance in multi-cell scenarios, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 6: Bonald, T., Borst, S. C., Proutière A. (2005). Inter-cell scheduling in wireless data networks. In: Proc. European Wireless '05 Conf.
• 7: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 8: Bonald, T., Proutière, A. (2006). Flow-level stability of utility-based allocations for non-convex rate regions. In: Proc. CISS 2006 Conf.
• 9: Borst, S. C. (2003). User-level performance of channel-aware scheduling algorithms in wireless data networks. In: Proc. Infocom 2003.
• 10: Sem Borst, User-level performance of channel-aware scheduling algorithms in wireless data networks, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.636-647, June 2005 [doi>10.1109/TNET.2005.850215]
• 11: Borst, S. C., Jonckheere, M. (2006). Flow-level stability of channel-aware scheduling algorithms, In: Proc. WiOpt '06 Conf.
• 12: Borst, S. C., Whiting, P. A. (2003). Dynamic channel-sensitive scheduling algorithms for wireless data throughput optimization. IEEE Trans. Veh. Techn.52, 569--586.
• 13: Chaponniere, E. F., Black, P. J., Holtzman, J. M., Tse, D. N. C. (2002). Transmitter directed code division multiple access system using path diversity to equitably maximize throughput. US Patent 6, 449--490.
• 14: Cohen, J. W. (1984). On a functional relation in three complex variables; three coupled processors. Technical report 359, Mathematical Institute, University of Utrecht.
• 15: Cohen, J. W., Boxma, O. J. (1983). Boundary Value Problems in Queueing System Analysis. (North-Holland Publ. Cy., Amsterdam).
• 16: Fayolle, G., Iasnogorodski, R. (1979). Two coupled processors: the reduction to a Riemann-Hilbert problem. Z. Wahr. verw. Geb.47, 325--351.
• 17: Lin, X., Shroff, N. B. (2005). The impact of imperfect scheduling on cross-layer rate control in wireless networks. In: Proc. Infocom 2005.
• 18: Xin Liu , Edwin K. P. Chong , Ness B. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.451-474, 15 March 2003 [doi>10.1016/S1389-1286(02)00401-2]
• 19: William A. Massey, Stochastic ordering for Markov processes on partially ordered spaces, Mathematics of Operations Research, v.12 n.2, p.350-367, May 1987 [doi>10.1287/moor.12.2.350]
• 20: Meyn, S. P. (1995) Transience of multiclass queuing networks via fluid limit models. Ann. Appl. Prob.5, 946--957.
• 21: Robert, P. (2003). Stochastic Networks and Queues, Stochastic Modelling and Applied Probability Series, Vol. 52, (Springer Verlag, New York).
• 22: Tassiulas, L., Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Aut. Contr.37, 1936--1948.
• 23: Tassiulas, L., Ephremides, A. (1993). Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inf. Theory30, 466--478.
• 24: Tsibonis, V., Georgiadis, L., Tassiulas, L. (2003). Exploiting wireless channel state information for throughput maximization. In: Proc. Infocom 2003.
• 25: Gustavo de Veciana , Takis Konstantopoulos , Tae-Jin Lee, Stability and performance analysis of networks supporting elastic services, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.2-14, Feb., 2001 [doi>10.1109/90.909020]
• 26: Viswanath, P., Tse, D. N. C., Laroia, R. (2002). Opportunistic beamforming using dumb antennas. IEEE Trans. Inf. Theory48, 1277--1294.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Performance

Keywords:
stability, state-dependent service rates, stochastic comparisons