Quick simulation of rare events in networks

ABSTRACT

We study the problem of how to simulate the occurrence of rare events on networks of queues; an interesting application is to obtain the expected time until the network buffers fill up.We show that the unique optimal (minimum variance) change of measure (importance sampling) to simulate an event is given by the law of the process conditioned on the event (rare or not).Some theory is needed to circumvent the fact that knowledge of the conditional laws implies knowledge of the solution. We present two ways to handle the problem. Boundary theory of Markov Chains provides the theoretical framework. The method sheds light on the way that rare events happen; this in turn explains why some large deviations ("LD" in what follows) heuristics (Walrand and Parekh) fail for important combinations of parameter values (optimal buffer allocation).A compactness argument and a scale-down version of the model are used to simulate successfully the chances of excessive backlogs for many M/M/1 queues in tandem and for any combination of parameters.Alternatively, we can build on the LD heuristics and, using the notion of convex combination of harmonics, we successfully treat the optimal buffer allocation case.

REFERENCES

• 1: Anantharam, V., "The Optimal Buffer Allocation Problem," Preprint, School of Electrical Engineering, Cornell University, Ithaca, NY, 1988.
• 2: Cottrell, M., Fort, J., Malgouyres, G., "Large Deviations and Rare Events in the Study of Stochastic Algorithms". IEEE Trans. A. C. vol. AC-28, No. 9
• 3: Freedman, David, "Markov Chains", Springer-Verlag, New York, 1983.
• 4: Fresnedo, R., "Quick Simulations of Rare Events in Networks", Ph.D. dissertation, Dept. of Statistics, Univ. Calif. Berkeley, 1989
• 5: Greenberg, A. G. and R. J. Vanderbei, "On Successive Approximation Methods for Stochastic Problems," Technical Memorandum, AT&T Bell Labs, Murray Hill, 1987.
• 6: Kelly, Frank, "Reversibility and Stochastic Networks", John Wiley & Sons, 1979.
• 7: Kemeny, John G., J. Laurie Snell, and Anthony W. Knapp, "Denumerable Markov Chains", Springer-Verlag, New York, 1976.
• 8: Parekh, S., "Rare Events in Networks", Ph.D. dissertation, Dep. EECS, Univ. Calif. Berkeley, 1986.
• 9: Parekh, S., Walrand J., "A Quick Simulation Method for Excessive Backlogs in Networks of Queues", IEEE Transactions on Automatic Control, Vol. 34, No. 1, January, 1989.
• 10: Ripley, Brian D., "Stochastic Simulation", John Wiley & Sons, New York, 1987.
• 11: Siegmund, D., "Importance Sampling in the Monte Carlo study of sequential tests". Annals of Statistics, 4, 673--684, 1976.
• 12: Walrand, Jean, "An Introduction to Queueing Networks", Prentice Hall, 1987

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance, Theory