Analysis and Adaptive Control of a Discrete-Time Single-Senrer Network with Random Routing.

Abstract

This paper considers a discrete time system composed of K infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechanism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation algorithm is proposed to drive a long- run average cost to a given value. The motivation can be traced to implementation imues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions that guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems.