Hostname: page-component-6898cfcb55-w5hgh Total loading time: 0 Render date: 2026-11-11T14:28:42.320Z Has data issue: false hasContentIssue false
  • English
  • Français

Large-scale join-idle-queue system with general service times

Part of:Special processesOperations research and management science

Published online by Cambridge University Press:  30 November 2017

S. Foss and
A. L. Stolyar
S. Foss*
Affiliation:
Heriot-Watt University and Novosibirsk State University
A. L. Stolyar*
Affiliation:
University of Illinois at Urbana-Champaign
*
* Postal address: Department of Actuarial Mathematics and Statistics, Heriot-Watt University, Edinburgh EH14 4AS, UK. Email address: s.foss@hw.ac.uk
** Postal address: Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, 104 S. Mathews Avenue, Office 201C, Urbana, IL 61801, USA. Email address: stolyar@illinois.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → ∞ and the customer input flow rate is λn. Under the condition λ / μ < ½, we prove that, as n → ∞, the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

Keywords

Large-scale service systempull-based load distributionjoin-idle-queueload balancingfluid limitstationary distributionasymptotic optimality

MSC classification

Primary:90B15: Network models, stochastic
Secondary:60K25: Queueing theory

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 4 , December 2017, pp. 995 - 1007
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Badonnel, R. and Burgess, M. (2008). Dynamic pull-based load balancing for autonomic servers. In Network Operations and Management Symposium, NOMS 2008, IEEE, pp. 751–754. Google Scholar
[2] Billingsley, P. (1995). Probability and Measure, 3rd edn. John Wiley, New York. Google Scholar
[3] Bramson, M., Lu, Y. and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems 71, 247–292. Google Scholar
[4] Bramson, M., Lu, Y. and Prabhakar, B. (2013). Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Prob. 23, 1841–1878. Google Scholar
[5] Eschenfeldt, P. and Gamarnik, D. (2015). Join the shortest queue with many servers. The heavy traffic asymptotics. Preprint. Available at https://arxiv.org/abs/1502.00999. Google Scholar
[6] Lu, Y. et al. (2011). Join-idle-queue: a novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68, 1056–1071. Google Scholar
[7] Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12, 1094–1104. Google Scholar
[8] Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H. and Whiting, P. A. (2016). Universality of load balancing schemes on the diffusion scale. J. Appl. Prob. 53, 1111–1124. Google Scholar
[9] Stolyar, A. L. (2015). Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80, 341–361. Google Scholar
[10] Stolyar, A. L. (2017). Large-scale heterogeneous service systems with general packing constraints. Adv. Appl. Prob. 49, 61–83. CrossRefGoogle Scholar
[11] Stolyar, A. L. (2017). Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers. Queueing Systems 85, 31–65. Google Scholar
[12] Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). A queueing system with a choice of the shorter of two queues—an asymptotic approach. Problems Information Transmission 32, 15–27. Google Scholar