A Simple Problem of Flow Control I: Optimality Results.

Abstract

This paper presents a problem of optimal flow control for discrete M|M|1 queues. The problem is cast as a constrained Markov decision process, where the throughput is maximized with a bound on the average queue size. By Lagrangian arguments, the optimal strategy is shown to be of threshold type and to saturate the constraint. The method of analysis proceeds through the discounted version of the Lagrangian problems for which the corresponding value functions are shown to be integer-concave. Dynamic Programming and stochastic comparison ideas constitute the main ingredients of the solution.