Events Calendar

Utility Optimal Scheduling in Networks: Small Delay and No Underflow

Speaker: Longbo Huang, USC

Talk Title: Utility Optimal Scheduling in Networks: Small Delay and No Underflow

Abstract: The recently developed Lyapunov optimization technique (commonly known as Backpressure / Max-Weight) is a powerful tool for solving a large class of stochastic network optimization problems. In this talk, we extend the theory in two directions: (i) We prove that dramatically improved delay is achievable with a simple Last-In-First Out (LIFO)-Backpressure rule, (ii) We generalize to "processing networks" where processing actions combine commodities of different queues to produce outputs, which involves a challenging "no underflow" constraint.

In the first part of the talk, we show that the LIFO-Backpressure algorithm can achieve utility within epsilon of optimality (for any epsilon>0), with O([log(1/epsilon)]^2) average delay. This dramatically improves upon the previous O(1/epsilon) delay bounds, and results in 95-98% delay reduction in practical implementations. Remarkably, LIFO-Backpressure achieves this performance by simply changing the queueing discipline of the original Backpressure algorithm. It is also the first algorithm that achieves such poly-logarithmic delay performance without knowing or learning any implicit network parameters.

In the second part of the talk, we consider processing networks that are generalizations of the traditional data networks, where commodities in one or more queues can be combined to produce new commodities that are delivered to other parts of the network. These networks can be used to model problems such as data fusion, stream processing and manufacturing, etc. Scheduling algorithms in such networks must ensure that the queues always have enough contents to support the actions, i.e., no underflow happens. We develop the Perturbed Max-Weight algorithm (PMW) for general processsing networks with random arrivals and activation costs. We show that by carefully perturbing the weights used in the usual Max-Weight algorithm, PMW simultaneously prevents queue underflows and optimizes network utility.


Biography: Longbo Huang received the B.E. degree from Sun Yat-sen University, Guangzhou, China in June 2003, and the M.S. degree from Columbia University, New York City, in December 2004, both in Electrical Engineering. He is currently working toward his Ph.D. degree at the University of Southern California. His research interests are in the areas of Queueing Theory, Stochastic Network Optimization and Network Pricing.

Host: Alex Dimakis, dimakis@usc.edu, EEB 532, x09264

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos