Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T21:13:32.355Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast simulation of Markov fluid models

Published online by Cambridge University Press:  14 July 2016

Ad Ridder
Ad Ridder*
Affiliation:
Free University of Amsterdam
*
∗Postal address: Econometrics, Free University of Amsterdam, De Boelelaan 1105, 1081 HV Amsterdam, Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study continuous flow finite buffer systems with input rates modulated by Markov chains. Discrete event simulations are applied for estimating loss probabilities. The simulations are executed under a twisted version of the original probability measure (importance sampling). We present a simple rule for determining a new measure, then show that the new measure matches the ‘most likely' empirical measure that we expect from large deviations arguments, and finally prove optimality of the new measure.

Keywords

CONTINUOUS FLOW SYSTEMSIMPORTANCE SAMPLINGLARGE DEVIATIONSOVERFLOW PROBABILITYAMS 1991 SUBJECT CLASSIFICATION90B1260F1065C05
Type
Research Papers
Information
Journal of Applied Probability , Volume 33 , Issue 3 , September 1996 , pp. 786 - 803
Copyright
Copyright © Applied Probability Trust 1996 

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

[1] Anantharam, V. (1988) How large delays build up in a GI/G/1 queue. Queueing Systems 5, 345–368.Google Scholar
[2] Anick, D., Mitra, D. and Sondhi, M. M. (1982) Stochastic theory of a data-handling system with multiple sources. Bell Syst. Tech. J. 61, 1871–1894.Google Scholar
[3] Bucklew, J. A., Ney, P. and Sadowsky, J. S. (1990) Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob. 27, 44–59.Google Scholar
[4] Chang, C.-S., Heidelberger, P., Juneja, S. and Shahabuddin, P. (1992) Effective bandwidth and fast simulation of ATM intree networks. IBM Research Paper. Google Scholar
[5] Cottrell, M., Fort, J.-C. and Malgouyres, G. (1983) Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automatic Control 9, 907–920.CrossRefGoogle Scholar
[6] De Veciana, G., Olivier, C. and Walrand, J. (1993) Large deviations of birth-death Markov fluids. Prob. Eng. Inf. Sci. 7, 237–255.Google Scholar
[7] Ellis, R. S. (1985) Entropy, Large Deviations and Statistical Mechanics. Springer, New York.Google Scholar
[8] Elwalid, A. I. and Mitra, D. (1991) Analysis and design of rate-based congestion control of high speed networks, I: Stochastic fluid models, access regulation. Queueing Systems 9, 29–64.Google Scholar
[9] Elwalid, A. I. and Mitra, D. (1993) Effective bandwidth of general Markovian traffic sources and admission control of high speed networks. IEEE/ACM Trans. Network. 1, 329–343.Google Scholar
[10] Freidlin, M. I. and Wentzell, A. D. (1984) Random Perturbations of Dynamical Systems. Springer, New York.Google Scholar
[11] Gibbens, R. J. and Hunt, P. J. (1991) Effective bandwidths for the multi-type UAS channel. Queueing Systems 9, 17–28.CrossRefGoogle Scholar
[12] Glynn, P. W. and Iglehart, D. L. (1989) Importance sampling for stochastic simulations. Management Sci. 35, 1367–1392.Google Scholar
[13] Kelly, F. P. (1991) Effective bandwidths at multi-class queues. Queueing Systems 9, 5–16.Google Scholar
[14] Kesidis, G. and Walrand, J. (1993) Quick simulation of ATM buffers with on-off multiclass Markov fluid sources. ACM Trans. Model. Comput. Simul. 3, 269–276.Google Scholar
[15] Kesidis, G. and Walrand, J. (1993) Relative entropy between Markov transition rate matrices. IEEE Trans. Inf. Theory 39, 1056–1057.Google Scholar
[16] Kesidis, G., Walrand, J. and Chang, C. S. (1993) Effective bandwidths for multiclass Markov fluids and other ATM sources. IEEE/ACM Trans. Network. 1, 424–428.Google Scholar
[17] Kifer, Y. (1988) Random Perturbations of Dynamical Systems. Birkhäuser, Boston.Google Scholar
[18] Kosten, L. (1984) Stochastic theory of data-handling systems with groups of multiple sources. In Performance of Computer-Communication Systems. ed. Rudin, H. and Bux, W. Elsevier, Amsterdam, pp. 321–331.Google Scholar
[19] Parekh, S. and Walrand, J. (1989) A quick simulation method for excessive backlog in network of queues. IEEE Trans. Automatic Control 34, 54–66.Google Scholar
[20] Ridder, A. and Walrand, J. (1992) Some large deviations results in Markov fluid models. Prob. Eng Inf. Sci. 6, 543–560.CrossRefGoogle Scholar
[21] Sadowsky, J. S. (1993) On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inf. Theory 39, 119–128.Google Scholar
[22] Siegmund, D. (1976) Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673–684.Google Scholar
[23] Wentzell, A. D. (1976) Rough limit theorems on large deviations for Markov stochastic processes, part II. Theory Prob. Appl. 21, 499–512.Google Scholar