EE 381K Advanced Telecommunication Networks - Fall 2010
Large Deviations and Stochastic Network Models with Applications to Network Analysis
- Instructor: Gustavo de Veciana
- Class: M W 9:30-11 in ENS 302
- Office : ACES 3.120
- Office hours: MTuW 11-12 and by appointment
- Email: gustavo@ece.utexas.edu, WWW: http://www.ece.utexas.edu/~gustavo
Description
This course will cover diverse large deviations results, network utility maximzation and
and stochastic network models and their applications to modeling and analysis of network systems.
Applications will include, approches to resource allocation in communication networks,
TCP-based congestion control, wireless scheduling, P2P networks, and possibly energy systems.
As time permits I also intend to cover some topics in
stochastic comparisons, which I think will be useful to you in your graduate studies.
The material in this course is a mix of standard matarial and recent research results,
as such, lectures will be drawn from standard texts in the area as well as key research
papers.
Course Contents
- Large deviations and applications to network analysis
- Large Deviations Principle (LDP) and background on convex duality.
- Cramer's Theorem, Sanov's Theorem, and Gartner-Ellis Theorem.
- Analysis of queues: large buffer and many source regimes.
- Abstract LDPs, sample path LDPs, Contraction Principle, brief topology background.
- Queues as continous mappings and most likely overflow paths.
- Large deviations and optimality properties of systems subject to Lyapunov-drift minimizng policies.
- Network Utility Maximization
- Resource allocation and fairness: max-min, proportional and alpha-fairness.
- Algorithms for utility maximization.
- Internet congestion control protocols.
- Possible topic: Multipath routing and resource pooling
- Stochastic Network Models
- Flow-level models for the Internet
- Stability and performance: Insensitivty and balanced, and modifed proportionally fair resource
allocation.
- Stochastic Ordering and Comparisons
- Stochastic and increasing convex ordering for random variables
- Functions of order RVs
- Applications to comparing performance in network systems.
Course web page
Prerequisites
You will need to have taken the following graduate level courses (or have equivalent background):
(1) EE 381J Probability and Random Processes;
(2) EE 381 K Analysis and Design of Communication Networks, i.e.,
background in queueing theory and time-reversible Markov Chains;
(3) background in analysis and convex optimization.
The end goal is to model and analyse a variety of network systems. You should be familiar
with the basic communication and wireless network systems.
This is an advanced course,
which for the most part should be taken by 2nd-3rd year graduate students.
Expect it to be challenging but hopefully rewarding too!
Some Texts and Selected Papers
The course will cover a variety of topics drawing from various texts and research papers.
Below I've listed several books some of which are available on the web. The papers to be
discussed in the course are available in blackboard.
I plan to follow both "Big queues" and "Network Optimization and Control" for reasonably
large sections of the course.
- Big Queues, A. Ganesh, N. O'Connel and D. Wishik,
Lecture Notes in Mathematics 1838, Springer, 2003. (Available electronically through UT Library)
- Large deviations techniques and applications, A. Dembo and O. Zeitouni,
Springer 1998.
- Large deviations for performance analysis, A. Shwartz and A. Weiss,
Chapman & Hall 1995.
- Network Optimization and Control, Srinivas Shakkottai and R. Srikant,
Now 2007. (Available on web)
- Reversibility and Stochastic Networks, F. Kelly, Wiley 1978. (Available on web)
- Multiservice Loss Models for Broadband Telecommunication Networks, K. Ross,
Springer 1997.
- Comparison methods for stochastic models and risks, A. Muller and D. Stoyan,
Wiley 2002.
Format/Evaluation
You will be responsible for basic material presented in class and strongly encouraged
to participate in class discussions. Think of this as a team effort.
Your grade will be based
20% homework and class participation,
30% on two quizzes,
and 50% on your presentations and project.
- Homeworks:
Will be assigned sporadically. Homework solutions will be typset
and homeworks will be graded by students in the class.
This will count towards your homework grades and participation.
Unfortunately this class has no TA support :(.
- Quizzes:
I intend have give you 2 (closed notes) quizzes to check you are learning/digesting
the basic material we have discussed in class.
- Class Project and Presentations:
You will be required to do a small project for the class. This may be either detailed
reading and presenting of a research paper, or an attempt to tackle a problem of your own.
You can work in teams of no more than two. You will be required to make two presentations:
the first will be a problem/research statement plus an overview
of the state of the art on your topic;
the second a followon with results you or others were able to obtain.
All students will be expected to present.
The final presentations will be part of a class "mini-symposium" that will take
place at the end of the term. We will
run it like a "formal" conference, with strict time deadlines, and invite faculty
and students to attend.
Where does course fit in?
This course is intended to build on your own background and interests as well as
material in Probability and Random Processes,
Communication Networks: Analysis and Design, Information Theory and Optimization.
Note: All departmental, college and university regulations
concerning drops will be followed. The University of Texas at Austin provides
upon request appropriate academic accommodations for qualified students
with disabilities. For more information, contact the Office of the Dean
of Students at 471-6259, 471-4641 TTY.