Perturbation analysis for control and optimization of queueing systems: An overview and the state of the art

Perturbation Analysis (PA) has evolved over the past ten years as a methodology for estimating performance gradients with respect to parameters of Discrete Event Dynamic Systems, and particularly, queueing systems, from information extracted from a single observed sample path. This paper is a self-contained tutorial on the state of the art in this field. The authors develop the principles of Infinitesimal PA (IPA) in terms of evaluating derivatives of sample functions and using them as unbiased estimators of performance derivatives for certain classes of queueing systems. They then present extensions of IPA, including an overview of recent results. Finally, the authors provide a broader view of PA as a means for global performance response surface estimation for both continuous and discrete parameters.