ALGORITHMS FOR ACCELERATED RARE EVENT SIMULATION WITH MARKOV CHAIN MODELLING IN COMMUNICATION NETWORKS

摘要

The paper recommends an effective approach to estimate the probability of buffer overflow in communication networks. The buffer overflow probability in queuing systems is defined as a rare event and can be estimated using rare event simulation with Markov chains. Two-node queuing networks are considered in this paper; and an event of buffer overflow at the second node is studied. Probability of a rare event that the content of the second buffer would exceed some high level L, starting from a certain state, is analyzed. The approach is based on the Markov additive representation of the buffer processes, leading to exponential change of measure, which is used in an importance sampling method. The examples, considered in this paper, confirm that when the first buffer is finite, the relative error is bound independent of some high level L. However, when the first buffer is infinite, a natural extension of exponential change of measure for finite buffer case is proposed. The relative error is shown to be bound independent of L only when at the second node there is a bottleneck, i.e. buffer overflow may occur. However, when at the first node there is a bottleneck; experimental results confirm that the relative error is linearly bound to the level L. Two efficient rare event simulation algorithms, based on the importance sampling and cross-entropy methods, are developed and applied to accelerate the overflow probability simulation with Markov chains in communication networks. Numerical examples and simulation results are provided.