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

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.