Efficient Simulation of Population Overflow in Parallel Queues

In this paper we propose a state-dependent importance sampling heuristic to estimate the probability of population overflow in networks of parallel queues. This heuristic approximates the “optimal��? state-dependent change of measure without the need for dif��?cult mathematical analysis or costly optimization involved in adaptive methodologies. Comprehensive simulations of networks with an arbitrary number of parallel queues and different traf��?c intensities yield asymptotically ef��?cient estimates (with relative error increasing sub-linearly in the overflow level) where no other state-independent importance sampling techniques are known to be ef��?cient. The ef��?ciency of the proposed heuristic surpasses those based on adaptive importance sampling algorithms, yet it is easier to determine and implement and scales better for large networks.