A spectral approach to compute performance measures in a correlated single server queue

ABSTRACT

The coupling matrix was introduced in [8] to compute the performance measures of a PH/PH/1 single server queue. This matrix was extended in [1, 2] to include arrival and service processes that are possibly serially correlated processes, although the service process remains independent of the arrival process and all marginal distributions are matrix exponential, and this current paper is an extended abstract of [2]. The coupling matrix is constructed from the arrival and the service distributions without any computational effort, and the performance measures (such as waiting times and queue length distributions) are derived directly from its spectrum.

REFERENCES

• 1: J. Kumaran, K. Mitchell, and A. van de Liefvoort, "An Efficient Solution to the Waiting Time Distribution in a Correlated Single Server Queue," to appear in ITC 19, (Beijing, China).
• 2: J. Kumaran, K. Mitchell, and A. van de Liefvoort, "Steady State solutions for the correlated G/G/I queue using the Spectral Decomposition of the Coupling matrix" Submitted, available as Technical Report http://j.web.umkc.edu/jk343/papers/wait_11_24.pdf.
• 3: L. Lipsky, Queueing Theory: A Linear Algebraic Approach. New York: MacMillan, 1992.
• 4: L. Lipsky, P. Fiorini, W-J. Hsin and A. van de Liefvoort "Auto-Correlation of Lag-κ For Customers Departing From Semi-Markov Processes", Technical Report 342/04/95, Institut für Informatik, Technische Universität München, February 1995
• 5: M. Neuts, "Models based on the Markovian Arrival Process" IEICE Trans Comm, Vol E75-B, no 12, 1992.
• 6: B. Sengupta, "The semi-Markovian queue: Theory and applications," Stochastic Models, vol. 6, no. 3, pp. 383--414, 1990.
• 7: H. Tran, T. Do, "Computational aspects for steady state analysis of QBD processes," Per. Pol. Elec. Eng., vol. 44 no. 2, pp. 179--200, 2000.
• 8: A. van de Liefvoort, "The waiting time distribution and its moments of the PH/PH/1 queue," Operations Research Letters, vol. 9, no. 4, pp. 261--269, 1990.
• 9: M. L. Chaudhry , Manju Agarwal , J. G. C. Templeton, Exact and approximate numerical solutions of steady-state distributions arising in the queue GI/G/1, Queueing Systems: Theory and Applications, v.10 n.1-2, p.105-152, Jan. 1992 [doi>10.1007/BF01158522]
• 10: A. van de Liefvoort and Armin Heindl, "Approximating Matrix-Exponential Distributions by Global Randomization", Stochastic Models, vol. 21, no. 2-3, pp. 1--25, 2005.
• 11: W. Smith, "Distribution of Queueing Times", Proc. Cambridge Philos. Soc., vol. 49, pp 449--461, 1953.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.5 Servers

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Design, Performance, Reliability, Theory