A convex optimisation approach to optimal control in queueing systems

Abstract

Convex optimisation and max-weight are central topics in networking and control, and having a clear understanding of their relationship and what this involves is crucial from a theoretical and practical point of view. In this thesis we investigate how max-weight fits into convex optimisation from a pure convex approach without using fluid limits or Lyapunov optimisation. That is, we study how to equip convex optimisation with discrete actions and allow it to make optimal control decisions without previous knowledge of the mean packet arrival rate into the system. Our results are sound and show that max-weight approaches can be encompassed within the body of convex optimisation. In particular, max-weight is a special case of the stochastic dual subgradient method with Ek-subgradients and constant step size. We clarify the fundamental properties required for convergence, and bring to the fore the use of Ek-subgradients as a key component for modelling problem characteristics apart from discrete actions. One of the great advantages of our approach is that optimal scheduling policies can be decoupled from the choice of convex optimisation algorithm or subgradient used to solve the dual problem, and as a result, it is possible to design scheduling policies with a high degree of flexibility. We illustrate the power of the analysis with three applications: the design of a traffic signal controller; distributed and asynchronous packet transmissions; and scheduling packets in networks where there are costs associated to selecting discrete actions. The work in this thesis brings clarity and a fresh outlook to network optimisation problems, but also makes max-weight accessible from a convex optimisation perspective and therefore to a wider audience beyond networking and control. We believe that making max-weight accessible from a convex optimisation viewpoint will help to light the way to discovering new applications currently not covered by either max-weight approaches or convex optimisation.