In this seminar-styled course, we will study the techniques of stochastic optimization and how to apply them to the design of control algorithms for communication networks. The applications include how to route traffic and schedule link transmissions for wireless networks and how to design distributed algorithms for network content distribution. We will mainly study two sets of techniques, which are broadly applicable. The first is Lyapunov optimization and drift analysis, and the second is the theory of Markov Chain Monte Carlo. The latter is the basis for important randomized algorithms for combinatorial optimization or for sampling from combinatorial structures. In the wireless network setting, we will focus on randomized schemes for multiple access, such as various versions of CSMA.
We will study recent papers from top networking conferences, such as INFOCOM and SIGMETRICS. Students should have a good background in probability theory and optimization, or should be willing to learn. At the end of the course, students should be able to read theoretical papers from these conferences more easily.
T: period 7, CSE220
R: period 7-8, CSE220
Mostly, you should do your reading assignments. There will be two written assignments asking you to fill in the details of the results from your reading.
Attendance and participation
will be important for the final grades.
L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource Allocation and Cross-Layer Control in Wireless Networks. Foundations and Trends in Networking Vol. 1, no. 1, pp. 1-144, 2006.
PDF file available on the webญญญญญญญญญญญญญญญญญญ
Dynamic Programming and Optimal Control (two volumes)
Dimitri P. Bertsekas
Vol. I, 3RD EDITION, 2005, 558 pages
Vol. II, 3RD EDITION, 2007, 464 pages
Markov Decision Processes: Discrete Stochastic Dynamic Programming
2005
Martin L. Puterman
Books on Convex Optimization
Dimitri Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition, 1999.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization.
Books on Probability Theory
Sheldon M. Ross. Stochastic Processes
Knowledge in the areas of probability and stochastic processes, linear algebra, mathematical analysis, convex optimization, queueing systems.
Friday: 1-3pm, E538