Stochastic Network Optimization with Application to Communication and Queueing Systems

✍ Scribed by Michael J. Neely, Jean Walrand

• Publisher: Morgan and Claypool Publishers
• Year: 2010
• Tongue: English
• Leaves: 212
• Series: Synthesis Lectures on Communication Networks
• Category: Library

✦ Synopsis

This text presents a modern theory of analysis, control, and optimization for dynamic networks. Mathematical techniques of Lyapunov drift and Lyapunov optimization are developed and shown to enable constrained optimization of time averages in general stochastic systems. The focus is on communication and queueing systems, including wireless networks with time-varying channels, mobility, and randomly arriving traffic. A simple drift-plus-penalty framework is used to optimize time averages such as throughput, throughput-utility, power, and distortion. Explicit performance-delay tradeoffs are provided to illustrate the cost of approaching optimality. This theory is also applicable to problems in operations research and economics, where energy-efficient and profit-maximizing decisions must be made without knowing the future. Topics in the text include the following: - Queue stability theory - Backpressure, max-weight, and virtual queue methods - Primal-dual methods for non-convex stochastic utility maximization - Universal scheduling theory for arbitrary sample paths - Approximate and randomized scheduling theory - Optimization of renewal systems and Markov decision systems Detailed examples and numerous problem set questions are provided to reinforce the main concepts. Table of Contents: Introduction / Introduction to Queues / Dynamic Scheduling Example / Optimizing Time Averages / Optimizing Functions of Time Averages / Approximate Scheduling / Optimization of Renewal Systems / Conclusions

✦ Table of Contents

Preface......Page 12
Example Opportunistic Scheduling Problem......Page 14
Example Problem 2: Maximizing Throughput Subject to Time Average Power Constraints......Page 15
Example Problem 3: Maximizing Throughput-Utility Subject to Time Average Power Constraints......Page 16
General Stochastic Optimization Problems......Page 17
Lyapunov Drift and Lyapunov Optimization......Page 18
Alternative Approaches......Page 20
On General Markov Decision Problems......Page 21
Optimal O(V) and O(log(V)) delay tradeoffs......Page 22
Order-optimal Delay Scheduling and Queue Grouping......Page 23
Capacity and Delay Tradeoffs for Mobile Networks......Page 24
Preliminaries......Page 25
Introduction to Queues......Page 28
Rate Stability......Page 30
Stronger Forms of Stability......Page 31
Randomized Scheduling for Rate Stability......Page 32
A 3-Queue, 2-Server Example......Page 33
A 2-Queue Opportunistic Scheduling Example......Page 35
Exercises......Page 38
Scheduling for Stability......Page 42
The S-only Algorithm and max......Page 43
Lyapunov Drift for Stable Scheduling......Page 44
The Min-Drift'' orMax-Weight'' Algorithm......Page 47
Iterated Expectations and Telescoping Sums......Page 49
Stability and Average Power Minimization......Page 50
Drift-Plus-Penalty......Page 52
Analysis of the Drift-Plus-Penalty Algorithm......Page 53
Optimizing the Bounds......Page 54
Simulations of the Drift-Plus-Penalty Algorithm......Page 55
Generalizations......Page 56
Lyapunov Drift Theorem......Page 58
Lyapunov Optimization Theorem......Page 60
Probability 1 Convergence......Page 62
General System Model......Page 65
Optimality via -only Policies......Page 66
Virtual Queues......Page 69
The Min Drift-Plus-Penalty Algorithm......Page 71
Dynamic Server Scheduling......Page 75
Opportunistic Scheduling......Page 77
Variable V Algorithms......Page 80
Place-Holder Backlog......Page 82
Non-i.i.d. Models and Universal Scheduling......Page 85
Markov Modulated Processes......Page 87
Non-Ergodic Models and Arbitrary Sample Paths......Page 90
Exercises......Page 94
The Region......Page 105
Characterizing Optimality......Page 106
Optimizing Functions of Time Averages......Page 110
Jensen's Inequality......Page 111
Auxiliary Variables......Page 112
Solving the Transformed Problem......Page 113
A Flow-Based Network Model......Page 117
Performance of the Flow-Based Algorithm......Page 120
Limitations of this Model......Page 121
Multi-Hop Queueing Networks......Page 122
Transmission Variables......Page 123
Multi-Hop Network Utility Maximization......Page 124
Backpressure-Based Routing and Resource Allocation......Page 126
General Optimization of Convex Functions of Time Averages......Page 127
Non-Convex Stochastic Optimization......Page 129
Worst Case Delay......Page 133
The -persistent service queue......Page 135
The Drift-Plus-Penalty for Worst-Case Delay......Page 136
Algorithm Performance......Page 138
Alternative Fairness Metrics......Page 141
Exercises......Page 142
Approximate Scheduling......Page 150
Computing over Multiple Slots......Page 151
Randomized Searching for the Max-Weight Solution......Page 153
The Jiang-Walrand Theorem......Page 154
Multiplicative Factor Approximations......Page 157
The Renewal System Model......Page 162
The Optimization Goal......Page 163
Optimality over i.i.d. algorithms......Page 164
Drift-Plus-Penalty for Renewal Systems......Page 165
Minimizing the Drift-Plus-Penalty Ratio......Page 170
The Bisection Algorithm......Page 172
Optimization over Pure Policies......Page 173
Caveat --- Frames with Initial Information......Page 174
Task Processing Example......Page 175
Utility Optimization for Renewal Systems......Page 177
The Utility Optimal Algorithm for Renewal Systems......Page 180
Delay-Limited Transmission Example......Page 181
Markov Decision Problem for Minimum Delay Scheduling......Page 184
Exercises......Page 187
Conclusions......Page 192
Bibliography......Page 194
Author's Biography......Page 212