Instability in Stochastic and Fluid Queueing Networks
David Gamarnik and J. J. Hasenbein
The fluid model has proven to be one of the most effective tools for the
analysis of
stochastic queueing networks, specifically for the analysis of stability.
It is known that stability of a fluid model implies positive (Harris)
recurrence (stability) of a
corresponding stochastic queueing network, and weak stability implies rate
stability
of a corresponding stochastic network. These results have been established
both for cases of specific
scheduling policies and for the class of all work conserving policies.
However, only partial converse results have been established and in
certain cases converse statements
do not hold. In this paper we close one of the existing gaps. For the case
of networks with two stations
we prove that if the fluid model is not
weakly stable under the class of all work conserving policies,
then a corresponding queueing network
is not rate stable under the class of all work conserving policies. We
establish the result by
building a particular work conserving scheduling policy which makes the
associated stochastic
process transient. An important corollary of our result is that the
condition
rho* < 1, which was proven in a paper by Dai and VandeVate to be the exact
condition for global
weak stability of the fluid model, is also the exact global rate stability
condition
for an associated queueing network. Here rho* is a certain computable
parameter of the network involving virtual station
and push start conditions.