Sample-path analysis of queueing systems (Q1294788): Difference between revisions

Let \(0:= T(0)< T(1)<T(2)<\dots\) be a sequence of points on the real line such that \(T(n)\) tends to infinity as \(n\) tends to infinity, and let \(N(t)\) denote the number of points of this sequence in \([0,t]\). Then the following statement is true: if \(N(t)/t\) has a positive limit as \(t\) tends to infinity, then \(T(n)/n\) has a positive limit as \(n\) tends to infinity, and the product of the two limits is equal to \(1\). The converse is also true. The authors of the book call the sequence \(\{T(n)\}\) a (deterministic) point process and call the function \(N(\cdot)\) a process, too, denoting it as \(\{N(t); t\geq 0\}\). This is the language of stochastic processes, but nothing is random here. However, the function \(N(\cdot)\) could be a ``simple path'' of a renewal process. In this case one can combine the above statement with the strong law of large numbers to arrive at the elementary renewal theorem. This very simple example has all the features that characterize the work presented in this monograph. For given deterministic processes on the nonnegative real line one assumes the existence of certain limits as time tends to infinity, typically of some asymptotic frequencies or means. This allows to establish relationships between these limits and/or further limits whose existence follows from the assumptions. Typically, though not always and not exclusively, the processes can be viewed as sample paths of random processes describing some aspect of a queueing system, and by means of additional arguments of a probabilistic nature, such as the ergodic theorem or the memoryless property of the exponential distribution, one may transform the results of pure sample path analysis into probabilistic results. This is what the book does throughout its eight chapters, the focus being on the deterministic part of the job. An introductory chapter is followed by three chapters presenting applications of a basic sample path relationship stating that, for a continuous-time cost process, the asymptotic average cost rate equals the rate at which points of an imbedded point process occur times the average cost incurred between successive points. The stochastic analogue in renewal theory is the renewal reward theorem. The applications include a sample path rate conservation law, a result stating that the sample path asymptotic time average of a process is equal to the mean of its asymptotic frequency distribution, and sample path balance relationships between asymptotic state and transition frequencies. Chapter 5 is devoted to a property of rate stability of an input-output process. A nonnegative process of the form \(Z(t)= Z(0)+ A(t)- D(t)\), where \(A(\cdot)\) and \(D(\cdot)\) are nondecreasing, is called an input-output process and is said to be rate stable if \(Z(t)/t\) tends to \(0\) as \(t\) tends to infinity. The biggest chapter, extending over 60 pages, is Chapter 6 on Little's formula and its extensions. Chapter 7 presents a sample path approach to the phenomenon of insensitivity in certain queueing models, i.e. the phenomenon that the asymptotic frequency distribution of the number of customers in the system depends on the asymptotic frequency distribution of service times only through its mean. Finally, in Chapter 8, the authors develop a complete sample path version of the theory of Palm probabilities and their relation to time-stationary probabilities. This is again based on the analogue of the renewal theorem of Chapter 2. All chapters contain applications to stochastic queueing models. The book closes with three appendices on stochastic background material. There are bibliographic notes throughout, but no exercises. The book is not a textbook, although the greater part of it is rather simple mathematics. For those doing research or teaching in queueing theory and related subjects, however, the book would be a very valuable, even indispensable, companion, the more so since it is written in a very clear style, keeping the reader informed at every instant about the current issues and the intended direction.