Lyapunov Drift-Plus-Penalty Optimization for Queues With Finite Capacity
Lorenzo Bracciale, Pierpaolo Loreti
Abstract
Lyapunov optimization is a powerful control technique that allows the stabilisation of real or virtual queues while optimizing a performance objective. The method has become popular due to the fact that it applies a greedy optimization that does not rely on any statistical knowledge of the underlying process. Moreover, the technique includes a parameter V to control the stability vs utility trade-off, offering a theoretical bound on the performance. However, in its basic form, the optimization ensures that queues are only asymptotically stable, and there is no guarantee that queues will stay below a given threshold at all times. This can affect the applicability of this technique to many applications with queues with limited capacity or, equivalently, systems with hard delay constraints. In this letter we analyse the conditions under which it is possible to set a queue maximum capacity constraint, and we provide a technique to set an extra bound on the parameter V to enforce such constraint.