Accelerating performance inference over closed systems by asymptotic methods

Abstract

Recent years have seen a rapid growth of interest in exploiting monitoring data collected from enterprise applications for automated management and performance feedbacks. In spite of this trend, even simple performance inference problems involving queueing theoretic formulas often incur computational bottlenecks, for example upon computing likelihoods in models of batch systems. Motivated by this issue, we revisit the solution of multiclass closed queueing networks, which are popular models used to describe batch and distributed applications with parallelism constraints. We first prove that the normalizing constant of the equilibrium state probabilities of a closed model can be reformulated in an exact manner as a multidimensional integral over the unit simplex. This gives as a by-product the first exact expressions for the multiclass normalizing constant that are both tractable and explicit. We then derive a novel method based on cubature rules to efficiently evaluate the proposed integral form in small and medium-sized models. For large models, we propose novel asymptotic expansions and Monte Carlo sampling methods to efficiently and accurately approximate normalizing constants and likelihoods. We illustrate the resulting accuracy gains in problems involving optimization-based inference.