Max-Weight Achieves the Exact $O1-V, OV$ Utility-Delay Tradeoff Under Markov Dynamics - Mathematics > Optimization and ControlReportar como inadecuado




Max-Weight Achieves the Exact $O1-V, OV$ Utility-Delay Tradeoff Under Markov Dynamics - Mathematics > Optimization and Control - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this paper, we show that the Quadratic Lyapunov function based AlgorithmQLA, also known as MaxWeight or Backpressure achieves an exact $O1-V,OV$ utility-delay tradeoff in stochastic network optimization problems withMarkovian network dynamics. Note that though the QLA algorithm has beenextensively studied, most of the performance results are obtained under i.i.d.network radnomness, and it has not been formally proven that QLA achieves theexact $O1-V, OV$ utility-delay tradeoff under Markov dynamics. Ouranalysis uses a combination of duality theory and a variable multi-slotLyapunov drift argument. The variable multi-slot Lapunov drift argument here isdifferent from previous multi-slot drift analysis, in that the slot number is arandom variable corresponding to the renewal time of the network randomness.This variable multi-slot drift argument not only allows us to obtain an exact$O1-V, OV$ tradeoff, but also allows us to state the performance of QLAin terms of explicit parameters of the network dynamic process.



Autor: Longbo Huang, Michael J. Neely

Fuente: https://arxiv.org/







Documentos relacionados