Queueing Theory 1

Vladimir Anisimov is Full Professor in Applied Statistics. He works in the Center for Design & Analysis at Amgen Inc. in London, UK. His research interests include probability models and stochastic processes, clinical trials modeling, applied statistics, queueing models and asymptotic techniques. Nikolaos Limnios is Full Professor in Applied Mathematics at the University of Technology of Compiègne, part of the Sorbonne University Group, in France. His research interests include stochastic processes and statistics, Markov and semi-Markov processes, random evolutions with applications in reliability, queueing systems, earthquakes and biology.

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