Dudin / Klimenok / Vishnevsky The Theory of Queuing Systems with Correlated Flows

1. Auflage 2019
ISBN: 978-3-030-32072-0
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 430 Seiten

This book is dedicated to the systematization and development of models, methods, and algorithms for queuing systems with correlated arrivals. After first setting up the basic tools needed for the study of queuing theory, the authors concentrate on complicated systems: multi-server systems with phase type distribution of service time or single-server queues with arbitrary distribution of service time or semi-Markovian service. They pay special attention to practically important retrial queues, tandem queues, and queues with unreliable servers. 
Mathematical models of networks and queuing systems are widely used for the study and optimization of various technical, physical, economic, industrial, and administrative systems, and this book will be valuable for researchers, graduate students, and practitioners in these domains.

Autoren/Hrsg.

Dudin, Alexander N.

Klimenok, Valentina I.

Vishnevsky, Vladimir M.

Inhaltsverzeichnis

1;Foreword;5
2;Introduction;7
3;Contents;15
4;Notation;21
5;1 Mathematical Methods to Study Classical Queuing Systems;23
5.1;1.1 Introduction;23
5.2;1.2 Input Flow, Service Time;24
5.3;1.3 Markov Random Processes;29
5.3.1;1.3.1 Birth-and-Death Processes;30
5.3.2;1.3.2 Method of Transition Intensity Diagrams;33
5.3.3;1.3.3 Discrete-Time Markov Chains;34
5.4;1.4 Probability Generating Function, Laplace and Laplace-Stieltjes Transforms;35
5.5;1.5 Single-Server Markovian Queuing Systems;37
5.5.1;1.5.1 M/M/1 Queue;37
5.5.2;1.5.2 M/M/1/n Queue;40
5.5.3;1.5.3 System with a Finite Number of Sources;41
5.6;1.6 Semi-Markovian Queuing Systems and Their Investigation Methods;42
5.6.1;1.6.1 Embedded Markov Chain Method to Study an M/G/1;42
5.6.2;1.6.2 The Method of Embedded Markov Chains for a G/M/1 Queue;50
5.6.3;1.6.3 Method of Supplementary Variables;53
5.6.4;1.6.4 Method of Supplementary Events;57
5.7;1.7 Multi-Server Queues;62
5.7.1;1.7.1 M/M/n and M/M/n/n+m Queues;63
5.7.2;1.7.2 M/M/n/n and M/G/n/n Queues;65
5.7.3;1.7.3 M/M/? Queue;67
5.7.4;1.7.4 M/G/1 with Processor Sharing and Preemptive LIFO Disciplines;71
5.8;1.8 Priority Queues;72
5.9;1.9 Multiphase Queues;78
6;2 Methods to Study Queuing Systems with Correlated Arrivals;84
6.1;2.1 Batch Markovian Arrival Process (BMAP): Phase-Type Distribution;84
6.1.1;2.1.1 Definition of the Batch Markovian Arrival Process;84
6.1.2;2.1.2 The Flow Matrix Counting Function;85
6.1.3;2.1.3 Some Properties and Integral Characteristics of BMAP;88
6.1.4;2.1.4 Special Cases of BMAP;94
6.1.5;2.1.5 Phase-Type Distribution;95
6.1.5.1;2.1.5.1 Definition of a PH Distribution;95
6.1.5.2;2.1.5.2 Partial Cases of PH Distribution;97
6.1.5.3;2.1.5.3 The Distribution of the Minimum and Maximum of Random Variables with a PH Distribution;98
6.1.6;2.1.6 Calculating the Probabilities of a Fixed Number of BMAP Arrivals During a Random Time;100
6.1.7;2.1.7 Superposition and Sifting of BMAP s;102
6.1.8;2.1.8 Batch Marked Markovian Arrival Process (BMMAP);103
6.1.9;2.1.9 Semi-Markovian Arrival Process (SM);105
6.2;2.2 Multidimensional Birth-and-Death Processes;106
6.2.1;2.2.1 Definition of the Quasi-Birth-and-Death Process and Its Stationary State Distribution;107
6.2.2;2.2.2 Application of the Results Obtained for QBD Processes to the MAP/PH/1 Queue Analysis;110
6.2.3;2.2.3 Spectral Approach for the Analysis of Quasi-Birth-and-Death Processes;114
6.3;2.3 G/M/1-Type Markov Chains;115
6.3.1;2.3.1 Definition of a G/M/1-Type MC and its Stationary State Distribution;115
6.3.2;2.3.2 Application of Results to Analysis of a G/PH/1-Type Queue;119
6.4;2.4 M/G/1-Type Markov Chains;126
6.4.1;2.4.1 Definition of an M/G/1-Type Markov Chain and Its Ergodicity Criteria;126
6.4.2;2.4.2 The Method of Generating Functions to Find the Stationary State Distribution of an M/G/1-Type MC;130
6.4.3;2.4.3 Calculation of Factorial Moments;135
6.4.4;2.4.4 A Matrix-Analytic Method to Find the Stationary State Probability Distribution of an M/G/1-Type MC(the Method of M. Neuts);138
6.5;2.5 M/G/1-Type Markov Chains with Finite State Space;146
6.6;2.6 Asymptotically Quasi-Toeplitz Discrete-Time Markov Chains;147
6.6.1;2.6.1 The Ergodicity and Nonergodicity Conditions for an Asymptotically Quasi-Toeplitz MC;148
6.6.2;2.6.2 Algorithm to Calculate the Stationary State Probabilities of an Asymptotically Quasi-Toeplitz Markov Chain;154
6.7;2.7 Asymptotically Quasi-Toeplitz Continuous-Time Markov Chains;160
6.7.1;2.7.1 Definition of a Continuous-Time AQTMC;160
6.7.2;2.7.2 Ergodicity Conditions for a Continuous-Time Asymptotically Quasi-Toeplitz MC;162
6.7.3;2.7.3 Algorithm to Calculate the Stationary State Distribution;166
7;3 Queuing Systems with Waiting Space and Correlated Arrivals and Their Application to Evaluation of Network Structure Performance;168
7.1;3.1 BMAP/G/1 Queue;168
7.1.1;3.1.1 Stationary Distribution of an Embedded Markov Chain;169
7.1.2;3.1.2 The Stationary Distribution of the System at an Arbitrary Time;177
7.1.3;3.1.3 The Virtual and Real Waiting Time Distributions;182
7.2;3.2 BMAP/SM/1 Queue;189
7.2.1;3.2.1 The Stationary Probability Distribution of an Embedded Markov Chain;190
7.2.2;3.2.2 The Stationary Probability Distribution of the System States at an Arbitrary Time;193
7.3;3.3 BMAP/SM/1/N Queue;196
7.3.1;3.3.1 Analysis of the System with the Partial AdmissionDiscipline;197
7.3.1.1;3.3.1.1 Transition Probabilities of the Embedded Markov Chain;197
7.3.1.2;3.3.1.2 A Direct Algorithm to Find the Stationary State Distribution of the Embedded Markov Chain;198
7.3.1.3;3.3.1.3 Modified Algorithm to Find the Stationary State Distribution of the Embedded Markov Chain;199
7.3.1.4;3.3.1.4 The Stationary Probability Distribution of the System States at an Arbitrary Time;201
7.3.2;3.3.2 Analysis of the System with the Complete Admission and Complete Rejection Disciplines;204
7.3.2.1;3.3.2.1 The Transition Probabilities of the Embedded Markov Chain;204
7.3.2.2;3.3.2.2 Calculation of the Vectors of the Stationary State Probabilities of the Embedded Markov Chain;207
7.3.2.3;3.3.2.3 The Stationary Distribution of the System States at an Arbitrary Time and the Loss Probability;208
7.4;3.4 BMAP/PH/N Queue;210
7.5;3.5 BMAP/PH/N/N Queue;215
7.5.1;3.5.1 The Stationary Distribution of the System States for the PA Discipline;216
7.5.2;3.5.2 The Stationary Distribution of the System States for the CR Discipline;220
7.5.3;3.5.3 The Stationary Distribution of the System States for the CA Discipline;221
8;4 Retrial Queuing Systems with Correlated Input Flows and Their Application for Network Structures Performance Evaluation;224
8.1;4.1 BMAP/SM/1 Retrial System;224
8.1.1;4.1.1 Stationary Distribution of Embedded Markov Chain;225
8.1.2;4.1.2 Stationary Distribution of the System at an Arbitrary Time;230
8.1.3;4.1.3 Performance Measures;232
8.2;4.2 BMAP/PH/N Retrial System;233
8.2.1;4.2.1 System Description;234
8.2.2;4.2.2 Markov Chain Describing the Operation of the System;234
8.2.3;4.2.3 Ergodicity Condition;238
8.2.4;4.2.4 Performance Measures;242
8.2.5;4.2.5 Case of Impatient Customers;244
8.2.6;4.2.6 Numerical Results;245
8.3;4.3 BMAP/PH/N Retrial System in the Case of a Phase Distribution of Service Time and a Large Number of Servers;254
8.3.1;4.3.1 Choice of Markov Chain for Analysis of System;254
8.3.2;4.3.2 Infinitesimal Generator and Ergodicity Condition;256
8.3.3;4.3.3 Numerical Examples;257
8.3.4;4.3.4 Algorithm for Calculation of the Matrices Pn(?), An(N,S), and LN-n(N,S?);259
8.3.4.1;4.3.4.1 Calculation of the Matrices LN-n(N,S?);259
8.3.4.2;4.3.4.2 Calculation of the Matrices Am(N,S), m=0,N;260
8.3.4.3;4.3.4.3 Calculation of the Matrices Pm(?), m=1,N-1;260
9;5 Mathematical Models and Methods of Investigation of Hybrid Communication Networks Based on Laser and Radio Technologies;262
9.1;5.1 Analysis of Characteristics of the Data Transmission Process Under Hot-Standby Architecture of a High-Speed FSO Channel Backed Up by a Wireless Broadband Radio Channel;264
9.1.1;5.1.1 Model Description;264
9.1.2;5.1.2 Process of the System States;265
9.1.3;5.1.3 Condition for Stable Operation of the System: Stationary Distribution;267
9.1.4;5.1.4 Vector Generating Function of the Stationary Distribution: Performance Measures;270
9.1.5;5.1.5 Sojourn Time Distribution;272
9.2;5.2 Analysis of Characteristics of the Data Transmission Process Under Cold-Standby Architecture of a High-Speed FSO Channel Backed Up by a Wireless Broadband Radio Channel;274
9.2.1;5.2.1 Model Description;275
9.2.2;5.2.2 Process of the System States;276
9.2.3;5.2.3 Stationary Distribution: Performance Measures;278
9.2.4;5.2.4 Numerical Experiments;282
9.2.5;5.2.5 The Case of an Exponential System;288
9.3;5.3 Analysis of Characteristics of the Data Transmission Process Under Hot-Standby Architecture of a High-Speed FSO Channel Backed Up by a Millimeter Radio Channel;294
9.3.1;5.3.1 Model Description;294
9.3.2;5.3.2 Process of the System States;295
9.3.3;5.3.3 Stationary Distribution: Performance Measures;297
9.4;5.4 Analysis of Characteristics of the Data Transmission Process Under Cold-Standby Architecture of a High-Speed FSO Channel and Millimeter Channel Backed Up by a Wireless Broadband Radio Channel;302
9.4.1;5.4.1 Model Description;302
9.4.2;5.4.2 Process of the System States;303
9.4.3;5.4.3 Stationary Distribution;308
9.4.4;5.4.4 Vector Generating Function of the Stationary Distribution: System Performance Measures;314
9.5;5.5 Numerical Experiments;317
10;6 Tandem Queues with Correlated Arrivals and Their Application to System Structure Performance Evaluation;328
10.1;6.1 Brief Review of Tandem Queues with Correlated Arrivals;328
10.2;6.2 BMAP/G/1 ?·/M/N/0 Queue with a Group Occupation of Servers of the Second Station;331
10.2.1;6.2.1 Mathematical Model;331
10.2.2;6.2.2 Stationary State Distribution of the Embedded MarkovChain;332
10.2.3;6.2.3 Stationary State Distribution at an Arbitrary Time;337
10.2.4;6.2.4 Performance Characteristics of the System;343
10.2.5;6.2.5 Stationary Sojourn Time Distribution;344
10.2.6;6.2.6 Sojourn Time Moments;352
10.2.7;6.2.7 Numerical Examples;356
10.3;6.3 BMAP/SM/1 ?·/M/N/0 Queue with a Group Occupation of Servers at the Second Station;361
10.3.1;6.3.1 Mathematical Model;361
10.3.2;6.3.2 The Stationary State Distribution of the Embedded Markov Chain;362
10.3.3;6.3.3 Stationary State Distribution at an Arbitrary Time;364
10.3.4;6.3.4 Performance Characteristics of the System;366
10.3.5;6.3.5 Numerical Examples;366
10.4;6.4 BMAP/G/1 ?·/M/N/R Queue;368
10.4.1;6.4.1 Mathematical Model;368
10.4.2;6.4.2 Stationary State Distribution of the Embedded MarkovChain;368
10.4.3;6.4.3 Stationary State Distribution at an Arbitrary Time;370
10.4.4;6.4.4 Performance Characteristics of the System;371
10.4.5;6.4.5 Numerical Examples;372
10.5;6.5 BMAP/G/1 ?·/M/N/0 Retrial Queue with a Group Occupation of Servers at the Second Station;374
10.5.1;6.5.1 Mathematical Model;374
10.5.2;6.5.2 Stationary State Distribution of the Embedded MarkovChain;375
10.5.3;6.5.3 Stationary State Distribution at an Arbitrary Time;378
10.5.4;6.5.4 Performance Characteristics of the System;380
10.5.5;6.5.5 Numerical Examples;381
10.6;6.6 Tandem of Multi-Server Queues Without Buffers;385
10.6.1;6.6.1 The System Description;385
10.6.2;6.6.2 Output Flows from the Stations;386
10.6.3;6.6.3 Stationary State Distribution of a MAP/PH/N/NQueue;388
10.6.4;6.6.4 Stationary State Distribution of the Tandem and Its Fragments;390
10.6.5;6.6.5 Customer Loss Probability;391
10.6.6;6.6.6 Investigation of the System Based on the Construction of a Markov Chain Using the Ramaswami-Lucantoni Approach;392
10.7;6.7 Tandem of Multi-Server Queues with Cross-Trafficand No Buffers;395
10.7.1;6.7.1 The System Description;395
10.7.2;6.7.2 Output Flows from the Stations: Stationary State Distribution of the Tandem and Its Fragments;396
10.7.3;6.7.3 Loss Probabilities;398
10.7.4;6.7.4 Investigation of the System Based on the Construction of the Markov Chain Using the Ramaswami-Lucantoni Approach;401
10.8;6.8 Tandem of Single-Server Queues with Finite Buffers and Cross-Traffic;403
10.8.1;6.8.1 The System Description;403
10.8.2;6.8.2 Output Flows from the Stations;404
10.8.3;6.8.3 Stationary State Distribution and the Customer Sojourn Time Distribution for a MAP/PH/1/N Queue;406
10.8.4;6.8.4 The Stationary Distribution of the Tandem and ItsFragments;408
10.8.5;6.8.5 Loss Probabilities;409
10.8.6;6.8.6 Stationary Distribution of Customer Sojourn Time in the Tandem Stations and in the Whole Tandem;411
11;A Some Information from the Theory of Matrices and Functions of Matrices;414
11.1;A.1 Stochastic and Sub-stochastic Matrices: Generators and Subgenerators;414
11.2;A.2 Functions of Matrices;419
11.3;A.3 Norms of Matrices;422
11.4;A.4 The Kronecker Product and Sum of the Matrices;423
12;References;425