ATCS II - Stochastic Network Optimization Theory

Course Overview

This course will give an in-depth introduction to the recently developed Lyapunov optimization theory for stochastic networks. It aims at introducing to the students various concepts of queue stability, general models for stochastic queueing networks, the minimum-drift algorithm design principle, and the Lyapunov drift analysis technique. It will also present applications of the theory to both networking and operations research problems, and encourage the students to apply the theory to their own problems of interest. Here is the course syllabus.

Course Texts

• Required text: M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool 2010.

• Supplementary reading:

  • L. Georgiadis, M. J. Neely, L. Tassiulas, Resource Allocation and Cross-Layer Control in Wireless Networks, Foundations and Trends in Networking, Vol. 1, no. 1, pp. 1-144, 2006.

  • D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar, Convex Analysis and Optimization.

  • S. Boyd and L. Vandenberghe, Convex Optimization.

  • D. Bertsekas and R. Gallager, Data Network.

  • Articles on the Stochastic Network Optimization Homepage: http:ee.usc.edu/stochastic-nets.

Grading

The course grade consists of the following three components

1. Homework 20%

2. Midterm 30%

3. Course Project 50%

Course Schedule

1. Introductions to Queues, Definitions of Stability, Intro to Lyapunov Analysis

2. Single Queue System Analysis, A 2-Queue Control Problem, Multihop Network Scheduling.

3. Multihop Network Scheduling, Caratheodory’s Theorem, Virtual Queues

4. Scheduling for Utility Maximization-I

5. Scheduling for Utility Maximization-II

6. Optimizing Functions of Time Averages, Multi-Timescale Control

7. Optimization for Wired Network, NUM and Dual Decomposition

8. Midterm

9. The Optimization Approach and the Lyapunov Technique, Delay Reduction Techniques

10. No Class

11. Lyapunov Analysis for Processing Networks, Algorithm Design for Renewal Systems and Linear Fractional Programming

12. Max-Weight CSMA, Markov Approximation and its Applications, Mixing Time

13. Alternative Lyapunov Functions and Network Control, Systems with Markovian Dynamics

14. Special Topics: Scheduling for Content Distribution NetworkCloud ComputingMapReduce

15. Special Topics: Delay-based Lyapunov Control

16. Project Presentations