Balancing Tradeoffs in Network Queue Management Problem via Forward–Backward Sweeping with Finite Checkpoints

Abstract

Network queue management can be modelled as an optimal control problem and is aimed at controlling the dropping rate, in which the state and control variables are the instantaneous queue length and the dropping rate, respectively. One way to solve it is by using an indirect method, namely forward–backward sweeping based on the Pontryagin minimum principle to derive control the trajectory of the dropping rate. However, there exists some performance balance issues in the network queue, such as memory usage versus runtime of the algorithm, or dropping rate versus network queue length. Many researchers have exploited symmetry for constrained systems, controllers, and model predictive control problems to achieve an exponential memory reduction and simple, intuitive optimal controllers. In this article, we introduce the integration of the checkpointing method into forward–backward sweeping to address such balancing issues. Specifically, we exploit the revolve algorithm in checkpointing and choose a finite number of checkpoints to reduce the complexity. Both numerical and simulation results in a popular network simulator (ns-2) are provided through two experiments: varying bandwidth and offered load, which solidify our proposal in comparison to other deployed queue management algorithms.

Keywords

• network queue
• optimal control
• automatic differentiation
• parametric optimization
• checkpointing technique