Analysis of an importance sampling estimator for tandem queues

ABSTRACT

We analyze the performance of an importance sampling estimator for a rare-event probability in tandem Jackson networks. The rare event we consider corresponds to the network population reaching K before returning to ø, starting from ø, with K large. The estimator we study is based on interchanging the arrival rate and the smallest service rate and is therefore a generalization of the asymptotically optimal estimator for an M/M/1 queue. We examine its asymptotic performance for large K, showing that in certain parameter regions the estimator has an asymptotic efficiency property, but that in other regions it does not. The setting we consider is perhaps the simplest case of a rare-event simulation problem in which boundaries on the state space play a significant role.

REFERENCES

• 1: AN~3~THAR~, V. 1989. The optimal buffer allocation problem. IEEE Trans. Inf. Theor. 35, 721-725.
• 2: ANANTI~RAM, V., AND GANESH, A. Correctness within a constant of an optimal buffer allocation rule of thumb. IEEE Trans. Inf. Theor. (to appear).
• 3: ANANTHARAM, V., HEIDELBERGER, P., AND TScUCAS, P. 1990. Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation. IBM Res. Rep. RC16820. Yorktown Heights, N.Y.
• 4: ASMUSSEN, S. 1982. Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue. Adv. Appl. Prob. 14, 143 170.
• 5: ASMUSSEN, S. 1987. Applied Probability and Queues. Wiley, New York.
• 6: BUCKLEW, J.A. 1990. Large Dewations Techntques in Decision, Simulation, and Esttmatton. Wiley, New York.
• 7: 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
• 8: DuPuIs, P., ISHII, H., AND SONER, H.M. 1990. A viscosity solution approach to the asymptotic analysis of queueing systems. Ann. Probab. 18, 226-255.
• 9: FRATER, M. R., LENON, T. M., AND ANDERSON, B. D.O. 1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Aurora. Control TAC-36, 1395-1405.
• 10: GLASSERMAN, P., AND KOU, S.-G. 1993. Overflow probabilities in Jackson networks. In Proceed- ings of the 32nd IEEE Conference on Decision and Control. IEEE Press, New York, 3178-3182.
• 11: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 12: JANSON, S. 1986. Moments for first-passage and last-exit times, the minimum, and related quantities for random walks with positive drift. Adv. Appl. Probab. 18, 865-879.
• 13: KELLY, F.J. 1979. Revers~bdity and Stochastic Networks. Wiley, New York.
• 14: G. Kesidis , J. Walrand, Quick simulation of ATM buffers with on-off multiclass Markov fluid sources, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.3, p.269-276, July 1993 [doi>10.1145/174153.174162]
• 15: PAREK~, S., AND WALRAND, J. 1989. Quick simulation of rare events in networks. IEEE Trans. Autom. Control TAC-34, 54-66.
• 16: SADOWSKY, J.S. 1991. Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queues. IEEE Trans. Autom. Control TAC-36, 1383-1394.
• 17: SmGMUND, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673-684.
• 18: SIMON, B. 1979. Functmnal Integration and Quantum Physics. Academic Press, New York.
• 19: TsoucAs, P. 1992. Rare events in series of queues. J. Appl. Probab. 29, 168-175.
• 20: WEBER, R.R. 1979. The interchangeability of M/M/1 queues m series. J. Appl. Probab. 16, 690-695.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Performance, Theory

Keywords:
Markov chains, importance sampling, queueing networks, rare events