Suchen und Finden
Mehr zum Inhalt
Queueing Theory for Telecommunications - Discrete Time Modelling of a Single Node System
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
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.