Regenerations in Multiclass Open Queueing Networks

Multiclass open queueing networks find wide applications in communication, computer and fabrication networks. Often one is interested in steady state performance measures associated with these systems. One can use the regenerative structure of the process to estimate the steady state performance measures via regenerative simulation. In a queueing network, if all the interarrival times are Markovian (have exponential distributions), it is easy to identify regeneration instants, e.g., an instant corresponding to an arrival to an empty network. In this presentation, we consider networks where interarrival times are generally distributed but have exponential or fatter tails. We show that such distributions can be decomposed into mixture of sums of independent random variables such that at least one of the components is exponentially distributed. This allows an embedded regenerative structure in the Markov process. We show that under mild conditions on the network primitives, the regenerative mean and standard deviation estimators are consistent and satisfy a joint central limit theorem. This is important as it allows construction of asymptotically valid confidence intervals. We show that amongst all such interarrival time decompositions, the one with largest mean exponential component minimizes the asymptotic variance of the standard deviation estimator.