Stability and Instability of the MaxWeight Policy
Stability and Instability of the MaxWeight Policy
复制标题
MaxWeight 策略的稳定性和不稳定性
DOI：
10.1287/moor.2020.1106
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
N. Walton
中科院分区：
文献类型：
--
作者：
M. Bramson;B. D’Auria;N. Walton
考虑一个交换排队网络，其队列之间具有一般路由。MaxWeight策略通过在不同的可行服务选项中最大化目标函数[Formula：see text]来分配可用服务，其中[Formula：see text]表示队列大小，[Formula：see text]表示在队列[Formula：see text]处要执行的服务量。MaxWeight是一种贪婪策略，它不依赖于到达率的知识，并且易于实现。这些属性及其简单的公式表明MaxWeight作为一个严重的候选人，在设置开关交换网络的实施; MaxWeight已被广泛研究的通信网络的背景下。然而，MaxWeight的流体模型变体先前被证明不是最大稳定的。在这里，我们证明了MaxWeight本身一般不是最大稳定的。我们还证明了MaxWeight是最大限度地稳定在一个更严格的设置，和加权版本的MaxWeight，其中的权重取决于交通强度，总是稳定的。
Consider a switched queueing network with general routing among its queues. The MaxWeight policy assigns available service by maximizing the objective function [Formula: see text] among the different feasible service options, where [Formula: see text] denotes queue size and [Formula: see text] denotes the amount of service to be executed at queue [Formula: see text]. 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.