Probabilistic Inference in Queueing Networks

TitleProbabilistic Inference in Queueing Networks
Publication TypeConference Proceedings
Year of Conference2008
AuthorsSutton, Charles, & Michael I. Jordan
Conference NameIn Workshop on Tackling Computer Systems Problems with Machine Learning Techniques (SysML)
Date Published2008
PublisherUSENIX Association

Although queueing models have long been used to model the performance of computer systems, they are out of favor with practitioners, because they have a reputation for requiring unrealistic distributional assumptions. In fact, these distributional assumptions are used mainly to facilitate analytic approximations such as asymptotics and large-deviations bounds. In this paper, we analyze queueing networks from the probablistic modeling perspective, applying inference methods from graphical models that afford significantly more modeling flexibility. In particular, we present a Gibbs sampler and stochastic EM algorithm for networks of M/M/1 FIFO queues. As an application of this technique, we localize performance problems in distributed systems from incomplete system trace data. On both synthetic networks and an actual distributed Web application, the model accurately recovers the system's service time using 1% of the available trace data.