Website |
|
xi | |
Preface |
|
xiii | |
Guide to Notation and Terminology |
|
xix | |
|
|
1 | (28) |
|
1.1 About the Title of This Book |
|
|
1 | (1) |
|
|
2 | (2) |
|
1.3 Two Examples of Queueing Networks |
|
|
4 | (3) |
|
1.4 SPN Examples with Additional Features |
|
|
7 | (6) |
|
|
13 | (4) |
|
1.6 Illuminating Examples of Instability |
|
|
17 | (9) |
|
1.7 Structure of the Book and Intended Audience |
|
|
26 | (1) |
|
1.8 Sources and Literature |
|
|
27 | (2) |
|
2 Stochastic Processing Networks |
|
|
29 | (25) |
|
2.1 Common Elements of the Two Model Formulations |
|
|
29 | (7) |
|
2.2 Baseline Stochastic Assumptions |
|
|
36 | (1) |
|
|
37 | (4) |
|
|
41 | (3) |
|
2.5 Recap of Essential System Relationships |
|
|
44 | (2) |
|
2.6 Unitary Networks and Queueing Networks |
|
|
46 | (4) |
|
2.7 More on the Concept of Class |
|
|
50 | (3) |
|
2.8 Sources and Literature |
|
|
53 | (1) |
|
|
54 | (25) |
|
3.1 General Framework and Definition of Stability |
|
|
55 | (2) |
|
3.2 Sufficient Condition for SPN Stability |
|
|
57 | (1) |
|
3.3 First Examples of Markov Representations |
|
|
58 | (5) |
|
3.4 Examples with Phase-Type Distributions |
|
|
63 | (4) |
|
3.5 Canonical Representation with a Simply Structured Policy |
|
|
67 | (4) |
|
3.6 A Mild Added Restriction on the CTMC Representation |
|
|
71 | (2) |
|
3.7 Sufficient Condition for Irreducibility |
|
|
73 | (2) |
|
3.8 Markov Representations with General State Space |
|
|
75 | (2) |
|
3.9 Sources and Literature |
|
|
77 | (2) |
|
4 Extensions and Complements |
|
|
79 | (28) |
|
4.1 Markovian Arrival Processes |
|
|
79 | (2) |
|
4.2 Alternate Routing with Immediate Commitment |
|
|
81 | (6) |
|
|
87 | (3) |
|
4.4 Equivalent Head-of-Line Model for a PS Network |
|
|
90 | (5) |
|
4.5 Bandwidth Sharing Networks |
|
|
95 | (3) |
|
4.6 Queueing Networks with HLSPS and HLPPS Control |
|
|
98 | (1) |
|
4.7 Parallel-Server Systems |
|
|
99 | (1) |
|
4.8 Example Involving Fork-and-Join Jobs |
|
|
100 | (6) |
|
4.9 Sources and Literature |
|
|
106 | (1) |
|
5 Is Stability Achievable? |
|
|
107 | (17) |
|
5.1 Standard Load Condition for a Unitary Network |
|
|
108 | (1) |
|
5.2 Defining Criticality via the Static Planning Problem |
|
|
108 | (3) |
|
5.3 The Subcritical Region |
|
|
111 | (3) |
|
5.4 Only Subcritical Networks Can Be Stable |
|
|
114 | (4) |
|
5.5 Instability with Multiresource Activities |
|
|
118 | (1) |
|
5.6 Instability with Multiinput Activities |
|
|
119 | (2) |
|
5.7 Stability Region and Maximally Stable Policies |
|
|
121 | (2) |
|
5.8 Sources and Literature |
|
|
123 | (1) |
|
6 Fluid Limits, Fluid Equations, and Positive Recurrence |
|
|
124 | (24) |
|
|
124 | (3) |
|
|
127 | (7) |
|
6.3 Standard Setup for Study of Fluid Limits |
|
|
134 | (2) |
|
6.4 Definition and Properties of Fluid Limits |
|
|
136 | (8) |
|
6.5 Fluid Model Stability Implies SPN Stability |
|
|
144 | (1) |
|
6.6 Sources and Literature |
|
|
145 | (3) |
|
7 Fluid Equations That Characterize Specific Policies |
|
|
148 | (12) |
|
7.1 Queueing Network with a Nonidling Policy |
|
|
149 | (1) |
|
7.2 Queueing Network with Nonpreemptive Static Buffer Priorities |
|
|
150 | (4) |
|
7.3 Queueing Network with FCFS Control |
|
|
154 | (2) |
|
7.4 Unitary Network with Specially Structured Control |
|
|
156 | (3) |
|
7.5 Sources and Literature |
|
|
159 | (1) |
|
8 Proving Fluid Model Stability Using Lyapunov Functions |
|
|
160 | (34) |
|
8.1 Fluid Model Calculus and Lyapunov Functions |
|
|
160 | (7) |
|
8.2 Advantage of Fluid Models over Markov Chains |
|
|
167 | (4) |
|
8.3 Feedforward Queueing Network (Piecewise Linear Lyapunov Function) |
|
|
171 | (4) |
|
8.4 Queueing Network with HLSPS Control (Linear Lyapunov Function) |
|
|
175 | (3) |
|
8.5 Assembly Operation with Complementary Side Business |
|
|
178 | (1) |
|
8.6 Global Stability of Ring Networks |
|
|
179 | (4) |
|
8.7 Global Stability of Reentrant Lines |
|
|
183 | (9) |
|
8.8 Sources and Literature |
|
|
192 | (2) |
|
9 Max-Weight and Back-Pressure Control |
|
|
194 | (25) |
|
|
195 | (4) |
|
9.2 Basic Back-Pressure Policy |
|
|
199 | (3) |
|
9.3 Relaxed Back-Pressure Policy |
|
|
202 | (2) |
|
9.4 More about Max-Weight and Back-Pressure Policies |
|
|
204 | (2) |
|
9.5 The Characteristic Fluid Equation |
|
|
206 | (5) |
|
9.6 Maximal Stability of Relaxed BP (Quadratic Lyapunov Function) |
|
|
211 | (1) |
|
9.7 Maximal Stability of Basic BP with Single-Server Activities |
|
|
212 | (5) |
|
9.8 Sources and Literature |
|
|
217 | (2) |
|
10 Proportionally Fair Resource Allocation |
|
|
219 | (33) |
|
10.1 A Concave Optimization Problem |
|
|
219 | (5) |
|
10.2 Proportional Fairness in a Static Setting |
|
|
224 | (5) |
|
10.3 Aggregation Property of the PF Allocation Function |
|
|
229 | (2) |
|
10.4 Unitary Network with PF Control |
|
|
231 | (4) |
|
10.5 Proof of Fluid Model Stability Using Entropy Lyapunov Function |
|
|
235 | (12) |
|
10.6 Maximal Stability of the PF Control Policy |
|
|
247 | (3) |
|
10.7 Sources and Literature |
|
|
250 | (2) |
|
11 Task Allocation in Server Farms |
|
|
252 | (16) |
|
|
252 | (1) |
|
11.2 A Map-Only Model with Three Levels of Proximity |
|
|
253 | (2) |
|
11.3 Augmented SPN Formulation |
|
|
255 | (3) |
|
11.4 Markov Representation |
|
|
258 | (1) |
|
11.5 Simplified Criterion for Subcriticality |
|
|
259 | (1) |
|
11.6 Workload-Weighted Task Allocation (WWTA) |
|
|
260 | (1) |
|
|
261 | (3) |
|
11.8 Maximal Stability of WWTA (Quadratic Lyapunov Function) |
|
|
264 | (3) |
|
11.9 Sources and Literature |
|
|
267 | (1) |
|
12 Multihop Packet Networks |
|
|
268 | (43) |
|
12.1 General Slotted-Time Model |
|
|
269 | (5) |
|
12.2 Additional Structure of Links and Link Configurations |
|
|
274 | (8) |
|
12.3 Fluid-Based Criterion for Positive Recurrence |
|
|
282 | (4) |
|
12.4 Max-Weight and Back-Pressure Control |
|
|
286 | (3) |
|
12.5 Maximal Stability of Back-Pressure Control |
|
|
289 | (4) |
|
12.6 Proportional Scheduling with Fixed Routes |
|
|
293 | (8) |
|
12.7 Fluid Limits and Fluid Model under Random Proportional Scheduling |
|
|
301 | (7) |
|
12.8 Maximal Stability of Random Proportional Scheduling |
|
|
308 | (1) |
|
12.9 Sources and Literature |
|
|
309 | (2) |
Appendix A Selected Topics in Real Analysis |
|
311 | (8) |
Appendix B Selected Topics in Probability |
|
319 | (12) |
Appendix C Discrete-Time Markov Chains |
|
331 | (13) |
Appendix D Continuous-Time Markov Chains and Phase-Type Distributions |
|
344 | (18) |
Appendix E Markovian Arrival Processes |
|
362 | (7) |
Appendix F Convergent Square Matrices |
|
369 | (2) |
References |
|
371 | (8) |
Index |
|
379 | |