Efficient simulation of a tandem Jackson network

ABSTRACT

The two-node tandem Jackson network serves as a convenient reference model for the analysis and testing of different methodologies and techniques in rare event simulation. In this paper we consider a new approach to efficiently estimate the probability that the content of the second buffer exceeds some high level L before it becomes empty, starting from a given state. The approach is based on a Markov additive process representation of the buffer processes, leading to an exponential change of measure to be used in an importance sampling procedure. Unlike changes of measures proposed and studied in recent literature, the one derived here is a function of the content of the first buffer. We prove that when the first buffer is finite, this method yields asymptotically efficient simulation for any set of arrival and service rates. In fact, the relative error is bounded independent of the level L; a new result which is not established for any other known method. When the first buffer is infinite, we propose a natural extension of the exponential change of measure for the finite buffer case. In this case, the relative error is shown to be bounded (independent of L) only when the second server is the bottleneck; a result which is known to hold for some other methods derived through large deviations analysis. When the first server is the bottleneck, experimental results using our method seem to suggest that the relative error is bounded linearly in L.

REFERENCES

• 1: Anantharam, V., Heidelberger, P., and Tsoucas, P. 1990. Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation. Tech. Rep. 16280, IBM Research Devision.
• 2: Asmussen, S. and Rubinstein, R. 1995. Steady state rare events simulation in queueing models and its complexity properties. In Advances in Queueing: Theory, Methods and Open Problems, J. Dshalalow, Ed. CRC Press, New York, 429--461.
• 3: Cheng-Shang Chang , Philip Heidelberger , Sandeep Juneja , Perwez Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Performance Evaluation, v.20 n.1-3, p.45-65, May 1994
• 4: Chihara, T. 1978. An Introduction to Orthogonal Polynomials. Gordon and Breach, New York.
• 5: de Boer, P.-T., Nicola, V., and Rubinstein, R. 2000. Dynamic importance sampling simulation of queueing networks: An adaptive approach based on cross-entropy. In Proceedings of the 2000 Winter Simulation Conference. IEEE Computer Society Press, Orlando, FL.
• 6: Frater, M. and Anderson, B. 1989. Fast estimation of the statistics of excessive backlogs in tandem networks of queues. Australian Telecommun. Res. 23, 49--55.
• 7: Frater, M., Lenon, T., and Anderson, B. 1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Autom. Control 36, 1395--1405.
• 8: Garvels, M. and Kroese, D. 1999. On the entrance distribution in RESTART simulation. In Proceedings of the RESIM'99 workshop. University of Twente, 11--12 March 1999, Enschede, 65--88.
• 9: Paul Glasserman , Shing-Gang Kou, Analysis of an importance sampling estimator for tandem queues, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.22-42, Jan. 1995 [doi>10.1145/203091.203093]
• 10: Glasserman, P. and Wang, Y. 1997. Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7, 4, 731--746.
• 11: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 12: Kingman, J. 1961. A convexity property of positive matrices. Quart. J. Math. 12, 283--284.
• 13: Kroese, D. and Nicola, V. 1998. Efficient simulation of backlogs in fluid flow lines. AEÜ Int. J. Electron. Commun. 52, 165--172.
• 14: Kroese, D., Scheinhardt, W., and Taylor, P. 2002. Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. In preparation.
• 15: Neuts, M. 1981. Matrix-geometric solutions in stochastic models. Johns Hopkins University Press, Baltimore.
• 16: Ney, P. and Nummelin, E. 1987a. Markov additive processes I. Eigenvalue properties and limit theorems. Annals Probab. 15, 2, 561--592.
• 17: Ney, P. and Nummelin, E. 1987b. Markov additive processes II. Large deviations. Annals Probab. 15, 2, 593--609.
• 18: Nicola, V., Shahabuddin, P., Heidelberger, P., and Glynn, P. 1993. Fast simulation of steady-state availability in non-Markovian highly dependable systems. In Proceedings of the 23rd International Symposium on Fault-Tolerant Computing. IEEE Computer Society Press, Toulouse, France, 38--47.
• 19: Parekh, S. and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Contr. 34, 54--66.
• 20: Rubinstein, R. 1999. The cross-entropy method for combinatorial and continuous optimization. Methodol. Comput. Appl. Probab. 2, 127--190.
• 21: Tsoucas, P. 1992. Rare events in series of queues. J. Appl. Probab. 29, 168--175.
• 22: Veciana, G. D., Courcoubetis, C., and Walrand, J. 1994. Decoupling bandwidths for networks: A decomposition approach to resource management for networks. In Proceedings of INFOCOM'94. IEEE Press, Toronto, Canada, 466--473.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Systems theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory; Stochastic processes

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
Bounded relative error, Markov additive processes, importance sampling, orthogonal polynomials, rare event simulation, tandem Jackson network