Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 4 (2007) open journal systems 

Martingale proofs of many-server heavy-traffic limits for Markovian queues

Guodong Pang, Columbia University
Rishi Talreja, Columbia University
Ward Whitt, Columbia University

This is an expository review paper illustrating the “martin- gale method” for proving many-server heavy-traffic stochastic-process limits for queueing models, supporting diffusion-process approximations.Careful treatment is given to an elementary model – the classical infinite-server model M/M/∞, but models with finitely many servers and customer abandonment are also treated. The Markovian stochastic process representing the number of customers in the system is constructed in terms of rate-1 Poisson processes in two ways: (i) through random time changes and (ii) through random thinnings. Associated martingale representations are obtained for these constructions by applying, respectively: (i) optional stopping theorems where the random time changes are the stopping times and (ii) the integration theorem associated with random thinning of a counting process. Convergence to the diffusion process limit for the appropriate sequence of scaled queueing processes is obtained by applying the continuous mapping theorem. A key FCLT and a key FWLLN in this framework are established both with and without applying martingales.

AMS 2000 subject classifications: Primary 60F17, 60K25.

Keywords: multiple-server queues,many-server heavy-traffic limits for queues, diffusion approximations, martingales, functional central limit theorems.

Creative Common LOGO

Full Text: PDF

Pang, Guodong, Talreja, Rishi, Whitt, Ward, Martingale proofs of many-server heavy-traffic limits for Markovian queues, Probability Surveys, 4, (2007), 193-267 (electronic). DOI: 10.1214/06-PS091.


[1]   Armony, M. 2005. Dynamic routing in large-scale service systems with heterogeneous servers. Queueing Systems 51, 287–329. MR2189596

[2]   Armony M., I., Gurvich and C. Maglaras. 2006. Cross-selling in a call center with a heterogeneous customer population. Working Paper, New York University, New York, NY, and Columbia University, New York, NY.

[3]   Armony M., I. Gurvich and A. Mandelbaum. 2006. Service level differentiation in call Centers with fully flexible servers. Management Science, forthcoming.

[4]   Atar R. 2005. Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic. Ann. Appl. Probab. 15, 2606-2650. MR2187306

[5]   Atar R., A. Mandelbaum and M. I. Reiman. 2004a. Scheduling a multi-class queue with many exponential servers. Ann. Appl. Probab. 14, 1084-1134. MR2071417

[6]   Atar R., A. Mandelbaum and M. I. Reiman. 2004b. Brownian control problems for queueing systems in the Halfin-Whitt regime. Ann. Appl. Probab. 14, 1084-1134. MR2071417

[7]   Bickel P.J. and M.J. Wichura. 1971. Convergence criteria for multiparameter stochastic processes and some applications. Ann. Math. Statist. 42, 1656–1670. MR0383482

[8]   Billingsley, P. 1968. Convergence of Probability Measures, Wiley (second edition, 1999). MR1700749

[9]   Borovkov, A. A. 1967. On limit laws for service processes in multi-channel systems (in Russian). Siberian Math J. 8, 746–763. MR0222973

[10]   Borovkov, A. A. 1984. Asymptotic Methods in Queueing Theory, Wiley, New York. MR0745620

[11]   Borst, S., A. Mandelbaum and M. I. Reiman. 2004. Dimensioning large call centers. Oper. Res. 52, 17–34. MR2066238

[12]   Brémaud, P. 1981. Point Processes and Queues: Martingale Dynamics, Springer. MR0636252

[13]   Csörgó M. and P. Révéz. 1981. Strong Approximations in Probability and Statistics. Akademiai Kiado.

[14]   Dai J. G. and T. Tezcan. 2005. State space collapse in many server diffusion limits of parallel server systems. Working Paper, Georgia Institute of Technology, Atlanta, GA.

[15]   Dai J. G. and T. Tezcan. 2006. Dynamic control of N systems with many servers: asymptotic optimality of a static priority policy in heavy traffic. Working Paper, Georgia Institute of Technology, Atlanta, GA.

[16]   Dai J. G. and T. Tezcan. 2007. Optimal control of parallel server systems with many servers in heavy traffic. Working Paper, Georgia Institute of Technology, Atlanta, GA.

[17]   Daley, D. J. and D. Vere-Jones. 2003. An Introduction to the Theory of Point Processes, second ed., Springer. MR0950166

[18]   Dupuis, P. and H. Ishii. 1991. On when the solution to the Skorohod problem is Lipschitz continuous with applications. Stochastics 35, 31–62. MR1110990

[19]   Ethier, S. N. and T. G. Kurtz. 1986. Markov Processes; Characterization and Convergence, Wiley. MR0838085

