Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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 to conduct such stability and performance analyses. A certain LP (linear program), 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. Some systems satisfy an auxiliary set of linear constraints. Examples are systems operating under buffer priority policies or incorporating models of machine failures. Their performance is also bounded by a Performance LP, provided that they are stable, i.e., have a finite first moment for the number of parts. If the Performance LP is infeasible, then the system is unstable. Any feasible solution to the dual of the Performance LP provides a quadratic form with a negative drift. If this quadratic form is copositive, then the system is geometrically ergodic as above. If not, the system is either unstable or else is highly nonrobust in that arbitrarily small perturbations can lead to an unstable system. One can use known algorithms to check the copositivity of the required matrix. These results carry over to fluid models, allowing the study of networks with nonexponential distributions. There is another LP test of stability that avoids a copositivity check. If a modification of the Performance LP, called the Monotone LP, is bounded, then the system is stable. Moreover, the stability holds for all smaller arrival rates. 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. 1996 IEEE.
