Stability of queueing networks and scheduling policies
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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 Dai-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. 1995 IEEE.
