We believe that the intuitive deterministic approach of this book will be beneficial to researchers and practitioners, who will gain better insights into many questions in queueing theory, and to teachers and students, who will appreciate the simplicity and intuitive appeal of the arguments.
Features. A distinctive feature of this book is that it consistently takes the point of view of focusing on one sample path of a stochastic process. That is, 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. In many cases of interest in queueing theory relations hold quite generally assuming limits exist, and the proofs are elementary and intuitive. On the other hand, proofs of the existence of limits (almost surely) require the heavy machinery of stochastic processes, such as the the theory of regenerative processes or stationary marked point processes. This book also covers recent topics such as pathwise stability.
Problems Studied. Sample-path analysis has been quite effective in establishing
fundamental results such as relationships between time and point averages in a general setting.
Examples include a pathwise version of the renewalreward theorem, Little's formula
(L = 
W)
and its extension
H = G,
meanvalue analysis, the covariance formula, the arrivals-see-time-average
property (ASTA), sample-path versions of the rate-conservation principle, the global balance conditions, and
various relations between time-average state frequencies and frequencies at the points of an imbedded point
process. It has also been successful in providing complete and pure pathwise arguments in the case of rate
stability and backward/forward recurrence times.
Proofs. Sample-path proofs are delicate and sometimes their simplicity is misleading. In a sample-path setting one works with fewer assumptions than in the corresponding stochastic framework. One therefore has limited resources to utilize in the proof. Moreover, because one focuses on a particular sample path, one has to examine carefully all sorts of pathological and strange behaviors before insuring the validity of the argument. Once a sample-path proof is constructed, however, it tends to be for the most part simple, intuitive, and elegant: a good return on one's investment of time and effort.
Relation to Stochastic Approach. In many cases it is possible to provide pure pathwise results. In other cases one can provide a sample-path intermediate result, then invoke an appropriate ergodic theorem to complete the analysis. In such cases we advocate pushing sample-path arguments as far as possible before resorting to stochastic analysis. The advantages of this approach are clear: the sample-path arguments are simple and intuitive; thus they provide a clear insight into the issues at hand. Sample-path analysis helps pinpoint why and when stochastic arguments are needed. Typically stochastic analysis is required to construct stationary versions of the process in question and to ensure that the appropriate limits are well defined. At the sample-path level we focus on one realization of the underlying stochastic process, so the construction of a stationary stochastic version becomes irrelevant. Our approach is to assume the relevant limits are well defined on the sample path in question and then trace out the implications of this assumption.
The fewer the assumptions one makes, the more general the results tend to be. General results have wider applicability, but they may not be useful in solving a particular problem. One should not expect sample-path analysis to be instructive in providing results where a stochastic condition is crucial to obtaining a result (such as the stationary distribution in an M/M/1 queue). Making stochastic assumptions provides the analyst with more tools with which to construct a proof.
In summary, we recommend use of sample-path analysis 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. (These are typically presented at the end of a chapter.)
Organization. This book contains eight chapters and three appendices. Chapter 1 provides an introductory
survey of some basic sample-path properties of queueing models at an elementary level. Topics include Little's
formula, imbedded properties of input-output processes, busy period analysis, and conditional properties of
queues. (These topics are revisited at a more advanced level in subsequent chapters. Readers familiar with
queueing theory who wish to move directly to more general models and results may omit this chapter.) Chapter 2
contains a collection of fundamental results that are needed in the rest of the book. It discusses in detail the
relation
Y = X,
which is a pathwise version or the renewal-reward theorem. It also covers cumulative
processes and the rate conservation law, among other topics. Chapter 3 deals with a process with a general state
space and an imbedded point process, with applications to the
G/G/1
queue and a martingale proof of ASTA.
Chapter 4 specializes the topics of Chapter 3 to the case of a countable state space, with applications to networks
of queues, one-dimensional processes, and numerous examples. The relationships discussed in Chapters 3 and 4
are applicable to a wide range of discrete-event dynamic systems. Chapter 5 deals with pathwise rate stability in
the context of a general input-output system, with applications to singleserver and multiple-server queues, among
others. It also discuses several other notions of pathwise stability and the connections among them. Chapter 6
discuses Little's formula
(L = W)
and its generalization
H = G.
It also contains discussion of fluid versions of
these relations under minimal conditions. Chapter 7 proves the insensitivity phenomenon (i.e., the property that
the queue-length distribution is independent of the service-time distribution) for the infinite-server queue, the
Erlang loss model, and a round-robin model in discrete time. Chapter 8 extends the basic relations in Chapters 3
and 4 to the multi-dimensional case by providing a sample-path approach to Palm calculus. Results include the
Palm inversion formula and Neveu's exchange formulas. Appendix A contains a brief introduction to the strong
law of large numbers and other ergodic theorems that are useful when it becomes necessary invoke stochastic
assumptions in the context of stationary processes and random marked point processes. Appendix B reviews
limit theorems from Markov and regenerative processes. Appendix C contains a survey of different concepts of
stability in stochastic models.
Prerequisites. A basic course in probability and stochastic processes or queueing theory and some knowledge of calculus suffice for Chapters 1-7, with the exception of Section 3 in Chapter 3 on martingale ASTA, which requires knowledge of the basic elements of martingale theory. Chapter 8 requires more advanced background, perhaps familiarity with random marked point processes.