Switching Processes in Queueing Models

by Anisimov, Vladimir

• ISBN13: 9781848210455
• ISBN10: 1848210450
• Edition: 1st
• Format: Hardcover
• Copyright: 2008-11-03
• Publisher: Wiley-ISTE

Summary

Switching processes, invented by the author in 1977, is the main tool used in the investigation of traffic problems from automotive to telecommunications. The title provides a new approach to low traffic problems based on the analysis of flows of rare events and queuing models. In the case of fast switching, averaging principle and diffusion approximation results are proved and applied to the investigation of transient phenomena for wide classes of overloading queuing networks. The book is devoted to developing the asymptotic theory for the class of switching queuing models which covers models in a Markov or semi-Markov environment, models under the influence of flows of external or internal perturbations, unreliable and hierarchic networks, etc.

Author Biography

Vladimir V. Anisimov is Director of the Research Statistics Unit at GlaxoSmithKline, UK.

Table of Contents

Preface	p. 13
Definitions	p. 17
Switching Stochastic Models	p. 19
Random processes with discrete component	p. 19
Markov and semi-Markov processes	p. 21
Processes with independent increments and Markov switching	p. 21
Processes with independent increments and semi-Markov switching	p. 23
Switching processes	p. 24
Definition of switching processes	p. 24
Recurrent processes of semi-Markov type (simple case)	p. 26
RPSM with Markov switching	p. 26
General case of RPSM	p. 27
Processes with Markov or semi-Markov switching	p. 27
Switching stochastic models	p. 28
Sums of random variables	p. 29
Random movements	p. 29
Dynamic systems in a random environment	p. 30
Stochastic differential equations in a random environment	p. 30
Branching processes	p. 31
State-dependent flows	p. 32
Two-level Markov systems with feedback	p. 32
Bibliography	p. 33
Switching Queueing Models	p. 37
Introduction	p. 37
Queueing systems	p. 38
Markov queueing models	p. 38
A state-dependent system M[subscript Q]/M[subscript Q]/1/[infinity]	p. 39
Queueing system M[subscript M,Q]/M[subscript M,Q]/1/m	p. 40
System M[subscript Q,B]/M[subscript Q,B]/1/[infinity]	p. 41
Non-Markov systems	p. 42
Semi-Markov system SM/M[subscript SM,Q]/1	p. 42
System M[subscript SM,Q]/M[subscript SM,Q]/1/[infinity]	p. 43
System M[subscript SM,Q]/M[subscript SM,Q]/1/V	p. 44
Models with dependent arrival flows	p. 45
Polling systems	p. 46
Retrial queueing systems	p. 47
Queueing networks	p. 48
Markov state-dependent networks	p. 49
Markov network (M[subscript Q]/M[subscript Q]/m/[infinity])[superscript r]	p. 49
Markov networks (M[subscript Q,B]/M[subscript Q,B]/m/[infinity])[superscript r] with batches	p. 50
Non-Markov networks	p. 50
State-dependent semi-Markov networks	p. 50
Semi-Markov networks with random batches	p. 52
Networks with state-dependent input	p. 53
Bibliography	p. 54
Processes of Sums of Weakly-dependent Variables	p. 57
Limit theorems for processes of sums of conditionally independent random variables	p. 57
Limit theorems for sums with Markov switching	p. 65
Flows of rare events	p. 67
Discrete time	p. 67
Continuous time	p. 69
Quasi-ergodic Markov processes	p. 70
Limit theorems for non-homogenous Markov processes	p. 73
Convergence to Gaussian processes	p. 74
Convergence to processes with independent increments	p. 78
Bibliography	p. 81
Averaging Principle and Diffusion Approximation for Switching Processes	p. 83
Introduction	p. 83
Averaging principle for switching recurrent sequences	p. 84
Averaging principle and diffusion approximation for RPSMs	p. 88
Averaging principle and diffusion approximation for recurrent processes of semi-Markov type (Markov case)	p. 95
Averaging principle and diffusion approximation for SMP	p. 105
Averaging principle for RPSM with feedback	p. 106
Averaging principle and diffusion approximation for switching processes	p. 108
Averaging principle and diffusion approximation for processes with semi-Markov switching	p. 112
Bibliography	p. 113
Averaging and Diffusion Approximation in Overloaded Switching Queueing Systems and Networks	p. 117
Introduction	p. 117
Markov queueing models	p. 120
System M[subscript Q,B]/M[subscript Q,B]/1/[infinity]	p. 121
System M[subscript Q]/M[subscript Q]/1/[infinity]	p. 124
Analysis of the waiting time	p. 129
An output process	p. 131
Time-dependent system M[subscript Q,t]/M[subscript Q,t]/1/[infinity]	p. 132
A system with impatient calls	p. 134
Non-Markov queueing models	p. 135
System GI/M[subscript Q]/1/[infinity]	p. 135
Semi-Markov system SM/M[subscript SM,Q]/1/[infinity]	p. 136
System M[subscript SM,Q]/M[subscript SM,Q]/1/[infinity]	p. 138
System SM[subscript Q]/M[subscript SM,Q]/1/[infinity]	p. 139
System G[subscript Q]/M[subscript Q]/1/[infinity]	p. 142
A system with unreliable servers	p. 143
Polling systems	p. 145
Retrial queueing systems	p. 146
Retrial system M[subscript Q]/G/1/w.r	p. 147
System M/G/1/w.r	p. 150
Retrial system M/M/m/w.r	p. 154
Queueing networks	p. 159
State-dependent Markov network (M[subscript Q]/M[subscript Q]/1/[infinity])[superscript r]	p. 159
Markov state-dependent networks with batches	p. 161
Non-Markov queueing networks	p. 164
A network (M[subscript SM,Q]/M[subscript SM,Q]/1/[infinity])[superscript r] with semi-Markov switching	p. 164
State-dependent network with recurrent input	p. 169
Bibliography	p. 172
Systems in Low Traffic Conditions	p. 175
Introduction	p. 175
Analysis of the first exit time from the subset of states	p. 176
Definition of S-set	p. 176
An asymptotic behavior of the first exit time	p. 177
State space forming a monotone structure	p. 180
Exit time as the time of first jump of the process of sums with Markov switching	p. 182
Markov queueing systems with fast service	p. 183
M/M/s/m systems	p. 183
System M[subscript M]/M/l/m in a Markov environment	p. 185
Semi-Markov queueing systems with fast service	p. 188
Single-server retrial queueing model	p. 190
Case 1: fast service	p. 191
State-dependent case	p. 194
Case 2: fast service and large retrial rate	p. 195
State-dependent model in a Markov environment	p. 197
Multiserver retrial queueing models	p. 201
Bibliography	p. 204
Flows of Rare Events in Low and Heavy Traffic Conditions	p. 207
Introduction	p. 207
Flows of rare events in systems with mixing	p. 208
Asymptotically connected sets (V[subscript n]-S-sets)	p. 211
Homogenous case	p. 211
Non-homogenous case	p. 214
Heavy traffic conditions	p. 215
Flows of rare events in queueing models	p. 216
Light traffic analysis in models with finite capacity	p. 216
Heavy traffic analysis	p. 218
Bibliography	p. 219
Asymptotic Aggregation of State Space	p. 221
Introduction	p. 221
Aggregation of finite Markov processes (stationary behavior)	p. 223
Discrete time	p. 223
Hierarchic asymptotic aggregation	p. 225
Continuous time	p. 227
Convergence of switching processes	p. 228
Aggregation of states in Markov models	p. 231
Convergence of the aggregated process to a Markov process (finite state space)	p. 232
Convergence of the aggregated process with a general state space	p. 236
Accumulating processes in aggregation scheme	p. 237
MP aggregation in continuous time	p. 238
Asymptotic behavior of the first exit time from the subset of states (non-homogenous in time case)	p. 240
Aggregation of states of non-homogenous Markov processes	p. 243
Averaging principle for RPSM in the asymptotically aggregated Markov environment	p. 246
Switching MP with a finite state space	p. 247
Switching MP with a general state space	p. 250
Averaging principle for accumulating processes in the asymptotically aggregated semi-Markov environment	p. 251
Diffusion approximation for RPSM in the asymptotically aggregatd Markov environment	p. 252
Aggregation of states in Markov queueing models	p. 255
System M[subscript Q]/M[subscript Q]/r/[infinity] with unreliable servers in heavy traffic	p. 255
System M[subscript M,Q]/M[subscript M,Q]/1/[infinity] in heavy traffic	p. 256
Aggregation of states in semi-Markov queueing models	p. 258
System SM/M[subscript SM,Q]/1/[infinity]	p. 258
System M[subscript SM,Q]/M[subscript SM,Q]/1/[infinity]	p. 259
Analysis of flows of lost calls	p. 260
Bibliography	p. 263
Aggregation in Markov Models with Fast Markov Switching	p. 267
Introduction	p. 267
Markov models with fast Markov switching	p. 269
Markov processes with Markov switching	p. 269
Markov queueing systems with Markov type switching	p. 271
Averaging in the fast Markov type environment	p. 272
Approximation of a stationary distribution	p. 274
Proofs of theorems	p. 275
Proof of Theorem 9.1	p. 275
Proof of Theorem 9.2	p. 277
Proof of Theorem 9.3	p. 279
Queueing systems with fast Markov type switching	p. 279
System M[subscript M,Q]/M[subscript M,Q]/1/N	p. 279
Averaging of states of the environment	p. 279
The approximation of a stationary distribution	p. 280
Batch system BM[subscript M,Q]/BM[subscript M,Q]/1/N	p. 281
System M/M/s/m with unreliable servers	p. 282
Priority model M[subscript Q]/M[subscript Q]/m/s, N	p. 283
Non-homogenous in time queueing models	p. 285
System M[subscript M,Q,t]/M[subscript M,Q,t]/s/m with fast switching-averaging of states	p. 286
System M[subscript M,Q]/M[subscript M,Q]/s/m with fast switching-aggregation of states	p. 287
Numerical examples	p. 288
Bibliography	p. 289
Aggregation in Markov Models with Fast Semi-Markov Switching	p. 291
Markov processes with fast semi-Markov switches	p. 292
Averaging of a semi-Markov environment	p. 292
Asymptotic aggregation of a semi-Markov environment	p. 300
Approximation of a stationary distribution	p. 305
Averaging and aggregation in Markov queueing systems with semi-Markov switching	p. 309
Averaging of states of states of the environment	p. 309
Asymptotic aggregation of states of the environment	p. 310
The approximation of a stationary distribution	p. 311
Bibliography	p. 313
Other Applications of Switching Processes	p. 315
Self-organization in multicomponent interacting Markov systems	p. 315
Averaging principle and diffusion approximation for dynamic systems with stochastic perturbations	p. 319
Recurrent perturbations	p. 319
Semi-Markov perturbations	p. 321
Random movements	p. 324
Ergodic case	p. 324
Case of the asymptotic aggregation of state space	p. 325
Bibliography	p. 326
Simulation Examples	p. 329
Simulation of recurrent sequences	p. 329
Simulation of recurrent point processes	p. 331
Simulation of RPSM	p. 332
Simulation of state-dependent queueing models	p. 334
Simulation of the exit time from a subset of states of a Markov chain	p. 337
Aggregation of states in Markov models	p. 340
Index	p. 343
Table of Contents provided by Ingram. All Rights Reserved.