Informatics and Applications
2017, Volume 11, Issue 2, pp 1624
ON THE EFFICIENCY OF BRIDGE MONTECARLO ESTIMATOR
 O. V. Lukashenko
 E. V Morozov
 M. Pagano
Abstract
Longterm 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, wellrecognized 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 adhoc techniques should be used to estimate its probability. To this aim, the authors present a variant of the wellknown conditional MonteCarlo (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. Wilson. 1994. On the selfsimilar nature of Ethernet traffic (extended version). IEEE ACM Trans. Network. 2(1):115.
 Norros, I. 1995. On the use of fractional Brownian motion in the theory of connectionless networks. IEEEJ. Sel. Area. Comm. 13(6):953962.
 Mandjes, M. 2007. Large deviations of Gaussian queues. Chichester: Wiley. 340 p.
 Erramilli, A., O. Narayan, and W Willinger. 1996. Experimental queueing analysis with longrange dependent packet traffic. IEEE ACM Trans. Network. 4(2):209223.
 Samorodnitsky, G. 2007. Long range dependence. Found. TrendsŪ Stochastic Syst. 1(3):163257. doi: 10.1561/0900000004.
 Allman, M., V. Paxson, and E. Blanton. 2009. TCP Congestion Control. RFC 5681 (Draft Standard).
 Kouvatsos, D. D. 2000. Performance evaluation and applications 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):4385.
 Glasserman, P., and Y. Wang. 1997. Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7(3):731746.
 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:280288. doi: 10.1007/9783319308432_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:207220. doi: 10.1007/9783319446158_18.
 Giordano, S., M. Gubinelli, andM. Pagano. 2005. Bridge MonteCarlo: A novel approach to rare events of Gaussian processes. 5th St. Petersburg Workshop on Simulation Proceedings. 281286.
 Norros, I. 1999. Busy periods of fractional Brownian storage: A large deviations approach. Adv. Perf. Anal. 2:119.
 Mandjes, M., I. Norros, and P. Glynn. 2009. On convergence to stationarity of fractional Brownian storage. Ann. Appl. Probab. 19:13851403.
 Taqqu, M. S., W Willinger, and R. Sherman. 1997. Proof of a fundamental result in selfsimilar traffic modeling. Comput. Commun. Rev. 27:523.
 Addie, R., P. Mannersalo, and I. Norros. 2002. Most probable paths and performance formulae for buffers with Gaussian input traffic. Eur. Trans. Telecommun. 13:183196.
 Kulkarni, V., and T. Rolski. 1994. Fluid model driven by an OrnsteinUhlenbeck process. Probab. Eng. Inform. Sc. 8:403417.
 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:12691293.
 Dieker, A. B. 2005. Conditional limit theorems for queues with Gaussian input: A weak convergence approach. Stoch. Proc. Appl. 115(5):849873.
 Dieker, A. B., and M. Mandjes. 2005. On asymptotically efficient simulation of large deviation probabilities. Adv. Appl. Probab. 37:539552.
 Dieker, A. B., and M. Mandjes. 2006. Fast simulation of overflow probabilities in a queue with Gaussian input. ACMTrans. Model. Comput. Simul. 16:119151.
 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 MonteCarlo and Importance Sampling. Next generation teletraffic and wired/wireless advanced networking. Eds. Y. Koucheryavy, J. Harju, andA. Sayenko. Computer communication networks and telecommunications ser. BerlinHeidelberg: Springer. 4712:269280.
 Lukashenko, O. V., E. V. Morozov, andM. Pagano. 2012. Performance analysis of Bridge MonteCarlo estimator. Transactions ofKarRC RAS 5:5460.
 Gut, A. 2009. An intermediate course in probability. Springer. 304 p.
[+] About this article
Title
ON THE EFFICIENCY OF BRIDGE MONTECARLO ESTIMATOR
Journal
Informatics and Applications
2017, Volume 11, Issue 2, pp 1624
Cover Date
20170630
DOI
10.14357/19922264170202
Print ISSN
19922264
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
