ALCOMFT-TR-02-104

Carme \`Alvarez, Maria Blesa and Maria Serna
A characterization of universal stability for directed graphs in the adversarial queueing model
Barcelona. Work packages 2 and 4. May 2002.

Abstract: In this paper we provide a characterization of universal stability for digraphs in the general case that the packets are not restricted to follow simple paths. Furthermore, we consider a variation of the Nearest To Go protocol and we show that stability under this queueing policy is equivalent to universal stability.

Goel [Stability of networks and protocols in the adversarial queueing model for packet routing. Networks, 37(4):219-224, 2001] also studied the universal stability of digraphs when only packets following simple paths are allowed, and gave a characterization in terms of three forbidden minors. We show that a graph that does not contain any of these forbidden minors is unstable, disproving this result.

Postscript file: ALCOMFT-TR-02-104.ps.gz (90 kb).