Skip to content

SCS

Seminar

Snapshot simulation - an importance sampling technique for traffic with heavy tailed flows

Addie, RJ; Pao, DCW; Wong, EWM (Southern Queensland: Hong Kong)
Tuesday 22 June 2010, 15:05-15:30

Seminar Room 1, Newton Institute

Abstract

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. [1] 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. [2] 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.

Presentation

[pdf ]

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