Efficient simulation of network performance by importance sampling

Abstract

Simulation is a flexible means for assessment of the quality of service offered by a telecommunication system. However, when very strict requirements are put on the quality of service, the simulation becomes inefficient because the performance depends on rare events to occur. A rare event is, for instance, a cell loss or a system breakdown. A simulation technique that speeds up the experiments must be added. Various techniques are known from the literature and they should be combined to achieve additional speedups. The most efficient speedup techniques for systems dependent on rare events, are importance sampling and RESTART. The importance sampling technique is very sensitive to the change of the underlying simulation process. This is denoted the biasing of the simulation parameters. In this thesis, explicit expressions of the variance of importance sampling estimates and the likelihood ratio are developed for an M/M/1/N queue. The study of how the variance expressions vary as the biasing changes, demonstrates that the importance sampling is very efficient in a narrow region, and that the variance is unbounded outside. It is also observed that, seemingly, the likelihood ratio and its variance may be used as an indication of the accuracy of simulation results, in combination with the variance of the estimate itself. Neither importance sampling nor RESTART are easily applied to multidimensional models, e.g. a model of a telecommunication network with a variety of different users. In this thesis, the focus is on how to do importance sampling simulations of telecommunication networks with balanced utilisation of the resources. A network system are described by a multidimensional model. The balanced resource utilisation implies that the system performance is not given by a single bottleneck. Hence, previous approaches for importance sampling biasing are no longer efficient. The reason is that they assume that the performance of a single resource significantly constrains the system performance, and under this assumption, the parameters can be biased with respect to the bottleneck resource only.A new adaptive biasing technique is defined for dynamically setting up the simulation parameters in the importance sampling experiment. This is the major contribution of this thesis, and it has been successfully applied to several networks. The basic idea is to change the simulation parameters to make the simulation process move toward the parts of the state space where the most important rare events occur. Because this importance depends on the current state, the change of parameters is adapted to the state changes in the simulation process. The networks used for feasibility demonstration are offered traffic from (i) users with different resource capacities and traffic parameters, (ii) users with and without alternative routing strategies, and (iii) users with different preemptive priority levels and a network with a link failure. The simulation results are validated by comparison with exact results, rough dimensioning rules, and correctness indicators given by the observed likelihood ratio.