2019/09/24 by Bramson, Maury, D'Auria, Bernardo, Walton, Neil · 1 citation
#60K25 #68M20 #90B15 #FOS: Computer and information sciences #FOS: Mathematics #Networking and Internet Architecture (cs.NI) #Probability (math.PR)
paper · doi:10.48550/arxiv.1909.10825
Consider a switched queueing network with general routing among its queues. The MaxWeight policy assigns available service by maximizing the objective function ∑j Qj σj among the different feasible service options, where Qj 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, as well as 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 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 version of MaxWeight, where the weighting depends on the traffic intensity, is always stable.