STABILITY OF QUEUING-NETWORKS AND SCHEDULING POLICIES

Usually, the stability of queueing networks is established by explicitly determining the invariant distribution, Outside of the narrow class of queueing networks possessing a product form solution, however, such explicit solutions are rare, and consequently little is also known concerning stability. 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 example of 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 Serve (FCFS) policy, We determine a subset of the stability region for the Dal-Wang example, for which they have shown that the Brownian approximation does not hold, In another re-entrant line, we show that the Last Buffer First Serve (LBFS) and First Buffer First Serve (FBFS) policies are stable for all load factors less than one, Finally, for the Rybko-Stolyar example, 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,