A large deviations analysis of the transient of a queue with many Markov fluid inputs: approximations and fast simulation

ABSTRACT

This article analyzes the transient buffer content distribution of a queue fed by a large number of Markov fluid sources. We characterize the probability of overflow at time t, given the current buffer level and the number of sources in the on-state. After scaling buffer and bandwidth resources by the number of sources n, we can apply large deviations techniques. The transient overflow probability decays exponentially in n. In case of exponential on/off sources, we derive an expression for the decay rate of the rare event probability under consideration. For general, Markov fluid sources, we present a plausible conjecture. We also provide the "most likely path" from the initial state to overflow (at time t). Knowledge of the decay rate and the most likely path to overflow leads to (i) approximations of the transient overflow probability, and (ii) efficient simulation methods of the rare event of buffer overflow. The simulation methods, based on importance sampling, give a huge speed-up compared to straightforward simulations. The approximations are of low computational complexity, and accurate, as verified by means of simulation experiments.

REFERENCES

• 1: V. Anantharam, How large delays build up in a GI/G/1 quqe, Queueing Systems: Theory and Applications, v.5 n.4, p.345-368, November 1989 [doi>10.1007/BF01225324]
• 2: Anick, D., Mitra, D., and Sondhi, M. 1982. Stochastic theory of a data-handling system with multiple sources. Bell Syst. Tech. J. 61, 1871--1894.
• 3: Asmussen, S. and Rubinstein, R. 1995. Steady state rare event simulation in queueing models and its complexity properties. In Advances in Queueing Theory, Theory, Methods and Open Problems, J. Dshalalow, Ed. CRC Press, Boca Raton, USA, 429--461.
• 4: Bahadur, R. and Rao, R. R. 1960. On deviations of the sample mean. Ann. Math. Stat. 31, 1015--1027.
• 5: Botvich, D. and Duffield, N. 1995. Large deviations, the shape of the loss curve, and economies of scale in large multiplexers. Queue. Syst. 20, 293--320.
• 6: Brandt, A. and Brandt, M. 1994. On the distribution of the number of packets in the fluid flow approximation of packet arrival streams. Queue. Syst. 17, 275--315.
• 7: Cohen, J. 1974. Superimposed renewal processes and storage with gradual input. Stochast. Proc. Appl. 2, 31--57.
• 8: Cottrell, M., Fort, J.-C., and Malgouyres, G. 1983. Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automat. Cont. 28, 907--920.
• 9: Courcoubetis, C. and Weber, R. 1996. Buffer overflow asymptotics for a buffer handling many traffic sources. J. Appl. Prob. 33, 886--903.
• 10: N. G. Duffield, Conditioned asymptotics for tail probabilities in large multiplexers, Performance Evaluation, v.31 n.3-4, p.281-300, Jan. 1998 [doi>10.1016/S0166-5316(97)00004-7]
• 11: Dupuis, P. and Ellis, R. 1997. A Weak Convergence Approach to the Theory of Large deviations. Wiley, New York.
• 12: Gelfand, I. and Fomin, S. 1963. Calculus of Variations. Prentice-Hall, Englewood Cliffs, N.J.
• 13: 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]
• 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: George Kesidis , Jean Walrand , Cheng-Shang Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.424-428, Aug. 1993 [doi>10.1109/90.251894]
• 16: Charles Knessl , J. A. Morrison, Heavy-traffic analysis of a data-handling system with many sources, SIAM Journal on Applied Mathematics, v.51 n.1, p.187-213, Feb. 1991 [doi>10.1137/0151012]
• 17: Kobayashi, H. and Ren, Q. 1992. A mathematical theory for transient analysis of communication networks. IEICE Trans. Commun. E75-B, 1226--1276.
• 18: Kosten, L. 1974. Stochastic theory of a multi-entry buffer, part 1. Delft Progress Report, Series F 1.
• 19: Kosten, L. 1984. Stochastic theory of data-handling systems with groups of multiple sources. In Performance of Computer-Communication Systems, H. Rudin and W. Bux, Eds. Elsevier, Amsterdam, the Netherlands, 321--331.
• 20: Kroese, D. and Nicola, V. 1998. Efficient simulation of backlogs in fluid flow lines. AEU International Journal on Electronics and Communications 52, 165--171.
• 21: Dirk P. Kroese , Victor F. Nicola, Efficient simulation of a tandem Jackson network, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.411-419, December 05-08, 1999, Phoenix, Arizona, United States [doi>10.1145/324138.324264]
• 22: Mandjes, M. 1999. Rare event of the state frequencies of a large number of markov chains. Stochastic Models 15, 577--592.
• 23: Mandjes, M. and Ridder, A. 1995. Finding the conjugate of Markov fluid processes. Prob. Engin. Inf. Sci. 9, 297--315.
• 24: Michel Mandjes , Ad Ridder, Optimal trajectory to overflow in a queue fed by a large number of sources, Queueing Systems: Theory and Applications, v.31 n.1-2, p.137-170, 1999 [doi>10.1023/A:1019154129708]
• 25: Parekh, S. and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Automat. Cont. 34, 54--66.
• 26: Ridder, A. 1996. Fast simulation of markov fluid models. J. Appl. Prob. 33, 786--803.
• 27: Ridder, A. 1999. Efficient simulation of fluid queues with many sources. In Proceedings of the 2nd International Workshop on Rare Event Simulation. University of Twente, Netherlands, 19--27.
• 28: Sadowsky, J. 1991. Large deviations and efficient simulation of excessive backlogs in a GI/G/m queue. IEEE Trans. Automat. Cont. 36, 1383--1394.
• 29: Mischa Schwartz, Broadband integrated networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 30: Shwartz, A. and Weiss, A. 1995. Large Deviations for Performance Analysis, Queues, Communication, and Computing. Chapman and Hall, New York.
• 31: Simonian, A. and Guibert, J. 1995. Large deviations approximation for fluid queues fed by a large number of on/off sources. IEEE J. Sel. Areas Commun. 13, 1017--1027.
• 32: Takeshi Tanaka , On Hashida , Yukio Takahashi, Transient analysis of fluid model for ATM statistical multiplexer, Performance Evaluation, v.23 n.2, p.145-162, Aug. 1995 [doi>10.1016/0166-5316(94)00048-O]
• 33: Tijms, H. 1994. Stochastic Models. An Algorithmic Approach. Wiley, New York.
• 34: Weiss, A. 1986. A new technique of analyzing large traffic systems. Adv. Appl. Prob. 18, 506--532.
• 35: Wischik, D. 2001. Sample path large deviations for queues with many inputs. Ann. Appl. Prob.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory

General Terms:
Algorithms, Performance

Keywords:
ATM multiplexers, IP routers, buffer overflow, calculus of variations, importance sampling simulations, large deviations asymptotics, queuing theory, transient probabilities