Switching Processes in Queueing Models

Vladimir V. Anisimov is currently Director of the Research Statistics Unit at GlaxoSmithKline, UK. He has written about 200 papers, nine books and manuals in this area.

Preface 13

Definitions 17

Chapter 1. Switching Stochastic Models 19

1.1. Random processes with discrete component 19

1.1.1.Markov and semi-Markov processes 21

1.1.2. Processes with independent increments and Markov switching 21

1.1.3. Processes with independent increments and semi-Markov switching 23

1.2. Switching processes 24

1.2.1. Definition of switching processes 24

1.2.2. Recurrent processes of semi-Markov type (simple case) 26

1.2.3.RPSMwithMarkov switching 26

1.2.4. General case of RPSM 27

1.2.5. Processes with Markov or semi-Markov switching 27

1.3. Switching stochastic models 28

1.3.1. Sums of random variables 29

1.3.2. Random movements 29

1.3.3. Dynamic systems in a random environment 30

1.3.4. Stochastic differential equations in a random environment 30

1.3.5. Branching processes 31

1.3.6. State-dependent flows 32

1.3.7. Two-level Markov systems with feedback 32

1.4. Bibliography 33

Chapter 2. Switching Queueing Models 37

2.1. Introduction 37

2.2. Queueing systems 38

2.2.1. Markov queueing models 38

2.2.1.1. A state-dependent system MQ/MQ/1/∞ 39

2.2.1.2. Queueing system MM,Q/MM,Q/1/m 40

2.2.1.3. System MQ,B/MQ,B/1/∞ 41

2.2.2.Non-Markov systems 42

2.2.2.1. Semi-Markov system SM/MSM,Q/1 42

2.2.2.2. System MSM,Q/MSM,Q/1/∞ 43

2.2.2.3. System MSM,Q/MSM,Q/1/V 44

2.2.3. Models with dependent arrival flows 45

2.2.4. Polling systems 46

2.2.5. Retrial queueing systems 47

2.3. Queueing networks 48

2.3.1. Markov state-dependent networks 49

2.3.1.1. Markov network (MQ/MQ/m/∞)r  49

2.3.1.2. Markov networks (MQ,B/MQ,B/m/∞)r with batches 50

2.3.2.Non-Markov networks 50

2.3.2.1. State-dependent semi-Markov networks 50

2.3.2.2. Semi-Markov networks with random batches 52

2.3.2.3. Networks with state-dependent input 53

2.4.Bibliography 54

Chapter 3. Processes of Sums of Weakly-dependent Variables 57

3.1. Limit theorems for processes of sums of conditionally independent random variables 57

3.2. Limit theorems for sums with Markov switching 65

3.2.1. Flows of rare events 67

3.2.1.1. Discrete time 67

3.2.1.2. Continuous time 69

3.3. Quasi-ergodic Markov processes 70

3.4. Limit theorems for non-homogenous Markov processes 73

3.4.1. Convergence to Gaussian processes 74

3.4.2. Convergence to processes with independent increments 78

3.5. Bibliography 81

Chapter 4. Averaging Principle and Diffusion Approximation for Switching Processes 83

4.1. Introduction 83

4.2. Averaging principle for switching recurrent sequences 84

4.3. Averaging principle and diffusion approximation for RPSMs 88

4.4. Averaging principle and diffusion approximation for recurrent processes of semi-Markov type (Markov case) 95

4.4.1. Averaging principle and diffusion approximation for SMP 105

4.5. Averaging principle for RPSM with feedback 106

4.6. Averaging principle and diffusion approximation for switching processes 108

4.6.1. Averaging principle and diffusion approximation for processes with semi-Markov switching 112

4.7. Bibliography 113

Chapter 5. Averaging and Diffusion Approximation in Overloaded Switching Queueing Systems and Networks 117

5.1. Introduction 117

5.2. Markov queueing models 120

5.2.1. System MQ,B/MQ,B/1/∞ 121

5.2.2. System MQ/MQ/1/∞ 124

5.2.3. Analysis of the waiting time 129

5.2.4. An output process 131

5.2.5. Time-dependent system MQ,t/MQ,t/1/∞ 132

5.2.6. Asystemwith impatient calls 134

5.3. Non-Markov queueing models 135

5.3.1. System GI/MQ/1/∞ 135

5.3.2. Semi-Markov system SM/MSM,Q/1/∞ 136

5.3.3. System MSM,Q/MSM,Q/1/∞ 138

5.3.4. System SMQ/MSM,Q/1/∞ 139

5.3.5. System GQ/MQ/1/∞ 142

5.3.6. A system with unreliable servers 143

5.3.7. Polling systems 145

5.4. Retrial queueing systems 146

5.4.1. Retrial system MQ/G/1/w.r 147

5.4.2. System M¯ /G¯/1/w.r 150

5.4.3. Retrial system M/M/m/w.r 154

5.5. Queueing networks 159

5.5.1. State-dependent Markov network (MQ/MQ/1/∞)r 159

5.5.2. Markov state-dependent networks with batches 161

5.6. Non-Markov queueing networks 164

5.6.1. A network (MSM,Q/MSM,Q/1/∞)r with semi-Markov switching 164

5.6.2. State-dependent network with recurrent input 169

5.7. Bibliography 172

Chapter 6. Systems in Low Traffic Conditions 175

6.1. Introduction 175

6.2. Analysis of the first exit time from the subset of states 176

6.2.1. Definition of S-set 176

6.2.2. An asymptotic behavior of the first exit time 177

6.2.3. State space forming a monotone structure 180

