Sample path methods in the control of queues

Sample path methods are now among the most used techniques in the control of queueing systems. However, due to the lack of mathematical formalism, they may appear to be non-rigorous and even sometimes mysterious. The goal of this paper is threefold: to provide a general mathematical setting, to survey the most popular sample path methods including forward induction, backward induction and interchange arguments, and to illustrate our approach through the study of a number of classical scheduling and routing optimization problems arising in queueing theory.Z. Liu was supported in part by the CEC DG XIII under the ESPRIT BRA grants QMIPS.P. Nain was supported in part by NSF under grant NCR-9116183 and by the CEC DG XIII under the ESPRIT BRA grants QMIPS.D. Towsley was supported in part by NSF under grant NCR-9116183.