Sample-Path Analysis of Queueing Systems, 1999
International Series in Operations Research & Management Science Series, Vol. 11

Sample-Path Analysis of Queueing Systems uses a deterministic (sample-path) approach to analyze stochastic systems, primarily queueing systems and more general input-output systems. Among other topics of interest it deals with establishing fundamental relations between asymptotic frequencies and averages, pathwise stability, and insensitivity. These results are utilized to establish useful performance measures. The intuitive deterministic approach of this book will give researchers, teachers, practitioners, and students better insights into many results in queueing theory. The simplicity and intuitive appeal of the arguments will make these results more accessible, with no sacrifice of mathematical rigor. Recent topics such as pathwise stability are also covered in this context.
The book consistently takes the point of view of focusing on one sample path of a stochastic process. Hence, it is devoted to providing pure sample-path arguments. With this approach it is possible to separate the issue of the validity of a relationship from issues of existence of limits and/or construction of stationary framework. Generally, in many cases of interest in queueing theory, relations hold, assuming limits exist, and the proofs are elementary and intuitive. In other cases, proofs of the existence of limits will require the heavy machinery of stochastic processes. The authors feel that sample-path analysis can be best used to provide general results that are independent of stochastic assumptions, complemented by use of probabilistic arguments to carry out a more detailed analysis. This book focuses on the first part of the picture. It does however, provide numerous examples that invoke stochastic assumptions, which typically are presented at the ends of the chapters.

1. Introduction and Overview.- 1.1 Introduction.- 1.2 Elementary Properties of Point Processes: Y = ?X.- 1.3 Little’s Formula: L = ?W.- 1.4 Stability and Imbedded Properties of Input-Output Systems.- 1.5 Busy-Period Analysis.- 1.6 Conditional Properties of Queues.- 1.7 Comments and References.- 2. Background and Fundamental Results.- 2.1 Introduction.- 2.2 Background on Point Processes: Y = ?X.- 2.3 Cumulative Processes.- 2.4 Rate-Conservation Law.- 2.5 Fundamental Lemma of Maxima.- 2.6 Time-Averages and Asymptotic Frequency Distributions.- 2.7 Comments and References.- 3. Processes with General State Space.- 3.1 Introduction.- 3.2 Relations between Frequencies for a Process with an Imbedded Point Process.- 3.3 Applications to the G/G/1 Queue.- 3.4 Relations between Frequencies for a Process with an Imbedded Cumulative Process (Fluid Model).- 3.5 Martingale ASTA.- 3.6 Comments and References.- 4. Processes with Countable State Space.- 4.1 Introduction.- 4.2 Basic Relations.- 4.3 Networks of Queues: The Arrival Theorem.- 4.4 One-Dimensional Input-Output Systems.- 4.5 Applications to Stochastic Models.- 4.6 Relation to Operational Analysis.- 4.7 Comments and References.- 5. Sample-Path Stability.- 5.1 Introduction.- 5.2 Characterization of Stability.- 5.3 Rate Stability for Multiserver Models.- 5.4 Rate Stability for Single-Server Models.- 5.5 ?-Rate Stability.- 5.6 Comments and References.- 6. Little’s Formula and Extensions.- 6.1 Introduction.- 6.2 Little’s Formula: L = ?W.- 6.3 Little’s Formula for Stable Queues.- 6.4 Generalization of Little’s Formula: H = ?G.- 6.5 Fluid Version of Little’s Formula.- 6.6 Fluid Version of H = ?G 190 6.6.1 Necessary and Sufficient Conditions.- 6.7 Generalization of H = ?G.- 6.8 Applications to Stochastic Models.- 6.9Comments and References.- 7. Insensitivity of Queueing Networks.- 7.1 Introduction.- 7.2 Preliminary Result.- 7.3 Definitions and Assumptions.- 7.4 Infinite Server Model.- 7.5 Erlang Loss Model.- 7.6 Round Robin Model.- 7.7 Comments and References.- 8. Sample-Path Approach to Palm Calculus.- 8.1 Introduction.- 8.2 Two Basic Results.- 8.3 Extended Results.- 8.4 Relation to Stochastic Models.- 8.5 Comments and References.- Appendices.- References.

' ... it contains a wealth of useful material for those giving courses in stochastic processes at all levels, and its extremely readable style makes it suitable for anyone with previous exposure to basic probability and stochastic processes.'Short Book Reviews, 19:2 (1999)'... this monograph is well written, fairly comprehensive and a welcome addition to the growing number of books on queuing theory. It is of interest to a wide audience of operations researchers, applied probabilists and engineers.'Mathematical reviews, 2002d