Fast simulation of packet loss rates in a shared buffer communications switch

ABSTRACT

This article describes an efficient technique for estimating, via simulation, the probability of buffer overflows in a queueing model that arises in the analysis of ATM (Asynchronous Transfer Mode) communication switches. There are multiple streams of (autocorrelated) traffic feeding the switch that has a buffer of finite capacity. Each stream is designated as being of either high or low priority. When the queue length reaches a certain threshold, only high priority packets are admitted to the switch's buffer. The problem is to estimate the loss rate of high priority packets. An asymptotically optimal importance sampling approach is developed for this rare event simulation problem. In this approach, the importance sampling is done in two distinct phases. In the first phase, an importance sampling change of measure is used to bring the queue length up to the threshold at which low priority packets get rejected. In the second phase a different importance sampling change of measure is used to move the queue length from the threshold to the buffer capacity.

REFERENCES

• 1: ASMUSSEN, S.1989.Risk theory in a Markovian environment. Scand. Actuarial J., 69-100.
• 2: ASMUSSEN, S.1987. Applied Probability and Queues. John Wiley, New York.
• 3: ASMUSSEN, S. 1985.Conjugate processes and the simulation of ruin problems. Stochastic Process. Appl. 20, 213-229.
• 4: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 5: BREIMAN, L. 1968. Probabihty. Addison-Wesley, Reading, MA.
• 6: BUCKLEW, J. 1990.Large Deviation Techniques in Decision, S~mulat~on and Estimatwn. Wiley, New York.
• 7: BUCKLEW, J. A., NE~, P., AND S~OWS~Z, J. S. 1990. Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Probab 27, 44-99.
• 8: CuANG, C.S. 1994. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Trans. Autom. Control 39,913-931.
• 9: CHANG, C.S. 1992. Stability, queue length and delay, Part II: Stochastic queueing networks. In Proceedings of the Thirty-First IEEE Conference on Decision and Control (Tucson, AZ), IEEE Computer Society Press, Los Alamitos, CA, 1005 1010.
• 10: 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
• 11: CHANG, C. S., HEIDELBERGER, P., JUNEJA, S., AND SH~UDDIN, P. 1993. The application of effective bandwidth to fast simulation of communication networks. IBM Res. Rep. RC 18877, Yorktown Heights, New York.
• 12: COGBURN, R. 1975. A uniform theory for sums of Markov chain transition probabilities. Ann. Probab. 3, 191 214.
• 13: CRANE, M. A. AND IGLEHART, D.L. 1975 Simulating stable stochastic system III: regenerative processes and discrete event simulation. Oper. Res. 23, 33-45.
• 14: ELLIS, R. 1984. Large deviations for a general class of random vectors. Ann. Probab. 12, i 12.
• 15: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• 16: ELWALIB, A. I. AND MITRA, D. 1994. Statistical multiplexing w~th loss priorities in rate-based congestion control of high speed networks. IEEE Trans. Commum 42, 11, 2989-3002.
• 17: Anwar I. Elwalid , Debasis Mitra, Fluid models for the analysis and design of statistical multiplexing with loss priorities on multiple classes of bursty traffic, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 1), p.415-425, May 1992, Florence, Italy
• 18: FRATER, M. R. AND ANDERSON, B. D. O. 1989. Fast estimation of the statistics of excessive backlogs in tandem networks of queues. Aust. Telecomm. Res. 23, 49-55.
• 19: F~TER, M. R., BITME~, R. R., K~NNEDY, R. A., ~3~u ANDERSON, B. D.O. 1989. Rare events and reverse time models. In Proceedings of the Twenty-E~ghth Conference on Deciston and Control (Tampa, FL, Dec 13-15), IEEE Press, Piscataway, N J, 1180 1183.
• 20: 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. Autom. Control 36, 1395-1405
• 21: Gi~RTNER, J. 1977. On large deviations from invariant measure. Theor. Probab. Appl. 22, 24-39.
• 22: R. J. Gibbens , P. J. Hunt, Effective bandwidths for the multi-type UAS channel, Queueing Systems: Theory and Applications, v.9 n.1-2, p.17-28, Oct. 1991 [doi>10.1007/BF01158790]
• 23: GLASSERMSN, P. ~2~D KOU, S.G. 1993. Overflow probabilities in Jackson networks. In Proceedings of the Thirty-Second {EEE Conference on Decision and Control (San Antonio, TX, Dec. 15 17), IEEE Press, Piscataway, NJ, 3178-3182.
• 24: 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]
• 25: GU~RIN, R., AHMADI, H., AND NAGHSHINEH, M. 1991. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Select. Areas Commun. 9, 968-981
• 26: HAMMERSLE~, J. M. AND HANDSCOMB, D. C. 1964. Monte Carlo Methods. Methuen and Co., Ltd., London.
• 27: 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]
• 28: F. P. Kelly, Effective bandwidths at multi-class queues, Queueing Systems: Theory and Applications, v.9 n.1-2, p.5-16, Oct. 1991 [doi>10.1007/BF01158789]
• 29: 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]
• 30: LEHTONEN, T. AND NYRHINEN, H. 1992a. Simulating level-crossing probabilities by importance sampling. Advances Appl. Probab. 24,858-874.
• 31: LEHTONEN, T. AND NYRHINEN, H. 1992b. On asymptotically efficient simulation of ruin probabilities in a Markovian environment. Scand. Actuarial. J., 60 75.
• 32: NICOLA, V. F., S~UDDIN, P., ANn HEZDELBERGER, P. 1993. Techniques for fast simulation of highly dependable systems. In Proceedings of the Second International Workshop on Performability Modeling of Computer and Communication Systems (La Mont Saint-Michel, France, June 28-30).
• 33: NICOLA, V. F., SHAHABUDDIN, P., HEIDELBERGER, P., AND GLYNN, P.W. 1993. Fast simulation of steady-state availability in non-Markovian highly dependable systems. In Proceedings of the Twenty-Third International Symposium on Fault-Tolerant Computing (Toulouse, France, June 22-24), IEEE Computer Society Press, Piscataway, NJ, 38-47.
• 34: P~EKH, S. AND W~D, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Control 34, 54-56.
• 35: S~ows~, J.S. 1993. On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inf. Theory 39, 119-128.
• 36: S~ows~, J. S. 1991. Large deviations and efficient simulation of excessive backlogs in a GI/G/m queue. IEEE Trans. Autom. Control 36, 1383-1394.
• 37: S~DOWSKY, J. S. AND BUCKLEW, J. A. 1990. On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theory 36, 579-588.
• 38: Perwez Shahabuddin, Importance sampling for the simulation of highly reliable Markovian systems, Management Science, v.40 n.3, p.333-352, March 1994 [doi>10.1287/mnsc.40.3.333]
• 39: SIEGMU~D, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Stat. 4, 673-684.
• 40: SMITH, W~ L. 1955. Regenerative stochastic processes. Proc. Roy. Soc. Ser. A 232, 6-31.
• 41: WHirr, W. 1993. Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queues. Telecomm. Syst. 2, 71-107.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Management, Performance

Keywords:
communications switch, importance sampling, packet loss, queuing model, rare event, variance reduction