Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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 ρ< 1 , ρ= 1 , or ρ> 1. A central limit scaling takes place for a sub-critical load; for ρ= 1 , the number of free servers scales like nθθ+1 (θ 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 ρc(n)=1-an-θθ+1, the blocking is exponentially small and becomes of order n-θθ+1 at ρ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. © 2017, Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Asymptotics of insensitive load balancing and blocking phases
Autor:Jonckheere, M.; Prabhu, B.J.
Filiación:Instituto de cálculo, Universidad de Buenos Aires and Conicet, Buenos Aires, Argentina
LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France
Palabras clave:Blocking phases; Insensitive load balancing; Mean-field scalings; QED-Jagerman–Halfin–Whitt regime
Año:2018
Volumen:88
Número:3-4
Página de inicio:243
Página de fin:278
DOI: http://dx.doi.org/10.1007/s11134-017-9559-5
Título revista:Queueing Systems
Título revista abreviado:Queueing Syst.
ISSN:02570130
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02570130_v88_n3-4_p243_Jonckheere

Referencias:

  • Alzer, H., Baricz, A., Functional inequalities for the incomplete gamma function (2012) J. Math. Anal. Appl., 385 (1), pp. 167-178
  • Atar, R., A diffusion regime with nondegenerate slowdown (2012) Oper. Res., 60 (2), pp. 490-500
  • Benäim, M., (1999) Dynamics of stochastic approximation algorithms, , Lecture Notes in Math, Springer, Berlin, Séminaire de Probabilités XXXIII
  • Bonald, T., Jonckheere, M., Proutière, A., Insensitive load balancing (2004) SIGMETRICS Perform. Eval. Rev., 32 (1), pp. 367-377
  • Bonald, T., Massoulié, L., Proutière, A., Virtamo, J., A queueing analysis of max-min fairness, proportional fairness and balanced fairness (2006) Queueing Syst. Theory Appl., 53 (1-2), pp. 65-84
  • Bonald, T., Proutière, A., Insensitive bandwidth sharing in data networks (2003) Queueing Syst. Theory Appl., 44 (1), pp. 69-100
  • Bramson, M., Lu, Y., Prabakhar, B., Asymptotic independence of queues under randomized load balancing (2012) Queueing Syst., 71, pp. 247-292
  • Cover, T.M., Thomas, J.A., (2006) Elements of Information Theory, , Wiley, Hoboken
  • Eschenfeldt, P., Gamarnik, D., (2015) Join the shortest queue with many servers, , In:, The Heavy Traffic Asymptotics
  • Foss, S., Stolyar, A., (2016) Large-scale join-idle-queue system with general service times
  • Graham, C., Chaoticity on path space for a queueing network with selection of the shortest queue among several (2000) J. Appl. Probab., 37 (1), pp. 198-211
  • Halfin, S., Whitt, W., Heavy-traffic limits for queues with many exponential servers (1981) Oper. Res., 29 (3), pp. 567-588
  • Hordijk, A., Insensitive bounds for performance measures. In: Proceedings of the 12th International Teletraffic Congress (ITC 12) (1988) Torino
  • Hordijk, A., Koole, G., On the optimality of the generalized shortest queue policy (1990) Probab. Eng. Inf. Sci., 4 (4), pp. 477-487
  • Hordijk, A., Ridder, A., Insensitive bounds for the stationary distribution of non-reversible Markov chains (1988) J. Appl. Probab., 25 (1), pp. 9-20
  • http://information-technology.web.cern.ch/services/load-balancing-services; Jagerman, D.L., Some properties of the Erlang loss function (1974) Bell Syst. Tech. J., 53 (3), pp. 525-551
  • Janssen, A.J.E.M., Van Leeuwaarden, J.S.H., Zwart, B., Gaussian expansions and bounds for the Poisson distribution applied to the Erlang B formula (2008) Adv. Appl. Probab., 40 (1), pp. 122-143
  • Janssen, A.J.E.M., van Leeuwaarden, J.S.H., Zwart, A.P., Corrected asymptotics for a multi-server queue in the Halfin–Whitt regime (2008) Queueing Syst. Theory Appl., 58 (4), pp. 261-301
  • Janssen, A.J.E.M., van Leeuwaarden, J.S.H., Zwart, A.P., Refining square-root safety staffing by expanding Erlang C (2011) Oper. Res., 59 (6), pp. 1512-1522
  • Jonckheere, M., Insensitive versus efficient dynamic load balancing in networks without blocking (2006) Queueing Syst., 54 (3), pp. 193-202
  • Jonckheere, M., Mairesse, J., Towards an Erlang formula for multiclass networks (2010) Queueing Syst., 66 (1), pp. 53-78
  • Kipnis, C., Landim, C., (2013) Scaling Limits of Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften, , Springer, Berlin
  • Knessl, C., Yao, H., On the finite capacity shortest queue problem (2011) Prog. Appl. Math., 2 (1), pp. 1-34
  • Le Boudec, J.Y., The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points (2013) Netw. Hetegnereous Med., 8 (2), pp. 1529-1540
  • Leino, J., Virtamo, J., Insensitive load balancing in data networks (2006) Comput. Netw., 50 (8), pp. 1059-1068
  • Lu, Y., Xie, Q., Kliot, G., Geller, A., Larus, J.R., Greenberg, A., Join-idle-queue: a novel load balancing algorithm for dynamically scalable web services (2011) Perform. Eval., 68 (11), pp. 1056-1071
  • Maman, S., (2009) Uncertainty in the demand for service: the case of call centers and emergency departments, , Master’s Thesis, Technion, April
  • Mitzenmacher, M., The power of two choices in randomized load balancing. Ph.D (1996) Thesis
  • Mukherjee, D., Borst, S.C., van Leeuwaarden, J.S.H., Whiting, P.A., Universality of load balancing schemes on the diffusion scale (2016) J. Appl. Probab., 53 (4), pp. 1111-1124. , 12
  • Mukhopadhyay, A., Karthik, A., Mazumdar, R.R., Guillemin, F., Mean field and propagation of chaos in multi-class heterogeneous loss models (2015) Perform. Eval., 91, pp. 117-131. , (Special issue: performance 2015)
  • Nemes, G., An explicit formula for the coefficients in Laplace’s method (2013) Constr. Approx., 38 (3), pp. 471-487
  • Pla, V., Virtamo, J., Martinez-Bauset, J., Optimal robust policies for bandwidth allocation and admission control in wireless networks (2008) Comput. Netw., 52 (17), pp. 3258-3272
  • Robert, P., (2003) Stochastic Networks and Queues, , Springer, Berlin
  • Sagitov, S., (2013) Weak Convergence of Probability Measures, , http://www.math.chalmers.se/~serik/WeakConv/C-space.pdf
  • Sparaggis, P.D., Towsley, D., Cassandras, C.G., Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service rates (1993) J. Appl. Probab., 30 (1), pp. 223-236
  • Stolyar, A., (2015) Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
  • Vvedenskaya, N.D., Dobrushin, R.L., Karpelevich, F.I., Queueing system with selection of the shortest of two queues: an asymptotic approach (1996) Probl. Inf. Transm., 32 (1), pp. 15-27
  • Whitt, W., Heavy traffic approximations for service systems with blocking (1984) Bell Syst. Tech. J., 63 (4), pp. 689-708
  • Whittle, P., Partial balance and insensitivity (1985) J. Appl. Probab., 22 (1), pp. 168-176
  • Xie, Q., Dong, X., Lu, Y., Srikant, R., Power of d choices for large-scale bin packing: a loss model (2015) Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS’15, pp. 321-334. , In: ACM, New York

Citas:

---------- APA ----------
Jonckheere, M. & Prabhu, B.J. (2018) . Asymptotics of insensitive load balancing and blocking phases. Queueing Systems, 88(3-4), 243-278.
http://dx.doi.org/10.1007/s11134-017-9559-5
---------- CHICAGO ----------
Jonckheere, M., Prabhu, B.J. "Asymptotics of insensitive load balancing and blocking phases" . Queueing Systems 88, no. 3-4 (2018) : 243-278.
http://dx.doi.org/10.1007/s11134-017-9559-5
---------- MLA ----------
Jonckheere, M., Prabhu, B.J. "Asymptotics of insensitive load balancing and blocking phases" . Queueing Systems, vol. 88, no. 3-4, 2018, pp. 243-278.
http://dx.doi.org/10.1007/s11134-017-9559-5
---------- VANCOUVER ----------
Jonckheere, M., Prabhu, B.J. Asymptotics of insensitive load balancing and blocking phases. Queueing Syst. 2018;88(3-4):243-278.
http://dx.doi.org/10.1007/s11134-017-9559-5