Queues and stochastic networks are analyzed in this book with purely probabilistic methods. The purpose of these lectures is to show that general results from Markov processes, martingales or ergodic theory can be used directly to study the corresponding stochastic processes. Recent developments have shown that, instead of having ad-hoc methods, a better understanding of fundamental results on stochastic processes is crucial to study the complex behavior of stochastic networks.

In this book, various aspects of these stochastic models are investigated in depth in an elementary way: Existence of equilibrium, characterization of stationary regimes, transient behaviors (rare events, hitting times) and critical regimes, etc. A simple presentation of stationary point processes and Palm measures is given. Scaling methods and functional limit theorems are a major theme of this book. In particular, a complete chapter is devoted to fluid limits of Markov processes.

uses the full strength of stochastic calculus methods applied to networks detailed presentation of most classical queueing models new material on scaling methods, fluid limits are thoroughly presented and discussed extensive use of martingale and stochastic calculus methods to investigate transient behaviour of queueing models Includes supplementary material: sn.pub/extras

Autorentext

Philippe Robert ist Kriminalsoziologe und Directeur de recherche am CNRS (Centre National de la Recherche Scientifique), Paris.

Inhalt

1. Point Processes: 1.1 General Definitions; 1.2 Poisson Processes; 1.3 Poisson Point Processes on the Real Line; 1.4 Renewal Point Processes.- 2. The GI/GI/1 FIFO Queue and Random Walks: 2.1 General results on the GI/GI/1 FIFO Queue; 2.2 Wiener-Hopf Factorization; 2.3 Applications to the GI/GI/1 Queue; 2.4 The GI/M/1 and M/GI/1 Queues; 2.5 The H/G/1 Queue; 2.6 A Probabilistic Proof.- 3. Limit Theorems for the GI/GI/1 Queue: 3.1 Introduction; 3.2 The Biased Random Walk; 3.3 The Tail Distribution of W; 3.4 The Maximum of a Busy Period; 3.5 The GI/GI/1 Queue near Saturation; 3.6 The Random Walk Conditioned to Hit Level a.- 4. Stochastic Networks and Reversibility: 4.1 Introduction; 4.2 Reversibility of Markov Processes; 4.3 Local Balance Equations; 4.4 Queueing Networks with Product Form.- 5. The M/M/1 Queue: 5.1 Introduction; 5.2 Exponential Martingales; 5.3 Hitting Times: Downward; 5.4 Convergence to Equilibrium; 5.5 Hitting Times: Upward; 5.6 Rare Events; 5.7 Fluid Limits; 5.8 Large Deviations; 5.9 Appendix.- 6. The M/M/infinity Queue: 6.1 Introduction; 6.2 Positive Martingales; 6.3 Hitting Times: Downward; 6.4 Hitting Times: Upward; 6.5 Fluid Limits; 6.6 A Functional Central Limit Theorem; 6.7 The M/M/N/N Queue; 6.8 Appendix.- 7. Queues with Poisson Arrivals: 7.1 FIFO Queue; 7.2 Infinite Server Queue; 7.3 LIFO Queue with Preemptive Service; 7.4 Processor-Sharing Queue; 7.5 The Insensitivity Property; 7.6 The Distribution Seen by Customers.- 8. Recurrence and Transience of Markov Chains: 8.1 Recurrence of Markov Chains; 8.2 Ergodicity; 8.3 Transience; 8.4 Ergodicity of Markov Processes; 8.5 Some Applications; 8.6 The Classical Version of Lyapunov's Theorem.- 9. Rescaled Markov Processes and Fluid Limits: 9.1 Introduction; 9.2 Rescaled Markov Processes; 9.3 The Fluid Limits of a Class of Markov Processes; 9.4 Fluid Limits and Skorohod Problems; 9.5 Fluid Limits and Ergodicity Properties; 9.6 Fluid Limits and Local Equilibrium; 9.7 Bibliographical Notes.- 10. ErgodicTheory: Basic Results: 10.1 Discrete Dynamical Systems; 10.2 Ergodic Theorems; 10.3 Continuous Time Dynamical Systems; 10.4 Markovian Endomorphisms.- 11. Stationary Point Processes: 11.1 Introduction; 11.2 The Palm Space of the Arrival Process; 11.3 Construction of a Stationary Point Process; 11.4 Relations Between the Palm Space and Its Extension; 11.5 Joint Distribution of the Points Around t=0; 11.6 Some Properties of Stationary Point Processes; 11.7 Appendix.- 12. The G/G/1 FIFO Queue: 12.1 The Waiting Time; 12.2 Virtual Waiting Time; 12.3 The Number of Customers; 12.4 The Associated Stationary Point Processes; 12.5 The Unstable G/G/1 Queue; 12.6 A Queue with Two Servers, the G/G/2 Queue.- A. Martingales: A.1 Discrete Time Parameter Martingales; A.2 Continuous Time Martingales; A.3 The Stochastic Integral for a Poisson Process; A.4 Stochastic Differential Equations with Jumps.- B. Markovian Jump Processes: B.1 Q-Matrices; B.2 Global Balance Equations; B.3 The Associated Martingales.- C. Convergence in Distribution: C.1 The Total Variation Norm on Probability Distributions; C.2 Convergence of Stochastic Processes.- D. An Introduction to Skorohod Problems: D.1 Dimension 1; D.2 Multi-Dimensional Skorohod Problems