OPTIMAL QUEUE-SIZE SCALING IN SWITCHED NETWORKS

• 成果类型: Article
• 署名作者: Shah, D.; Walton, N. S.; Zhong, Y.
• 署名单位: Massachusetts Institute of Technology (MIT); University of Amsterdam; Columbia University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP970
• 发表日期: 2014
• 页码: 2207-2245
• 关键词: state-space collapse; maximum pressure policies; qualitative properties; delay; insensitivity; approximation; Throughput; models

摘要

We consider a switched (queuing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture (documented in Shah, Tsitsildis and Zhong [Queueing Syst. 68 (2011) 375-384]) about optimal queue-size scaling for input-queued switches.