This text is written to teach the theory of Lyapunov drift and Lyapunov optimization for stochastic network optimization. It assumes only that the reader is familiar with basic probability concepts (such as expectations and the law of large numbers). Familiarity with Markov chains and with standard
Copyright c 2010 by Morgan claypool All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means-clectronic, mechanical, photocopy, recording, or any other except for brief quotations printed reviews, without the prior permission of the publisher Stochastic Network Optimization with Application to Communication and Queueing Systems Michael J. Neely www.MorgAnclaypool.com ISBN: 9781608454556 Paperback ISBN:9781608454563 DOI10.2200/S00271ED1V01Y201006CNT007 A Publication in the morgan Claypool Publishers series SYNTHESIS LECTURES ON COMMUNICATION NETWORKS Lecture #7 Series Editor: Jean Walrand, University of California, Berkele Series issn Synthesis Lectures on Communication Networl Print 1935-4185 Electronic 1935-4193 This material is supported in part by one or more of the following: the DARPA IT-MANET Program grant W911NF-07-0028, the NSF Career grant CCF-0747525, and continuing through participation in the Network Science Collaborative Technology Alliance sponsored by the U.S. Army Research Laboratory. 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 010 Performance Modeling of communication networks with markov chains onghoon Mo 10 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 A1 pplication to Communication and Queueing Systems Michael. Neely University of Southern California SYNTHESIS LECTURES ON COMMUNICATION NETWORKS #7 M mORGAN &CLAYPOOL PUBLIShers ABSTRACT This text presents a modern thcory of analysis, control, and optimization for dynamic networks Mathematical techniques of lyapunov drift and lyapunov optimization are developed and show 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 cxamples and numcrous problem sct qucstions are 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 outing, backpressure, max-weight virr queues Contents Preface 1 Introduction 1.1 Example Opportunistic Scheduling proble 1.1.1 Example Problem 1: Minimizing Time Average Power Subject to tability 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 1.3 Lyapunov Drift and lyapunov Optimization 1.4 Differences from our earlier text 1.51 ternative Approaches…… 7 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 1.7.4 Order-optimal Delay Scheduling and Queue Grouping........ 10 17.5 Heavy Traffic and Decay Exponents.…… 1.7.6 Capacity and Delay Tradeoffs for Mobile Networks 11 1.8 Preliminaries 2 Introduction to Queues .15 2. 1 Rate Stability 2.2 Stronger Forms of stability .18 2.3 Randomized Scheduling for Rate Stability 2.3.1 A 3-Queue, 2-Server Example 20 2.3.2 A 2-Queue Opportunistic Scheduling Examp 22 2.4 Exercises VIll 3 Dynamic Scheduling Example 29 3.1 Scheduling for stabili ty 29 3.1.1 The S-only Algorithm and Emax 30 31.2 Lyapunov Drift for Stable Scheduling.………………31 3. 1.3 The "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............................43 4 Optimizing Time Averages 45 4.1 yapunov 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 @-only Policies 53 4.4 Virtulal Queues 56 4.5 The Min Drift-Plus-Penalty algorithm 58 4.5.1 Where are we Using the i.i.d. Assumptions? 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 backlog 69 4.9Non-id. Models and Universal Scheduling.…,…,… ..72 4.9.2 Non-Ergodic Models and Arbitrary Sample Paths 49.1 Markov modulated pi 74 ..77 4.10 ExE 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 Rectang nt 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 5.3 Multi-Hop Queueing Networks 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 6. 1 The e-persistent service queue 122 5.6.2 The Drift-Plus-Penalty for Worst-Case Delay .123 5.6.3 Algorithm Performance 125 5.7 Alternative Fairness metrics 128 5.8E 129 6 Approximate Scheduling .137 6.1 Time-Invariant Interference Networks 138 6.1.1 Computing over Multiple Slots 138 6.1.2 Randomized Searching for the Max-Weight Solution .....140 6. 1.3 The Jiang-Walrand Th theorem .141 6.2 Multiplicative Factor Approximations 144 7 Optimization of Renewal Systems .149 7.1 The Renewal System Model 149 7. 1.1 The Optimization Goal ..,,.....150 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