The Best Paper Award
On-line Estimation by Importance Sampling for the Packet Loss Probability of FIFO Queue
Nobuhiro KOBAYAHI , Kenji NAKAGAWA
i˜a•Ά˜_•ΆŽB@•½¬24”N5ŒŽ†ŒfΪj
Nobuhiro KOBAYAHI Kenji NAKAGAWA        
@In this paper a new method is proposed for estimating the packet loss probability of FIFO (First In First Out) queues, accurately and at high speed, by using importance sampling (IS) simulation. The network simulator NS-2 is used for simulation.
@When estimating the packet loss probability using NS-2, Monte Carlo (MC) simulation is commonly used. However, if the packet loss probability to be estimated is very small, packet loss events of interest do not occur frequently in the MC method, so the simulation takes a long time and the estimator obtained is of low reliability. Therefore the IS method is applied in order to improve the accuracy and speed of the simulation. In the IS method, a different probability distribution from the actual distribution is used to generate low probability events frequently and to obtain an estimator of the target probability by correcting the value obtained.
@In a common IS simulation of packet loss probability, the packet arrival rate is increased to generate loss events more frequently than occurs with the MC method. But in a real network, it is not possible to increase the arrival rate of usersf packets. In this paper, the authors have proposed a new IS method to make the queue length longer by reducing the service rate. More specifically, in parallel with the real packet processing, the length of the virtual queue is made longer by using slow packet processing. In order to implement slow packet processing, utilizing the features of NS-2, which is an event driven simulator, the virtual queue is renewed only at the time of packet arrivals into the queue (enqueue) and departures from the queue (dequeue).
@This paper has produced the following results.
(1) An "online IS" method has been proposed and implemented in NS-2.
(2) A theoretical study has determined the optimal service rate which gives the minimum variance IS estimator.
It is shown that the authorsf method achieved simulation about 4,000 times faster than the MC method under realistic conditions.
@The contribution of this paper is notable from both practical and theoretical points of view which is why it is considered appropriate for paper award.

Close