第1页 / 共211页
第2页 / 共211页
第3页 / 共211页
第4页 / 共211页
第5页 / 共211页
第6页 / 共211页
第7页 / 共211页
第8页 / 共211页
Stochastic Network Optimization Communication and Queueing Syste....pdf
Preface
Introduction
Example Opportunistic Scheduling Problem
Example Problem 1: Minimizing Time Average Power Subject to Stability
Example Problem 2: Maximizing Throughput Subject to Time Average Power Constraints
Example Problem 3: Maximizing Throughput-Utility Subject to Time Average Power Constraints
General Stochastic Optimization Problems
Lyapunov Drift and Lyapunov Optimization
Differences from our Earlier Text
Alternative Approaches
On General Markov Decision Problems
On Network Delay
Delay and Dynamic Programming
Optimal O(V) and O(log(V)) delay tradeoffs
Delay-optimal Algorithms for Symmetric Networks
Order-optimal Delay Scheduling and Queue Grouping
Heavy Traffic and Decay Exponents
Capacity and Delay Tradeoffs for Mobile Networks
Preliminaries
Introduction to Queues
Rate Stability
Stronger Forms of Stability
Randomized Scheduling for Rate Stability
A 3-Queue, 2-Server Example
A 2-Queue Opportunistic Scheduling Example
Exercises
Dynamic Scheduling Example
Scheduling for Stability
The S-only Algorithm and max
Lyapunov Drift for Stable Scheduling
The ``Min-Drift'' or ``Max-Weight'' Algorithm
Iterated Expectations and Telescoping Sums
Simulation of the Max-Weight Algorithm
Stability and Average Power Minimization
Drift-Plus-Penalty
Analysis of the Drift-Plus-Penalty Algorithm
Optimizing the Bounds
Simulations of the Drift-Plus-Penalty Algorithm
Generalizations
Optimizing Time Averages
Lyapunov Drift and Lyapunov Optimization
Lyapunov Drift Theorem
Lyapunov Optimization Theorem
Probability 1 Convergence
General System Model
Boundedness Assumptions
Optimality via -only Policies
Virtual Queues
The Min Drift-Plus-Penalty Algorithm
Where are we Using the i.i.d. Assumptions?
Examples
Dynamic Server Scheduling
Opportunistic Scheduling
Variable V Algorithms
Place-Holder Backlog
Non-i.i.d. Models and Universal Scheduling
Markov Modulated Processes
Non-Ergodic Models and Arbitrary Sample Paths
Exercises
Appendix 4.A --- Proving Theorem 4.5
The Region
Characterizing Optimality
Optimizing Functions of Time Averages
The Rectangle Constraint R
Jensen's Inequality
Auxiliary Variables
Solving the Transformed Problem
A Flow-Based Network Model
Performance of the Flow-Based Algorithm
Delayed Feedback
Limitations of this Model
Multi-Hop Queueing Networks
Transmission Variables
The Utility Optimization Problem
Multi-Hop Network Utility Maximization
Backpressure-Based Routing and Resource Allocation
General Optimization of Convex Functions of Time Averages
Non-Convex Stochastic Optimization
Worst Case Delay
The -persistent service queue
The Drift-Plus-Penalty for Worst-Case Delay
Algorithm Performance
Alternative Fairness Metrics
Exercises
Approximate Scheduling
Time-Invariant Interference Networks
Computing over Multiple Slots
Randomized Searching for the Max-Weight Solution
The Jiang-Walrand Theorem
Multiplicative Factor Approximations
Optimization of Renewal Systems
The Renewal System Model
The Optimization Goal
Optimality over i.i.d. algorithms
Drift-Plus-Penalty for Renewal Systems
Alternate Formulations
Minimizing the Drift-Plus-Penalty Ratio
The Bisection Algorithm
Optimization over Pure Policies
Caveat --- Frames with Initial Information
Task Processing Example
Utility Optimization for Renewal Systems
The Utility Optimal Algorithm for Renewal Systems
Dynamic Programming Examples
Delay-Limited Transmission Example
Markov Decision Problem for Minimum Delay Scheduling
Exercises
Conclusions
Bibliography
Author's Biography
Stochastic Network Optimization
with Application to
Communication and
Queueing Systems
Copyright © 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—electronic, mechanical, photocopy, recording, or any other except for brief quotations in
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
ISBN: 9781608454563
paperback
ebook
DOI 10.2200/S00271ED1V01Y201006CNT007
A Publication in the Morgan & Claypool Publishers series
SYNTHESIS LECTURES ON COMMUNICATION NETWORKS
Lecture #7
Series Editor: Jean Walrand, University of California, Berkeley
Series ISSN
Synthesis Lectures on Communication Networks
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
Michael J. Neely
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
2010
Communication Networks: A Concise Introduction
Jean Walrand and Shyam Parekh
2010
Path Problems in Networks
John S. Baras and George Theodorakopoulos
2010
iv
Performance Modeling, Loss Networks, and Statistical Multiplexing
Ravi R. Mazumdar
2009
Network Simulation
Richard M. Fujimoto, Kalyan S. Perumalla, and George F. Riley
2006
Stochastic Network Optimization
with Application to
Communication and
Queueing Systems
Michael J. Neely
University of Southern California
SYNTHESIS LECTURES ON COMMUNICATION NETWORKS #7
CM&
Morgan
&
cLaypool
publishers
ABSTRACT
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.
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
vii
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.1
Example Opportunistic Scheduling Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Example Problem 1: Minimizing Time Average Power Subject to
Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Example Problem 2: Maximizing Throughput Subject to Time
Average Power Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Example Problem 3: Maximizing Throughput-Utility Subject to Time
Average Power Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 General Stochastic Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3
Lyapunov Drift and Lyapunov Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Differences from our Earlier Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5
Alternative Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 On General Markov Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 On Network Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7.1 Delay and Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
V ) and O(log(V )) delay tradeoffs . . . . . . . . . . . . . . . . . . . . . . 9
1.7.2 Optimal O(
1.7.3 Delay-optimal Algorithms for Symmetric Networks . . . . . . . . . . . . . . . . . . 10
1.7.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
Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
√
1.8
Introduction to Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Rate Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1
Stronger Forms of Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2
2.3
Randomized Scheduling for Rate Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 A 3-Queue, 2-Server Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 A 2-Queue Opportunistic Scheduling Example . . . . . . . . . . . . . . . . . . . . . . 22
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4
1
2
viii
3
4
Dynamic Scheduling Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Scheduling for Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1
3.1.1 The S-only Algorithm and max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.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
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
3.2
Optimizing Time Averages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Lyapunov Drift and Lyapunov Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1
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
Virtual Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4
4.5
The Min Drift-Plus-Penalty Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5.1 Where are we Using the i.i.d. Assumptions? . . . . . . . . . . . . . . . . . . . . . . . . . 62
Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.6.1 Dynamic Server Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.6.2 Opportunistic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Variable V Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Place-Holder Backlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Non-i.i.d. Models and Universal Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.11.2 Characterizing Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.7
4.8
4.9
4.6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