6.2.4. Exit time as the time of first jump of the process of sums with Markov switching 182

6.3. Markov queueing systems with fast service 183

6.3.1. M/M/s/m systems 183

6.3.1.1. System MM/M/l/m in a Markov environment 185

6.3.2. Semi-Markov queueing systems with fast service 188

6.4. Single-server retrial queueing model 190

6.4.1. Case 1: fast service 191

6.4.1.1. State-dependent case 194

6.4.2. Case 2: fast service and large retrial rate 195

6.4.3. State-dependent model in a Markov environment 197

6.5. Multiserver retrial queueing models 201

6.6. Bibliography 204

Chapter 7. Flows of Rare Events in Low and Heavy Traffic Conditions 207

7.1. Introduction 207

7.2. Flows of rare events in systems with mixing 208

7.3. Asymptotically connected sets (Vn-S-sets) 211

7.3.1. Homogenous case 211

7.3.2. Non-homogenous case 214

7.4. Heavy traffic conditions 215

7.5. Flows of rare events in queueing models 216

7.5.1. Light traffic analysis in models with finite capacity 216

7.5.2. Heavy traffic analysis 218

7.6. Bibliography 219

Chapter 8. Asymptotic Aggregation of State Space 221

8.1. Introduction 221

8.2. Aggregation of finite Markov processes (stationary behavior) 223

8.2.1. Discrete time 223

8.2.2. Hierarchic asymptotic aggregation 225

8.2.3. Continuous time 227

8.3. Convergence of switching processes 228

8.4. Aggregation of states in Markov models 231

8.4.1. Convergence of the aggregated process to a Markov process (finite state space) 232

8.4.2. Convergence of the aggregated process with a general state space 236

8.4.3. Accumulating processes in aggregation scheme 237

8.4.4. MP aggregation in continuous time 238

8.5. Asymptotic behavior of the first exit time from the subset of states (non-homogenous in time case) 240

8.6. Aggregation of states of non-homogenous Markov processes 243

8.7. Averaging principle for RPSM in the asymptotically aggregated Markov environment 246

8.7.1. Switching MP with a finite state space 247

8.7.2. Switching MP with a general state space 250

8.7.3. Averaging principle for accumulating processes in the asymptotically aggregated semi-Markov environment 251

8.8. Diffusion approximation for RPSM in the asymptotically aggregated Markov environment 252

8.9. Aggregation of states in Markov queueing models 255

8.9.1. System MQ/MQ/r/∞ with unreliable servers in heavy traffic 255

8.9.2. System MM,Q/MM,Q/1/∞ in heavy traffic 256

8.10. Aggregation of states in semi-Markov queueing models 258

8.10.1. System SM/MSM,Q/1/∞ 258

8.10.2. System MSM,Q/MSM,Q/1/∞ 259

8.11. Analysis of flows of lost calls 260

8.12. Bibliography 263

Chapter 9. Aggregation in Markov Models with Fast Markov Switching 267

9.1. Introduction 267

9.2. Markov models with fast Markov switching 269

9.2.1.Markov processes with Markov switching 269

9.2.2. Markov queueing systems with Markov type switching 271

9.2.3. Averaging in the fast Markov type environment 272

9.2.4. Approximation of a stationary distribution 274

9.3. Proofs of theorems 275

9.3.1. Proof of Theorem 9.1 275

9.3.2. Proof of Theorem 9.2 277

9.3.3. Proof of Theorem 9.3 279

9.4. Queueing systems with fast Markov type switching 279

9.4.1. System MM,Q/MM,Q/1/N 279

9.4.1.1. Averaging of states of the environment 279

9.4.1.2. The approximation of a stationary distribution 280

9.4.2. Batch system BMM,Q/BMM,Q/1/N 281

9.4.3. System M/M/s/mwith unreliable servers 282

9.4.4. Priority model MQ/MQ/m/s,N 283

9.5. Non-homogenous in time queueing models 285

9.5.1. SystemMM,Q,t/MM,Q,t/s/m with fast switching – averaging of states 286

9.5.2. System MM,Q/MM,Q/s/m with fast switching – aggregation of states 287

9.6. Numerical examples 288

9.7. Bibliography 289

Chapter 10. Aggregation in Markov Models with Fast Semi-Markov Switching 291

10.1. Markov processes with fast semi-Markov switches 292

10.1.1.Averaging of a semi-Markov environment 292

10.1.2. Asymptotic aggregation of a semi-Markov environment 300

10.1.3. Approximation of a stationary distribution 305

10.2. Averaging and aggregation in Markov queueing systems with semi-Markov switching 309

10.2.1.Averaging of states of the environment 309

10.2.2. Asymptotic aggregation of states of the environment 310

10.2.3. The approximation of a stationary distribution 311

10.3. Bibliography 313

Chapter 11. Other Applications of Switching Processes 315

11.1. Self-organization in multicomponent interacting Markov systems 315

11.2. Averaging principle and diffusion approximation for dynamic systems with stochastic perturbations 319

11.2.1. Recurrent perturbations 319

11.2.2. Semi-Markov perturbations 321

11.3. Random movements 324

11.3.1. Ergodic case 324

11.3.2. Case of the asymptotic aggregation of state space 325

11.4. Bibliography 326

Chapter 12. Simulation Examples 329

12.1. Simulation of recurrent sequences 329

12.2. Simulation of recurrent point processes 331

12.3. Simulation ofRPSM 332

12.4. Simulation of state-dependent queueing models 334

12.5. Simulation of the exit time from a subset of states of a Markov chain 337

12.6. Aggregation of states in Markov models 340

Index 343