Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization

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, also known as the MaxWeight algorithm). We show that for every stochastic problem, there is a corresponding 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 is the first such result for the class of algorithms built upon quadratic Lyapunov functions. The result quantifies the "network gravity" role of Lagrange Multipliers in network scheduling. It not only helps to explain how QLA achieves the desired performance but also suggests that one can roughly "sub-tract out" a Lagrange multiplier from the system induced by QLA. Based on this finding, we develop a family of Fast Quadratic Lyapunov based Algorithms (FQLA), which use virtual place-holder bits and virtual control processes for decision making. We prove that FQLA achieves an [O(1/V), O([log(V)](2))] performance-delay tradeoff for problems with discrete action sets, and achieves a square-root tradeoff for continuous problems. The performance of FQLA is similar to the optimal tradeoffs achieved in prior work by Neely (2007) via drift-steering methods, and shows that QLA can also be used to approach such performance.