A Simple Problem of Flow Control: Optimality and Adaptive Implementations

Abstract

The purpose of flow control is to reduce the congestion experienced in many systems, such as data networks or computer communications systems, by restricting access in order to achieve a desirable performance level. This dissertation considers the optimal flow control problem for a simple discrete-time queue, where the decision-maker seeks to maximize the throughput subject to the constraint that the average holding cost does not exceed a prespecified value. The problem is cast as a constrained Markov decision problem, and by making use of Lagrangian arguments, the optimal policy is shown to be a threshold policy which saturates the constraint. The key step of the analysis lies in establishing the concavity of the value function for the discounted version of the Lagrangian problem. The optimal threshold policy is a function of the model parameters, and is not implementable when some of these parameters are not known exactly. This naturally raises the question of how to design on-line implementable policies so that the same performance as the optimal threshold policy can be achieved. Several implementations of threshold policies are investigated in this study. Implementation is first discussed in terms of an adaptive algorithm of the Stochastic Approximations type, and the analysis relies on the strong consistency of the algorithm and makes use of ideas from the theory of Stochastic Approximations.