|
ECE 598SM Fall 2004 Tues & Thurs 1:30-2:50 Trans. Bldg 206
This course will develop the foundations of stochastic modeling and control for complex networks. Specific applications include scheduling algorithms for manufacturing models and the larger supply-chain; congestion control algorithms for the Internet; and control of power flows in power distribution systems. Topics will include model reduction techniques based on workload; performance analysis using simulation and Markov chain approaches; and feedback control techniques based on approximate dynamic programming.
Prerequisites
Some exposure to optimization at the level of ECE 415, and exposure to stochastic processes at the level of ECE 434 or MATH 366 (or consent of instructor.)
Grading
- 15% Homework (approximately 7 problem set)
- 70% Two 90-minute exams
- 15% Project
The project will consist of readings of three references that have a common theme of relevance to the course. The student will prepare a 10-15 page typed report explaining the contributions. In addition, computer implementation and simulations will be performed to illustrate some of these contributions.
Resources
The main text is the lecture notes of the same name:
The following texts are useful, but not required:
- Chen, H. and Yao, D. D. Fundamentals of queueing networks: Performance, asymptotics, and optimization. Springer-Verlag, NY, 2001.
- W. Whitt. Stochastic-Process Limits, Springer-Verlag, NY 2002.
- Berstekas and Gallager, Data Networks, 2nd edition.
- Kleinrock, Queueing Systems, Volume 1.
- Steven Shreve 's Lectures on Stochastic Calculus and Finance
- Meyn & Tweedie, Markov Chains & Stochastic Stability
Outline
I. NETWORK MODELS
1. Introduction to queueing and flow models; survey of the single queue.
Network examples; Models; Introduction to Poisson’s equation and other invariance equations.
2. Control and modeling in production systems.
The Klimov model; Simple re-entrant line models; Priority policies; Myopic policies; Transient control issues; General stochastic models.
3. Equilibria in flow models
Sources of inefficiency: loops; transmission constraints; dynamic issues. Braess' paradox; notions of fairness and efficiency. Examples from power distribution systems and telecommunications.
4. Instability in simple routing and production models
Sources of poor performance and instability in simple models. Introduction to fluid limit models.
5. Hedging points and safety-stocks
Examples of safety-stocks to improve performance in the previous examples. An introduction to hedging-point policies through examples.
II. WORKLOAD MODELS
1. Workload & system load in production systems and routing models
Basic definitions in production systems, and in routing models. Resource pooling in flow models. Linear-programming approaches to computing workload.
2. Workload relaxations and model reduction
Diffusion approximations based on the heavy-traffic theory of Kushner, Harrison, Dai, Williams, and Bramson. Workload relaxations and model reduction for fluid and stochastic models. Examples.
3. The effective cost and effective state
Introduction to control based on workload relaxations. Sensitivity to buffer constraints. Examples.
III. PERFORMANCE EVALUATION
1. Stability: Lyapunov criteria
Stability and performance evaluation based on Lyapunov function techniques, and the Comparison Theorem.
2. Monotonicity, coupling, and ergodicity.
Equilibria equations; coupling; monotonicity; mean ergodic theorems; and geometric ergodicity.
3. Stability: Fluid limit criteria.
Stability of networks and their fluid limits; bounds on Poisson’s equation.
4. Performance bounds
Lyapunov criteria revisited, and the LP approaches of Kumar, Schwerer, etc..
5. Simulation and control-variates
Introduction to simulation theory; Poisson’s equation and Lyapunov functions for fast simulation.
IV. OPTIMIZATION
1. Safety-stocks and approximate optimality.
Translation of policy from a fluid or workload relaxation based on safety-stocks for starvation avoidance. Large deviation and Lyapunov-function approaches to analysis.
2. Dynamic programming equations.
Dynamic programming for a network and its relaxations. Computation and structure of discounted and average-cost value functions.
3. Approximate optimality
Introduction to switching curves for fluid models, and structure of optimal policies in stochastic networks. Analogs in flow models. Computation of optimal hedging point values in stochastic models.