ALCOMFT-TR-02-86

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
The Impact of Structure on Stability in Adversarial Queueing Theory
Patras and Cyprus. Work packages 2 and 4. May 2002.

Abstract: In this paper, we continue the study of stability issues in the Adversarial Queueing Theory model for packet-switched routing in communication networks. We are interested in revealing structural properties of the networks that critically determine the stability or instability properties of common protocols, such as FIFO and NTG, running of them. We obtain the following structural results:

• We present an improved analysis of FIFO stability for any given network; this analysis relies on a careful consideration of the precise role played by several structural (graph-theoretic) parameters of the network, such as the maximum number of disjoint paths used by the adversary in any given execution, the maximum directed path length and the maximum in-degree of the underlying graph. The end result of our analysis is an improved upper bound on the adversary's injection rate, as a function of structural parameters of the network, that suffices to guarantee that FIFO is stable on the network; this result represents a substantial improvement over a corresponding result shown recently by Diaz et al. [DKNSST01].

  To illustrate the strength and applicability of our analytical techniques, we first apply them to a particular, simple network with just three queues, originally studied in [G01]. The application yields that this network is stable for FIFO against any adversary with injection rate no more than 0.2357; this represents an improvement over a corresponding result shown in [DKNSST01].

• On the negative side, we are interested in determining structural properties of a network, stated in terms of forbidden graph minors, that suffice to imply that the network is not universally stable (i.e., it is not stable for any protocol in a given class). We introduce two new graph minors, and we show that they are forbidden (as graph minors) for any universally stable network; furthermore, we analyze their instability thresholds: these are lower bounds on the adversary's injection rate above which the graph minors are unstable. Interestingly, each of these graph minors is a subgraph of some graph minor in a family of three that were claimed in [G01] to be forbidden graph minors for any universally stable network. Moreover, none of the three graph minors in [G01] is a subgraph of the forbidden minors we identify, and this implies that a structural characterization of universal stability is needed that is more refined than the one claimed in [G01].

Postscript file: ALCOMFT-TR-02-86.ps.gz (212 kb).