Events Calendar

Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization

Speaker: Longbo Huang,
USC PhD CandidateAbstract: In this paper, we consider the problem of reducing network delay in stochastic network utility optimization problems. We start by studying the recently proposed quadratic Lyapunov function based algorithms (QLA). We show that for every stochastic problem, there is a corresponding \emph{deterministic} problem, whose dual optimal solution ``exponentially attracts'' the network backlog process under QLA. In particular, the probability that the backlog vector under QLA deviates from the attractor is exponentially decreasing in their Euclidean distance. This suggests that one can roughly ``subtract out'' a Lagrange multiplier from the system induced by QLA. We thus develop a family of \emph{Fast Quadratic Lyapunov based Algorithms} (FQLA) that achieve an $[O(1/V), O(\log2(V))]$ performance-delay tradeoff.These results highlight the "network gravity'' role of Lagrange Multipliers in network scheduling. This role can be viewed as the counterpart of the ``shadow price'' role of Lagrange Multipliers in flow regulation for classic flow-based network problems.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 University of Southern California. His research interests are in the areas of Queueing Theory, Stochastic Network Optimization and Network Pricing.Host: Michael Neely, mjneely@usc.edu, EEB 520, x03505

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

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos