From Local to Global Stability in Stochastic Processing Networks Through Quadratic Lyapunov Functions
From MaRDI portal
Publication:5169683
DOI10.1287/MOOR.2013.0588zbMATH Open1291.90066arXiv1210.0258OpenAlexW2122029049MaRDI QIDQ5169683
No author found.
Publication date: 11 July 2014
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: We construct a generic, simple, and efficient scheduling policy for stochastic processing networks, and provide a general framework to establish its stability. Our policy is randomized and prioritized: with high probability it prioritizes jobs which have been least routed through the network. We show that the network is globally stable under this policy if there exists an appropriate quadratic local Lyapunov function that provides a negative drift with respect to nominal loads at servers. Applying this generic framework, we obtain stability results for our policy in many important examples of stochastic processing networks: open multiclass queueing networks, parallel server networks, networks of input-queued switches, and a variety of wireless network models with interference constraints. Our main novelty is the construction of an appropriate global Lyapunov function from quadratic local Lyapunov functions, which we believe to be of broader interest.
Full work available at URL: https://arxiv.org/abs/1210.0258
Related Items (4)
Stability analysis of data-driven local model networks ⋮ Stochastic bandwidth packing process: stability conditions via Lyapunov function technique ⋮ Asymmetric flow networks ⋮ Concave switching in single-hop and multihop networks
This page was built for publication: From Local to Global Stability in Stochastic Processing Networks Through Quadratic Lyapunov Functions
