Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T19:53:13.304Z Has data issue: false hasContentIssue false
  • English
  • Français

Exploiting Markov chains to infer queue length from transactional data

Part of: Special processes Stochastic processes

Published online by Cambridge University Press:  14 July 2016

D. J. Daley  and
L. D. Servi
D. J. Daley*
Affiliation:
The Australian National University
L. D. Servi*
Affiliation:
GTE Laboratories Inc.
*
∗Postal address: Statistics Research Section, School of Mathematical Sciences, Australian National University, Canberra, GPO Box 4, ACT 2601, Australia.
∗∗Postal address: GTE Laboratories Incorporated, 40 Sylvan Road, Waltham, MA 02254, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The use of taboo probabilities in Markov chains simplifies the task of calculating the queue-length distribution from data recording customer departure times and service commencement times such as might be available from automatic bank-teller machine transaction records or the output of telecommunication network nodes. For the case of Poisson arrivals, this permits the construction of a new simple exact O(n3) algorithm for busy periods with n customers and an O(n2 log n) algorithm which is empirically verified to be within any prespecified accuracy of the exact algorithm. The algorithm is extended to the case of Erlang-k interarrival times, and can also cope with finite buffers and the real-time estimates problem when the arrival rate is known.

Keywords

M/GI/1 QUEUEEK/GI/1 QUEUETABOO PROBABILITIESPOISSON PROCESSCROSS-COUPLING

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60G55: Point processes
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 3 , September 1992 , pp. 713 - 732
Copyright
Copyright © Applied Probability Trust 1992 

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

Bertsimas, D. J. and Servi, L. D. (1992) Deducing queueing from transactional data: the queue inference engine revisited. Operat. Res. 40.CrossRefGoogle Scholar
Chung, K. L. (1960) Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin.Google Scholar
Enns, E. G. (1969) The trivariate distribution of the maximum queue length, the number of customers served and the duration of the busy period for the M/G/1 queueing system. J. Appl. Prob. 6, 154–161.CrossRefGoogle Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. 1, 3rd edn. Wiley, New York.Google Scholar
Gawlick, R. (1990). Estimating disperse network queues: the queue inference engine. Computer Commun. Rev. 20, 111–118.Google Scholar
Larson, R. (1990) The queue inference engine: deducing queue statistics from transactional data. Management Sci. 36, 586–601.Google Scholar
Larson, R. (1991) The queue inference engine: deducing queue statistics from transactional data, addendum. Management Sci. 36, 1062.CrossRefGoogle Scholar
Moran, P. A. P. (1968) An Introduction to Probability Theory. Clarendon Press, Oxford.Google Scholar
Prabhu, N. U. (1965) Queues and Inventories: A Study of Their Basic Stochastic Processes. Wiley, New York.Google Scholar
Stoyan, D. (1983) Comparison Methods for Queues and Other Stochastic Models (English translation ed. Daley, D. J.). Wiley, Chichester.Google Scholar