Informatics and Applications
2017, Volume 11, Issue 2, pp 16-24
ON THE EFFICIENCY OF BRIDGE MONTE-CARLO ESTIMATOR
- O. V. Lukashenko
- E. V Morozov
- M. Pagano
Abstract
Long-term correlation is a key feature of traffic flows and has a deep impact on network performance. Indeed, the arrival rate can persist on relatively high values for a considerable amount of time, provoking long busy periods and possibly bursts of lost packets. The authors focus on Gaussian processes, well-recognized and flexible traffic models, and consider the probability that the normalized cumulative workload grows at least as the length T of the considered interval. As T increases, such event becomes rare and ad-hoc techniques should be used to estimate its probability. To this aim, the authors present a variant of the well-known conditional Monte-Carlo (MC) method, in which the target probability is expressed as a function of the corresponding bridge process. In more detail, they derive the analytical expression of the estimator, verify its effectiveness through simulations (for different sets of parameters), and investigate the effects of the discretization step.
[+] References (28)
- Leland, W. E., M. S. Taqqu, W. Willinger, and D. V. Wil-son. 1994. On the self-similar nature of Ethernet traffic (extended version). IEEE ACM Trans. Network. 2(1):1-15.
- Norros, I. 1995. On the use of fractional Brownian motion in the theory of connectionless networks. IEEEJ. Sel. Area. Comm. 13(6):953-962.
- Mandjes, M. 2007. Large deviations of Gaussian queues. Chichester: Wiley. 340 p.
- Erramilli, A., O. Narayan, and W Willinger. 1996. Ex-perimental queueing analysis with long-range dependent packet traffic. IEEE ACM Trans. Network. 4(2):209-223.
- Samorodnitsky, G. 2007. Long range dependence. Found. TrendsŪ Stochastic Syst. 1(3):163-257. doi: 10.1561/0900000004.
- Allman, M., V. Paxson, and E. Blanton. 2009. TCP Con-gestion Control. RFC 5681 (Draft Standard).
- Kouvatsos, D. D. 2000. Performance evaluation and appli-cations of ATM networks. Kluwer Academic. 472 p.
- Ross, S. M. 2006. Simulation. Elsevier. 314 p.
- Ganesh, A., N. O'Connell, and D. Wischik. 2004. Big queues. Lecture notes in mathematics ser. Springer. 260 p.
- Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Com- put. Simul. 5(1):43-85.
- Glasserman, P., and Y. Wang. 1997. Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7(3):731-746.
- Lukashenko, O.V., E. V. Morozov, andM. Pagano. 2016. On Conditional Monte Carlo estimation of busy period probabilities in Gaussian queues. Comm. Com. Inf. Sc.
601:280-288. doi: 10.1007/978-3-319-30843-2_29.
- Lukashenko, O.V., E. V. Morozov, andM. Pagano. 2016. On the use of a bridge process in a Conditional Monte Carlo simulation of Gaussian queues. Comm. Com. Inf. Sc.
638:207-220. doi: 10.1007/978-3-319-44615-8_18.
- Giordano, S., M. Gubinelli, andM. Pagano. 2005. Bridge Monte-Carlo: A novel approach to rare events of Gaussian processes. 5th St. Petersburg Workshop on Simulation Proceedings. 281-286.
- Norros, I. 1999. Busy periods of fractional Brownian stor-age: A large deviations approach. Adv. Perf. Anal. 2:1-19.
- Mandjes, M., I. Norros, and P. Glynn. 2009. On conver-gence to stationarity of fractional Brownian storage. Ann. Appl. Probab. 19:1385-1403.
- Taqqu, M. S., W Willinger, and R. Sherman. 1997. Proof of a fundamental result in self-similar traffic modeling. Comput. Commun. Rev. 27:5-23.
- Addie, R., P. Mannersalo, and I. Norros. 2002. Most probable paths and performance formulae for buffers with Gaussian input traffic. Eur. Trans. Telecommun. 13:183-196.
- Kulkarni, V., and T. Rolski. 1994. Fluid model driven by an Ornstein-Uhlenbeck process. Probab. Eng. Inform. Sc. 8:403-417.
- Deuschel, J. D., and D. W. Stroock. 1989. Large deviations. Academic Press. 330 p.
- Mandjes, M., P. Mannersalo, I. Norros, andM. vanUitert. 2006. Large deviations of infinite intersections of events in Gaussian processes. Stoch. Proc. Appl. 116:1269-1293.
- Dieker, A. B. 2005. Conditional limit theorems for queues with Gaussian input: A weak convergence approach. Stoch. Proc. Appl. 115(5):849-873.
- Dieker, A. B., and M. Mandjes. 2005. On asymptotically efficient simulation of large deviation probabilities. Adv. Appl. Probab. 37:539-552.
- Dieker, A. B., and M. Mandjes. 2006. Fast simulation of overflow probabilities in a queue with Gaussian input. ACMTrans. Model. Comput. Simul. 16:119-151.
- Asmussen, S., ans P. Glynn. 2007. Stochastic simulation: Algorithms and analysis. Springer. 476 p.
- Giordano, S., M. Gubinelli, andM. Pagano. 2007. Rare events of Gaussian processes: A performance comparison between Bridge Monte-Carlo and Importance Sampling. Next generation teletraffic and wired/wireless advanced networking. Eds. Y. Koucheryavy, J. Harju, andA. Sayenko. Computer communication networks and telecommunications ser. Berlin-Heidelberg: Springer. 4712:269-280.
- Lukashenko, O. V., E. V. Morozov, andM. Pagano. 2012. Performance analysis of Bridge Monte-Carlo estimator. Transactions ofKarRC RAS 5:54-60.
- Gut, A. 2009. An intermediate course in probability. Springer. 304 p.
[+] About this article
Title
ON THE EFFICIENCY OF BRIDGE MONTE-CARLO ESTIMATOR
Journal
Informatics and Applications
2017, Volume 11, Issue 2, pp 16-24
Cover Date
2017-06-30
DOI
10.14357/19922264170202
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
Gaussian processes; conditional Monte Carlo; bridge process; rare events; variance reduction
Authors
O. V. Lukashenko  ,  , E. V Morozov , , and M. Pagano 
Author Affiliations
Institute of Applied Mathematical Research of Karelian Research Centre of the Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Republic of Karelia, Russian Federation
Petrozavodsk State University, 33 Lenin Str., Petrozavodsk 185910, Republic of Karelia, Russian Federation
University of Pisa, 43 Lungarno Pacinotti, Pisa 56126, Italy
|