Fast estimation of the statistics of excessive backlogs in tandem networks of queues

Abstract

The estimation of the statistics of buffer overflows in networks of queues is inherently costly, simply because of the rarity of these events. This paper presents two extensions to the known theory for finding optimal transformations for simulating such networks. The first is a direct proof of the asymptotic (as buffer size becomes large) optimality of exchanging the arrival and service rates in the simulation of an M/M/1 queue under the assumption that the arrival and service rates of the simulation system are state-independent. The second extension is a proof, using large deviations theory, that a similar technique can be used for tandem networks of queues. This transformation is also shown to be unique.