Stability of queueing networks. École d'Été de probabilités de Saint-Flour XXXVI-2006 (Q931256)

This book deals with the issue of the queueing network stability. We recall that a queueing network is stable when its underlying Markov process of the queueing network is a positive Harris recurrent. Intuitively, a natural condition for stability (assuming all states communicate), is that \(\rho_{i} < 1\) for all stations \(i\). The material of the book is divided into three parts. The first (Chapter 2) discusses the ``classical'' queueing networks introduced in the BCMP model including networks with FIFO, PS and LIFO disciplines. For \(\rho_{i} < 1\) for all stations \(i\), these networks are stable, and explicit product-like formulas are given for their stationary distributions. The second part (Chapter 3) of this book presents the best known examples of unstable subcritical queueing networks in a more-or-less chronological order. To these examples belongs, among others, the so-called \textit{adversarial queueing system}, where an all-knowledgeable adversary is allowed to modify the precise timing of input into the system. Service times are deterministic and are often assumed to be the same everywhere. The third part (Chapters 4 and 5) gives general and sufficient conditions for the stability of a queueing network. The main results of this part show that the queueing network is stable whenever an associated fluid model is stable. Applications of such stability are given in Sections 5.1 - 5.3. In each presented case, the procedure to demonstrate the stability of a related fluid model is given. In the remaining of this the global stability problem is discussed. Applying the given theorem, a queueing network will be globally stable if its fluid model exists. For a two-station fluid model with deterministic routing a complete theory of stability is given. Moreover, the basic fluid model is employed to demonstrate the global rate stability, often called globally weak stability. This book, including the material from a series of nine lectures given at the Saint-Flour-Probability Summer School, 2006, is very important. In my opinion it answer the needs of all who use queueing networks in their research studies.