This first volume includes ten chapters written by experts well-known in their areas. The book studies the analysis of queues with interdependent arrival and service times, characteristics of fluid queues, modifications of retrial queueing systems and finite-source retrial queues with random breakdowns, repairs and customers’ collisions. Some recent tendencies in the asymptotic analysis include the average and diffusion approximation of Markov queueing systems and networks, the diffusion and Gaussian limits of multi-channel queueing networks with rather general input flow, and the analysis of two-time-scale nonhomogenous Markov chains using the large deviations principle.
The book also analyzes transient behavior of infinite-server queueing models with a mixed arrival process, the strong stability of queueing systems and networks, and applications of fast simulation methods for solving high-dimension combinatorial problems.
Table of Contents
Preface xi
Chapter 1. Discrete Time Single-server Queues with Interdependent Interarrival and Service Times 1
Attahiru Sule ALFA
1.1. Introduction 1
1.2. The Geo/Geo/1 case 3
1.2.1. Arrival probability as a function of service completion probability 4
1.2.2. Service times dependent on interarrival times 6
1.3. The PH/PH/1 case 7
1.3.1. A review of discrete PH distribution 7
1.3.2. The PH/PH/1 system 9
1.4. The model with multiple interarrival time distributions 10
1.4.1. Preliminaries 11
1.4.2. A queueing model with interarrival times dependent on service times 13
1.5. Interdependent interarrival and service times 15
1.5.1. A discrete time queueing model with bivariate geometric distribution 16
1.5.2. Matrix equivalent model 17
1.6. Conclusion 18
1.7. Acknowledgements 18
1.8. References 18
Chapter 2. Busy Period, Congestion Analysis and Loss Probability in Fluid Queues 21
Fabrice GUILLEMIN, Marie-Ange REMICHE and Bruno SERICOLA
2.1. Introduction 21
2.2. Modeling a link under congestion and buffer fluctuations 24
2.2.1. Model description 25
2.2.2. Peaks and valleys 26
2.2.3. Minimum valley height in a busy period 28
2.2.4. Maximum peak level in a busy period 33
2.2.5. Maximum peak under a fixed fluid level 37
2.3. Fluid queue with finite buffer 42
2.3.1. Congestion metrics 42
2.3.2. Minimum valley height in a busy period 43
2.3.3. Reduction of the state space 46
2.3.4. Distributions of τ1(x) and V1(x) 47
2.3.5. Sequences of idle and busy periods 49
2.3.6. Joint distributions of loss periods and loss volumes 51
2.3.7. Total duration of losses and volume of information lost 56
2.4. Conclusion 59
2.5. References 60
Chapter 3. Diffusion Approximation of Queueing Systems and Networks 63
Dimitri KOROLIOUK and Vladimir S. KOROLIUK
3.1. Introduction 63
3.2. Markov queueing processes 64
3.3. Average and diffusion approximation 65
3.3.1. Average scheme 65
3.3.2. Diffusion approximation scheme 68
3.3.3. Stationary distribution 73
3.4. Markov queueing systems 78
3.4.1. Collective limit theorem in R1 78
3.4.2. Systems of M/M type 81
3.4.3. Repairman problem 82
3.5. Markov queueing networks 85
3.5.1. Collective limit theorems in RN 85
3.5.2. Markov queueing networks 89
3.5.3. Superposition of Markov processes 91
3.6. Semi-Markov queueing systems 92
3.7. Acknowledgements 96
3.8. References 96
Chapter 4. First-come First-served Retrial Queueing System by Laszlo Lakatos and its Modifications 97
Igor Nikolaevich KOVALENKO†
4.1. Introduction 97
4.2. A contribution by Laszlo Lakatos and his disciples 98
4.3. A contribution by E.V. Koba 98
4.4. An Erlangian and hyper-Erlangian approximation for a Laszlo Lakatos-type queueing system 99
4.5. Two models with a combined queueing discipline 102
4.6. References 104
Chapter 5. Parameter Mixing in Infinite-server Queues 107
Lucas VAN KREVELD and Onno BOXMA
5.1. Introduction 107
5.2. The MΛ/Coxn/∞ queue 109
5.2.1. The differential equation 110
5.2.2. Calculating moments 113
5.2.3. Steady state 120
5.2.4. MΛ/M/∞ 125
5.3. Mixing in Markov-modulated infinite-server queues 131
5.3.1. The differential equation 131
5.3.2. Calculating moments 133
5.4. Discussion and future work 142
5.5. References 143
Chapter 6. Application of Fast Simulation Methods of Queueing Theory for Solving Some High-dimension Combinatorial Problems 145
Igor KUZNETSOV and Nickolay KUZNETSOV
6.1. Introduction 146
6.2. Upper and lower bounds for the number of some k-dimensional subspaces of a given weight over a finite field 147
6.2.1. A general fast simulation algorithm 149
6.2.2. An auxiliary algorithm 153
6.2.3. Exact analytical formulae for the cases k = 1 and k = 2 155
6.2.4. The upper and lower bounds for the probability P{Yω(r)} 158
6.2.5. Numerical results 164
6.3. Evaluation of the number of “good” permutations by fast simulation on the SCIT-4 multiprocessor computer complex 167
6.3.1. Modified fast simulation method 168
6.3.2. Numerical results 171
6.4. References 174
Chapter 7. Diffusion and Gaussian Limits for Multichannel Queueing Networks 177
Eugene LEBEDEV and Hanna LIVINSKA
7.1. Introduction 177
7.2. Model description and notation 182
7.3. Local approach to prove limit theorems 184
7.3.1. Network of the [GI|M|∞]r-type in heavy traffic 185
7.4. Limit theorems for networks with controlled input flow 190
7.4.1. Diffusion approximation of [SM|M|∞]r-networks 190
7.4.2. Asymptotics of stationary distribution for [SM|GI|∞]r-networks 192
7.4.3. Convergence to Ornstein-Uhlenbeck process 194
7.5. Gaussian approximation of networks with input flow of general structure 195
7.5.1. Gaussian approximation of [G|M|∞]r-networks 195
7.5.2. Criterion of Markovian behavior for r-dimensional Gaussian processes 197
7.5.3. Non-Markov Gaussian approximation of [G|GI|∞]r-networks 198
7.6. Limit processes for network with time-dependent input flow 201
7.6.1. Gaussian approximation of [Mt|M|∞]r -networks in heavy traffic 201
7.6.2. Limit process in case of asymptotically large initial load 205
7.7. Conclusion 207
7.8. Acknowledgements 208
7.9. References 208
Chapter 8. Recent Results in Finite-source Retrial Queues with Collisions 213
Anatoly NAZAROV, János SZTRIK and Anna KVACH
8.1. Introduction 213
8.2. Model description and notations 216
8.3. Systems with a reliable server 220
8.3.1. M/M/1 systems 220
8.3.2. M/GI/1 system 224
8.4. Systems with an unreliable server 229
8.4.1. M/M/1 system 229
8.4.2. M/GI/1 system 237
8.4.3. Stochastic simulation of special systems 240
8.4.4. Gamma distributed retrial times 242
8.4.5. The effect of breakdowns disciplines 243
8.5. Conclusion 251
8.6. Acknowledgments 253
8.7. References 253
Chapter 9. Strong Stability of Queueing Systems and Networks: a Survey and Perspectives 259
Boualem RABTA, Ouiza LEKADIR and Djamil AÏSSANI
9.1. Introduction 259
9.2. Preliminary and notations 261
9.3. Strong stability of queueing systems 263
9.3.1. M/M/1 queue 264
9.3.2. PH/M/1 and M/PH/1 queues 269
9.3.3. G/M/1 and M/G/1 queues 270
9.3.4. Other queues 276
9.3.5. Queueing networks 277
9.3.6. Non-parametric perturbation 286
9.4. Conclusion and further directions 287
9.5. References 287
Chapter 10. Time-varying Queues: a Two-time-scale Approach 293
George YIN, Hanqin ZHANG and Qing ZHANG
10.1. Introduction 293
10.2. Time-varying queues 295
10.3. Main results 298
10.3.1. Large deviations of two-time-scale queues 298
10.3.2. Computation of H(y, t) 301
10.3.3. Applications to queueing systems 303
10.4. Concluding remarks 309
10.5. References 310
List of Authors 313
Index 315
