CRITICALLY LOADED QUEUEING MODELS THAT ARE THROUGHPUT SUBOPTIMAL

• 成果类型: Article
• 署名作者: Atar, Rami; Shaikhet, Gennady
• 署名单位: Technion Israel Institute of Technology; Carnegie Mellon University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/08-AAP551
• 发表日期: 2009
• 页码: 521-555
• 关键词: systems

摘要

This paper introduces and analyzes the notion of throughput suboptimality for many-server queueing systems in heavy traffic. The queueing model under consideration has multiple customer classes, indexed by a finite set l, and heterogenous, exponential servers. Servers are dynamically chosen to serve customers, and buffers are available for customers waiting to be served. The arrival rates and the number of servers are scaled up in such a way that the processes representing the number of class-i customers in the system, i is an element of l, fluctuate about a static fluid model, that is assumed to be critically loaded in a standard sense. At the same time, the fluid model is assumed to be throughput suboptimal. Roughly, this means that the servers can be allocated so as to achieve a total processing rate that is greater than the total arrival rate. We show that there exists a dynamic control policy for the queueing model that is efficient in the following strong sense: Under this policy, for every finite T, the measure of the set of times prior to T, at which at least one customer is in the buffer, converges to zero in probability as the arrival rates and number of servers go to infinity. On the way to prove our main result, we provide a characterization of throughput suboptimality in terms of properties of the buffer-station graph.