Staffing many-server systems with admission control and retrials. (English) Zbl 1318.60091

Janssen, A. J. E. M.; van Leeuwaarden, J. S. H.

Adv. Appl. Probab. 47, No. 2, 450-475 (2015).

Summary: In many-server systems it is crucial to staff the right number of servers so that targeted service levels are met. These staffing problems typically lead to constraint satisfaction problems that are difficult to solve. During the last decade, a powerful many-server asymptotic theory has been developed to solve such problems and optimal staffing rules are known to obey the square-root staffing principle. In this paper we develop many-server asymptotics in the so-called quality and efficiency driven regime, and present refinements to many-server asymptotics and square-root staffing for a Markovian queueing model with admission control and retrials.

MSC:

60K25	Queueing theory (aspects of probability theory)
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

many-server systems; QED regime; Halfin-Whitt regime; Markovian queueing model; heavy traffic; diffusion limits; admission control; retrials; square-root staffing; optimality gap

References:

[1]	Abramowitz, M. and Stegun, I. A. (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables . U.S. Government Printing Office, Washington, D.C. · Zbl 0171.38503
[2]	Asmussen, S., Lipsky, L. and Thompson, S. (2014). Failure Recovery in Computing and Data Transmission. In Analytic and Stochastic Modelling Techniques and Applications. (Lecture Notes Comput. Sci. 8499 ). Springer, Berlin, pp. 253-272.
[3]	Asmussen, S. et al. (2008). Asymptotic behavior of total times for jobs that must start over if a failure occurs. Math. Operat. Res. 33 , 932-944. · Zbl 1213.90096
[4]	Bertsekas, D. P. and Gallager, R. (1992). Data Networks , 2nd edn. Prentice Hall, London. · Zbl 0734.68006
[5]	Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation . Cambridge University Press. · Zbl 0617.26001
[6]	Fiorini, P. M., Sheahan, R. and Lipsky, L. (2005). On unreliable computing systems when heavy-tails appear as a result of the recovery procedure. ACM SIGMETRICS Performance Evaluation Rev. 33 , 15-17.
[7]	Jelenković, P. R. and Olvera-Cravioto, M. (2012). Implicit renewal theorem for trees with general weights. Stoch. Process. Appl. 122 , 3209-3238. · Zbl 1258.60040
[8]	Jelenković, P. R. and Skiani, E. D. (2012). Uniform approximation of the distribution for the number of retransmissions of bounded documents. In Proc. 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems , ACM, New York, pp. 101-112. June 2012.
[9]	Jelenković, P. R. and Skiani, E. D. (2012). Distribution of the number of retransmissions of bounded documents. Extended version. Available at http://arxiv.org/abs/1210.8421v1. · Zbl 1337.60253
[10]	Jelenković, P. R. and Tan, J. (2007). Are end-to-end acknowlegements causing power law delays in large multi-hop networks? In 14th Informs Applied Probability Conference , APS, pp. 9-11.
[11]	Jelenković, P. R. and Tan, J. (2007). Can retransmissions of superexponential documents cause subexponential delays? In Proc. 26th IEEE INFOCOM’07 , IEEE, pp. 892-900.
[12]	Jelenković, P. R. and Tan, J. (2007). Is ALOHA causing power law delays? In Managing Traffic Performance in Converged Networks (Lecture Notes Comput. Sci. 4516 ). Springer, Berlin, pp. 1149-1160.
[13]	Jelenković, P. R. and Tan, J. (2008). Dynamic packet fragmentation for wireless channels with failures. In Proc. 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing , ACM, New York, pp. 73-82.
[14]	Jelenković, P. R. and Tan, J. (2009). Stability of finite population ALOHA with variable packets. Preprint. Available at http://arxiv.org/abs/0902.4481v2.
[15]	Jelenković, P. R. and Tan, J. (2010). Modulated branching processes, origins of power laws, and queueing duality. Math. Operat. Res. 35 , 807-829. · Zbl 1221.60120
[16]	Jelenković, P. R. and Tan, J. (2013). Characterizing heavy-tailed distributions induced by retransmissions. Adv. Appl. Prob. 45 , 106-138. Extended version available at http://arxiv.org/pdf/0709.1138.pdf · Zbl 1287.60045
[17]	Nair, J. et al . (2010). File fragmentation over an unreliable channel. In Proc. IEEE INFOCOM’10 , IEEE, pp. 965-973.
[18]	Ross, S. M. (2002). A First Course in Probability , 6th edn. Prentice Hall, Upper Saddle River, NJ. · Zbl 0327.60003
[19]	Sheahan, R., Lipsky, L., Fiorini, P. M. and Asmussen, S. (2006). On the completion time distribution for tasks that must restart from the beginning if a failure occurs. ACM SIGMETRICS Performance Evaluation Rev. 34 , 24-26.
[20]	Tan, J. and Shroff, N. B. (2010). Transition from heavy to light tails in retransmission durations. In Proc. IEEE INFOCOM’10 , IEEE, pp. 1334-1342.