[20]   Gans, N., G. Koole and A. Mandelbaum. 2003. Telephone call centers: tutorial, review and research prospects. Manufacturing Service Oper. Management 5(2), 79–141.

[21]   Garnett, O., A. Mandelbaum and M. I. Reiman. 2002. Designing a call center with impatient customers. Manufacturing Service Oper. Management 4, 208–227.

[22]   Glynn, P. W. and W. Whitt. 1991. A new view of the heavy-traffic limit theorem for the infinite-server queue. Adv. Appl. Prob. 23, 188–209. MR1091098

[23]   Gurvich, I. and W. Whitt. 2007a. Queue-and-idleness-ratio controls in many-server servbice systems. working paper, Columbia University. Available at: http://www.columbia.edu/~ww2040

[24]   Gurvich, I. and W. Whitt. 2007b. Service-level differentiation in many-server service systems: a solution based on fixed-queue-ratio routing. working paper, Columbia University. Available at: http://www.columbia.edu/~ww2040

[25]   Gurvich, I. and W. Whitt. 2007c. Scheduling Flexible Servers with convex delay costs in many-server service systems. Manufacturing and Service Operations Management, forthcoming. Available at: http://www.columbia.edu/~ww2040

[26]   Halfin, S. and W. Whitt. 1981. Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29, 567–588. MR0629195

[27]   Harrison, J. M. and A. Zeevi. 2005. Dynamic scheduling of a multiclass queue in the Halfin and Whitt heavy traffic regime. Oper. Res. 52, 243–257. MR2066399

[28]   Helms, L. L. 1974. Ergodic properties of several interacting Poisson particles. Advances in Math. 12, 32–57. MR0345247

[29]   Iglehart, D. L. 1965. Limit diffusion approximations for the many server queue and the repairman problem. J. Appl. Prob. 2, 429–441. MR0184302

[30]   Jacod, J. and A. N. Shiryayev. 1987. Limit Theorems for Stochastic Processes, Springer. MR0959133

[31]   Jelenković, P., A. Mandelbaum and P. Momčilović. 2004. Heavy traffic limits for queues with many deterministic servers. Queueing Systems 47, 53–69. MR2074672

[32]   Kallenberg, O. 2002. Foundations of Modern Probability, second edition, Springer. MR1876169

[33]   Karatzas, I, and S. Shreve. 1988. Brownian Motion and Stochastic Calculus, Springer. MR0917065

[34]   Kaspi, H. and K. Ramanan. 2007. Law of large numbers limit for many-server queues. Working paper. The Technion and Carnegie Mellon University.

[35]   Khoshnevisan D. 2002. Multiparameter Processes: An Introduction to Random Fields, Springer. MR1914748

[36]   Kogan, Y., R. Sh. Liptser and A. V. Smorodinskii. 1986. Gaussian diffusion approximations of closed Markov models of computer networks. Problems. Inform. Transmission 22, 38–51. MR0838688

[37]   Krichagina, E. V. and A. A. Puhalskii. 1997. A heavy-traffic analysis of a closed queueing system with a GI∕service center. Queueing Systems 25, 235–280. MR1458591

[38]   Kunita, H. and S. Watanabe. 1967. On square-integrble martingales. Nagoya Math. J. 30, 209–245. MR0217856

[39]   Kurtz, T. 1978. Strong approximation theorems for density dependent Markov chains. Stoch. Process Appl. 6, 223–240. MR0464414

[40]   Kurtz, T. 1980. Representations of Markov processes as multiparameter time changes. Ann. Probability 8, 682–715. MR0577310

[41]   Kurtz, T. 2001. Lectures on Stochastic Analysis, Department of Mathematics and Statistics, University of Wisconsin, Madison, WI 53706-1388.

[42]   Lévy, P. 1948. Processus Stochastiques et Mouvement Borownien, Gauthiers-Villars, Paris.

[43]   Lions, P. and A. Sznitman. 1984. Stochastic differential equations with reflecting boundary conditions. Commun. Pure Appl. Math. 37, 511–537. MR0745330

[44]   Liptser, R. Sh. and A. N. Shiryayev. 1989. Theory of Martingales, Kluwer (English translation of 1986 Russian edition).

[45]   Louchard, G. 1988. Large finite population queueing systems. Part I: The infinite server model. Comm. Statist. Stochastic Models 4(3), 473–505. MR0971602

[46]   Mandelbaum, A., W. A. Massey and M. I. Reiman. 1998. Strong approximations for Markovian service networks. Queueing Systems 30, 149–201. MR1663767

[47]   Mandelbaum, A. and G. Pats. 1995. State-dependent queues: approximations and applications. In Stochastic Networks, F. P. Kelly, R. J. Williams (eds.), Institute for Mathematics and its Applications, Vol. 71, Springer, 239–282. MR1381015

