The Theory of Queuing Systems with Correlated Flows (eBook)

Foreword 5
Introduction 7
Contents 15
Notation 21
1 Mathematical Methods to Study Classical Queuing Systems 23
1.1 Introduction 23
1.2 Input Flow, Service Time 24
1.3 Markov Random Processes 29
1.3.1 Birth-and-Death Processes 30
1.3.2 Method of Transition Intensity Diagrams 33
1.3.3 Discrete-Time Markov Chains 34
1.4 Probability Generating Function, Laplace and Laplace-Stieltjes Transforms 35
1.5 Single-Server Markovian Queuing Systems 37
1.5.1 M/M/1 Queue 37
1.5.2 M/M/1/n Queue 40
1.5.3 System with a Finite Number of Sources 41
1.6 Semi-Markovian Queuing Systems and Their Investigation Methods 42
1.6.1 Embedded Markov Chain Method to Study an M/G/1 42
1.6.2 The Method of Embedded Markov Chains for a G/M/1 Queue 50
1.6.3 Method of Supplementary Variables 53
1.6.4 Method of Supplementary Events 57
1.7 Multi-Server Queues 62
1.7.1 M/M/n and M/M/n/n+m Queues 63
1.7.2 M/M/n/n and M/G/n/n Queues 65
1.7.3 M/M/? Queue 67
1.7.4 M/G/1 with Processor Sharing and Preemptive LIFO Disciplines 71
1.8 Priority Queues 72
1.9 Multiphase Queues 78
2 Methods to Study Queuing Systems with Correlated Arrivals 84
2.1 Batch Markovian Arrival Process (BMAP): Phase-Type Distribution 84
2.1.1 Definition of the Batch Markovian Arrival Process 84
2.1.2 The Flow Matrix Counting Function 85
2.1.3 Some Properties and Integral Characteristics of BMAP 88
2.1.4 Special Cases of BMAP 94
2.1.5 Phase-Type Distribution 95
2.1.5.1 Definition of a PH Distribution 95
2.1.5.2 Partial Cases of PH Distribution 97
2.1.5.3 The Distribution of the Minimum and Maximum of Random Variables with a PH Distribution 98
2.1.6 Calculating the Probabilities of a Fixed Number of BMAP Arrivals During a Random Time 100
2.1.7 Superposition and Sifting of BMAP s 102
2.1.8 Batch Marked Markovian Arrival Process (BMMAP) 103
2.1.9 Semi-Markovian Arrival Process (SM) 105
2.2 Multidimensional Birth-and-Death Processes 106
2.2.1 Definition of the Quasi-Birth-and-Death Process and Its Stationary State Distribution 107
2.2.2 Application of the Results Obtained for QBD Processes to the MAP/PH/1 Queue Analysis 110
2.2.3 Spectral Approach for the Analysis of Quasi-Birth-and-Death Processes 114
2.3 G/M/1-Type Markov Chains 115
2.3.1 Definition of a G/M/1-Type MC and its Stationary State Distribution 115
2.3.2 Application of Results to Analysis of a G/PH/1-Type Queue 119
2.4 M/G/1-Type Markov Chains 126
2.4.1 Definition of an M/G/1-Type Markov Chain and Its Ergodicity Criteria 126
2.4.2 The Method of Generating Functions to Find the Stationary State Distribution of an M/G/1-Type MC 130
2.4.3 Calculation of Factorial Moments 135
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
2.5 M/G/1-Type Markov Chains with Finite State Space 146
2.6 Asymptotically Quasi-Toeplitz Discrete-Time Markov Chains 147
2.6.1 The Ergodicity and Nonergodicity Conditions for an Asymptotically Quasi-Toeplitz MC 148
2.6.2 Algorithm to Calculate the Stationary State Probabilities of an Asymptotically Quasi-Toeplitz Markov Chain 154
2.7 Asymptotically Quasi-Toeplitz Continuous-Time Markov Chains 160
2.7.1 Definition of a Continuous-Time AQTMC 160
2.7.2 Ergodicity Conditions for a Continuous-Time Asymptotically Quasi-Toeplitz MC 162
2.7.3 Algorithm to Calculate the Stationary State Distribution 166
3 Queuing Systems with Waiting Space and Correlated Arrivals and Their Application to Evaluation of Network Structure Performance 168
3.1 BMAP/G/1 Queue 168
3.1.1 Stationary Distribution of an Embedded Markov Chain 169
3.1.2 The Stationary Distribution of the System at an Arbitrary Time 177
3.1.3 The Virtual and Real Waiting Time Distributions 182
3.2 BMAP/SM/1 Queue 189
3.2.1 The Stationary Probability Distribution of an Embedded Markov Chain 190
3.2.2 The Stationary Probability Distribution of the System States at an Arbitrary Time 193
3.3 BMAP/SM/1/N Queue 196
3.3.1 Analysis of the System with the Partial AdmissionDiscipline 197
3.3.1.1 Transition Probabilities of the Embedded Markov Chain 197
3.3.1.2 A Direct Algorithm to Find the Stationary State Distribution of the Embedded Markov Chain 198
3.3.1.3 Modified Algorithm to Find the Stationary State Distribution of the Embedded Markov Chain 199
3.3.1.4 The Stationary Probability Distribution of the System States at an Arbitrary Time 201
3.3.2 Analysis of the System with the Complete Admission and Complete Rejection Disciplines 204
3.3.2.1 The Transition Probabilities of the Embedded Markov Chain 204
3.3.2.2 Calculation of the Vectors of the Stationary State Probabilities of the Embedded Markov Chain 207
3.3.2.3 The Stationary Distribution of the System States at an Arbitrary Time and the Loss Probability 208
3.4 BMAP/PH/N Queue 210
3.5 BMAP/PH/N/N Queue 215
3.5.1 The Stationary Distribution of the System States for the PA Discipline 216
3.5.2 The Stationary Distribution of the System States for the CR Discipline 220
3.5.3 The Stationary Distribution of the System States for the CA Discipline 221
4 Retrial Queuing Systems with Correlated Input Flows and Their Application for Network Structures Performance Evaluation 224
4.1 BMAP/SM/1 Retrial System 224
4.1.1 Stationary Distribution of Embedded Markov Chain 225
4.1.2 Stationary Distribution of the System at an Arbitrary Time 230
4.1.3 Performance Measures 232
4.2 BMAP/PH/N Retrial System 233
4.2.1 System Description 234
4.2.2 Markov Chain Describing the Operation of the System 234
4.2.3 Ergodicity Condition 238
4.2.4 Performance Measures 242
4.2.5 Case of Impatient Customers 244
4.2.6 Numerical Results 245
4.3 BMAP/PH/N Retrial System in the Case of a Phase Distribution of Service Time and a Large Number of Servers 254
4.3.1 Choice of Markov Chain for Analysis of System 254
4.3.2 Infinitesimal Generator and Ergodicity Condition 256
4.3.3 Numerical Examples 257
4.3.4 Algorithm for Calculation of the Matrices Pn(?), An(N,S), and LN-n(N,S?) 259
4.3.4.1 Calculation of the Matrices LN-n(N,S?) 259
4.3.4.2 Calculation of the Matrices Am(N,S), m=0,N 260
4.3.4.3 Calculation of the Matrices Pm(?), m=1,N-1 260
5 Mathematical Models and Methods of Investigation of Hybrid Communication Networks Based on Laser and Radio Technologies 262
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
5.1.1 Model Description 264
5.1.2 Process of the System States 265
5.1.3 Condition for Stable Operation of the System: Stationary Distribution 267
5.1.4 Vector Generating Function of the Stationary Distribution: Performance Measures 270
5.1.5 Sojourn Time Distribution 272
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
5.2.1 Model Description 275
5.2.2 Process of the System States 276
5.2.3 Stationary Distribution: Performance Measures 278
5.2.4 Numerical Experiments 282
5.2.5 The Case of an Exponential System 288
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
5.3.1 Model Description 294
5.3.2 Process of the System States 295
5.3.3 Stationary Distribution: Performance Measures 297
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
5.4.1 Model Description 302
5.4.2 Process of the System States 303
5.4.3 Stationary Distribution 308
5.4.4 Vector Generating Function of the Stationary Distribution: System Performance Measures 314
5.5 Numerical Experiments 317
6 Tandem Queues with Correlated Arrivals and Their Application to System Structure Performance Evaluation 328
6.1 Brief Review of Tandem Queues with Correlated Arrivals 328
6.2 BMAP/G/1 ?·/M/N/0 Queue with a Group Occupation of Servers of the Second Station 331
6.2.1 Mathematical Model 331
6.2.2 Stationary State Distribution of the Embedded MarkovChain 332
6.2.3 Stationary State Distribution at an Arbitrary Time 337
6.2.4 Performance Characteristics of the System 343
6.2.5 Stationary Sojourn Time Distribution 344
6.2.6 Sojourn Time Moments 352
6.2.7 Numerical Examples 356
6.3 BMAP/SM/1 ?·/M/N/0 Queue with a Group Occupation of Servers at the Second Station 361
6.3.1 Mathematical Model 361
6.3.2 The Stationary State Distribution of the Embedded Markov Chain 362
6.3.3 Stationary State Distribution at an Arbitrary Time 364
6.3.4 Performance Characteristics of the System 366
6.3.5 Numerical Examples 366
6.4 BMAP/G/1 ?·/M/N/R Queue 368
6.4.1 Mathematical Model 368
6.4.2 Stationary State Distribution of the Embedded MarkovChain 368
6.4.3 Stationary State Distribution at an Arbitrary Time 370
6.4.4 Performance Characteristics of the System 371
6.4.5 Numerical Examples 372
6.5 BMAP/G/1 ?·/M/N/0 Retrial Queue with a Group Occupation of Servers at the Second Station 374
6.5.1 Mathematical Model 374
6.5.2 Stationary State Distribution of the Embedded MarkovChain 375
6.5.3 Stationary State Distribution at an Arbitrary Time 378
6.5.4 Performance Characteristics of the System 380
6.5.5 Numerical Examples 381
6.6 Tandem of Multi-Server Queues Without Buffers 385
6.6.1 The System Description 385
6.6.2 Output Flows from the Stations 386
6.6.3 Stationary State Distribution of a MAP/PH/N/NQueue 388
6.6.4 Stationary State Distribution of the Tandem and Its Fragments 390
6.6.5 Customer Loss Probability 391
6.6.6 Investigation of the System Based on the Construction of a Markov Chain Using the Ramaswami-Lucantoni Approach 392
6.7 Tandem of Multi-Server Queues with Cross-Trafficand No Buffers 395
6.7.1 The System Description 395
6.7.2 Output Flows from the Stations: Stationary State Distribution of the Tandem and Its Fragments 396
6.7.3 Loss Probabilities 398
6.7.4 Investigation of the System Based on the Construction of the Markov Chain Using the Ramaswami-Lucantoni Approach 401
6.8 Tandem of Single-Server Queues with Finite Buffers and Cross-Traffic 403
6.8.1 The System Description 403
6.8.2 Output Flows from the Stations 404
6.8.3 Stationary State Distribution and the Customer Sojourn Time Distribution for a MAP/PH/1/N Queue 406
6.8.4 The Stationary Distribution of the Tandem and ItsFragments 408
6.8.5 Loss Probabilities 409
6.8.6 Stationary Distribution of Customer Sojourn Time in the Tandem Stations and in the Whole Tandem 411
A Some Information from the Theory of Matrices and Functions of Matrices 414
A.1 Stochastic and Sub-stochastic Matrices: Generators and Subgenerators 414
A.2 Functions of Matrices 419
A.3 Norms of Matrices 422
A.4 The Kronecker Product and Sum of the Matrices 423
References 425