Stability and Instability of the MaxWeight Policy

• 成果类型: Article
• 署名作者: Bramson, Maury; D'Auria, Bernardo; Walton, Neil
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; Universidad Carlos III de Madrid; University of Manchester
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1106
• 发表日期: 2021
• 页码: 1611-1638
• 关键词: multiclass queuing-networks; Throughput

摘要

Consider a switched queueing network with general routing among its queues. TShe MaxWeight policy assigns available service by maximizing the objective function Sigma(j)Q(j)sigma(j) among the different feasible service options, where Q(j) denotes queue size and sigma(j) denotes the amount of service to be executed at queue j. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. These properties and its simple formulation suggest MaxWeight as a serious candidate for implementation in the setting of switched queueing networks; MaxWeight has been extensively studied in the context of communication networks. However, a fluid model variant of MaxWeight was previously shown not to be maximally stable. Here, we prove that MaxWeight itself is not in general maximally stable. We also prove MaxWeight is maximally stable in a much more restrictive setting, and that a weighted version of MaxWeight, where the weighting depends on the traffic intensity, is always stable.