KALASHNIKOV MEMORIAL SEMINAR Efficient Simulation of Buffer Overflow in Queueing Networks

Consider a continuous-time queueing network with probabilistic routing, including feedback. External batch arrival and batch service processes are characterized by independent Markov additive processes (MAPs). An effective change of measure is proposed for use in importance sampling procedure to estimate the probability of buffer overflow in an arbitrary (‘target’) queue during its busy period. The change of measure is state-independent and is obtained by exponentially twisting the original arrival and service processes as well as the routing probabilities. Assuming that, under the change of measure, all queues (except the target queue) are either stable or ‘critical, ’ we determine the twisting parameters by solving a non-linear optimization problem subject to appropriate inequality constraints. Under some assumptions, it can be shown that a large amount of variance reduction is guaranteed. Experimental results using the proposed change of measure indicate that the relative error of the obtained estimates grows sub-linearly with the overflow level. 1. BACKGROUND A significant literature exists on the efficient estimation (via simulation) of extremely small probabilities of rare events, such as buffer overflows in special classes of queueing networks. Parekh and Walrand (1989) were the first to present a heuristic for efficiently simulating networks with single server at each queue an