Research Article
Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization
@INPROCEEDINGS{10.1109/WIOPT.2009.5291609, author={Longbo Huang and Michael Neely}, title={Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization}, proceedings={7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks}, publisher={IEEE}, proceedings_a={WIOPT}, year={2009}, month={10}, keywords={Queueing Dynamic Control Lyapunov analysis Stochastic Optimization}, doi={10.1109/WIOPT.2009.5291609} }- Longbo Huang
Michael Neely
Year: 2009
Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization
WIOPT
IEEE
DOI: 10.1109/WIOPT.2009.5291609
Abstract
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 roughlysubtract 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(log^2(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 theshadow price' role of Lagrange Multipliers in flow regulation for classic flow-based network problems.