Adversarial queuing theory

We consider packet routing when packets are injected continuously into a ne twork. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds ligh t on various queuing policies in simple networks, and paves the way for a s ystematic study of queuing with few or no probabilistic assumptions.