Queueing Theory for Telecommunications (eBook)

Attahiru S. Alfa is a professor and NSERC Industrial Research of Teletraffic in the Department of Electrical and Computer Engineering at the University of Manitoba. He obtained his BEng from Ahmadu Bello University, Nigeria, MSc from the University of Manitoba, Canada, and PhD from the University of New South Wales, Australia. One of his main teaching and research interests is in the area of discrete time queues with applications to telecommunication systems as well as manufacturing and transportation systems. Over the years he has made a number of significant contributions in the area of matrix-analytic methods.

Preface 6
Acknowledgements 8
Contents 9
Chapter 1 13
Introduction 13
1.1 Introduction 13
1.2 A single node queue 14
1.3 A tandem queueing systems 16
1.4 A network system of queues 17
1.5 Queues in Communication networks 18
1.6 Why are queueing systems of interest? 20
1.7 Discrete time vs Continuous time analyses 20
1.7.1 Time 21
Chapter 2 23
Markov Processes 23
2.1 Introduction 23
2.2 Stochastic Processes 23
2.3 Markov Processes 25
2.4 Discrete Time Markov Chains 26
2.4.1 Examples 27
2.4.2 State of DTMC at arbitrary times 30
2.4.2.1 Example 30
2.4.2.2 Chapman Kolmogorov Equations 32
2.4.3 Classification of States 33
2.4.4 Classification of Markov Chains 35
2.5 First Passage Time 37
2.5.1 Examples 40
2.5.2 Some Key Information Provided by First Passage 41
2.5.3 Example 42
2.5.4 Mean first recurrence time 43
2.6 Absorbing Markov Chains 43
2.6.1 Characteristics of an absorbing Markov chain 44
2.7 Transient Analysis 46
2.7.1 Direct Algebraic Operations 47
2.7.1.1 Naive repeated application of P 47
2.7.1.2 Matrix decomposition approach 47
2.7.2 Transient Analysis Based on the z-Transform 48
2.8 Limiting Behaviour of Markov Chains 49
2.8.1 Ergodic Chains 49
2.8.2 Non-Ergodic Chains 50
2.8.3 Mean First Recurrence Time and Steady State Distributions 51
2.9 Numerical Computations of the Invariant Vectors 51
2.9.1 Finite State Markov Chains 51
2.9.1.1 Direct Methods 53
2.9.1.2 Iterative Methods: 55
2.9.2 Bivariate Discrete Time Markov Chains 57
2.9.3 Computing Stationary Distribution for the Finite Bivariate DTMC 58
2.9.4 Special Finite State DTMC 61
2.9.5 Infinite State Markov Chains 63
2.9.6 Some Results for Infinite State Markov Chains with Repeating Structure 63
2.9.7 Matrix-Analytical Method for Infinite State Markov Chains 65
2.9.7.1 The GI/M/1 Type 66
2.9.7.2 Key Measures 69
2.9.7.3 Computing matrix R 69
2.9.7.4 Some Special Structures of the Matrix R often Encountered 71
2.9.7.5 The M/G/1 Type: 71
2.9.7.6 Stationary distribution 72
2.9.7.7 Computing Matrix G 73
2.9.7.8 Some Special Structures of the Matrix G often Encountered 76
2.9.7.9 QBD 77
2.9.7.10 Computing the matrices R and G 80
2.9.7.11 Some Special Structures of the Matrix R and the matrix G 81
2.9.8 Other special QBDs of interest 81
2.9.8.1 Level-dependent QBDs: 81
2.9.8.2 Tree structured QBDS 82
2.9.9 Re-blocking of transition matrices 84
2.9.9.1 The non-skip-free M/G/1 type 84
2.9.9.2 The non-skip-free GI/M/1 type 86
2.9.9.3 Time-inhomogeneous Discrete Time Markov Chains 88
2.9.9.4 Time-inhomogeneous and spatially-homogeneous QBD 89
2.10 Software Tools for Matrix-Analytic Methods 90
Chapter 3 91
Characterization of Queueing Systems 91
3.1 Introduction 91
3.1.1 Factors that affect the measures 94
3.2 Arrival and Service Processes 95
3.2.1 Renewal Process 97
3.2.1.1 Number of renewals 99
3.3 Special Arrival and Service Processes in Discrete Time 99
3.3.1 Geometric Distribution 99
3.3.1.1 Lack of Memory Property: 101
3.3.2 Phase Type Distribution 101
3.3.2.1 Two very important closure properties of phase type distributions: 104
3.3.2.2 Minimal coefficient of variation of a discrete PH distribution 104
3.3.2.3 Examples of special phase type distributions 105
3.3.2.4 Analogy between PH and Geometric distributions 105
3.3.2.5 Phase Renewal Process: 106
3.3.3 The infinite phase distribution (IPH) 107
3.3.4 General Inter-event Times 108
3.3.4.1 Remaining Time Representation 108
3.3.4.2 Elapsed Time Representation 108
3.3.5 Markovian Arrival Process 109
3.3.5.1 Platoon Arrival Process (PAP) 111
3.3.5.2 Batch Markovian Arrival Process (BMAP) 113
3.3.6 Marked Markovian Arrival Process 113
3.3.7 Semi Markov Processes 114
3.3.8 Data Fitting for PH and MAP 114
Chapter 4 116
Single Node Queuing Models 116
4.1 Introduction 116
4.2 Birth-and-Death Process 117
4.3 Discrete time B-D Process 118
4.4 Geo/Geo/1 Queues 119
4.4.1 Algebraic Approach 120
4.4.2 Transform Approach 120
4.4.3 Matrix-geometric Approach 121
4.4.4 Performance Measures 122
4.4.4.1 Mean number in system: 122
4.4.4.2 Mean number in queue: 123
4.4.4.3 Waiting time in the queue: 123
4.4.4.4 Waiting time in system: 124
4.4.4.5 Duration of a Busy Period: 125
4.4.4.6 Number Served During a Busy Period: 127
4.4.4.7 Age Process 128
4.4.4.8 Workload: 128
4.4.5 Discrete time equivalent of Little’s Law: 129
4.4.6 Geo/Geo/1/K Queues 129
4.4.6.1 Departure Process 132
4.5 Geo/G/1 Queues 132
4.5.1 Supplementary Variable Technique 133
4.5.1.1 Transform Approach 133
4.5.1.2 Matrix-analytic approach 134
4.5.2 Imbedded Markov Chain Approach 136
4.5.2.1 Distribution of number in the system 137
4.5.2.2 Waiting Time: 137
4.5.2.3 Workload: 138
4.5.2.4 Age Process: 139
4.5.2.5 Busy Period: 139
4.5.3 Geo/G/1/K Queues 140
4.6 GI/Geo/1 Queues 141
4.6.1 Supplementary Variable Technique 141
4.6.1.1 Matrix-analytic approach 141
4.6.2 Imbedded Markov Chain Approach 143
4.6.2.1 Matrix-geometric approach: 144
4.6.2.2 Transform approach 144
4.6.3 GI/Geo/1/K Queues 146
4.7 Geo/PH/1 Queues 147
4.7.1 Waiting Times 148
4.8 PH/Geo/1 Queues 149
4.8.1 Waiting Times 150
4.9 PH/PH/1 Queues 151
4.9.1 Examples 153
4.9.1.1 A Numerical Example 153
4.9.1.2 Another Example 154
4.9.2 Waiting Time Distirbution 155
4.9.2.1 Workload 157
4.9.2.2 Age Process 157
4.9.3 PH/PH/1 Queues at points of events 158
4.10 GI/G/1 Queues 163
4.10.1 The (RT,RT) representation for the GI/G/1 queue 163
4.10.2 New algorithm for the GI/G/1 system 165
4.10.3 The (ET,ET) representation for the GI/G/1 queue 167
4.11 GI/G/1/K Queues 169
4.11.1 Queue length 171
4.11.2 Waiting times 171
4.11.3 Model II 173
4.12 MAP/PH/1 Queues 176
4.13 Batch Queues 176
4.13.1 GeoX/Geo/1 queue 176
4.13.1.1 Transform Approach 177
4.13.1.2 Examples 178
4.13.1.3 Matrix-analytic Approach 179
4.13.2 Geo/GeoY /1 queue 179
Chapter 5 181
Advance Single Node Queuing Models 181
5.1 Multiserver Queues 181
5.1.1 Geo/Geo/k Systems 181
5.1.1.3 An Example 186
5.1.1.4 Waiting Times 187
5.1.2 GI/Geo/k Systems 189
5.1.2.1 Using MAM Same as using supplementary variables 189
k. 5.1.2.2 Numerical Example 191
5.1.3 PH/PH/k Systems 192
5.1.4 Geo/D/k Systems 194
5.1.5 MAP/D/k Systems 197
5.1.6 BMAP/D/k Systems 197
5.2 Vacation Queues 197
5.2.1 Geo/G/1 vacation systems 198
5.2.1.1 Single vacation system 199
5.2.1.2 Multiple vacations system 201
5.2.2 GI/Geo/1 vacation systems 204
5.2.3 MAP/PH/1 vacation systems 205
5.2.3.1 Exhaustive single vacation: 205
5.2.3.2 Stationary Distribution: 208
5.2.3.3 Example of the Geo/Geo/1 vacation: 208
5.2.3.4 Exhaustive multiple vacations 209
5.2.4 MAP/PH/1 vacation queues with number limited service 210
5.2.5 MAP/PH/1 vacation queues with time limited service 212
5.2.6 Random Time Limited Vacation Queues/Queues with Server Breakdowns and Repairs 213
5.3 Priority Queues 215
5.3.1 Geo/Geo/1 Preemptive 216
5.3.1.1 Stationary Distribution 218
5.3.2 Geo/Geo/1 Non-preemptive 223
5.3.2.1 Stationary Distribution 225
5.3.3 MAP/PH/1 Preemptive 226
5.3.3.1 Stationary Distribution 228
5.3.4 MAP/PH/1 Non-preemptive 231
5.4 Queues with Multiclass of Packets 235
5.4.1 Multiclass systems – with FCFS the MMAP[K]/PH[K]/1 235
5.4.1.1 Stationary distribution and waiting times 236
5.4.2 Multiclass systems – with LCFS the MMAP[K]/PH[K]/1 237
5.4.2.1 Stability conditions 238
5.4.2.2 Performance measures 239
References 242
Index 247