×

Brownian models of multiclass queueing networks: Current status and open problems. (English) Zbl 0781.60090

The problem of heavy traffic approximation by reflected Brownian motion (BM) for open queueing network with \(D\) nodes and \(C\) customer classes is surveyed. The network has Markovian routing, and customers are assumed to switch among classes in Markovian fashion also. It is assumed that external input processes can be correlated and obey some functional central limit theorem with limiting \(C\)-dimensional BM with zero drift. The same is right for cumulative service capacity process, too (with \(D\)- dimensional limiting BM). The relation between BM and heavy traffic theory is discussed. Continuous time workload, queue-size and some other basic processes are introduced for each customer type and the whole network. A natural scaling of time and space is considered. The main scaling factor is the vector of differences between long-time average service rates and traffic intensities for all nodes. Then the Brownian model is defined that approximates scaled system of the mentioned network processes. Heavy traffic convergence is considered. Two numerical examples are presented where complete sojourn time distributions are estimated.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
60J65 Brownian motion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Benes,General Stochastic Processes in the Theory of Queues (Addison-Wesley, Reading, MA, 1963). · Zbl 0125.09802
[2] H. Chen and A. Mandelbaum, Stochastic discrete flow networks: Diffusion approximations and bottlenecks, Ann. Prob. 19(1991) 1463-1519. · Zbl 0757.60094 · doi:10.1214/aop/1176990220
[3] H. Chen and W. Whitt, Diffusion approximations for open queueing networks with server interruptions, submitted. · Zbl 0783.60088
[4] J.G. Dai and J.M. Harrison, Reflected Brownian motion in an orthant: Numerical methods for steady-state analysis, Ann. Appl. Prob. 2 (1992) 65-86. · Zbl 0786.60107 · doi:10.1214/aoap/1177005771
[5] P.W. Glynn, Diffusion approximations, in:Handbook on OR and MS, Vol. 2, eds. D.P. Heyman and M.J. Sobel (Elsevier Science/North-Holland, 1990) pp. l45-198.
[6] B.S. Greenberg, Queueing systems with returning customers and the order of tandem queues, Ph.D. Dissertation, University of California, Berkeley (1986).
[7] S. Halfin and W. Whitt, Heavy traffic limits for queues with many exponential servers, Oper. Res. 29 (1981) 567-588. · Zbl 0455.60079 · doi:10.1287/opre.29.3.567
[8] J.M. Harrison, The diffusion approximation for tandem queues in heavy traffic, Adv. Appl. Prob. 10 (1978) 886-905. · Zbl 0387.60090 · doi:10.2307/1426665
[9] J.M. Harrison,Brownian Motion and Stochastic Flow Systems (Wiley, New York, 1985). · Zbl 0659.60112
[10] J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, in:Stochastic Differential Systems, Stochastic Control Theory and Their Applications, eds. W. Fleming and P.L. Lions, Vol. 10 in the IMA Series on Mathematics and its Applications (Springer, New York, 1988) pp. 147-186.
[11] J.M. Harrison and V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems 6 (1990) 1-32. · Zbl 0702.60082 · doi:10.1007/BF02411463
[12] J.M. Harrison and M.I. Reiman, Reflected Brownian motion on an orthant, Ann. Prob. 9 (1981) 302-308. · Zbl 0462.60073 · doi:10.1214/aop/1176994471
[13] J.M. Harrison and R.J. Williams, Multidimensional reflected Brownian motions having exponential stationary distributions, Ann. Prob. 15 (1987) 115-137. · Zbl 0615.60072 · doi:10.1214/aop/1176992259
[14] J.M. Harrison and R.J. Williams, Brownian models of open queueing networks with homogeneous customer populations, Stochastics 22 (1987) 77-115. · Zbl 0632.60095
[15] J.M. Harrison and R.J. Williams, Brownian models of feedforward queueing networks: Quasireversibility and product-form solution, Ann. Appl. Prob. 2 (1992) 263-293. · Zbl 0753.60071 · doi:10.1214/aoap/1177005704
[16] D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic, I and II, Adv. Appl. Prob. 2 (1970) 150-177 and 355-364. · Zbl 0218.60098 · doi:10.2307/3518347
[17] J.R. Jackson, Networks of waiting lines, Oper. Res. 5 (1957) 518-521. · doi:10.1287/opre.5.4.518
[18] J.R. Jackson, Jobshop-like queueing systems, Manag. Sci. 10 (1963) 131-142. · doi:10.1287/mnsc.10.1.131
[19] D.P. Johnson, Diffusion approximations for optimal filtering of jump processes and for queueing networks, Ph.D. Dissertation, University of Wisconsin, Madison (1983).
[20] O. Kella and W. Whitt, Diffusion approximations for queues with server vacations, Adv. Appl. Prob. 22 (1990) 706-729. · Zbl 0713.60101 · doi:10.2307/1427465
[21] F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
[22] J.F.C. Kingman, The heavy traffic approximation in the theory of queues, in:Congestion Theory, eds. W.L. Smith and W.E. Wilkinson (The University of North Carolina Press, Chapel Hill, 1965) pp. 137-159. · Zbl 0189.51604
[23] P.R. Kumar, Re-entrant lines, Queueing systems 13 (1993), this issue.
[24] W.P. Peterson, Diffusion approximations for networks of queues with multiple customer types, Math. Oper. Res. 16 (1991) 90-118. · Zbl 0727.60114 · doi:10.1287/moor.16.1.90
[25] M.T. Pich, Brownian models of open queueing networks with general station capabilities, Ph.D. Dissertation, Stanford University (1992).
[26] M.I. Reiman, The heavy traffic diffusion approximation for sojourn times in Jackson networks, in:Applied Probability-Computer Science: The Interface, Vol. 2, eds. R.L. Disney and T. Ott (Birkhäuser, Boston, 1982) pp. 409-422.
[27] M.I. Reiman, Open queueing networks in heavy traffic, Math. Oper. Res. 9 (1984) 441-458. · Zbl 0549.90043 · doi:10.1287/moor.9.3.441
[28] M.I. Reiman, A multiclass feedback queue in heavy traffic, Adv. Appl. Prob. 20 (1988) 179-207. · Zbl 0647.60100 · doi:10.2307/1427275
[29] M.I. Reiman and R. Williams, A boundary property of semimartingale reflecting Brownian motions, Prob. Theory Rel. Fields 77 (1988) 87-97. · Zbl 0617.60081 · doi:10.1007/BF01848132
[30] R. Suri and S. Treville, Full speed ahead, OR/MS Today (June 1991) 34-42.
[31] L. Taylor and R. Williams, Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant, Prob. Theory Rel. Fields, to appear. · Zbl 0794.60079
[32] W. Whitt, Heavy traffic theorems for queues: A survey, in:Mathematical Methods in Queueing Theory, ed. A.B. Clark (Springer, Berlin, 1974). · Zbl 0295.60081
[33] W. Whitt, Refining diffusion approximations for queues, Oper. Res. Lett. 1 (1982) 165-169. · Zbl 0538.90025 · doi:10.1016/0167-6377(82)90033-5
[34] W. Whitt, The queueing network analyzer, Bell Sys. Tech. J. 62 (1983) 2779-2185.
[35] W. Whitt, Large fluctuations in a deterministic multiclass network of queues, Manag. Sci. (1993), to appear. · Zbl 0783.60090
[36] R. Williams, Reflected Brownian motion with skew symmetric data in a polyhedral domain, Prob. Theory Rel. Fields 75 (1987) 459-485. · Zbl 0608.60074 · doi:10.1007/BF00320328
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.