STABILITY OF QUEUING-NETWORKS AND SCHEDULING POLICIES

Usually, the stability of queueing networks is established by explicit ly determining the invariant distribution, Outside of the narrow class of queueing networks possessing a product form solution, however, suc h explicit solutions are rare, and consequently little is also known c oncerning stability. We develop here a programmatic procedure for esta blishing the stability of queueing networks and scheduling policies, T he method uses linear or nonlinear programming to determine what is an appropriate quadratic functional to use as a Lyapunov function, If th e underlying system is Markovian, our method establishes not only posi tive recurrence and the existence of a steady-state probability distri bution, but also the geometric convergence of an exponential moment. W e illustrate this method on several example problems, For an example o f an open re-entrant line, we show that all stationary nonidling polic ies are stable for all load factors less than one, This includes the w ell-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-ent rant line, we show that the Last Buffer First Serve (LBFS) and First B uffer 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,