An Optimal Scheme for Two Competing Queues with Constraints.

Abstract

Two types of traffic, e.g., voice and data, share a single synchronous and noisy communication channel. This situation is modeled as a system of two discrete-time queues with geometric service requirements which compete for the attention of a single server. The problem is cast as one in Markov decision theory with long-run average cost and constraint. An optimal strategy is identified that possesses a simple structure, and its implementation is discussed in terms of an adaptive algorithm that is extremely simple, recursive and easily implementable, with no prior knowledge of the actual values of the statistical parameters. The derivation of the results combines martingale arguments, results on Markov chains, O.D.E. characterization of the limit of stochastic approximations , methods from weak convergence. The ideas developed here are of independent interest , should prove useful in studying broad classes of constrained Markov decision problems.