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.