Advanced Networks Colloquium: R. Srikant, "State-Space Collapse via Drift Conditions"
Friday, September 9, 2011
2107 Computer Science Instructional Center
301 405 6579
Advanced Networks Colloquium
State-Space Collapse via Drift Conditions
University of Illinois at Urbana-Champaign
| video |
Establishing the optimality of routing and scheduling problems in communication networks requires the computation of upper and lower bounds on steady-state queue lengths. It is well known that setting the drift of the Lyapunov function equal to zero in steady-state provides bounds on the expected queue lengths. However, such bounds are often very loose due to the fact that they fail to capture resource pooling effects. We will show that the approach of setting the drift of a Lyapunov function equal to zero can be used to obtain bounds on the steady-state queue lengths which are tight in the heavy-traffic limit. The key is to establish an appropriate notion of state-space collapse in terms of steady-state moments of weighted queue length differences, and use this state-space collapse result when setting the Lyapunov drift equal to zero. We will illustrate the technique by applying it to a routing problem and a scheduling problem.
R. Srikant is with the University of Illinois at Urbana-Champaign, where he is the Fredric G. and Elizabeth H. Nearing Endowed Professor of Electrical and Computer Engineering and a Research Professor in the Coordinated Science Lab. His research interests include communication networks, stochastic processes and queueing theory. He is the author of the book "Mathematics of Internet Congestion Control" and a co-author of the monograph "Network Optimization and Control." He is a Fellow of the IEEE and a Distinguished Lecturer of the IEEE Communications Society for 2011-2012.