Stability and moment bounds under utility-maximising service allocations: finite and infinite networks. (English) Zbl 1473.60145
Summary: We study networks of interacting queues governed by utility-maximising service-rate allocations in both discrete and continuous time. For finite networks we establish stability and some steady-state moment bounds under natural conditions and rather weak assumptions on utility functions. These results are obtained using direct applications of Lyapunov-Foster-type criteria, and apply to a wide class of systems, including those for which fluid-limit-based approaches are not applicable. We then establish stability and some steady-state moment bounds for two classes of infinite networks, with single-hop and multi-hop message routes. These results are proved by considering the infinite systems as limits of their truncated finite versions. The uniform moment bounds for the finite networks play a key role in these limit transitions.
Keywords:
stochastic stability; stationary moment bounds; utility-maximising service allocations; queueing networks; wireless networks; single-hop networks; multi-hop networks; infinite networksReferences:
| [1] | Bonald, T. and Massoulie, L. (2001). Impact of fairness on Internet performance. ACM SIGMETRICS Performance Evaluation Rev.29, 82-91. |
| [2] | Dai, J. G. (1995). On the positive Harris recurrence for open multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Prob.5, 49-77. · Zbl 0822.60083 |
| [3] | Dai, J. G. and Meyn, S. P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Automatic Control40, 1889-1904. · Zbl 0836.90074 |
| [4] | De Veciana, G., Konstantopoulos, T. and Lee, T. (2001). Stability and performance analysis of networks supporting elastic services. IEEE/ACM Trans. Networking9, 2-14. |
| [5] | Foster, F. G. (1953). On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist.24, 355-360. · Zbl 0051.10601 |
| [6] | Jiang, L. and Walrand, J. (2010). A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Trans. Networking18, 960-972. |
| [7] | Kelly, F. P., Maulloo, A. K. and Tan, D. K. H. (1998). Rate control for communication networks: Shadow prices, proportional fairness and stability. J. Operat. Res. Soc.49, 237-252. · Zbl 1111.90313 |
| [8] | Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking8, 556-567. |
| [9] | Roberts, J. and Massoulie, L. (2000). Bandwidth sharing and admission control for elastic traffic. Telecommun. Systems15, 185-201. · Zbl 1030.68774 |
| [10] | Rybko, A. N. and Stolyar, A. L. (1992). Ergodicity of stochastic processes describing the operation of open queueing networks. Probl. Inf. Transm.28, 199-220. · Zbl 0768.60089 |
| [11] | Sankararaman, A., Baccelli, F. and Foss, S. (2018). Interference queueing networks on grids. Preprint. Available at http://arxiv.org/abs/1710.09797. · Zbl 1442.60104 |
| [12] | Shah, D. and Shin, J. (2012). Randomized scheduling algorithm for queueing networks. Ann. Appl. Prob.22, 128-171. · Zbl 1411.60135 |
| [13] | Shah, D., Tsitsiklis, J. and Zhong, Y. (2014). Qualitative properties of \(\alpha \) -fair policies in bandwidth-sharing networks. Ann. Appl. Prob.24, 76-113. · Zbl 1304.60102 |
| [14] | Shneer, S. and Stolyar, A. L. (2018). Stability conditions for a discrete-time decentralised medium access algorithm. Ann. Appl. Prob.28, 3600-3628. · Zbl 1404.60140 |
| [15] | Shneer, S. and Stolyar, A. L. (2018). Stability conditions for a decentralised medium access algorithm: single- and multi-hop networks. Submitted. · Zbl 1404.60140 |
| [16] | Stolyar, A. L. (1995). On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. Markov Process. Relat. Fields1, 491-512. · Zbl 0902.60079 |
| [17] | Stolyar, A. L. (2008). Dynamic distributed scheduling in random access networks. J. Appl. Prob.45, 297-313. · Zbl 1151.90006 |
| [18] | Tassiulas, L. and Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control37, 1936-1948. · Zbl 0771.60070 |
| [19] | Tweedie, R. (1981). Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes. J. Appl. Prob.18, 122-130. · Zbl 0458.60070 |
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.
