On the Behavior of LIFO Preemptive Resume Queues in Heavy Traffic

Vlada Limic (Cornell University)

Abstract


This paper studies heavy traffic behavior of a G/G/1 last-in-first-out (LIFO) preemptive resume queue, by extending the techniques developed in Limic (1999). The queue length process exhibits a perhaps unexpected heavy traffic behavior. The diffusion limit depends on the type of arrivals (and services) in a fairly intricate way, related to the Wiener-Hopf factorization for random walks.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 13-27

Publication Date: November 26, 1999

DOI: 10.1214/ECP.v5-1014

References

  1. D.J. Aldous, The continuum random tree III, Ann. Probab., 21:248-289, 1993. Math Review link
  2. K.B. Athreya and P.E. Ney, Branching Processes, Springer-Verlag, New York-Heidelberg, 1972. Math Review link
  3. M. Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing systems: Theory and Applications, 30:89-148, 1998. Math Review link
  4. J.G. Dai and T.G. Kurtz, A multiclass station with Markovian feedback in heavy traffic, Mathematics of Operations Research, 20:721-741, 1995. Math Review link
  5. S.N. Ethier and T.G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, New York, 1986. Math Review link
  6. W. Feller, An Introduction to Probability Theory and Its Applications, volume 2, Wiley, 1971. Math Review link
  7. J.F. Le Gall and Y. Le Jan, Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses, Ann. Probab., 26:1407-1432, 1998. Math Review link
  8. J.F. Le Gall and Y. Le Jan, Branching processes in Lévy processes: The exploration process, Ann. Probab., 26:213-252, 1998. Math Review link
  9. T.E. Harris, First passage and recurrence distributions, Trans. Amer. Math. Soc, 73:471-486, 1974. Math Review link
  10. D.G. Kendall, Some problems in the theory of queues, J. Royal Statist. Soc., B 13:151-185, 1951. Math Review link
  11. V.F. Kolchin, Random Mappings, Optimisation Software, New York, 1986 (translation of Russian original). Math Review link
  12. V. Limic, A LIFO queue in heavy traffic, Technical report, UC San Diego, 1999. Preprint.
  13. N.U. Prabhu, Stochastic Storage Processes: Queues, Insurance Risk, Dams and Data Communication, Springer, Second edition, 1998. Math Review link
  14. M.I. Reiman, Some diffusion approximations with state space collapse, In Lecture Notes in Contr. and Inf. Sci., volume 60, pages 209-240. Springer, Berlin-New York, 1984. Math Review link
  15. M.I. Reiman, A multiclass feedback queue in heavy traffic, Advances in Applied Probability, 20:179-207, 1988. Math Review link
  16. R.J. Williams, Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse, Queueing systems: Theory and Applications, 30:27-88, 1998. Math Review link
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.