Snapshot simulation - an importance sampling technique for traffic with heavy tailed flows
Seminar Room 1, Newton Institute
Two key ideas have informed importance sampling and rare event sampling of traffic models in
the scientific literature: (i) distortion of probabilities together with use of the likelihood ratio to
correct the collected statistics, and (ii) the restart method, or particle methods, in which many
simulation threads are run simultaneously and the threads which focus on the rare events of interest
are selected, and the collected statistics are corrected by keeping an appropriate weight for each
thread. However, these methods fail when applied to traffic processes with heavy-tailed flow lengths
because the threads must be very long in order to adequately explore the state space of the system,
including the region containing the rare events whose probability we wish to measure.
In this paper a new method which is able to quickly simulate very long simulation threads will be
described [1, 2]. In this method all threads are infinitely long but the level of detail in the thread
reduces (to zero, in the limit) as the time coordinate of the thread approaches -1. Threads may
be distorted by a likelihood ratio, and threads may be selected and duplicated, so this method is
complementary to the two importance sampling techniques described above.
In this paper the method will be extended to allow observation of delays between successive events
as well as merely the statistics of the state of the system at a certain point in time. This requires
care to ensure that the events observed are not unduly affected by the omitted details.
 R. G. Addie, “Snapshot simulation of internet traffic: fast and accurate for heavy-tailed flows,”
in Proceedings of the 1st International Workshop on the Evaluation of Quality of Service through
Simulation in the Future Internet. March 2008, ICST.
 R. G. Addie, “Snapshot simulation of internet traffic: queueing of fixed-rate flows,” in Proceedings
of the 2nd International Workshop on the Evaluation of Quality of Service through
Simulation in the Future Internet. March 2009, ICST.