Dynamic Importance sampling for queueing networks

Importance sampling is the most commonly used technique for speeding up Monte Carlo simulation of rare events. However, little is understood in the design of efficient importance sampling algorithms in the context of queueing networks. The standard approach, which simulates the system using an a priori fixed change of measure sug-gested by large deviation analysis, has been shown to fail even in the simplest setting such as two-node tandem networks. Exploiting the connection between importance sampling and differ-ential games, we demonstrate that one can build simple and efficient dynamic importance sampling schemes based on classical subsolutions of the corresponding Isaacs equation. The model we use to illustrate this approach is d-node tandem Jackson networks and rare-events of interest are various types of buffer overflows includes total population overflow and individual buffer overflows