Estimation of the statistics of rare events in data communications systems

Abstract

There are many examples of rare events in telecommunications systems, including buffer overflows in queueing systems, cycle slipping in phase-locked loops and the escape of adaptive equalizers from local (possibly incorrect) equilibria. In many cases, factors such as the high cost of the occurrence of these events mean that their statistics are of interest in spite of their rarity. The estimation of the statistics of these rare events via direct simulation is very time consuming, simply because of their rarity. In fact, the required simulation time can be so high as to make simulation not just difficult, but impossible. One technique that can be used to speed up simulations of rare events is importance sampling, in which the statistics of the event in which we are interested are inferred from the statistics (obtained by simulation) of some (less rare) event in a different system. Because the events are less rare, the simulation time is reduced. However, there remains the problem of maximizing the speedup to ensure that the simulation time is minimized. It has been shown previously that as the rarity of the events increases, large deviations theory can be used to create a simulation system that is optimal in the sense of minimizing the variance of a probability estimator in the simulation of a rare event. In this thesis, we extend these results, and also apply them to a number of specific applications for which we obtain analytic expressions for an asymptotically optimal simulation system. Examples studied include multiple-priority data streams and a number of queues with deterministic servers, which can be used in the modeling of asynchronous transfer mode (ATM) switches. In the case of buffer overflows in queueing systems, it will be shown that the required simulation time is reduced from being exponential in the buffer size for direct simulation , to being linear in the buffer size using the asymptotically optimal simulation system, and that this holds even for relatively small buffer sizes. While much of the previous work on fast simulation of rare events has concentrated on the use of large deviations and expon-ential changes of measure, we look beyond this class, and show that it is possible to obtain larger increases in simulation speed, using, for example, the reverse-time model of the system being studied. In fact , it is possible to obtain an infinite speedup. However, doing this may require omniscience, i.e. effectively knowing the answer before we start. In addition to the investigation of methods for performing fast simulation, the relationship between optimal control, large deviations and reverse-time modeling is explored, with particular reference to rare events. It is shown that, in addition to the previously known relationship between optimal control and large deviations, a similar relationship exists between optimal control and reverse-time modeling, in which the trajectory defining the solution of the optimal control problem in which control energy is minimized defines the mean path of the reverse-time model of the process.