Abstract
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.
Similar content being viewed by others
Notes
The simulation was carried out using a simulation package written in C++: PRONETSIM. See [32], Appendix A, for details about this software.
References
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)
Baccelli, F., Foss, S.: Ergodicity of Jackson-type queueing networks. Queueing Syst. 17(1–2), 5–72 (1994)
Bean, N., Green, D., Taylor, P.G.: The output process of an MMPP/M/1 queue. J. Appl. Probab. 35(4), 998–1002 (1998)
Bramson, M.: Stability of Queueing Networks. Springer, Berlin (2008)
Bramson, M., Dai, J.G.: Heavy traffic limits for some queueing networks. Ann. Appl. Probab. 11(1), 49–90 (2001)
Bramson, M., D’Auria, B., Walton, N.: Proportional switching in first-in, first-out networks. Oper. Res. 65(2), 496–513 (2016)
Burke, P.J.: The output of a queuing system. Oper. Res. 4(6), 699–704 (1956)
Chen, H.: Fluid approximations and stability of multiclass queueing networks I: Work-conserving disciplines. Ann. Appl. Probab. 5(3), 637–665 (1995)
Chen, H., Mandelbaum, A.: Stochastic discrete flow networks: Diffusion approximations and bottlenecks. Ann. Probab. 19(4), 1463–1519 (1991)
Chen, H., Yao, D.D.: Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, Berlin (2001)
Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5(1), 49–77 (1995)
Dai, J.G., Meyn, S.P.: Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Autom. Control 40(11), 1889–1904 (1995)
Dai, J.G., Harrison, M.J.: Steady-state analysis of RBM in a rectangle: Numerical methods and a queueing application. Ann. Appl. Probab. 1(1), 16–35 (1991)
Daley, D.J.: Queueing output processes. Adv. Appl. Probab. 8, 395–415 (1976)
Disney, R.L., Kiessler, P.C.: Traffic Processes in Queueing Networks-A Markov Renewal Approach. The Johns Hopkins University Press, Cambridge (1987)
Disney, R.L., Konig, D.: Queueing networks: A survey of their random processes. SIAM Rev. 27(3), 335–403 (1985)
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)
Goodman, J.B., Massey, W.: Non-ergodic Jackson network. J. Appl. Probab. 21(4), 860–869 (1984)
Gut, A.: Probability: A Graduate Course. Springer, Berlin (2005)
Gut, A.: Stopped Random Walks: Limit Theorems and Applications. Springer, Berlin (2009)
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)
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)
Jackson, J.R.: Jobshop-like queueing systems. Manage. Sci. 10(1), 131–142 (1963)
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)
Karlin, S., Taylor, H.M.: A First Course in Stochastic Processes. Academic Press, Cambridge (1975)
Kelly, F.: Reversibility and Stochastic Networks. Wiley, New York (1979)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Springer, Berlin (1960)
Kim, S.: Modeling cross correlation in three-moment four-parameter decomposition approximation of queueing networks. Oper. Res. 59(2), 480–497 (2011)
Kim, S., Muralidharan, R., O’Cinneide, C.A.: Taking account of correlations between streams in queueing network approximations. Queueing Syst. 49(3), 261–281 (2005)
Kuehn, P.: Approximate analysis of general queuing networks by decomposition. IEEE Trans. Commun. 27(1), 113–126 (1979)
Meyn, S.P.: Control Techniques for Complex Networks. Cambridge University Press, Cambridge (2008)
Nazarathy, Y.: On control of queueing networks and the asymptotic variance rate of outputs. PhD thesis, University of Haifa, (2008)
Nazarathy, Y., Weiss, G.: Positive Harris recurrence and diffusion scale analysis of a push pull queueing network. Perform. Eval. 67(4), 201–217 (2010)
Reiman, M.I.: Open queueing networks in heavy traffic. Math. Oper. Res. 9(3), 441–458 (1984)
Weiss, G.: Scheduling and Control of Queueing Networks. Institute of Mathematical Statistics Textbooks, Cambridge University Press (2021)
Whitt, W.: Performance of the queueing network analyzer. Bell Syst. Tech. J. 62(9), 2817–2843 (1983)
Whitt, W.: Stochastic Process Limits. Springer, New York (2002)
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)
Williams, R.J.: Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Syst. 30, 27–88 (1998)
Zhang, F. (ed.): The Schur complement and its applications. Numerical Methods and Algorithms, vol. 4. Springer, New York (2005)
Acknowledgements
YN is supported by Australian Research Council (ARC) grant DP180101602. Part of the work was carried out, while WS was supported by an Ethel Raybould Visiting Fellowship to the University of Queensland. SBM is supported by the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS) under grant number CE140100049. We thank an anonymous referee of this paper for their valuable comments and suggestions, particularly for highlighting the need for Assumption (A7). We also thank an anonymous referee of an earlier version of the paper for drawing our attention to the usefulness of the innovations method calculations.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Moka, S.B., Nazarathy, Y. & Scheinhardt, W. Diffusion parameters of flows in stable multi-class queueing networks. Queueing Syst 103, 313–346 (2023). https://doi.org/10.1007/s11134-022-09869-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-022-09869-1