Stochastic Network Optimization Communication and Queueing Systems

所需积分/C币:50 2017-11-20 13:01:49 1.37MB PDF
7
收藏 收藏
举报

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

...展开详情
试读 127P Stochastic Network Optimization Communication and Queueing Systems
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分or赚钱
    最新推荐
    Stochastic Network Optimization Communication and Queueing Systems 50积分/C币 立即下载
    1/127
    Stochastic Network Optimization Communication and Queueing Systems第1页
    Stochastic Network Optimization Communication and Queueing Systems第2页
    Stochastic Network Optimization Communication and Queueing Systems第3页
    Stochastic Network Optimization Communication and Queueing Systems第4页
    Stochastic Network Optimization Communication and Queueing Systems第5页
    Stochastic Network Optimization Communication and Queueing Systems第6页
    Stochastic Network Optimization Communication and Queueing Systems第7页
    Stochastic Network Optimization Communication and Queueing Systems第8页
    Stochastic Network Optimization Communication and Queueing Systems第9页
    Stochastic Network Optimization Communication and Queueing Systems第10页
    Stochastic Network Optimization Communication and Queueing Systems第11页
    Stochastic Network Optimization Communication and Queueing Systems第12页
    Stochastic Network Optimization Communication and Queueing Systems第13页
    Stochastic Network Optimization Communication and Queueing Systems第14页
    Stochastic Network Optimization Communication and Queueing Systems第15页
    Stochastic Network Optimization Communication and Queueing Systems第16页
    Stochastic Network Optimization Communication and Queueing Systems第17页
    Stochastic Network Optimization Communication and Queueing Systems第18页
    Stochastic Network Optimization Communication and Queueing Systems第19页
    Stochastic Network Optimization Communication and Queueing Systems第20页

    试读结束, 可继续阅读

    50积分/C币 立即下载 >