Stability of Adversarial Queues via Fluid Models

The subject of this paper is stability properties of adversarial queuing networks. Such queuing systems are used to model packet switch communication networks, in which packets are generated and routed dynamically, and have become a subject of research focus recently. Adversarial queuing networks are defined to be stable if the number of packets stays bounded over time. A central question is determining which adversarial queuing networks are stable when an arbitrary greedy packet routing policy is implemented. In this paper we show how stability of a queuing network can be determined by considering an associated fluid model. Our main result is that the stability of the fluid model implies the stability of an underlying adversarial queuing network. This opens the opportunity for analyzing stability of adversarial networks, using established stability methods from continuous time processes, for example, the method of Lyapunov functions or trajectory decomposition. We demonstrate the use of these methods on several examples.