Stability of networks and protocols in the adversarial queueing model for packet routing

The adversarial queueing theory model for packet routing was suggested by Borodin et al. We give a complete and simple characterization of all networks that are universally stable in this model. We show that the same characterization also holds for networks which are stable given that the packet forwarding protocol is FIFO (First in First out). We also show that a specific greedy protocol, SIS (Shortest in System), is stable against 0/1 stochastic adversaries.