This Article Abstract Free Full Text (Free PDF) Free Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Woudt, E. Articles by van Ommeren, J.-K. Search for Related Content Social Bookmarking                         What's this?

Improving Adaptive Importance Sampling Simulation of Markovian Queueing Models using Non-parametric Smoothing

Department of Electrical Engineering, Mathematics and Computer Science University of Twente, Enschede, The Netherlands

Pieter-Tjerk de Boer

Department of Electrical Engineering, Mathematics and Computer Science University of Twente, Enschede, The Netherlands, ptdeboer{at}cs.utwente.nl

Jan-Kees van Ommeren

Department of Electrical Engineering, Mathematics and Computer Science University of Twente, Enschede, The Netherlands

Previous work on state-dependent adaptive importance sampling techniques for the simulation of rare events in Markovian queueing models used either no smoothing or a parametric smoothing technique, which was known to be non-optimal. In this paper, we introduce the use of kernel smoothing in this conteXt. We derive eXpressions for the smoothed transition probabilities, compare several variations of the technique, and eXplore the choice of kernel width. We provide some eXamples, demonstrating that the technique significantly improves convergence and estimator variance.

Key Words: rare-event simulation • importance sampling • queueing networks

References

• Parekh, S. and J. Walrand. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Transactions on Automatic Control 34, 54-66.[CrossRef][Web of Science]
• Sadowsky, J.S. 1991. Large deviations theory and efficient simulation of excessive backlogs in a gi/gi/m queue. IEEE Transactions on Automatic Control 36, 1383-1394.[CrossRef][Web of Science]
• Glasserman, P. and S.-G. Kou. 1995. Analysis of an importance sampling estimator for tandem queues. ACM Transactions on Modeling and Computer Simulation 5(1), 22-42.[CrossRef]
• de Boer, P.T. 2006. Analysis of state-independent IS measures for the two-node tandem queue. ACM Transactions on Modeling and Computer Simulation 16, 225-250.[CrossRef][Web of Science]
• Nicola, V.F. and T.S. Zaburnenko. 2005. Importance sampling simulation of population overflow in two-node tandem networks. In 2nd International Conference on the Quantitative Evaluation of Systems, QEST'05, pp. 220-229.
• Kroese, D.P. and V.F. Nicola. 2002. Efficient simulation of a tandem jackson network. ACM Transactions on Modeling and Computer Simulation 12(2), 119-141.[CrossRef]
• Dupuis, P., A.D. Sezer, and H. Wang. 2007. Dynamic importance sampling for queueing networks. Ann. Appl. Probab., 17(4), 1306-1346.[CrossRef]
• Devetsikiotis, M. and J.K. Townsend. 1993. Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks. IEEE/ACM Transactions on Networking 1, 293-305.[CrossRef]
• de Boer, P.T. and V.F. Nicola. 2002. Adaptive state-dependent importance sampling simulation of markovian queueing networks. European Transactions on Telecommunications 13(4), 303-315.[Web of Science]
• Ahamed, T.P.I., V.S. Borkar, and S. Juneja. 2006. Adaptive importance sampling technique for Markov chains using stochastic approximation. Operations Research 54(3), 489-504. ISSN 0030-364X.[Abstract/Free Full Text]
• de Boer, P.T. 2000. Analysis and efficient simulation of queueing models of telecommunication systems. Ph.D. thesis, University of Twente.
• Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Transactions on Modeling and Computer Simulation 5, 43-85.[CrossRef]
• de Boer, P.T., D.P. Kroese, S. Mannor, and R.Y. Rubinstein. 2005. A tutorial on the cross-entropy method. Annals of Operations Research 134(1), 19-67.[CrossRef][Web of Science]
• Woudt, E. 2006. Optimization of simulation of overflows in Markovian queueing models. MSc thesis, University of Twente.
• Wand, M. and M. Jones. 1995. Kernel smoothing, volume 60 of Monographs on statistics and applied probability. London: Chapman & Hall.
• Yang, L. and R. Tschernig. 1999. Multivariate bandwidth selection for local linear regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 61(4), 793-815.[CrossRef][Web of Science]
• Frater, M.R., T.M. Lennon, and B.D. Anderson. 1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Transactions on Automatic Control 36, 1395- 1405.[CrossRef][Web of Science]

SIMULATION, Vol. 83, No. 12, 811-820 (2007)
DOI: 10.1177/0037549707087223


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This Article Abstract Free Full Text (Free PDF) Free Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Woudt, E. Articles by van Ommeren, J.-K. Search for Related Content Social Bookmarking                         What's this?