Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.