This paper presents a framework for analyzing time complexity of rare events estimators for queueing models. In particular, it deals with polynomial and exponential time switching regenerative (SR) estimators for the steady state probabilities of excessive backlog in the GI/GI/1 queue and some of its extensions. The SR estimators are based on large deviation theory and exponential change of measure, which is parametrized by a scalar t. The authors show how to find the optimal value w of parameter t, which leads to the optimal exponential change of measure (OECM), and they find conditions under which the OECM generates polynomial time estimators. Finally, the authors investigate the ‘robustness’ of the proposed SR estimators, in the sense that they find how much one can perturb the optimal value w in the OECM such that the Sr estimator still leads to a dramatic variance reduction and is still useful in practice. The present numerical results suggest that if optimal parameter value w is perturbed up to 20%, the authors only lose 2-3 orders of magnitude of variance reduction compared to the orders of tenth under the optimal value w.
