ALCOMFT-TR-02-103

Carme \`Alvarez, Maria Blesa and Maria Serna
Universal stability of undirected graphs in the adversarial queueing model
Barcelona. Work packages 2 and 4. May 2002.

Abstract: In this paper we study the universal stability of undirected graphs in the adversarial queueing model for packet routing. In this setting packets must be injected in some edge and have to traverse a path before leaving the system. Restrictions on the allowed types of path that packets must traverse provide different packet models. We consider three natural models, and provide polynomial time algorithms for testing universal stability. In the three cases we obtain a different characterization, thus showing that slight variations gives raise to non equivalent models.

We finally extend the results to show that the universal stability of digraphs, in the case in which packets follow directed paths without repeated vertices, can be decided in polynomial time.

Postscript file: ALCOMFT-TR-02-103.ps.gz (111 kb).