Change search
ReferencesLink to record
Permanent link

Direct link
Efficient simulation of network performance by importance sampling
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Telematics.
1998 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Dr.ingeniøravhandling, ISSN 0809-103X ; 1998:33
URN: urn:nbn:no:ntnu:diva-5950OAI: oai:DiVA.org:ntnu-5950DiVA: diva2:234329
Public defence
Totalrommet, NTNU (English)
Available from: 2009-09-21 Created: 2009-09-07 Last updated: 2009-09-21Bibliographically approved

Open Access in DiVA

fulltext(2569 kB)502 downloads
File information
File name FULLTEXT01.pdfFile size 2569 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Heegaard, Poul
By organisation
Department of Telematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 502 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 204 hits
ReferencesLink to record
Permanent link

Direct link