Essential Faces and Stability Conditions of Multiclass Networks with Priorities

V. Dumas

2001, v.7, Issue 4, 541-559

ABSTRACT

It is now well-known that multiclass networks may be unstable even under the ``usual conditions'' of stability (when the loads are less than one at all queues), but the proofs of transience (in the Markovian case) generally require a complex work based on the dynamics of an associated ``fluid model''. Here we develop a simple, sample-path argument introduced in a previous paper [V. Dumas, A multiclass network with non-linear, non-convex, non-monotonic stability conditions, Queueing Systems, Theory Appl., 1997,v.25, pp. 1-43] which provides new ergodicity conditions for networks ruled by priorities; when one of these conditions is violated, the network diverges at linear speed. Our approach is based on the identification of the ``unessential faces'', which are the sets of classes that cannot be simultaneously occupied. A graph is associated with the network, the existence of unessential faces being equivalent to the presence of cycles in this graph, in which case the usual conditions are not sufficient conditions of stability. As a by-product of our results, we recover the stability conditions and complete the analysis of two exemplary models, the Rybko-Stolyar network, see [D. Botvich and A. Zamyatin, Ergodicity of conservative communication networks, Rapport de recherche 1772, INRIA, 1992; A. Rybko and A. Stolyar, Ergodicity of stochastic processes describing the operation of open queueing networks, Problemy Peredachi Informatsii, 1992, v.28, N3, pp.3-26] and the Lu-Kumar network, see [J. Dai and G. Weiss, Stability and instability of fluid models for re-entrant lines, Math. Oper. Research, 1996, v. 21, N1, pp.115-134; S. Lu and P. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automatic Control, 1991, v.36, N12, pp.1406-1416].

Keywords: multiclass queueing networks,preemptive resume priorities,random walksin $Z_+^N$,space homogeneity,(un)essential faces,irreducibility,ergodicity,stability conditions

COMMENTS

Please log in or register to leave a comment