Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-29T22:27:06.375Z Has data issue: false hasContentIssue false
  • English
  • Français

Variational inference for Markovian queueing networks

Part of: Markov processes

Published online by Cambridge University Press:  08 October 2021

Iker Perez Open the ORCID record for Iker Perez [Opens in a new window]  and
Giuliano Casale
Iker Perez*
Affiliation:
University of Nottingham
Giuliano Casale*
Affiliation:
Imperial College London
*
*Postal address: School of Mathematical Sciences, University of Nottingham, Nottingham NG7 2RD, United Kingdom.
**Postal address: Department of Computing, Imperial College London, London SW7 2RH, United Kingdom.
Get access Rights & Permissions [Opens in a new window]

Abstract

Queueing networks are stochastic systems formed by interconnected resources routing and serving jobs. They induce jump processes with distinctive properties, and find widespread use in inferential tasks. Here, service rates for jobs and potential bottlenecks in the routing mechanism must be estimated from a reduced set of observations. However, this calls for the derivation of complex conditional density representations, over both the stochastic network trajectories and the rates, which is considered an intractable problem. Numerical simulation procedures designed for this purpose do not scale, because of high computational costs; furthermore, variational approaches relying on approximating measures and full independence assumptions are unsuitable. In this paper, we offer a probabilistic interpretation of variational methods applied to inference tasks with queueing networks, and show that approximating measure choices routinely used with jump processes yield ill-defined optimization problems. Yet we demonstrate that it is still possible to enable a variational inferential task, by considering a novel space expansion treatment over an analogous counting process for job transitions. We present and compare exemplary use cases with practical queueing networks, showing that our framework offers an efficient and improved alternative where existing variational or numerically intensive solutions fail.

Keywords

Queueing networksvariational methodsMarkov jump process

MSC classification

