Diffusion parameters of flows in stable multi-class queueing networks. (English) Zbl 1515.60290
Summary: We consider open multi-class queueing networks with general arrival processes, general processing time sequences and Bernoulli routing. The network is assumed to be operating under an arbitrary work-conserving scheduling policy that makes the system stable. We study the variability of flows within the network. Computable expressions for quantifying flow variability have previously been discussed in the literature. However, in this paper, we shed more light on such analysis to justify the use of these expressions in the asymptotic analysis of network flows. Toward that end, we find a simple diffusion limit for the inter-class flows and establish the relation to asymptotic (co-)variance rates.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
References:
| [1] | Al Hanbali, A.; Mandjes, M.; Nazarathy, Y.; Whitt, W., The asymptotic variance of departures in critically loaded queues, Adv. Appl. Probab., 43, 243-263 (2011) · Zbl 1279.90045 · doi:10.1239/aap/1300198521 |
| [2] | Baccelli, F.; Foss, S., Ergodicity of Jackson-type queueing networks, Queueing Syst., 17, 1-2, 5-72 (1994) · Zbl 0826.60081 · doi:10.1007/BF01158688 |
| [3] | Bean, N.; Green, D.; Taylor, PG, The output process of an MMPP/M/1 queue, J. Appl. Probab., 35, 4, 998-1002 (1998) · Zbl 0939.60096 · doi:10.1239/jap/1032438394 |
| [4] | Bramson, M., Stability of Queueing Networks (2008), Berlin: Springer, Berlin · Zbl 1189.60005 |
| [5] | Bramson, M.; Dai, JG, Heavy traffic limits for some queueing networks, Ann. Appl. Probab., 11, 1, 49-90 (2001) · Zbl 1016.60084 · doi:10.1214/aoap/998926987 |
| [6] | Bramson, M.; D’Auria, B.; Walton, N., Proportional switching in first-in, first-out networks, Oper. Res., 65, 2, 496-513 (2016) · Zbl 1366.90107 · doi:10.1287/opre.2016.1565 |
| [7] | Burke, PJ, The output of a queuing system, Oper. Res., 4, 6, 699-704 (1956) · Zbl 1414.90097 · doi:10.1287/opre.4.6.699 |
| [8] | Chen, H., Fluid approximations and stability of multiclass queueing networks I: Work-conserving disciplines, Ann. Appl. Probab., 5, 3, 637-665 (1995) · Zbl 0847.60073 · doi:10.1214/aoap/1177004699 |
| [9] | Chen, H.; Mandelbaum, A., Stochastic discrete flow networks: Diffusion approximations and bottlenecks, Ann. Probab., 19, 4, 1463-1519 (1991) · Zbl 0757.60094 · doi:10.1214/aop/1176990220 |
| [10] | Chen, H.; Yao, DD, Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization (2001), Berlin: Springer, Berlin · Zbl 0992.60003 · doi:10.1007/978-1-4757-5301-1 |
| [11] | Dai, JG, On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models, Ann. Appl. Probab., 5, 1, 49-77 (1995) · Zbl 0822.60083 · doi:10.1214/aoap/1177004828 |
| [12] | Dai, JG; Meyn, SP, Stability and convergence of moments for multiclass queueing networks via fluid limit models, IEEE Trans. Autom. Control, 40, 11, 1889-1904 (1995) · Zbl 0836.90074 · doi:10.1109/9.471210 |
| [13] | Dai, JG; Harrison, MJ, Steady-state analysis of RBM in a rectangle: Numerical methods and a queueing application, Ann. Appl. Probab., 1, 1, 16-35 (1991) · Zbl 0719.60115 · doi:10.1214/aoap/1177005979 |
| [14] | Daley, DJ, Queueing output processes, Adv. Appl. Probab., 8, 395-415 (1976) · Zbl 0349.60097 · doi:10.2307/1425911 |
| [15] | Disney, RL; Kiessler, PC, Traffic Processes in Queueing Networks-A Markov Renewal Approach (1987), Cambridge: The Johns Hopkins University Press, Cambridge · Zbl 0713.90032 |
| [16] | Disney, RL; Konig, D., Queueing networks: A survey of their random processes, SIAM Rev., 27, 3, 335-403 (1985) · Zbl 0581.60075 · doi:10.1137/1027109 |
| [17] | Glynn, P. W.: Diffusion approximations. In: D.P. Heyman, M.J. Sobel (eds.), Handbooks in Operations Research, Vol 2, North-Holland, Amsterdam, pp. 145-198 (1990) · Zbl 0698.00032 |
| [18] | Goodman, JB; Massey, W., Non-ergodic Jackson network, J. Appl. Probab., 21, 4, 860-869 (1984) · Zbl 0562.60096 · doi:10.2307/3213702 |
| [19] | Gut, A., Probability: A Graduate Course (2005), Berlin: Springer, Berlin · Zbl 1076.60001 |
| [20] | Gut, A., Stopped Random Walks: Limit Theorems and Applications (2009), Berlin: Springer, Berlin · Zbl 1166.60001 · doi:10.1007/978-0-387-87835-5 |
| [21] | Harrison, M.: Brownian models of queueing networks with heterogeneous customer populations. In Stochastic differential systems, stochastic control theory and applications, pp. 147-186. Springer, (1988) · Zbl 0658.60123 |
| [22] | Hautphenne, S.; Kerner, Y.; Nazarathy, Y.; Taylor, P., The intercept term of the asymptotic variance curve for some queueing output processes, Eur. J. Oper. Res., 242, 2, 455-464 (2015) · Zbl 1341.90029 · doi:10.1016/j.ejor.2014.10.051 |
| [23] | Jackson, JR, Jobshop-like queueing systems, Manage. Sci., 10, 1, 131-142 (1963) · doi:10.1287/mnsc.10.1.131 |
| [24] | Jacod, J., Shiryaev, A. N.: Limit theorems for stochastic processes, volume 288 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, second edition (2003) · Zbl 1018.60002 |
| [25] | Karlin, S.; Taylor, HM, A First Course in Stochastic Processes (1975), Cambridge: Academic Press, Cambridge · Zbl 0315.60016 |
| [26] | Kelly, F., Reversibility and Stochastic Networks (1979), New York: Wiley, New York · Zbl 0422.60001 |
| [27] | Kemeny, JG; Snell, JL, Finite Markov Chains (1960), Berlin: Springer, Berlin · Zbl 0089.13704 |
| [28] | Kim, S., Modeling cross correlation in three-moment four-parameter decomposition approximation of queueing networks, Oper. Res., 59, 2, 480-497 (2011) · Zbl 1233.90118 · doi:10.1287/opre.1100.0893 |
| [29] | Kim, S.; Muralidharan, R.; O’Cinneide, CA, Taking account of correlations between streams in queueing network approximations, Queueing Syst., 49, 3, 261-281 (2005) · Zbl 1093.90007 · doi:10.1007/s11134-005-6967-8 |
| [30] | Kuehn, P., Approximate analysis of general queuing networks by decomposition, IEEE Trans. Commun., 27, 1, 113-126 (1979) · Zbl 0392.60070 · doi:10.1109/TCOM.1979.1094270 |
| [31] | Meyn, SP, Control Techniques for Complex Networks (2008), Cambridge: Cambridge University Press, Cambridge · Zbl 1139.91002 |
| [32] | Nazarathy, Y.: On control of queueing networks and the asymptotic variance rate of outputs. PhD thesis, University of Haifa, (2008) |
| [33] | Nazarathy, Y.; Weiss, G., Positive Harris recurrence and diffusion scale analysis of a push pull queueing network, Perform. Eval., 67, 4, 201-217 (2010) · doi:10.1016/j.peva.2009.09.010 |
| [34] | Reiman, MI, Open queueing networks in heavy traffic, Math. Oper. Res., 9, 3, 441-458 (1984) · Zbl 0549.90043 · doi:10.1287/moor.9.3.441 |
| [35] | Weiss, G., Scheduling and Control of Queueing Networks (2021), Cambridge University Press: Institute of Mathematical Statistics Textbooks, Cambridge University Press · Zbl 1494.90002 · doi:10.1017/9781108233217 |
| [36] | Whitt, W., Performance of the queueing network analyzer, Bell Syst. Tech. J., 62, 9, 2817-2843 (1983) · doi:10.1002/j.1538-7305.1983.tb03205.x |
| [37] | Whitt, W., Stochastic Process Limits (2002), New York: Springer, New York · Zbl 0993.60001 · doi:10.1007/b97479 |
| [38] | Whitt, W.; You, W., Heavy-traffic limit of the GI/GI/1 stationary departure process and its variance function, Stochast. Syst., 8, 2, 143-165 (2018) · Zbl 1446.60076 · doi:10.1287/stsy.2018.0011 |
| [39] | Williams, RJ, Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse, Queueing Syst., 30, 27-88 (1998) · Zbl 0911.90171 · doi:10.1023/A:1019108819713 |
| [40] | Zhang, F. (ed.): The Schur complement and its applications. Numerical Methods and Algorithms, vol. 4. Springer, New York (2005) · Zbl 1075.15002 |
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.
