Dynamic importance sampling for tandem Jackson networks

Prior to the results in this thesis, the construction of a general asymptotically optimal IS scheme for the estimation of buffer overflows in two tandem M/M/1 queues sharing a single buffer was an open problem despite the considerable attention it received since the 1980's when early work began to appear on it. Two tandem M/M/1 queues is the simplest possible queueing network. What makes this problem difficult is the constraining boundaries of the state space of the process that represents the queue populations. In this thesis we use a game framework for importance sampling (IS) to study the construction of asymptotically optimal importance sampling schemes for buffer overflow events of stable Jackson networks. The main tool in this framework is an Isaacs Equation and a set of boundary conditions, which are derived from a game representation of the problem. We prove that for any stable open Jackson network, the problem of constructing asymptotically optimal IS schemes is equivalent to constructing smooth subsolutions to the Isaacs equation and the boundary conditions. We construct smooth subsolutions for the following two events: (1) The population of a tandem network with two or more nodes reaching a level n before the network empties. The system is assumed to be initially empty. This case covers the open problem mentioned in the first paragraph. (2) In a two-node tandem Jackson network with a separate finite buffer for each node, one of the buffers reach capacity before the network empties. The system is assumed to be initially empty. Smooth subsolutions for both of these rare events are smoothed versions of simple affine functions and lead to efficient and easily implementable IS algorithms.;We cover many practical aspects of subsolution construction such as various smoothing methods, linear (Neumann) and nonlinear boundary conditions of the Isaacs equation.;Finally, we prove that the IS schemes generated by this approach are robust in that small errors made in the construction of smooth subsolutions translate into small deviations of the IS schemes from asymptotic optimality.