Título:
|
A Characterization of universal stability in the adversarial queuing model
|
Autor/a:
|
Serna Iglesias, María José; Blesa Aguilera, Maria Josep; Álvarez Faura, M. del Carme
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
We study universal stability of directed and undirected graphs in the adversarial queueing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path before leaving the system. Restrictions on the allowed
packet trajectory provide a way to analyze stability under different packet trajectories.
We consider five packet trajectories, two for directed graphs and three for undirected graphs, and provide polynomial time algorithms for testing universal stability when considering each of them. In each case we obtain a different characterization of the universal
stability property in terms of a set of forbidden subgraphs. Thus we show that variations of the allowed packet trajectory lead to non-equivalent characterizations.
Using those characterizations we are able to provide also polynomial time algorithmsfor testing stability under the ntg-lis protocol. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Universal stability -Directed graphs -Undirected graphs -Adversarial queuing model |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|