Stability and Asymptotic Optimality of Generalized MaxWeight Policies

Sean Meyn

70 citations0/0 files storedSIAM Journal on Control and Optimization

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Queuing Theory Analysis Network Traffic and Congestion Control Age of Information Optimization

Abstract

It is shown that stability of the celebrated MaxWeight or back pressure policies is a consequence of the following interpretation: either policy is myopic with respect to a surrogate value function of a very special form, in which the “marginal disutility” at a buffer vanishes for a vanishingly small buffer population. This observation motivates the h-MaxWeight policy, defined for a wide class of functions h. These policies share many of the attractive properties of the MaxWeight policy as follows: (i) Arrival rate data is not required in the policy. (ii) Under a variety of general conditions, the policy is stabilizing when h is a perturbation of a monotone linear function, a monotone quadratic, or a monotone Lyapunov function for the fluid model. (iii) A perturbation of the relative value function for a workload relaxation gives rise to a myopic policy that is approximately average-cost optimal in heavy traffic, with logarithmic regret. The first results are obtained for a general Markovian network model. Asymptotic optimality is established for a general Markovian scheduling model with a single bottleneck, and with homogeneous servers.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 70 citations exist upstream.

References

1992Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks 1987Brownian Motion and Stochastic Flow Systems.1995On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit Models 1975Applying a New Device in the Optimization of Exponential Queuing Systems 2007Control Techniques for Complex Networks 2004MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic 1961The single server queue in heavy traffic 1962On Queues in Heavy Traffic

Cited by

2012Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization 2009Stable and utility-maximizing scheduling for stochastic processing networks 2014Optimal queue-size scaling in switched networks 2016Proportional Switching in First-in, First-out Networks 2012Optimal queue-size scaling in switched networks

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.