Study on Estimating Buffer Overflow Probabilities in High-Speed Communication Networks
DOI:
https://doi.org/10.13052/jcsm2245-1439.343Keywords:
high-speed communication networks, estimating probability of buffer overflow, two-node queuing system with feedback, Importance sampling method, Cross-entropy method, self-similar queuing system, RESTART method with limited relative error techniqueAbstract
The paper recommends new methods to estimate effectively the probabilities of buffer overflow in high-speed communication networks. The frequency of buffer overflow in queuing system is very small; therefore the overflow is defined as rare event and can be estimated using rare event simulation with continuous-time Markov chains. First, a two-node queuing system is considered and the buffer overflow at the second node is studied. Two efficient rare event simulation algorithms, based on the Importance sampling and Cross-entropy methods, are developed and applied to accelerate the buffer overflow simulation with Markov chain modeling. Then, the buffer overflow in self-similar queuing system is studied and the simulations with long-range dependent self-similar traffic source models are conducted. A new efficient simulation algorithm, based on the RESTART method with limited relative error technique, is developed and applied to accelerate the buffer overflow simulation with SSM/M/1/B modeling using different parameters of arrival processes and different buffer sizes. Numerical examples and simulation results are provided for all methods to estimate the probabilities of buffer overflow, proposed in this paper.
Downloads
References
Bobbio, A., Horváth, A., Scarpa, M., Telek, M. “Acyclic discrete phase type distributions: Properties and a parameter estimation algorithm.” Performance Evaluation, 54(1), 1–32, 2003.
Bolch, G., Greiner, S., Meer, H, Trivedi, K. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, NY: John Wiley & Sons, 1998.
Bueno, D. R., Srinivasan, R., Nicola, V., van Etten, W., Tattje, H. “Adaptive Importance Sampling for Performance Evaluation and Parameter Optimization of Communication Systems.” IEEE Transactions on Communications, 48(4), 557–565, 2000.
Bucklew, J. “An Introduction to Rare Event Simulation.” Springer Series in Statistics, XI, Berlin: Springer-Verlag, 2004.
C´erou, F., LeGland F., Del Moral P., and Lezaud P. “Limit theorems for the multilevel splitting algorithm in the simulation of rare events”. Proceedings of the 2005 Winter Simulation Conference, San Diego, USA, 682–691, 2005.
De Boer, P., Kroese, D., Rubinstein, R. “Estimating buffer overflows in three stages using cross-entropy.” Proceedings of the 2002 Winter Simulation Conference, San Diego, USA, 301–309, 2002.
Georg, C., Schreiber, F. “The RESTART/LRE method for rare event simulation”, Proceedings of the Winter Simulation Conference, Coronado, CA, USA, 390–397, 1996.
Giambene, G. Queueing Theory and Telecommunications: Networks and Applications. NY: Springer, 2005.
Heidelberger, P. “Fast Simulation for Rare Event in Queueing and Reliability Models.” ACM Transactions of Modeling and Computer Simulation, 5 (1), 43–85, 1995.
Kalashnikov, V. Geometric Sums: Bounds for Rare Events with Applications: Risk Analysis, Reliability, Queueing. Berlin: Kluwer Academic Publishers, 1997.
Keith, J., Kroese, D.P. “SABRES: Sequence Alignment by Rare Event Simulation.” Proceedings of the 2002 Winter Simulation Conference, San Diego, USA, 320–327, 2002.
Kroese, D., Nicola, V.F. “Efficient Simulation of a Tandem Jackson Network.” Proceedings of the Second International Workshop on Rare Event Simulation RESIM'99, 197–211, 1999.
Lokshina, I. “Study on Estimating Probability of Buffer Overflow in HighSpeed Communication Networks.” Proceedings of the 2014 Networking and Electronic Commerce Conference (NAEC 2014, Trieste, Italy, 306–321, 2014.
Lokshina, I. “Study about Effects of Self-similar IP Network Traffic on Queuing and Network Performance.” Int. J. Mobile Network Design and Innovation, 4(2), 76–90, 2012.
Lokshina, I., Bartolacci M. “Accelerated Rare Event Simulation with Markov Chain Modelling in Wireless Communication Networks.” Int. J. Mobile Network Design and Innovation, 4(4), 185–191, 2012.
Radev, D., Lokshina, I. “Performance Analysis of Mobile Communication Networks with Clustering and Neural Modelling”. Int. J. Mobile Network Design and Innovation, 1(3/4), 188–196, 2006-a.
Radev, D., Lokshina, I. “Rare Event Simulation with Tandem Jackson Networks.” Proceedings of the Fourteen International Conference on Telecommunication Systems: Modeling and Analysis – ICTSM 2006, Penn State Berks, Reading, PA, USA, 262–270, 2006-b.
Radev, D., Lokshina, I. “Advanced Models and Algorithms for Self-Similar Network Traffic Simulation and Performance Analysis”, Journal of Electrical Engineering, Vol. 61(6), 341–349, 2010.
Rubino G, Tuffin B. Rare Event Simulation using Monte Carlo Methods, UK: John Wiley & Sons, 2009.
Villen-Altamirano, M., Villen-Altamirano, J. “On the efficiency of RESTART for multidimensional systems.” ACM Transactions on Modeling and Computer Simulation, 16 (3), 251–279, 2006.
