Stochastic network optimization with application to communication and queueing systems， 经典的教材
Synthesis Lectures on Communication Networks Editor Jean Walrand, University of California, Berkeley Synthesis Lectures on Communication Networks is an ongoing series of 50-to 100-page publications on topics on the design, implementation, and management of communication networks. Each lecture is a self-contained presentation of one topic by a leading expert. The topics range from algorithms to hardware implementations and cover a broad spectrum of issues from security to multiple-access protocols. The series addresses technologies from sensor networks to reconfigurable optical networks The series is designed to Provide the best available presentations of important aspects of communication networks Help engineers and advanced students keep up with recent developments in a rapidly evolving technology. Facilitate the development of courses in this field Stochastic Network Optimization with Application to Communication and Queueing Systems chae 2010 Scheduling and Congestion Control for Wireless and Processing Networks Libin jiang and jean Walrand 2010 Performance Modeling of Communication Networks with Markov Chains Jeonghoon mo 010 Communication Networks: a Concise Introduction Jean walrand and shyam Parekh 2010 Path Problems in networks John S Baras and George Theodorakopoulos 2010 Performance Modeling, Loss Networks, and Statistical Multiplexing Ravir mazumdar 2009 Nctwork simulation Richard M. Fujimoto, Kalyan S. Perumalla, and george F. riley 2006 Stochastic Network Optimization with Al pplication to Communication and Queueing Systems Michael. Neely University of Southern California SYNTHESIS LECTURES ON COMMUNICATION NETWORKS #7 M MORGAN &CLAYPOOL PUBLISHERS ABSTRACT his text presents a modern thcory of analysis, control, and optimization for dynamic nctworks 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 Dctailed cxamples and numcrous problem sct qucstions arc provided to reinforce the main concepts KEYWORDS dynamic scheduling, decision theory, wireless networks, Lyapunov optimization, con gestion control, fairness, network utility maximization, multi-hop, mobile networks routing, backpressure, max-weight, virtual queues Contents Preface 1 Introduction 1.1 Example Opportunistic Scheduling Problem 1.1.1 Example Problem 1: Minimizing Time Average Power Subject to 1.1.2 Example Problem 2: Maximizing Throughput Subject to Time Average Power Constraints 1.1.3 Example Problem 3: Maximizing Throughput-Utility Subject to Time Average Power Constraints ·.·.:.·.:· 1.2 General Stochastic Optimization Problems ···,.·.··单 4 1.3 Lyapunov Drift and Lyapunov Optimization................5 1.4 Differences from our earlier Text 1.5 Alternative At pproaches 1.6 On Gencral Markov Dccision Problems 1.7 On Network Dclay 1.7.1 Delay and Dynamic Programming 1.7.2 Optimal O(V) and O(log(V) delay tradeoffs 1.7.3 Delay-optimal Algorithms for Symmetric Networks 10 17.4 Order-optimal Delay Scheduling and Queue Grouping∴…….10 1.7.5 Heavy Traffic and Decay Exponents ...11 1.7.6 Capacity and Delay Tradeoffs for Mobile Networks∴……11 1.8 Preliminaries 2 Introduction to Que 15 2.1 Rate Stability .17 2.2 Stronger Forms of Stability 18 2.3 Randomized Scheduling for Rate stabili 2.3.1 A 3-Queue, 2-Server Example 20 2.3.2 A 2-Queue Opportunistic Scheduling Example 22 2.4E 25 vIll 3 Dynamic Scheduling Example 29 3.1 Scheduling for Stability 4 29 3.1.1Thes- only Algorithm and∈max… 30 3. 1.2 Lyapunov Drift for Stable Scheduling 面 ..31 3.13The“ Min-Drift”or“ Max-Weight” Algorithm.…,.34 3.1.4 Iterated Expectations and Telescoping Sums 36 3.1.5 Simulation of the Max-Weight Algorithm ...37 3. 2 Stability and Average Power Minimization.................37 3. 2.1 Drift-Plus-Penalty 39 3.2.2 Analysis of the Drift-Plus-Penalty algorithm 40 3.2.3 Optimizing the bounds 41 3. 2. 4 Simulations of the Drift-Plus-Penalty Algorithm 42 3.3 Generalizations 4 Optimizing Time Averages 45 4.1 Lyapunov Drift and Lyapunov Optimization∴………………………45 4.1.1 Lyapunov Drift Theorem 45 4.1.2 Lyapunov Optimization Theorem ................. 47 4.1.3 Probability 1 Convergence 49 4.2 General System Model 52 4.2.1 Boundedness Assumptions....,…,,,……53 4.3 Optimality via c-only polic 53 4.4 Virtual queues 56 4.5 The Min Drift-Plus-Penalty 58 4.5.1 Where are we Using the i i.d. As ssumptions 62 4.6 62 4.6.1 Dynamic Server Scheduling………………62 4.6.2 Opportunistic Scheduling 64 4.7 Variable V Algorithms 67 4.8 Place-Holder B 69 4.9 Non-i i.d. Models and Universal scheduling ig .72 4.9.1 Markov modulated Processes .....................................74 4.9.2 Non-Ergodic Models and Arbitrary Sample Paths 77 4.10 Exercises ...81 4.11 Appendix 4.A- Proving Theorem 4.5 92 4. 11.1 The Region T ,..92 4. 11.2 Characterizing Optimality 5 Optimizing Functions of Time Averages 97 5.0.3 The Rectangle Constraint R 5.0.4 Jensens Inequality 5.0.5 Auxiliary variables 99 5.1 Solving the Transformed Problem 100 5.2 A Flow-Based Network model ...104 5.2.1 Performance of the Flow-Based Algorithm .....107 5.2.2 Delayed Feedback 5.2.3 Limitations of this model ∴.,.108 5.3 Multi-Hop Queueing Networks ..109 5.3.1 Transmission Variables 110 5.3.2 The Utility Optimization Problem 111 5.3.3 Multi-Hop Network Utility Maximization 111 5.3.4 Backpressure-Based Routing and Resource Allocation ........ 113 5.4 General Optimization of Convex Functions of Time Averages........ 114 5.5 Non-Convex Stochastic Optimization 画潘 116 5.6 Worst Case Delay 120 5.6.2 The Drift- Plus- Penalty for Worst-Case Delay….∴…122 5.6.1 The e-persistent service queue ·:· 123 5.6.3 Algorithm Performance 5.7 lternative Fairness metrics 128 5.8 Exercises 129 6 Approximate Scheduling 137 6.1 Time-Invariant Interference Networks 6.1.1 Computing over Multiple slots 6.1.2 Randomized Searching for the Max -Weight Solution 140 6. 1.3 The Jiang-Walrand Theorem 141 6.2 Multiplicative Factor Approximations 144 Optimization of renewal Systems 149 7. 1 The Renewal System Model 149 7.1.1 The Optimization goal 7. 1.2 Optimality over i.i.d. algorithms .151 7.2 Drift-Plus-Penalty for Renewal Systems 152 7. 2. 1 Alternate formulations .157 CONTENTS 7.3 Minimizing the Drift-Plus-Penalty Ratio 157 7.3.1 The B Algorith 159 7.3.2 Optimization over Pure Policies..................160 7.3.3 Caveat- Frames with Initial Information .161 7.4 Task Processing Example 162 7.5 Utility Optimization for Renewal systems 164 7.5.1 The Utility Optimal Algorithm for Renewal systems.........167 7.6 Dynamic Programming Examples 168 7.6. 1 Delay-Limited Transmission Example 168 7.6.2 Markov Decision Problem for Minimum Delay scheduling ..171 7.7 Exercises 174 Conclusions .,179 Bibliography .181 Author's Biography 199