
Utility Optimal Scheduling in Networks: Small Delay and No Underflow
Wed, Jan 12, 2011 @ 02:00 PM  03:00 PM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
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 / MaxWeight) 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 LastInFirst 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 LIFOBackpressure 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 9598% delay reduction in practical implementations. Remarkably, LIFOBackpressure achieves this performance by simply changing the queueing discipline of the original Backpressure algorithm. It is also the first algorithm that achieves such polylogarithmic 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 MaxWeight algorithm (PMW) for general processsing networks with random arrivals and activation costs. We show that by carefully perturbing the weights used in the usual MaxWeight algorithm, PMW simultaneously prevents queue underflows and optimizes network utility.
Biography: Longbo Huang received the B.E. degree from Sun Yatsen 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