Stochastic Networks and Queues

by Philippe Robert

Overview

Queues and shastic 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 shastic processes. Recent developments have shown that, instead of having ad-hoc methods, a better understanding of fundamental results on shastic processes is crucial to study the complex behavior of shastic networks.

In this book, various aspects of these shastic 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.

Product Details

ISBN-13:	9783540006572
Publisher:	Springer Berlin Heidelberg
Publication date:	08/13/2003
Series:	Stochastic Modelling and Applied Probability , #52
Edition description:	2003
Pages:	399
Product dimensions:	6.10(w) x 9.25(h) x 0.36(d)

Table of Contents

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. Shastic 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 Shastic Integral for a Poisson Process; A.4 Shastic 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 Shastic Processes.- D. An Introduction to Skorohod Problems: D.1 Dimension 1; D.2 Multi-Dimensional Skorohod Problems