ASYMPTOTIC ANALYSIS OF THE EFFECT OF ARRIVAL MODEL UNCERTAINTIES IN SOME OPTIMAL ROUTING-PROBLEMS

We study the effect of arrival model uncertainties on the optimal rout ing in a system of parallel queues. For exponential service time distr ibutions and Bernoulli routing, the optimal mean system delay generall y depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorit hm to produce a mean system delay higher than the true optimum. In thi s paper, we present an asymptotic analysis of the behavior of this err or under heavy traffic conditions for a general renewal arrival proces s. An asymptotic analysis of the error in optimal mean delay due to un certainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vani shes asymptotically as the traffic load approaches the system capacity . In contrast, this paper establishes the somewhat surprising result t hat, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival mo del is unbounded as the traffic approaches the system capacity. Howeve r, when both first and second moments are known, the error vanishes as ymptotically. Numerical examples corroborating the theoretical results are also presented.