Overflow probabilities in Jackson networks

We first consider overflow probabilities in arbitrary, stable Jackson networks. We show that if each node i has utilization parameter ρ_i<1, and if p_K denotes the probability that starting from zero the network population reaches K before returning to zero, then lim/K→∞K^-1 log p_K =max/i log (ρ_i). We then specialize to the case of a two-node tandem network and analyze the performance of an importance sampling estimator for p_K based on interchanging the arrival rate and the smaller service rate, a heuristic proposed by Parekh and Walrand (1989). We give a necessary condition for this scheme to be asymptotically efficient, and a separate sufficient condition. Our approach may prove useful in studying other importance sampling problems with boundaries