Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T06:39:26.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Stability and moment bounds under utility-maximising service allocations: Finite and infinite networks

Part of: Computer system organization Special processes

Published online by Cambridge University Press:  15 July 2020

Seva Shneer  and
Alexander Stolyar
Seva Shneer*
Affiliation:
Heriot-Watt University
Alexander Stolyar*
Affiliation:
University of Illinois
*
*Postal address: School of MACS, Heriot-Watt University, Edinburgh, EH14 4AS, United Kingdom. Email: [email protected]
**Postal address: ISE Department and Coordinated Science Lab, University of Illinois at Urbana-Champaign, Urbana, IL 61801. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 stabilitystationary moment boundsutility-maximising service allocationsqueueing networkswireless networkssingle-hop networksmulti-hop networksinfinite networks

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M12: Network protocols
Type
Original Article
Information
Advances in Applied Probability , Volume 52 , Issue 2 , June 2020 , pp. 463 - 490
Copyright
© Applied Probability Trust 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bonald, T. and Massoulie, L. (2001). Impact of fairness on Internet performance. ACM SIGMETRICS Performance Evaluation Rev. 29, 82–91.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Dai, J. G. and Meyn, S. P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Automatic Control 40, 1889–1904.CrossRefGoogle Scholar
De Veciana, G., Konstantopoulos, T. and Lee, T. (2001). Stability and performance analysis of networks supporting elastic services. IEEE/ACM Trans. Networking 9, 2–14.CrossRefGoogle Scholar
Foster, F. G. (1953). On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24, 355–360.CrossRefGoogle Scholar
Jiang, L. and Walrand, J. (2010). A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Trans. Networking 18, 960–972.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking 8, 556–567.10.1109/90.879343CrossRefGoogle Scholar
Roberts, J. and Massoulie, L. (2000). Bandwidth sharing and admission control for elastic traffic. Telecommun. Systems 15, 185–201.Google Scholar
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.Google Scholar
Sankararaman, A., Baccelli, F. and Foss, S. (2018). Interference queueing networks on grids. Preprint. Available at http://arxiv.org/abs/1710.09797.Google Scholar
Shah, D. and Shin, J. (2012). Randomized scheduling algorithm for queueing networks. Ann. Appl. Prob. 22, 128–171.CrossRefGoogle Scholar
Shah, D., Tsitsiklis, J. and Zhong, Y. (2014). Qualitative properties of $\alpha$ -fair policies in bandwidth-sharing networks. Ann. Appl. Prob. 24, 76–113.CrossRefGoogle Scholar
Shneer, S. and Stolyar, A. L. (2018). Stability conditions for a discrete-time decentralised medium access algorithm. Ann. Appl. Prob. 28, 3600–3628.CrossRefGoogle Scholar
Shneer, S. and Stolyar, A. L. (2018). Stability conditions for a decentralised medium access algorithm: single- and multi-hop networks. Submitted.Google Scholar
Stolyar, A. L. (1995). On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. Markov Process. Relat. Fields 1, 491–512.Google Scholar
Stolyar, A. L. (2008). Dynamic distributed scheduling in random access networks. J. Appl. Prob. 45, 297–313.CrossRefGoogle Scholar
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 Control 37, 1936–1948.10.1109/9.182479CrossRefGoogle Scholar
Tweedie, R. (1981). Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes. J. Appl. Prob. 18, 122–130.CrossRefGoogle Scholar