Report Number: CS-TN-97-59
Institution: Stanford University, Department of Computer Science
Title: Stability of Networks and Protocols in the Adversarial Queueing
Model for Packet Routing
Author: Goel, Ashish
Date: September 1997
Abstract: 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 a specific greedy protocol, SIS
(Shortest In System), is stable against a large class of
stochastic adversaries. New applications such as multicast
packet scheduling and job scheduling with precedence
constraints xsare suggested for the adversarial model.
http://i.stanford.edu/pub/cstr/reports/cs/tn/97/59/CS-TN-97-59.pdf