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. |