Stability and Instability of the MaxWeight Policy

Consider a switched queueing network with general routing among its queues. The MaxWeight policy assigns available service by maximizing the objective function Σ_j Q_j σ_jamong the different feasible service options, where Qj denotes queue size and denotes the amount of σ_j 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, as well as its simple formulation, suggest MaxWeight as a serious candidate for implementation in the setting of switched queueing networks; it has been extensively studied in the context of communication networks. However, a fluid model variant of MaxWeight was shown by Andrews-Zhang (2003) 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 versión of MaxWeight, where the weighting depends on the traffic intensity, is always stable.

Stability and Instability of the MaxWeight Policy Articles