Stability of queueing networks and scheduling policies

Usually, the stability of queueing networks is established by explicitly determining the invariant distribution. However, except for product form queueing networks, such explicit solutions are rare. We develop here a programmatic procedure for establishing the stability of queueing networks and scheduling policies. The method uses linear or nonlinear programming to determine what is an appropriate quadratic functional to use as a Lyapunov function. If the underlying system is Markovian, our method establishes not only positive recurrence and the existence of a steady-state probability distribution, but also the geometric convergence of an exponential moment. We illustrate this method on several example problems. For an open re-entrant line, we show that all stationary nonidling policies are stable for all load factors less than one. This includes the well known first-come-first-served (FCFS) policy. We determine a subset of the stability region for the Dai-Wang example (1991), for which they have shown that the Brownian approximation does not hold. In another re-entrant line, we show that the last-buffer-first-served (LBFS) and first-buffer-first-served (FBFS) policies are stable for all load factors less than one. Finally, for the Rybko-Stolyar example (1992), for which a subset of the instability region has been determined by them under a certain buffer priority policy, we determine a subset of the stability region