Optimally efficient estimation of the statistics of rare events in queueing networks

Abstract

Because of their rarity, the estimation of the statistics of buffer overflows in networks of queues by direct simulation is very costly. An asymptotically optimal (as the overflow recurrence time becomes large) scheme has been proposed by others, using importance sampling. Two aspects of this scheme are addressed. First, in the existing approach, a numerical minimization is required to generate the simulation network. An equivalent analytic minimization is described. A simple procedure for constructing the optimal simulation network is included. Second, it is shown that the average behaviour of the simulation system is the same as the average behavior of the original network in the period leading up to a buffer overflow. For a sufficiently large buffer size, the optimal simulation system depends only on the statistics of the service rate of one queue (that of the least serviced buffer) and the arrival process, assuming that no two service rates are actually equal, and does not depend in any way on the statistics of the service rates of buffers other than the one dominating the overflow statics