×

Throughput optimal scheduling policies in networks of constrained queues. (English) Zbl 1316.60138

Summary: This paper considers a fairly general model of constrained queuing networks that allows us to represent both Markov modulated Bernoulli processes arrivals and time-varying service constraints. We derive a set of sufficient conditions for throughput optimality of scheduling policies, which encompass and generalize all the results previously obtained in the field. This leads to the definition of new classes of (non-diagonal) throughput optimal scheduling policies. We prove the stability of queues by extending the traditional Lyapunov drift criterion methodology.

MSC:

60K25 Queueing theory (aspects of probability theory)
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ajmone Marsan, M., Leonardi, E., Mellia, M., Neri, F.: On the stability of isolated and interconnected input-queueing switches under multi-class traffic. IEEE Trans. Inform. Theory 51(3), 1167-1174 (2005) · Zbl 1309.94020 · doi:10.1109/TIT.2004.842562
[2] Chaporkar, P., Kar, K., Sarkar, S.: Throughput Guarantees in Maximal Scheduling in Wireless Networks. In: Allerton Conference on Communication, Control and Computing (2005) · Zbl 1304.94004
[3] Dai, J.G., Lin, W.: Maximum pressure policies in stochastic processing networks. Oper. Res. 53, 197-218 (2005) · Zbl 1165.90359 · doi:10.1287/opre.1040.0170
[4] Dimakis, A., Walrand, J.: Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits. Adv. Appl. Probab. 38(2), 505-521 (2006) · Zbl 1126.60074 · doi:10.1239/aap/1151337082
[5] Eryilmaz, A., Srikant, R., Perkins, J.R.: Stable scheduling policies for fading wireless channels. IEEE/ACM Trans. Networking 13(2), 411-424 (2005) · doi:10.1109/TNET.2004.842226
[6] Giaccone, P., Prabhakar, B., Shah, D.: Randomized-scheduling algorithms for high-aggregate bandwidth switches. IEEE J. Sel. Areas Commun. 21(4), 546-559 (2003) · doi:10.1109/JSAC.2003.810496
[7] Gupta, G., Sanghavi, S., Shroff, N.: Node Weighted Scheduling. ACM SIGMETRICS, 2009, June (2009) · Zbl 1165.90359
[8] Kesslassy, I., Mckeown, N.: Analysis of Scheduling Algorithms that Provide 100 · Zbl 1175.90182
[9] Kushner, H.J.: Stochastic Stability and Control. Academic Press, New York (1967) · Zbl 0244.93065
[10] Leonardi, E.: Throughput Optimal Scheduling Policies in Networks of Constrained Queues. Technical report. http://arxiv.org/abs/1304.2554 (2013) · Zbl 1316.60138
[11] Leonardi, E., Mellia, M., Neri, F., Ajmone Marsan, M.: Bounds on delays and queue lengths in input-queued cell switches. J. ACM 50(4), 520-550 (2003) · Zbl 1325.68037 · doi:10.1145/792538.792544
[12] Mekkittikul, A., McKeown, N.: A Practical Scheduling Algorithm to Achieve 100
[13] Meyn, S.: Stability and asymptotic optimality of generalized maxweight policies. J. Control Optim. 47(6), 3259-3294 (2009) · Zbl 1175.90182 · doi:10.1137/06067746X
[14] Meyn, S.P., Tweedie, R.L.: (1993), Markov Chains and Stochastic Stability. Cambridge University Press, Cambridge (Second Edition 2009) · Zbl 0925.60001
[15] Modiano, E., Shah, D., Zussman, G.: Maximizing Throughput in Wireless Networks via Gossiping. ACM SIGMETRICS (2006)
[16] Neely, M.J., Modiano, E., Rohrs, C.E.: Dynamic power allocation and routing for time varying wireless networks. IEEE J. Sel. Areas Commun. 23(1), 89-103 (2005) · doi:10.1109/JSAC.2004.837349
[17] Ross, K., Bambos, N.: Projective cone scheduling (PCS) algorithms for packet switches of maximal throughput. Trans. Networking 17(3), 976-989 (2009) · doi:10.1109/TNET.2008.2002557
[18] Shah, D., Wischik, D. J.: Optimal Scheduling Algorithms for Input-Queued Switches. INFOCOM, April (2006)
[19] Shah, D., Wischik, D.: Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. 22(1), 70-127 (2012) · Zbl 1242.90066
[20] Shah, D., Tsitsiklis, J., Zhong, Y.: Qualitative Properties of \[\alpha\] α-Weighted Scheduling Policies. ACM SIGMETRICS (2010) · Zbl 1304.60102
[21] Tassiulas, L.: Scheduling and performance limits of networks with constantly changing topology. IEEE Trans. Inf. Theory 43(3), 1067-1073 (1997) · Zbl 0878.90065 · doi:10.1109/18.568722
[22] Tassiulas, L.: Linear Complexity Algorithms for Maximum Throughput in Radio Networks and Input Queued Switches. INFOCOM, April (1998)
[23] Tassiulas, L., Ephremides, A.: Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multi-hop radio networks. IEEE Trans. Autom. Control 37, 1936-1948 (1992) · Zbl 0771.60070 · doi:10.1109/9.182479
[24] Wu, X., Srikant, R.: Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks. INFOCOM, April (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.