首页 | 本学科首页   官方微博 | 高级检索  
     


Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems
Authors:B. Mohanty  C. G. Cassandras
Affiliation:(1) Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, Massachusetts;(2) Qualcomm, San Diego, California
Abstract:We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties 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 vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.
Keywords:Routing  optimization  queueing systems  robustness  distributed algorithms
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号