Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies

Abstract

We consider the problems of performance analysis and stability/instability determination of queuing networks and scheduling policies. We exhibit a strong duality relationship between the performance of a system and its stability analysis via mean drift. We obtain a variety of linear programs (LPs) to conduct such stability and performance analyses. A certain LP, called the performance LP, bounds the performance of all stationary nonidling scheduling policies. If it is bounded, then its dual, called the drift LP, has a feasible solution which is a copositive matrix. The quadratic form associated with this copositive matrix has a negative drift, showing that all stationary nonidling scheduling policies result in a geometrically converging exponential moment. These results carry over to fluid models, allowing the study of networks with nonexponential distributions. If a modification of the performance LP, called the monotone LP, is bounded, then the system is stable. Finally, there is a another modification of the performance LP, called the finite time LP. It provides transient bounds on the performance of the system from any initial condition.

Cite this work

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

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

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