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 xiChapter 1. Discrete Time Single-server Queues with Interdependent Interarrival and Service Times 1Attahiru Sule ALFA1.1. Introduction 11.2. The Geo/Geo/1 case 31.2.1. Arrival probability as a function of service completion probability 41.2.2. Service times dependent on interarrival times 61.3. The PH/PH/1 case 71.3.1. A review of discrete PH distribution 71.3.2. The PH/PH/1 system 91.4. The model with multiple interarrival time distributions 101.4.1. Preliminaries 111.4.2. A queueing model with interarrival times dependent on service times 131.5. Interdependent interarrival and service times 151.5.1. A discrete time queueing model with bivariate geometric distribution 161.5.2. Matrix equivalent model 171.6. Conclusion 181.7. Acknowledgements 181.8. References 18Chapter 2. Busy Period, Congestion Analysis and Loss Probability in Fluid Queues 21Fabrice GUILLEMIN, Marie-Ange REMICHE and Bruno SERICOLA2.1. Introduction 212.2. Modeling a link under congestion and buffer fluctuations 242.2.1. Model description 252.2.2. Peaks and valleys 262.2.3. Minimum valley height in a busy period 282.2.4. Maximum peak level in a busy period 332.2.5. Maximum peak under a fixed fluid level 372.3. Fluid queue with finite buffer 422.3.1. Congestion metrics 422.3.2. Minimum valley height in a busy period 432.3.3. Reduction of the state space 462.3.4. Distributions of τ1(x) and V1(x) 472.3.5. Sequences of idle and busy periods 492.3.6. Joint distributions of loss periods and loss volumes 512.3.7. Total duration of losses and volume of information lost 562.4. Conclusion 592.5. References 60Chapter 3. Diffusion Approximation of Queueing Systems and Networks 63Dimitri KOROLIOUK and Vladimir S. KOROLIUK3.1. Introduction 633.2. Markov queueing processes 643.3. Average and diffusion approximation 653.3.1. Average scheme 653.3.2. Diffusion approximation scheme 683.3.3. Stationary distribution 733.4. Markov queueing systems 783.4.1. Collective limit theorem in R1 783.4.2. Systems of M/M type 813.4.3. Repairman problem 823.5. Markov queueing networks 853.5.1. Collective limit theorems in RN 853.5.2. Markov queueing networks 893.5.3. Superposition of Markov processes 913.6. Semi–Markov queueing systems 923.7. Acknowledgements 963.8. References 96Chapter 4. First-come First-served Retrial Queueing System by Laszlo Lakatos and its Modifications 97Igor Nikolaevich KOVALENKO†4.1. Introduction 974.2. A contribution by Laszlo Lakatos and his disciples 984.3. A contribution by E.V. Koba 984.4. An Erlangian and hyper-Erlangian approximation for a Laszlo Lakatos-type queueing system 994.5. Two models with a combined queueing discipline 1024.6. References 104Chapter 5. Parameter Mixing in Infinite-server Queues 107Lucas VAN KREVELD and Onno BOXMA5.1. Introduction 1075.2. The MΛ/Coxn/∞ queue 1095.2.1. The differential equation 1105.2.2. Calculating moments 1135.2.3. Steady state 1205.2.4. MΛ/M/∞ 1255.3. Mixing in Markov-modulated infinite-server queues 1315.3.1. The differential equation 1315.3.2. Calculating moments 1335.4. Discussion and future work 1425.5. References 143Chapter 6. Application of Fast Simulation Methods of Queueing Theory for Solving Some High-dimension Combinatorial Problems 145Igor KUZNETSOV and Nickolay KUZNETSOV6.1. Introduction 1466.2. Upper and lower bounds for the number of some k-dimensional subspaces of a given weight over a finite field 1476.2.1. A general fast simulation algorithm 1496.2.2. An auxiliary algorithm 1536.2.3. Exact analytical formulae for the cases k = 1 and k = 2 1556.2.4. The upper and lower bounds for the probability P{ Yω(r)} 1586.2.5. Numerical results 1646.3. Evaluation of the number of “good” permutations by fast simulation on the SCIT-4 multiprocessor computer complex 1676.3.1. Modified fast simulation method 1686.3.2. Numerical results 1716.4. References 174Chapter 7. Diffusion and Gaussian Limits for Multichannel Queueing Networks 177Eugene LEBEDEV and Hanna LIVINSKA7.1. Introduction 1777.2. Model description and notation 1827.3. Local approach to prove limit theorems 1847.3.1. Network of the [GI|M|∞]r-type in heavy traffic 1857.4. Limit theorems for networks with controlled input flow 1907.4.1. Diffusion approximation of [SM|M|∞]r-networks 1907.4.2. Asymptotics of stationary distribution for [SM|GI|∞]r-networks 1927.4.3. Convergence to Ornstein–Uhlenbeck process 1947.5. Gaussian approximation of networks with input flow of general structure 1957.5.1. Gaussian approximation of [G|M|∞]r-networks 1957.5.2. Criterion of Markovian behavior for r-dimensional Gaussian processes 1977.5.3. Non-Markov Gaussian approximation of [G|GI|∞]r-networks 1987.6. Limit processes for network with time-dependent input flow 2017.6.1. Gaussian approximation of [Mt|M|∞]r -networks in heavy traffic 2017.6.2. Limit process in case of asymptotically large initial load 2057.7. Conclusion 2077.8. Acknowledgements 2087.9. References 208Chapter 8. Recent Results in Finite-source Retrial Queues with Collisions 213Anatoly NAZAROV, János SZTRIK and Anna KVACH8.1. Introduction 2138.2. Model description and notations 2168.3. Systems with a reliable server 2208.3.1. M/M/1 systems 2208.3.2. M/GI/1 system 2248.4. Systems with an unreliable server 2298.4.1. M/M/1 system 2298.4.2. M/GI/1 system 2378.4.3. Stochastic simulation of special systems 2408.4.4. Gamma distributed retrial times 2428.4.5. The effect of breakdowns disciplines 2438.5. Conclusion 2518.6. Acknowledgments 2538.7. References 253Chapter 9. Strong Stability of Queueing Systems and Networks: a Survey and Perspectives 259Boualem RABTA, Ouiza LEKADIR and Djamil AÏSSANI9.1. Introduction 2599.2. Preliminary and notations 2619.3. Strong stability of queueing systems 2639.3.1. M/M/1 queue 2649.3.2. PH/M/1 and M/PH/1 queues 2699.3.3. G/M/1 and M/G/1 queues 2709.3.4. Other queues 2769.3.5. Queueing networks 2779.3.6. Non-parametric perturbation 2869.4. Conclusion and further directions 2879.5. References 287Chapter 10. Time-varying Queues: a Two-time-scale Approach 293George YIN, Hanqin ZHANG and Qing ZHANG10.1. Introduction 29310.2. Time-varying queues 29510.3. Main results 29810.3.1. Large deviations of two-time-scale queues 29810.3.2. Computation of H(y, t) 30110.3.3. Applications to queueing systems 30310.4. Concluding remarks 30910.5. References 310List of Authors 313Index 315