Atnaujinkite slapukų nuostatas

Processing Networks: Fluid Models and Stability [Kietas viršelis]

(Stanford University, California), (The Chinese University of Hong Kong)
  • Formatas: Hardback, 404 pages, aukštis x plotis x storis: 234x156x23 mm, weight: 730 g, Worked examples or Exercises
  • Išleidimo metai: 15-Oct-2020
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1108488897
  • ISBN-13: 9781108488891
Kitos knygos pagal šią temą:
  • Formatas: Hardback, 404 pages, aukštis x plotis x storis: 234x156x23 mm, weight: 730 g, Worked examples or Exercises
  • Išleidimo metai: 15-Oct-2020
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1108488897
  • ISBN-13: 9781108488891
Kitos knygos pagal šią temą:
This state-of-the-art account unifies material developed in journal articles over the last 35 years, with two central thrusts: It describes a broad class of system models that the authors call 'stochastic processing networks' (SPNs), which include queueing networks and bandwidth sharing networks as prominent special cases; and in that context it explains and illustrates a method for stability analysis based on fluid models. The central mathematical result is a theorem that can be paraphrased as follows: If the fluid model derived from an SPN is stable, then the SPN itself is stable. Two topics discussed in detail are (a) the derivation of fluid models by means of fluid limit analysis, and (b) stability analysis for fluid models using Lyapunov functions. With regard to applications, there are chapters devoted to max-weight and back-pressure control, proportionally fair resource allocation, data center operations, and flow management in packet networks. Geared toward researchers and graduate students in engineering and applied mathematics, especially in electrical engineering and computer science, this compact text gives readers full command of the methods.

Recenzijos

'The deep and rich theory of stochastic processing networks has served as the analytical foundation for the study of communication networks, cloud computing systems, and manufacturing networks. This book by two of the pioneers of the theory presents an authoritative and comprehensive treatment of the topic, and will serve as an important reference to researchers in the area.' R. Srikant, University of Illinois at Urbana-Champaign 'A system of interconnected resources can become overloaded and unstable even though each of its individual resources has the capacity to meet the demands on it. This striking observation, first made thirty years ago, has stimulated a major field of research. This book, written by two of the pioneers and leading researchers in the field, is a clear and authoritative account of the state-of-the-art.' Frank Kelly, University of Cambridge 'This book provides an elegant and unified exposition of the general modeling framework of stochastic processing networks (SPNs) and associated theory of stability using fluid models. Much of this material was only previously available in dispersed journal articles. Adopting a continuous-time Markov chain description for SPNs, valid under fairly general assumptions on arrivals, service times and controls, enables a self-contained, accessible treatment. An array of interesting examples and extensions, especially involving applications for telecommunication and data networks, enliven the volume. This monograph will be an invaluable premier resource for graduate students and researchers in computer science, electrical and industrial engineering, applied mathematics and operations management interested in theory and applications of stochastic processing networks.' Ruth J. Williams, University of California, San Diego

Daugiau informacijos

The state of the art in fluid-based methods for stability analysis, giving researchers and graduate students command of the tools.
Website xi
Preface xiii
Guide to Notation and Terminology xix
1 Introduction
1(28)
1.1 About the Title of This Book
1(1)
1.2 Activity Analysis
2(2)
1.3 Two Examples of Queueing Networks
4(3)
1.4 SPN Examples with Additional Features
7(6)
1.5 Stability
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)
2.3 Basic SPN Model
37(4)
2.4 Relaxed SPN Model
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)
3 Markov Representations
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)
4.3 PS Networks
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)
6.1 Overview
124(3)
6.2 Fluid Models
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)
9.1 Leontief Networks
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)
11.1 Data Locality
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)
11.7 Fluid Model
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
Jim Dai received his PhD in mathematics from Stanford University. He is currently Presidential Chair Professor in the Institute for Data and Decision Analytics at The Chinese University of Hong Kong, Shenzhen. He is also the Leon C. Welch Professor of Engineering in the School of Operations Research and Information Engineering at Cornell University. He was honored by the Applied Probability Society of INFORMS with its Erlang Prize (1998) and with two Best Publication Awards (1997 and 2017). In 2018 he received The Achievement Award from ACM SIGMETRICS. Professor Dai served as Editor-In-Chief of Mathematics of Operations Research from 2012 to 2018. J. Michael Harrison earned degrees in industrial engineering and operations research before joining the faculty of Stanford University's Graduate School of Business, where he served for 43 years. His research concerns stochastic models in business and engineering, including mathematical finance and processing network theory. His previous books include Brownian Models of Performance and Control (2013). Professor Harrison has been honored by INFORMS with its Expository Writing Award (1998), the Lanchester Prize for best research publication (2001), and the John von Neumann Theory Prize (2004); he was elected to the U.S. National Academy of Engineering in 2008.