Asymptotics of insensitive load balancing and blocking phases

Matthieu Jonckheere () and Balakrishna J. Prabhu ()
Additional contact information
Matthieu Jonckheere: Universidad de Buenos Aires and Conicet
Balakrishna J. Prabhu: Université de Toulouse, CNRS

Queueing Systems: Theory and Applications, 2018, vol. 88, issue 3, No 3, 243-278

Abstract: Abstract We study a single class of traffic acting on a symmetric set of processor-sharing queues with finite buffers, and we consider the case where the load scales with the number of servers. We address the problem of giving robust performance bounds based on the study of the asymptotic behaviour of the insensitive load balancing schemes, which have the desirable property that the stationary distribution of the resulting stochastic network depends on the distribution of job-sizes only through its mean. It was shown for small systems with losses that they give good estimates of performance indicators, generalizing henceforth Erlang formula, whereas optimal policies are already theoretically and computationally out of reach for networks of moderate size. We characterize the response of symmetric systems under those schemes at different scales and show that three amplitudes of deviations can be identified according to whether $$\rho 1$$ ρ > 1 . A central limit scaling takes place for a sub-critical load; for $$\rho =1$$ ρ = 1 , the number of free servers scales like $$n^{ {\theta \over \theta +1}}$$ n θ θ + 1 ( $$\theta $$ θ being the buffer depth and n being the number of servers) and is of order 1 for super-critical loads. This further implies the existence of different phases for the blocking probability. Before a (refined) critical load $$\rho _c(n)=1-a n^{- {\theta \over \theta +1}}$$ ρ c ( n ) = 1 - a n - θ θ + 1 , the blocking is exponentially small and becomes of order $$ n^{- {\theta \over \theta +1}}$$ n - θ θ + 1 at $$\rho _c(n)$$ ρ c ( n ) . This generalizes the well-known quality-and-efficiency-driven regime, or Halfin—Whitt regime, for a one-dimensional queue and leads to a generalized staffing rule for a given target blocking probability.

Keywords: Insensitive load balancing; Blocking phases; Mean-field scalings; QED-Jagerman–Halfin–Whitt regime; 60K25; 60F05; 60F10 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-017-9559-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:88:y:2018:i:3:d:10.1007_s11134-017-9559-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-017-9559-5

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().