Introduction to stochastic networks

Publication date 14 October 1999

Markov chain Palm probabilities point process Poisson process stochastic networks

Research exposition (monographs, survey articles) pertaining to probability theory (60-02) Queueing theory (aspects of probability theory) (60K25)

Review text

This is an excellent monograph from one of the leading experts in the field about stochastic queueing networks and related fundamentals of queueing theory, which will become a standard reference in the field, and which can be used for teaching as well. The book is intended for graduate students and researchers in engineering, science, and mathematics interested in the basic stochastic network processes that have been developed over the last twenty years. It may be considered as a sequel to \textit{F. P. Kelly}'s classical ``Reversibility and stochastic networks (1979; Zbl 0422.60001)] and of \textit{P. Whittle}'s ``Systems in stochastic equilibrium (1986; Zbl 0665.60107)]. Its subject are systems in which customers move among stations where they receive services. There may be queueing for services, and customer routing and service times may be random. These kinds of stochastic networks arise in many areas of computer science, communication, economics, engineering and biology. Typical examples are telecommunication and computer networks, manufacturing networks, maintenance and logistic networks and, of course, the Internet. The focus of the book is on Markov jump process models and their equilibrium distributions and performance parameters, which are analytically tractable via closed form expressions or computational algorithms, such as Little laws for queues and utility processes. In the later chapters it also provides a very readable introduction to Palm probabilities for stationary systems. A wealth of specific examples illuminate the main ideas and concepts. Exercises, ranging from medium to hard, and bibliographical notes complement each chapter. In my opinion the prerequisites for understanding this book are necessarily relatively high. An introductory course about stochastic processes covering Markov chains, Poisson processes and continuous-time Markov processes is sufficient for the first three chapters. The author avoids cumbersome notation, as seen often in more applied publications. As a consequence, a good training in more advanced aspects of probability theory, such as measure theory, conditional expectations and a glimpse of point processes, is helpful at least, or even necessary, for the rest of this monograph. Contents of the book: Chapter 1 introduces and discusses Whittle networks, where the service rate at each node is a function of the numbers of units at all the nodes. These are natural generalizations of the well known Jackson networks. Chapter 2 describes reversible Markov network processes with batch or multi-unit movements as well as single-unit movements and introduces the concept of partition-reversibility. Chapter 3 models networks with multiple types of units, including the well-known Kelly and BCMP networks. Poisson point processes, Palm probabilities and Little laws are the subject of the next three chapters. Chapter 4 with the title ``Network flows and travel times introduces Palm probabilities for Markov processes at their transition times and as key tool, an (apparently new) generalization of Lévy's formula for expectations of functionals of a Markov process. Addressed are questions about movements of units in stationary Jackson and Whittle processes, such as identifying Poisson flows in the network. Chapter 5 discusses Little laws for Markov systems and more generally, for stationary queueing systems. These Little laws are proved for the more general class of utility processes. Chapter 6 includes Palm calculus and Campell-Mecke formulas for functionals of stationary queueing systems. Chapter 7 introduces networks with so-called string transitions. Special cases are Whittle networks with batch movements. Invariant measures for such networks resemble those of Whittle networks, but now key parameters in the measures are obtained as solutions to more complicated nonlinear traffic equations. Chapter 8 presents results on quasi-reversible networks and product form distributions. A network is called quasi-reversible if for each node (viewed in isolation and in the stationary case) Poisson arrivals imply Poisson departures. The final Chapters 9 and 10 discuss space-time Poisson models and spatial queueing systems. Such models describe the collective movement of units or customers in space and time and are beginning to receive attention, f.i., from researchers in wireless communications, computer systems, biology and economics.

Recommendations

Cited in

(85)

This page was built for publication: Introduction to stochastic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4265492)