Stability and Instability of the MaxWeight Policy

Maury Bramson (), Bernardo D’Auria () and Neil Walton ()
Additional contact information
Maury Bramson: School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455
Bernardo D’Auria: Departmento de Estadística, Universidad Carlos III de Madrid, 28903 Madrid, Spain
Neil Walton: Department of Mathematics, University of Manchester, Manchester M13 9PL, United Kingdom

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1611-1638

Abstract: 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 σ j among the different feasible service options, where Q j denotes queue size and σ 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.

Keywords: Primary: 68M20; 60K25; 90B15; Primary: Queues: networks; secondary: queues: busy period analysis; MaxWeight; longest-queue-first-served; instability; stability; multihop; networks (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1611-1638

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().