loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
39th Annual Symposium on Foundations of Computer Science
Stability of Adversarial Queues via Fluid Models
Palo Alto, California
November 08-November 11
ISBN: 0-8186-9172-7
The subject of this paper is stability properties of adversarial queueing networks. Such queueing 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 queueing networks are defined to be stable, if the number of packets stays bounded over time. A central question is determining which adversarial queueing networks are stable, when an arbitrary greedy packet routing policy is implemented. In this paper we show how stability of a queueing network can be determined by considering an associated fluid models. Our main result is that the stability of the fluid model implies the stability of an underlying adversarial queueing network. This opens an opportunity for analyzing stability of adversarial networks, using established stability methods from continuous time processes, for example, the method of Lyapunov function or trajectory decomposition. We demonstrate the use of these methods on several examples.
Index Terms:
networks, stability, fluid models, scheduling
Citation:
David Gamarnik, "Stability of Adversarial Queues via Fluid Models," focs, pp.60, 39th Annual Symposium on Foundations of Computer Science, 1998
Usage of this product signifies your acceptance of the Terms of Use.