Stability of queueing networks and scheduling policies
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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 reentrant line, we show that all stationary non-idling 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 reentrant 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.
name of conference
Proceedings of 32nd IEEE Conference on Decision and Control
