Optimally Efficient Estimation of the Statistics of Rare Events in Queueing Networks

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. This paper addresses two aspects of this scheme. First, in the existing approach, a numerical minimization is required to generate the simulation network. This paper describes an equivalent analytic minimization. A simple procedure for constructing the optimal simulation network is included. Second, it is shown that the average behavior of the simulation system is the same as the average behavior of the original network in the period leading up to a buffer overflow.