Alfa Queueing Theory for Telecommunications

Discrete Time Modelling of a Single Node System
1. Auflage 2010
ISBN: 978-1-4419-7314-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 238 Seiten

Queueing theory applications can be discovered in many walks of life including; transportation, manufacturing, telecommunications, computer systems and more. However, the most prevalent applications of queueing theory are in the telecommunications field. Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System focuses on discrete time modeling and illustrates that most queueing systems encountered in real life can be set up as a Markov chain. This feature is very unique because the models are set in such a way that matrix-analytic methods are used to analyze them. Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System is the most relevant book available on queueing models designed for applications to telecommunications. This book presents clear concise theories behind how to model and analyze key single node queues in discrete time using special tools that were presented in the second chapter. The text also delves into the types of single node queues that are very frequently encountered in telecommunication systems modeling, and provides simple methods for analyzing them. Where appropriate, alternative analysis methods are also presented. This book is for advanced-level students and researchers concentrating on engineering, computer science and mathematics as a secondary text or reference book. Professionals who work in the related industries of telecommunications, industrial engineering and communications engineering will find this book useful as well.

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.

Autoren/Hrsg.

Alfa, Attahiru Sule

Inhaltsverzeichnis

1;Preface;6
2;Acknowledgements;8
3;Contents;9
4;Chapter 1;13
4.1;Introduction;13
4.1.1;1.1 Introduction;13
4.1.2;1.2 A single node queue;14
4.1.3;1.3 A tandem queueing systems;16
4.1.4;1.4 A network system of queues;17
4.1.5;1.5 Queues in Communication networks;18
4.1.6;1.6 Why are queueing systems of interest?;20
4.1.7;1.7 Discrete time vs Continuous time analyses;20
4.1.7.1;1.7.1 Time;21
5;Chapter 2;23
5.1;Markov Processes;23
5.1.1;2.1 Introduction;23
5.1.2;2.2 Stochastic Processes;23
5.1.3;2.3 Markov Processes;25
5.1.4;2.4 Discrete Time Markov Chains;26
5.1.4.1;2.4.1 Examples;27
5.1.4.2;2.4.2 State of DTMC at arbitrary times;30
5.1.4.2.1;2.4.2.1 Example;30
5.1.4.2.2;2.4.2.2 Chapman Kolmogorov Equations;32
5.1.4.3;2.4.3 Classification of States;33
5.1.4.4;2.4.4 Classification of Markov Chains;35
5.1.5;2.5 First Passage Time;37
5.1.5.1;2.5.1 Examples;40
5.1.5.2;2.5.2 Some Key Information Provided by First Passage;41
5.1.5.3;2.5.3 Example;42
5.1.5.4;2.5.4 Mean first recurrence time;43
5.1.6;2.6 Absorbing Markov Chains;43
5.1.6.1;2.6.1 Characteristics of an absorbing Markov chain;44
5.1.7;2.7 Transient Analysis;46
5.1.7.1;2.7.1 Direct Algebraic Operations;47
5.1.7.1.1;2.7.1.1 Naive repeated application of P;47
5.1.7.1.2;2.7.1.2 Matrix decomposition approach;47
5.1.7.2;2.7.2 Transient Analysis Based on the z-Transform;48
5.1.8;2.8 Limiting Behaviour of Markov Chains;49
5.1.8.1;2.8.1 Ergodic Chains;49
5.1.8.2;2.8.2 Non-Ergodic Chains;50
5.1.8.3;2.8.3 Mean First Recurrence Time and Steady State Distributions;51
5.1.9;2.9 Numerical Computations of the Invariant Vectors;51
5.1.9.1;2.9.1 Finite State Markov Chains;51
5.1.9.1.1;2.9.1.1 Direct Methods;53
5.1.9.1.2;2.9.1.2 Iterative Methods:;55
5.1.9.2;2.9.2 Bivariate Discrete Time Markov Chains;57
5.1.9.3;2.9.3 Computing Stationary Distribution for the Finite Bivariate DTMC;58
5.1.9.4;2.9.4 Special Finite State DTMC;61
5.1.9.5;2.9.5 Infinite State Markov Chains;63
5.1.9.6;2.9.6 Some Results for Infinite State Markov Chains with Repeating Structure;63
5.1.9.7;2.9.7 Matrix-Analytical Method for Infinite State Markov Chains;65
5.1.9.7.1;2.9.7.1 The GI/M/1 Type;66
5.1.9.7.2;2.9.7.2 Key Measures;69
5.1.9.7.3;2.9.7.3 Computing matrix R;69
5.1.9.7.4;2.9.7.4 Some Special Structures of the Matrix R often Encountered;71
5.1.9.7.5;2.9.7.5 The M/G/1 Type:;71
5.1.9.7.6;2.9.7.6 Stationary distribution;72
5.1.9.7.7;2.9.7.7 Computing Matrix G;73
5.1.9.7.8;2.9.7.8 Some Special Structures of the Matrix G often Encountered;76
5.1.9.7.9;2.9.7.9 QBD;77
5.1.9.7.10;2.9.7.10 Computing the matrices R and G;80
5.1.9.7.11;2.9.7.11 Some Special Structures of the Matrix R and the matrix G;81
5.1.9.8;2.9.8 Other special QBDs of interest;81
5.1.9.8.1;2.9.8.1 Level-dependent QBDs:;81
5.1.9.8.2;2.9.8.2 Tree structured QBDS;82
5.1.9.9;2.9.9 Re-blocking of transition matrices;84
5.1.9.9.1;2.9.9.1 The non-skip-free M/G/1 type;84
5.1.9.9.2;2.9.9.2 The non-skip-free GI/M/1 type;86
5.1.9.9.3;2.9.9.3 Time-inhomogeneous Discrete Time Markov Chains;88
5.1.9.9.4;2.9.9.4 Time-inhomogeneous and spatially-homogeneous QBD;89
5.1.10;2.10 Software Tools for Matrix-Analytic Methods;90
6;Chapter 3;91
6.1;Characterization of Queueing Systems;91
6.1.1;3.1 Introduction;91
6.1.1.1;3.1.1 Factors that affect the measures;94
6.1.2;3.2 Arrival and Service Processes;95
6.1.2.1;3.2.1 Renewal Process;97
6.1.2.1.1;3.2.1.1 Number of renewals;99
6.1.3;3.3 Special Arrival and Service Processes in Discrete Time;99
6.1.3.1;3.3.1 Geometric Distribution;99
6.1.3.1.1;3.3.1.1 Lack of Memory Property:;101
6.1.3.2;3.3.2 Phase Type Distribution;101
6.1.3.2.1;3.3.2.1 Two very important closure properties of phase type distributions:;104
6.1.3.2.2;3.3.2.2 Minimal coefficient of variation of a discrete PH distribution;104
6.1.3.2.3;3.3.2.3 Examples of special phase type distributions;105
6.1.3.2.4;3.3.2.4 Analogy between PH and Geometric distributions;105
6.1.3.2.5;3.3.2.5 Phase Renewal Process:;106
6.1.3.3;3.3.3 The infinite phase distribution (IPH);107
6.1.3.4;3.3.4 General Inter-event Times;108
6.1.3.4.1;3.3.4.1 Remaining Time Representation;108
6.1.3.4.2;3.3.4.2 Elapsed Time Representation;108
6.1.3.5;3.3.5 Markovian Arrival Process;109
6.1.3.5.1;3.3.5.1 Platoon Arrival Process (PAP);111
6.1.3.5.2;3.3.5.2 Batch Markovian Arrival Process (BMAP);113
6.1.3.6;3.3.6 Marked Markovian Arrival Process;113
6.1.3.7;3.3.7 Semi Markov Processes;114
6.1.3.8;3.3.8 Data Fitting for PH and MAP;114
7;Chapter 4;116
7.1;Single Node Queuing Models;116
7.1.1;4.1 Introduction;116
7.1.2;4.2 Birth-and-Death Process;117
7.1.3;4.3 Discrete time B-D Process;118
7.1.4;4.4 Geo/Geo/1 Queues;119
7.1.4.1;4.4.1 Algebraic Approach;120
7.1.4.2;4.4.2 Transform Approach;120
7.1.4.3;4.4.3 Matrix-geometric Approach;121
7.1.4.4;4.4.4 Performance Measures;122
7.1.4.4.1;4.4.4.1 Mean number in system:;122
7.1.4.4.2;4.4.4.2 Mean number in queue:;123
7.1.4.4.3;4.4.4.3 Waiting time in the queue:;123
7.1.4.4.4;4.4.4.4 Waiting time in system:;124
7.1.4.4.5;4.4.4.5 Duration of a Busy Period:;125
7.1.4.4.6;4.4.4.6 Number Served During a Busy Period:;127
7.1.4.4.7;4.4.4.7 Age Process;128
7.1.4.4.8;4.4.4.8 Workload:;128
7.1.4.5;4.4.5 Discrete time equivalent of Little’s Law:;129
7.1.4.6;4.4.6 Geo/Geo/1/K Queues;129
7.1.4.6.1;4.4.6.1 Departure Process;132
7.1.5;4.5 Geo/G/1 Queues;132
7.1.5.1;4.5.1 Supplementary Variable Technique;133
7.1.5.1.1;4.5.1.1 Transform Approach;133
7.1.5.1.2;4.5.1.2 Matrix-analytic approach;134
7.1.5.2;4.5.2 Imbedded Markov Chain Approach;136
7.1.5.2.1;4.5.2.1 Distribution of number in the system;137
7.1.5.2.2;4.5.2.2 Waiting Time:;137
7.1.5.2.3;4.5.2.3 Workload:;138
7.1.5.2.4;4.5.2.4 Age Process:;139
7.1.5.2.5;4.5.2.5 Busy Period:;139
7.1.5.3;4.5.3 Geo/G/1/K Queues;140
7.1.6;4.6 GI/Geo/1 Queues;141
7.1.6.1;4.6.1 Supplementary Variable Technique;141
7.1.6.1.1;4.6.1.1 Matrix-analytic approach;141
7.1.6.2;4.6.2 Imbedded Markov Chain Approach;143
7.1.6.2.1;4.6.2.1 Matrix-geometric approach:;144
7.1.6.2.2;4.6.2.2 Transform approach;144
7.1.6.3;4.6.3 GI/Geo/1/K Queues;146
7.1.7;4.7 Geo/PH/1 Queues;147
7.1.7.1;4.7.1 Waiting Times;148
7.1.8;4.8 PH/Geo/1 Queues;149
7.1.8.1;4.8.1 Waiting Times;150
7.1.9;4.9 PH/PH/1 Queues;151
7.1.9.1;4.9.1 Examples;153
7.1.9.1.1;4.9.1.1 A Numerical Example;153
7.1.9.1.2;4.9.1.2 Another Example;154
7.1.9.2;4.9.2 Waiting Time Distirbution;155
7.1.9.2.1;4.9.2.1 Workload;157
7.1.9.2.2;4.9.2.2 Age Process;157
7.1.9.3;4.9.3 PH/PH/1 Queues at points of events;158
7.1.10;4.10 GI/G/1 Queues;163
7.1.10.1;4.10.1 The (RT,RT) representation for the GI/G/1 queue;163
7.1.10.2;4.10.2 New algorithm for the GI/G/1 system;165
7.1.10.3;4.10.3 The (ET,ET) representation for the GI/G/1 queue;167
7.1.11;4.11 GI/G/1/K Queues;169
7.1.11.1;4.11.1 Queue length;171
7.1.11.2;4.11.2 Waiting times;171
7.1.11.3;4.11.3 Model II;173
7.1.12;4.12 MAP/PH/1 Queues;176
7.1.13;4.13 Batch Queues;176
7.1.13.1;4.13.1 GeoX/Geo/1 queue;176
7.1.13.1.1;4.13.1.1 Transform Approach;177
7.1.13.1.2;4.13.1.2 Examples;178
7.1.13.1.3;4.13.1.3 Matrix-analytic Approach;179
7.1.13.2;4.13.2 Geo/GeoY /1 queue;179
8;Chapter 5;181
8.1;Advance Single Node Queuing Models;181
8.1.1;5.1 Multiserver Queues;181
8.1.1.1;5.1.1 Geo/Geo/k Systems;181
8.1.1.1.1;5.1.1.3 An Example;186
8.1.1.1.2;5.1.1.4 Waiting Times;187
8.1.1.2;5.1.2 GI/Geo/k Systems;189
8.1.1.2.1;5.1.2.1 Using MAM Same as using supplementary variables;189
8.1.1.2.2;k. 5.1.2.2 Numerical Example;191
8.1.1.3;5.1.3 PH/PH/k Systems;192
8.1.1.4;5.1.4 Geo/D/k Systems;194
8.1.1.5;5.1.5 MAP/D/k Systems;197
8.1.1.6;5.1.6 BMAP/D/k Systems;197
8.1.2;5.2 Vacation Queues;197
8.1.2.1;5.2.1 Geo/G/1 vacation systems;198
8.1.2.1.1;5.2.1.1 Single vacation system;199
8.1.2.1.2;5.2.1.2 Multiple vacations system;201
8.1.2.2;5.2.2 GI/Geo/1 vacation systems;204
8.1.2.3;5.2.3 MAP/PH/1 vacation systems;205
8.1.2.3.1;5.2.3.1 Exhaustive single vacation:;205
8.1.2.3.2;5.2.3.2 Stationary Distribution:;208
8.1.2.3.3;5.2.3.3 Example of the Geo/Geo/1 vacation:;208
8.1.2.3.4; 5.2.3.4 Exhaustive multiple vacations;209
8.1.2.4;5.2.4 MAP/PH/1 vacation queues with number limited service;210
8.1.2.5;5.2.5 MAP/PH/1 vacation queues with time limited service;212
8.1.2.6;5.2.6 Random Time Limited Vacation Queues/Queues with Server Breakdowns and Repairs;213
8.1.3;5.3 Priority Queues;215
8.1.3.1;5.3.1 Geo/Geo/1 Preemptive;216
8.1.3.1.1;5.3.1.1 Stationary Distribution;218
8.1.3.2;5.3.2 Geo/Geo/1 Non-preemptive;223
8.1.3.2.1;5.3.2.1 Stationary Distribution;225
8.1.3.3;5.3.3 MAP/PH/1 Preemptive;226
8.1.3.3.1;5.3.3.1 Stationary Distribution;228
8.1.3.4;5.3.4 MAP/PH/1 Non-preemptive;231
8.1.4;5.4 Queues with Multiclass of Packets;235
8.1.4.1;5.4.1 Multiclass systems – with FCFS the MMAP[K]/PH[K]/1;235
8.1.4.1.1;5.4.1.1 Stationary distribution and waiting times;236
8.1.4.2;5.4.2 Multiclass systems – with LCFS the MMAP[K]/PH[K]/1;237
8.1.4.2.1;5.4.2.1 Stability conditions;238
8.1.4.2.2;5.4.2.2 Performance measures;239
9;References;242
10;Index;247