Invariant Rate Functions for Discrete-time Queues

Ganesh, Ayalvadi; O'Connell, Neil; Prabhakar, Balaji

HPL-BRIMS-2000-29

Keyword(s): large deviations; fixed points; tandem queues

Abstract: We consider a discrete time queue with general service distribution and characterize a class of arrival processes whose large deviation rate function remains unchanged in passing through the queue. This invariant rate function corresponds to a kind of exponential tilting of the service distribution. We establish a large deviations analogue of quasi-reversibility for this class of arrival processes. Finally, we prove the existence of stationary point processes whose probability law is preserved by the queueing operator, and conjecture that these have large deviation rate functions which belong to the class of invariant rate functions described above. Notes: Ayalvadi Ganesh, Microsoft Research, 1 Guildhall Street, Cambridge, CB2 3NH, UK Balaji Prabhakar, Dept of Electrical Eng. Stanford University, Stanford, CA 94305, USA

29 Pages

Back to Index