It presents how most queueing models in discrete-time can be set up as discrete-time Markov chains. Techniques such as matrix-analytic methods (MAM) that can used to analyze the resulting Markov chains are included. This book covers single node systems, tandem system and queueing networks. It shows how queues with time-varying parameters can be analyzed, and illustrates numerical issues associated with computations for the discrete-time queueing systems. Optimal control of queues is also covered.
Applied Discrete-Time Queues targets researchers, advanced-level students and analysts in the field of telecommunication networks. It is suitable as a reference book and can also be used as a secondary text book in computer engineering and computer science. Examples and exercises are included.
1 Introduction . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Examples of Transparent Queues . . . . . . . . . . . . . 2
1.1.2 Examples of Non-Transparent Queues . . . . . . . . . . . . . . . 5
1.1.3 Examples of Queues Not Involving Humans Directly . . . . 6
1.2 A single node queue. . . . . . . . . . . . . . . . . . . . 7
1.3 A tandem queueing systems . . . . . . . . . . . . . . . . . 9
1.4 A network system of queues . . . . . . . . . . . . . . . . 10
1.5 Some Well-known Application Areas for Queueing Models . . . . . . 11
1.5.1 Queues in Transportation and Traffic Systems . . . . . . . . . . . . 11
1.5.2 Queues in Manufacturing Systems . . . . . . . . . . . . . . . 12
1.5.3 Queues in the Health Care Systems. . . . . . . . . . . . . . . . . . 13
1.5.4 Queues in Communication networks . . . . . . . . . . . . . 14
1.6 Why are queueing systems of interest?. . . . . . . . . . . . 16
1.7 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7.1 Performance Measures . . . . . . . . . . . . . . . 18
1.8 Characterization of Queues . . . . . . . . .. . . . . . . . . . . . . 19
1.9 Discrete time vs Continuous time analyses . . . . . . . . . . . .. . . 20
1.9.1 Time . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 20
2 Arrival and Service Processes . . . . . . . . . . . . . . . . . . . . . . 23
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .. . 23
2.2 Review of Probability for Discrete Random
Variables and Matrices . . . . . . . . . . . . . . . . . 23
2.2.1 The z transform . . . . . . . .. . . . . . . . . . 24
2.2.2 Bivariate Cases . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Some very Common Discrete Distributions . . . . . . . . . . . .. 25
2.2.4 Brief Summary of Required Material from Matrices . . . . . 28
2.2.5 Examples of Simple Representations of
Discrete Distributions Using Matrices . . . . . . . . . . . . . . . 29
2.2.6 Matrix Representation . . . . . . . . . . . . . . 31
2.3 Arrival and Service Processes . . . . . . . . . . . . 31
2.4 Renewal Process. . . . . . . . . . . . . . . .. . . . . . . . . 32
2.4.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.2 Number of renewals . . . . .. . . . . . . . . . . . 34
2.5 Special Arrival and Service Processes in Discrete Time . . . . . 34
2.5.1 Bernoulli Process . . . . . . . . . . . . . . . . . . . 34
2.5.2 Geometric Distribution . . . . . . . . . . . . . 35
2.5.3 Phase Type Distribution . . . . . . . . . . .. 37
2.5.4 The infinite phase distribution (IPH) . . . . . . . .. 44
2.5.5 General Inter-event Times. . . . . . . . . . . . . . . . . 45
2.5.6 Markovian Arrival Process . . . . . . . . . . . . . . . . 46
2.5.7 Marked Markovian Arrival Process. . . . . . . . . . . . . . 51
2.5.8 Semi Markov Processes . . . . . . . . . . . . . . . . . . 51
2.5.9 Data Fitting for PH and MAP. . . . . . . . . . . . . 52
2.6 Service Times: What does this really mean?. . . . . . . . 53
2.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3 Discrete-Time Markov Chains . . . . . . . . . . . . . . . . . . . . 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Stochastic Processes. . . .. . . . . . . . . . . . . . 57
3.3 Markov Processes . . . . . . . . . . . . . . . . . . . . 59
3.4 Discrete Time Markov Chains . . . . . . . . . . . . 60
3.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.2 State of DTMC at arbitrary times . . . . . 64
3.4.3 Classification of States . . . . . . . . . . 68
3.4.4 Classification of Markov Chains . . . .. . 71
3.5 First Passage Time . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.2 Some Key Information Provided by First Passage . . . . . . . . 76
3.5.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.5.4 Mean first recurrence time .. . . . . . 78
3.6 Absorbing Markov Chains . .. . . . . . . . . . . . . . 78
3.6.1 Characteristics of an absorbing Markov chain . . . .. . 79
3.7 Censored Markov Chains . .. . . . . . . . . . . . . . . . . . 82
3.8 Transient Analysis. . .. . . . . . . . . . . . . . . . . . . . . . 83
3.8.1 Direct Algebraic Operations . . . . . . . . . . . . 83
3.8.2 Transient Analysis Based on the z-Transform . . . . . . . . . . . . 84
3.9 Limiting Behaviour of Markov Chains . . . . . . . . . . 85
3.9.1 Ergodic Chains. . . . . . .. . . . . . . . . . . . . . . . 85
3.9.2 Non-Ergodic Chains . . . . . . . . . . . . . 86
3.9.3 Mean First Recurrence Time and Steady State Distributions . . . 87
3.10 Bivariate Discrete Time Markov Chains . . . . . . . 88
4 Numerical Computations with Discrete-Time Markov Chains. . . . . . . . 91
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2 Numerical Computations of the Invariant Vectors . .. . 91
4.3 Finite State Markov Chains . . . .. . . . . . . . . . . . . . . . 92
4.3.1 Direct Methods . . . . . . . .. . . . . . . . . . 93
4.3.2 Iterative Methods . . . . . . . . . . . . . . . . . . . . . 95
4.4 Bivariate Discrete Time Markov Chains . . . . . . . . 98
4.4.1 Computing Stationary Distribution for the Finite Bivariate DTMC. . 99
4.5 Special Finite State DTMC . . . . . .. . . . . . . . . . . . 102
4.6 Infinite State Markov Chains . . . .. . . . . . . . . . . . . 104
4.7 Some Results for Infinite State Markov Chains with Repeating Structure . 105
4.8 Matrix-Analytical Method for Infinite State Markov Chains . . . . . . 107
4.8.1 The GI/M/1 Type . . . . . . . . . . . . . . . . . . . 107
4.8.2 Key Measures . . . . . . . . . . . . . . . . . . . . . 110
4.8.3 Some Special Structures of the Matrix R often Encountered. . . . . 113
4.8.4 The M/G/1 Type . . . . . . . . . . . 114
4.8.5 Computing Matrix G . . . . . . . . . .. . . . . . . 116
4.8.6 Some Special Structures of the Matrix G often Encountered. . . . 119
4.8.7 QBD. . . . . . . . . . . . . . . . . . . . . . . 120
4.8.8 Computing the matrices R and G . . . . . . . . . . 123
4.8.9 Some Special Structures of the Matrix R and the matrix G .. 125
4.9 Other special QBDs of interest . . . . . . . . . . . . 125
4.9.1 Level-dependent QBDs: . . . . . . 125
4.9.2 Tree structured QBDS . . . . . . . . . . . 126
4.9.3 Re-blocking of transition matrices . . . .. . 129
4.9.4 Time-inhomogeneous Discrete Time Markov Chains . . . . 132
4.9.5 Time-inhomogeneous and spatially-homogeneous QBD . . . . 134
4.10 Software Tools for Matrix-Analytic Methods. . . . . . 135
5 Basic Single Node Queueing Models with Infinite Buffers . . . . . 139
5.1 Introduction . . . . . . . . . . . . . . . . . . . . 139
5.2 Birth-and-Death Process . . .. . . . . . . . . . 140
5.3 Discrete time B-D Process . . . . . . . . . . 141
5.4 Geo/Geo/1 Queues .. . . . . . . . . . . . . . . . . . . . . . . 143
5.4.1 Algebraic Approach .. . . . . . 144
5.4.2 Transform Approach . . . . .. . . . 145
5.4.4 Performance Measures . . . . . . . . . 146
5.4.5 Discrete time equivalent of Little’s Law: . . . . . . . . 154
5.5 Geo/Geo/1 System with Start-up Times. . . . . . . . . . . .. 155
5.6 Geo/G/1 Queues . . . . . . . . . . . . . . . . . . . . . . 155
5.6.1 Supplementary Variable Technique . . . . . 156
5.6.2 Imbedded Markov Chain Approach . . . . . . . . 159
5.6.3 Mean-Value approach . . . . . . . . . . . . 164
5.7 GI/Geo/1 Queues . . . . . . . . . . . . . . . . . . . . . . . 166
5.7.1 Supplementary Variable Technique . . . . . 166
5.7.2 Imbedded Markov Chain Approach . . 168
5.8 Geo/PH/1 Queues .. . . . . . . . . . . . . . . . . . . 171
5.8.1 Waiting Times . . . . . . . . . . . 173
5.9 PH/Geo/1 Queues . . . . . . . . . . . . . . 174
5.9.1 Waiting Times . . . . . . . . . . . 175
5.10 PH/PH/1 Queues . . . . . . . . . . . . . . . . 176
5.10.1 Examples . . . . . . . . . . . . . . . . . . . . . . 178
5.10.2 Waiting Time Distribution . . . . . . . . . . . . . . 181
5.10.3 PH/PH/1 Queues at points of events . . . . . 184
5.11 PH/PH/1 System with Start-up Times . . . . . . . . 190
5.12 GI/G/1 Queues. . . . . . .. . . . . . . . . . . . . . . . . . . . 191
5.12.1 The (RT,RT) representation for the GI/G/1 queue . . . . . . . . 191
5.12.2 New algorithm for the GI/G/1 system . . . . .. . 193
5.12.3 The (ET,ET) representation for the GI/G/1 queue . . . . . . . . 196
5.13 MAP/PH/1 Queues . . . . . . . . . . . . . . . . . 198
5.14 Batch Queues . . . . . . . . . . . . . . . . . . . . . . . . 198
5.14.1 GeoX/Geo/1 queue . . . . . . . . . . . 199
5.14.2 The BMAP/PH/1 System . . . 202
5.14.3 Geo/GeoY /1 queue . . . . . . 204
6 Basic Single Node Queueing Models with Finite Buffers . . . 209
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
6.2 Geo/Geo/1/K Queues . . . . . . . . . . . . . . . . 209
6.2.1 Busy Period . . . . . . . . . . . . . . . . . . . . . 210
6.2.2 Waiting Time in the Queue. . . . . 211
6.2.3 Departure Process . . . . . . . 212
6.3 Geo/G/1/K-1 Queues . . . . . . . . . . . . . . . 212
6.4 GI/Geo/1/K-1 Queues . . . . . . . . . . . . . . 213
6.5 GI/G/1/K-1 Queues . . . . . . . . . . . . . . . . 214
6.5.1 GI/G/1/K-1 Queues – Model I . . . . . 214
6.5.2 GI/G/1/K-1 Queue – Model II . . . . . . 219
6.6 Queues with Very Large Buffers . . . . 221
6.6.1 When Traffic Intensity is Less Than 1 . . . . . 222
6.6.2 When Traffic Intensity is More Than 1 . . . . .. 223
7 Multiserver Single Node Queueing Models .. 227
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 227
7.2 Geo/Geo/k Systems . . . . . . . . . . . . . 227
7.2.1 As GI/M/1 type . . . . . . . . . . 228
7.2.2 As a QBD . . . . . . . . . . . . . . . . . . . 231
7.2.3 An Example . . . . . . . . . . . . 233
7.2.4 Waiting Times . . . . . . . . . 233
7.3 GI/Geo/k Systems . . . . . . . . . . . . . . . . 236
7.3.1 Using MAM - Same as using supplementary variables . . . 236
7.3.2 Numerical Example . . . . . . . . 239
7.4 PH/PH/k Systems . . . . . .. . . . . . . . . . . . 240
7.5 Geo/D/k Systems . .. . . . . . . . . . . . . . 242
7.5.1 Waiting Times . . . . . . . . 244
7.6 MAP/D/k Systems . . . . . . . . . . . . . . . . 245
7.7 BMAP/D/k Systems. . .. . . . . . . . . . 249
7.8 Geo/G/∞ Systems . . . . . . . . . . . . . . . . 252
7.8.1 Preliminaries . . . . . . . . . . . . 253
7.8.2 The Number in the System at Arbitrary Times.. 254
7.8.3 Special Case of Geo/D/∞. . . . . . . . . . 255
7.8.4 The Limiting Distribution of the Number in the System . . . . 256
7.8.5 Extension to the PH/G/∞ Case . . . . 259
8 Single Node Queueing Models with Server Vacations 261
8.1 Vacation Queues. . . . . . . . . . . . . . . . . . . 261
8.2 Geo/G/1 vacation systems . . . . . . . . . 262
8.2.1 Single vacation system . . . . . . 262
8.2.2 Multiple vacations system. . . . . . 265
8.3 GI/Geo/1 vacation systems . . . . . . . . . . . . . 268
8.4 MAP/PH/1 vacation systems . . . . . . . . . . . . . 270
8.4.1 Exhaustive single vacation . . . . . 270
8.4.2 Stationary Distribution . . . . . . . 273
8.4.3 Example of the Geo/Geo/1 vacation . . . . .. 273
8.4.4 Exhaustive multiple vacations . . . . . . . . 274
8.5 MAP/PH/1 vacation queues with number limited service . . . 275
8.6 MAP/PH/1 vacation queues with time limited service . . .277
8.7 Random Time Limited Vacation Queues/Queues with Server Breakdowns and Repairs. 279
9 Single Node Queueing Models with Priorities . . .. . 283
9.1 Introduction . . . . . . . . . . . . . . . . . . . . 283
9.2 Geo/Geo/1 Preemptive . . . . . . . . . . . . . . 283
9.2.1 Stationary Distribution . . . . 287
9.3 Geo/Geo/1 Non-preemptive . . . . . . . 292
9.3.1 Stationary Distribution . . . . . 294
9.4 MAP/PH/1 Preemptive . . . . . . . . . . . . . . . . 296
9.4.1 Stationary Distribution . . . . . . . 298
9.5 MAP/PH/1 Non-preemptive . . . . . . . . . . . . . 301
9.5.1 Stationary Distribution . . . . . . . . 304
10 Special Single Node Queueing Models . . . . . . . . . . . 307
10.1 Introduction . . . . . . . . . . . . . . . . . . . . 307
10.2 Queues with Multiclass of Packets . . . . . . 307
10.2.1 Multiclass systems – with FCFS - the MMAP [K]/PH[K]/1. . . . . . . . 308
10.2.2 Multiclass systems – with LCFS - the MMAP [K]/PH[K]/1 . . . . . . . . 310
10.3 Waiting Time Distribution for the LCFS Geo/Geo/1 System . . . . . . 315
10.4 Waiting Time Distribution for the Geo/Geo/1 System with SIRO. . 316
10.5 Pair Formation Queues (aka Double-ended Queues) . .. . 318
10.5.1 Pair formation bounded at one end . . . . 319
10.6 Finite Source Queues. . . . . . . . . . . . . 320
11 Queues with Time Varying Parameters . . . . . . 323
11.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . 323
11.2 Discrete Time Time-Varying B-D Process . . . 323
11.2.1 The Method of Rectangular Matrix . . . . .. 324
11.2.2 The Use of z-Transforms for the Geon/Geon/1 system . . . 325
11.3 The Geon/Geon/k system . .. . . . . . . . . . . 326
11.4 The Geon/GeoYn/1 system . . . . . . . . . . . . 328
11.5 The PHn/PHn/1 System . . . . . . . . . . . 330
11.6 The Geon/G/1 System . . . . . . . . . . . . . . . 332
11.7 The Geo(Xn)n /G/1 system . . . . 333
12 Tandem Queues and Queueing Networks. . . . 339
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . 339
12.2 Two Queues in Tandem – The Geometric Case . . . 339
12.2.1 Second Queue with Infinite Buffer . . . 340
12.2.2 Second Queue with Finite Buffer . . . . . . 347
12.3 Two Queues in Tandem – The Phase Type Case . . . . . . 350
12.3.1 Second Queue with Infinite Buffer . . . . . . . . 350
12.3.2 Second Queue with Finite Buffer . . . . . . . . . . . . 352
12.3.3 Both First and Second Queues with Finite Buffers . . . . . . . 356
12.4 Approximating (N > 2) Tandem Queues Using Above Results . . . 357
12.4.1 Decomposition to N single queues . . . . . . . 357
12.4.2 Decomposition to N −1 two tandem queues . . . . . 360
12.5 Queueing Networks. . . . . . . . . . . . . . . . . . . . . . . 361
12.5.1 The Challenges of Discrete Time Queueing Networks . . . 362
12.5.2 Approximations for Discrete Time Queueing Networks . 364
12.5.3 Simple Tandem . . . . . . . . . . 364
12.5.4 Merge . . . . . . . . . . . . . . . . . . . 364
12.5.5 Split . . . . . . . . . . . . . . . . . . . . . . 365
12.5.6 Merge-Split . . . . . . . . . . 365
13 Optimization and Control of Discrete-Time Queues . . . . 367
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 367
13.2 Controlling the Arrival Process . . . . . . . . . . . 368
13.2.1 One Queue Length Threshold Problem. . . . . 368
13.2.2 Two Queue Length Thresholds . . . . . . . . . 370
13.2.3 Maximizing Throughput, While Minimizing Loss Probability in Finite Buffer Systems 372
13.2.4 Finding the Maximum Profit, When Costs and Revenues are Associated 373
13.3 Controlling the Service Process . . . . . . . . . . . 375
13.3.1 Selection of Appropriate Number of Servers. . 376
No comments:
Post a Comment