ON THE OPTIMAL-CONTROL OF ARRIVALS TO A SINGLE QUEUE WITH ARBITRARY FEEDBACK DELAY

We consider a problem of admission control to a single queue in discre te time. The controller has access to Ic-step old queue lengths only, where k can be arbitrary. The problem is motivated, in particular, by recent advances in high-speed networking where information delays have become prominent. We formulate the problem in the framework of Comple tely Observable Controlled Markov Chains, in terms of a multi-dimensio nal state variable. Exploiting the structure of the problem, we show t hat under appropriate conditions, the multi-dimensional Dynamic Progra mming Equation (DPE) can be reduced to a unidimensional one. We then p rovide simple computable upper and lower bounds to the optimal value f unction corresponding to the reduced unidimensional DPE. These upper a nd lower bounds, along with a certain relationship among the parameter s of the problem, enable us to deduce partially the structural feature s of the optimal policy. Our approach enables us to recover simply, in part, the recent results of Altman and Stidham, who have shown that a multiple-threshold-type policy is optimal for this problem. Further, under the same relationship among the parameters of the problem, we pr ovide easily computable upper bounds to the multiple thresholds and sh ow the existence of simple relationships among these upper bounds. The se relationships allow us to gain very useful insights into the nature of the optimal policy. In particular, the insights obtained ate of gr eat importance for the problem of actually computing an optimal policy because they reduce the search space enormously.