Primary: 60J27: Continuous-time Markov processes on discrete state spaces
Secondary: 60J28: Applications of continuous-time Markov processes on discrete state spaces
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 3 , September 2021 , pp. 687 - 715
Check for updates
Copyright
© The Author(s) 2021. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Armero, C. and Bayarri, M. J. (1994). Prior assessments for prediction in queues. Statistician 43, 139–153.10.2307/2348939CrossRefGoogle Scholar
Baele, G., van de Peer, Y. and Vansteelandt, S. (2010). Using non-reversible context-dependent evolutionary models to study substitution patterns in primate non-coding sequences. J. Molec. Evolution 71, 34–50.10.1007/s00239-010-9362-yCrossRefGoogle ScholarPubMed
Baskett, F., Chandy, K. M., Muntz, R. R. and Palacios, F. G. (1975). Open, closed, and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22, 248–260.10.1145/321879.321887CrossRefGoogle Scholar
Blei, D. M., Kucukelbir, A. and McAuliffe, J. D. (2017). Variational inference: a review for statisticians. J. Amer. Statist. Assoc. 112, 859–877.10.1080/01621459.2017.1285773CrossRefGoogle Scholar
Bobbio, A., Gribaudo, M. and Telek, M. (2008). Analysis of large scale interacting systems by mean field method. In 2008 Fifth International Conference on Quantitative Evaluation of Systems, Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 215–224.CrossRefGoogle Scholar
Buzacott, J. A. and Shanthikumar, J. G. (1993). Stochastic Models of Manufacturing Systems, Vol. 4. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Cohn, I., El-Hay, T., Friedman, N. and Kupferman, R. (2010). Mean field variational approximation for continuous-time Bayesian networks. J. Mach. Learning Res. 11, 2745–2783.Google Scholar
Cooper, R. B. (1981). Queueing theory. In Proceedings of the ACM’81 conference, Association for Computing Machinery, New York, pp. 119–122.CrossRefGoogle Scholar
Daley, D. J. and Vere-Jones, D. (2007). An Introduction to the Theory of Point Processes, Volume II: General Theory and Structure. Springer, New York.Google Scholar
Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81, 2340–2361.10.1021/j100540a008CrossRefGoogle Scholar
Golightly, A. and Wilkinson, D. J. (2015). Bayesian inference for Markov jump processes with informative observations. Statist. Appl. Genet. Molec. Biol. 14, 169–188.10.1515/sagmb-2014-0070CrossRefGoogle ScholarPubMed
Hobolth, A. and Stone, E. A. (2009). Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution. Ann. Appl. Statist. 3, 1204–1231.10.1214/09-AOAS247CrossRefGoogle ScholarPubMed
Huelsenbeck, J. P., Bollback, J. P. and Levine, A. M. (2002). Inferring the root of a phylogenetic tree. Systematic Biol. 51, 32–43.10.1080/106351502753475862CrossRefGoogle ScholarPubMed
Kleinrock, L. (1976). Queueing Systems, Vol. II: Computer Applications. John Wiley, New York.Google Scholar
Koole, G. and Mandelbaum, A. (2002). Queueing models of call centers: an introduction. Ann. Operat. Res. 113, 41–59.10.1023/A:1020949626017CrossRefGoogle Scholar
Kraft, S., Pacheco-Sanchez, S., Casale, G. and Dawson, S. (2009). Estimating service resource consumption from response time measurements. In Valuetools ’09: Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools, Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, Brussels, pp. 1–10.CrossRefGoogle Scholar
Liu, Z., Wynter, L., Xia, C. H. and Zhang, F. (2006). Parameter inference of queueing models for IT systems using end-to-end measurements. Performance Evaluation 63, 36–60.CrossRefGoogle Scholar
Opper, M. and Sanguinetti, G. (2008). Variational inference for Markov jump processes. In Advances in Neural Information Processing Systems, MIT Press, Boston, MA, pp. 1105–1112.Google Scholar
Opper, M. and Sanguinetti, G. (2010). Learning combinatorial transcriptional dynamics from gene expression data. Bioinformatics 26, 1623–1629.10.1093/bioinformatics/btq244CrossRefGoogle ScholarPubMed
Orbanz, P. and Teh, Y. W. (2011). Bayesian nonparametric models. In Encyclopedia of Machine Learning, Springer, Boston, MA, pp. 81–89.Google Scholar
Osorio, C. and Bierlaire, M. (2009). An analytic finite capacity queueing network model capturing the propagation of congestion and blocking. Europ. J. Operat. Res. 196, 996–1007.10.1016/j.ejor.2008.04.035CrossRefGoogle Scholar
Perez, I., Hodge, D. and Kypraios, T. (2017). Auxiliary variables for Bayesian inference in multi-class queueing networks. Statist. Comput. 28, 1187–1200.10.1007/s11222-017-9787-xCrossRefGoogle Scholar
Perez, I. and Kypraios, T. (2019). Scalable Bayesian inference for population Markov jump processes. Preprint. Available at https://arxiv.org/abs/1904.08356.Google Scholar
Rao, V. A. and Teh, Y. W. (2013). Fast MCMC sampling for Markov jump processes and extensions. J. Mach. Learning Res. 14, 3295–3320.Google Scholar
Serfozo, R. F. (1972). Conditional Poisson processes. J. Appl. Prob. 9, 288–302.10.2307/3212799CrossRefGoogle Scholar
Spinner, S., Casale, G., Brosig, F. and Kounev, S. (2015). Evaluating approaches to resource demand estimation. Performance Evaluation 92, 51–71.10.1016/j.peva.2015.07.005CrossRefGoogle Scholar
Sutton, C. and Jordan, M. I. (2011). Bayesian inference for queueing networks and modeling of internet services. Ann. Appl. Statist. 5, 254–282.10.1214/10-AOAS392CrossRefGoogle Scholar
Wang, C., Blei, D. and Heckerman, D. (2012). Continuous time dynamic topic models. Preprint. Available at https://arxiv.org/abs/1206.3298.Google Scholar
Wang, W., Casale, G. and Sutton, C. (2016). A Bayesian approach to parameter inference in queueing networks. ACM Trans. Model. Comput. Simul. 27, 2:1–2:26.Google Scholar
Zechner, C. et al. (2014). Scalable inference of heterogeneous reaction kinetics from pooled single-cell recordings. Nature Methods 11, 197–202.10.1038/nmeth.2794CrossRefGoogle ScholarPubMed
Zhang, B., Pan, J. and Rao, V. A. (2017). Collapsed variational Bayes for Markov jump processes. In Advances in Neural Information Processing Systems, MIT Press, Boston, MA, pp. 3749–3757.Google Scholar
Zhao, T. et al. (2016). Bayesian analysis of continuous time Markov chains with application to phylogenetic modelling. Bayesian Anal. 11, 1203–1237.10.1214/15-BA982CrossRefGoogle Scholar