Control techniques for complex networks

Sean Meyn0521884411, 9780521884419, 9780511371028

Power grids, flexible manufacturing, cellular communications: interconnectedness has consequences. This remarkable book gives the tools and philosophy you need to build network models detailed enough to capture essential dynamics but simple enough to expose the structure of effective control solutions and to clarify analysis. Core chapters assume only exposure to stochastic processes and linear algebra at the undergraduate level; later chapters are for advanced graduate students and researchers/practitioners. This gradual development bridges classical theory with the state-of-the-art. The workload model that is the basis of traditional analysis of the single queue becomes a foundation for workload relaxations used in the treatment of complex networks. Lyapunov functions and dynamic programming equations lead to the celebrated MaxWeight policy along with many generalizations. Other topics include methods for synthesizing hedging and safety stocks, stability theory for networks, and techniques for accelerated simulation. Examples and figures throughout make ideas concrete. Solutions to end-of-chapter exercises available on a companion website.

---

Table of contents :
Preface……Page 2
Introduction……Page 10
Networks in practice……Page 11
Mathematical models……Page 16
What do you need to know to read this book?……Page 20
Notes……Page 32
I Modeling & Control……Page 34
Modeling the single server queue……Page 35
Klimov model……Page 41
Multiple-access communication……Page 44
Processor sharing model……Page 46
Power transmission network……Page 47
Simple re-entrant line……Page 49
Contention for resources and instability……Page 53
Routing model……Page 56
Braess’ paradox……Page 59
Notes……Page 61
The Single Server Queue……Page 62
Representations……Page 65
Approximations……Page 68
Stability……Page 72
Invariance equations……Page 77
Big queues……Page 87
Model selection……Page 92
Notes……Page 94
Exercises……Page 95
Scheduling……Page 99
Controlled random-walk model……Page 101
Fluid model……Page 109
Control techniques for the fluid model……Page 116
Comparing fluid and stochastic models……Page 128
Structure of optimal policies……Page 133
Safety-stocks……Page 136
Discrete review……Page 142
MaxWeight and MinDrift……Page 145
Perturbed value function……Page 148
Notes……Page 152
Exercises……Page 154
II Workload……Page 158
Workload & Scheduling……Page 159
Single server queue……Page 160
Workload for the CRW scheduling model……Page 163
Relaxations for the fluid model……Page 167
Stochastic workload models……Page 189
Pathwise optimality and workload……Page 194
Hedging in networks……Page 199
Notes……Page 209
Exercises……Page 211
Routing & Resource Pooling……Page 213
Workload in general models……Page 216
Resource pooling……Page 223
Routing and workload……Page 227
MaxWeight for routing and scheduling……Page 233
Simultaneous resource possession……Page 236
Workload relaxations……Page 239
Relaxations and policy synthesis for stochastic models……Page 253
Notes……Page 261
Exercises……Page 263
Demand……Page 266
Network models……Page 269
Transients……Page 274
Workload relaxations……Page 287
Hedging in a simple inventory model……Page 295
Hedging in networks……Page 301
Summary of steady-state control techniques……Page 312
Notes……Page 314
Exercises……Page 316
III Stability & Performance……Page 318
Foster-Lyapunov Techniques……Page 319
Lyapunov functions……Page 324
Lyapunov functions for networks……Page 328
Discrete-review……Page 338
MaxWeight……Page 342
MaxWeight and the average-cost optimality equation……Page 348
Linear programs for performance bounds……Page 352
Brownian workload model……Page 360
Notes……Page 367
Exercises……Page 369
Optimization……Page 374
Reachability and decomposibility……Page 379
Linear programming formulations……Page 381
Multi-objective optimization……Page 389
Optimality equations……Page 392
Algorithms……Page 401
Optimization in networks……Page 408
One dimensional inventory model……Page 413
Hedging and workload……Page 418
Notes……Page 430
Exercises……Page 433
ODE methods……Page 436
Examples……Page 441
Mathematical preliminaries……Page 445
Fluid limit model……Page 449
Fluid-scale stability……Page 453
Safety stocks and trajectory tracking……Page 462
Fluid-scale asymptotic optimality……Page 467
Brownian workload model……Page 474
Notes……Page 480
Exercises……Page 483
Simulation & Learning……Page 485
Deciding when to stop……Page 491
Asymptotic theory for Markov models……Page 495
The single server queue……Page 499
Control variates and shadow functions……Page 503
Estimating a value function……Page 516
Notes……Page 532
Exercises……Page 534
Every process is (almost) Markov……Page 538
Generators and value functions……Page 540
Equilibrium equations……Page 543
Criteria for stability……Page 552
Ergodic theorems and coupling……Page 560
Converse theorems……Page 568
List of Figures……Page 572
References……Page 576
Index……Page 611