[48]   Mandelbaum, A. and G. Pats. 1998. State-dependent stochastic networks. Part I: Approximations and Applications with continuous diffusion limits. Ann. Appl. Prob. 8, 569–646. MR1624965

[49]   Mandelbaum, A. and S. Zeltyn. 2005. The Erlang-A/Palm queue, with applications to call centers. Working paper, The Technion, Haifa, Israel. Available at: http://iew3.technion.ac.il/serveng/ References/references.html

[50]   Massey, W. A. and W. Whitt. 1993. Networks of infinite-server queues with nonstationary Poisson input. Queueing Systems 13, 183–250. MR1218848

[51]   Parthasarathy, K. R. 1967. Probability Measures on Metric Spaces, Academic Press. MR0226684

[52]   Puhalskii, A. A. 1994. On the invariance principle for the first passage time. Math. Oper. Res. 19, 946–954. MR1304631

[53]   Puhalskii, A. A. and M. I. Reiman. 2000. The mutliclass GI∕PH∕N queue in the Halfin-Whitt regime. Adv. Appl. Prob. 32, 564-595. MR1778580

[54]   Rebolledo, R. 1980. Central limit theorems for local martingales. Zeitschrift Wahrscheinlichkeitstheorie verw. Gebiete 51, 269–286. MR0566321

[55]   Reed, J. 2005. The G∕GI∕N queue in the Halfin-Whitt regime. working paper, Georgia Institute of Technology.

[56]   Reed, J. and A. R. Ward. 2007. Approximating the GI∕GI∕1 + GI queue with a nonlinear drift diffusion: hazard-rate scaling in heavy traffic. working paper, Georgia Institute of Technology.

[57]   Robert, P. 2003. Stochastic Networks and Queues, Springer. MR1996883

[58]   Rogers, L. C. G. and D. Williams. 1987. Diffusions, Markov Processes and Martingales, Volume 2: Ito Calculus, Wiley. MR0921238

[59]   Rogers, L. C. G. and D. Williams. 2000. Diffusions, Markov Processes and Martingales, Volume 1: Foundations, Cambridge University Press. MR1796539

[60]   Skorohod, A. V. 1956. Limit theorems for stochastic processes. Prob. Theory Appl. 1, 261–290. MR0084897

[61]   Srikant, R. and W. Whitt. 1996. Simulation run lengths to estimate blocking probabilities. ACM Trans. Modeling Computer Simulations 6, 7–52.

[62]   Stone, C. 1963. Limit theorems for random walks, birth and death processes and diffusion processes. Illinois J. Math. 4, 638–660. MR0158440

[63]   Tezcan T. 2006. Optimal control of distributed parallel server systems under the Halfin and Whitt regime. Working Paper, University of Illinois at Urbana-Champaign. Available at: https://netfiles.uiuc.edu/ ttezcan/www/TolgaTezcansubmittedMOR121906.pdf

[64]   van der Vaart, A. W. 2006. Martingales, Diffusions and Financial Mathematics Lecture Notes, Available at: http://www.math.vu.nl/sto/ onderwijs/mdfm/

[65]   Ward, A. R. and P. W. Glynn. 2003a. A diffusion approximation for a Markovian queue with reneging. Queueing Systems 43, 103–128. MR1957808

[66]   Ward, A. R. and P. W. Glynn. 2003b. Properties of the reflected Ornstein-Uhlenbeck process. Queueing Systems 44, 109–123. MR1993278

[67]   Ward, A. R. and P. W. Glynn. 2005. A diffusion approximation for a GI∕GI∕1 queue with balking or reneging. Queueing Systems 50, 371–400. MR2172907

[68]   Whitt, W. 1982. On the heavy-traffic limit theorem for GI∕G∕ queues. Adv. Appl. Prob. 14, 171–190. MR0644013

[69]   Whitt, W. 2002. Stochastic-Process Limits, Springer. MR1876437

[70]   Whitt, W. 2002a. Internet Supplement to Stochastic-Process Limits, Available at: http://www.columbia.edu/~ww2040/supplement.html

[71]   Whitt, W. 2004. Efficiency-driven heavy-traffic approximations for many-server queues with abandonments. Management Science 50, 1449–1461.

[72]   Whitt, W. 2005. Heavy-traffic limits for the G∕H2*∕n∕m queue. Math. Oper. Res. 30, 1–27. MR2125135

[73]   Whitt, W. 2007. Proofs of the martingale functional central limit theorem. Probability Surveys, forthcoming.

[74]   Zeltyn S. and A. Mandelbaum. 2005. Call centers with impatient customers: many-server asymptotics of the M/M/n+G queue. Queueing Systems 51, 361–402. MR2189598

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787