Abstract of Paper

Adversarial models for priority-based networks
by C. Alvarez, M.Blesa, J. Diaz, A. Fernandez, and M. Serna

Abstract:

We propose several variations of the adversarial queueing model. 
The \emph{priority} model takes into account the
case in which the packets can have different priorities, assigned by
the adversary at injection time. The \emph{ variable priority} model 
is an extension of the priority model in which the adversary may
change the priority of packets at each time step. The
\emph{failure} and \emph{reliable} models are designed to cope with
dynamic networks in which the adversary controls, under different
constraints, the edge failures. 

We address stability issues in the proposed adversarial models. We
show that the set of \emph{universally stable} networks in the
adversarial model remains the same in the priority, variable priority, 
failure and  reliable  models.
   
From the point of view of queueing policies we show that several 
queueing policies that are universally stable in the adversarial model
remain so in the priority, failure and reliable  models. However, we
show that LIS, a universally stable queueing policy in the
adversarial model, is not universally stable in any of the other models.
Moreover, we show that no greedy  queueing policy is  universally stable
in the variable priority model.

Finally we analyze the problem of deciding stability of a given
network under a fixed protocol.  We provide a characterization of the
networks that are stable under FIFO and LIS in the failure model
(and therefore in the reliable and priority models). This
characterization allows us to show that the stability problem under
FIFO and LIS in the failure model can be solved in polynomial time.