Queue Stability and Probability 1 Convergence via Lyapunov Optimization
Queue Stability and Probability 1 Convergence via Lyapunov Optimization
复制标题
通过 Lyapunov 优化实现队列稳定性和概率 1 收敛
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Neely
中科院分区：
文献类型：
--
作者：
M. Neely
李雅普诺夫漂移和李雅普诺夫优化是在随机混沌网络中优化时间平均值的强大技术。然而，在文献中有各种各样的队列稳定性的定义，最方便的李雅普诺夫漂移条件往往提供的稳定性和性能界的时间平均期望，而不是一个纯粹的时间平均。我们扩展的理论表明，二次李雅普诺夫函数的基本漂移条件，连同温和的有界四阶矩条件，意味着所有主要形式的稳定性。此外，我们表明，基本的漂移加惩罚条件意味着相同的界限，排队积压和惩罚支出，是已知的时间平均期望也持有纯时间平均概率为1。我们的分析结合了李雅普诺夫漂移理论与Kolmogorov大数定律的有限方差鞅差。
Lyapunov drift and Lyapunov optimization are powerful techniques for optimizing time averages in stochastic queueing networks subject to stability. However, there are various definitions of queue stability in the literature, and the most convenient Lyapunov drift conditions often provide stability and performance bounds only in terms of a time average expectation, rather than a pure time average. We extend the theory to show that for quadratic Lyapunov functions, the basic drift condition, together with a mild bounded fourth moment condition, implies all major forms of stability. Further, we show that the basic drift-plus-penalty condition implies that the same bounds for queue backlog and penalty expenditure that are known to hold for time average expectations also hold for pure time averages with probability 1. Our analysis combines Lyapunov drift theory with the Kolmogorov law of large numbers for martingale differences with finite variance.