SWITCHED NETWORKS WITH MAXIMUM WEIGHT POLICIES: FLUID APPROXIMATION AND MULTIPLICATIVE STATE SPACE COLLAPSE

• 成果类型: Article
• 署名作者: Shah, Devavrat; Wischik, Damon
• 署名单位: Massachusetts Institute of Technology (MIT); University of London; University College London
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/11-AAP759
• 发表日期: 2012
• 页码: 70-127
• 关键词: pressure policies; queuing-networks

摘要

We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936-1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling.