skip to main content
article

A recursive analysis technique for multi-dimensionally infinite Markov chains

Published: 01 September 2004 Publication History

Abstract

Performance analysis of multiserver systems with multiple classes of jobs often has a common source of difficulty: the state space needed to capture the system behavior grows infinitely in multiple dimensions. For example, consider two processors, each serving its own M/M/1 queue, where one of the processors (the "donor") can help the other processor (the "beneficiary") with its jobs, during times when the donor processor is idle [5, 16] or when some threshold conditions are met [14, 15]. Since the behavior of beneficiary jobs depends on the number of donor jobs in system, performance analysis of beneficiary jobs involves a two dimensionally infinite (2D-infinite) state space, where one dimension corresponds to the number of beneficiary jobs and the other dimension corresponds to the number of donor jobs. Another example is an M/M/2 queue with two priority classes, where high priority jobs have preemptive priority over low priority jobs (see for example [1, 3, 4, 8, 10, 11, 12, 17] and references therein). Since the behavior of low priority jobs depends on the number of high priority jobs in system, performance analysis of low priority jobs involves 2D-infinite state space, where each dimension corresponds to the number of each class of jobs in system. As we will see, when there are <i>m</i> priority classes, performance analysis of the lowest priority classes involves <i>m</i> dimensionally infinite state space.

References

[1]
A. Bondi and J. Buzen. The response times of priority classes under preemptive resume in M/G/m queues. In ACM Sigmetrics, pages 195--201, August 1984.
[2]
J. Cohen and O. Boxma. Boundary Value Problems in Queueing System Analysis. North-Holland Publ. Cy., 1983.
[3]
G. Fayolle, P. King, and I. Mitrani. The solution of certain two-dimensional markov models. Advances in Applied Probability, 14:295--308, 1982.
[4]
H. Gail, S. Hantler, and B. Taylor. On a preemptive Markovian queues with multiple servers and two priority classes. Mathematics of Operations Research, 17:365--391, 1992.
[5]
L. Green. A queueing system with general use and limited use servers. Operations Research, 33(1): 168--182, 1985.
[6]
M. Harchol-Balter, C. Li, T. Osogami, A. Scheller-Wolf, and M. Squillante. Task assignment with cycle stealing under central queue. In Proceedings of The 23rd International Conference on Distributed Computing Systems (ICDCS 2003), pages 628--637, May 2003.
[7]
M. Harchol-Balter, C. Li, T. Osogami, A. Scheller-Wolf, and M. Squillante. Task assignment with cycle stealing under immediate dispatch. In Proceedings of the ACM SPAA, pages 274--285, June 2003.
[8]
E. Kao and K. Narayanan. Modeling a multiprocessor system with preemptive priorities. Management Science, 2:185--97, 1991.
[9]
G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM, Philadelphia, 1999.
[10]
D. Miller. Steady-state algorithmic analysis of M/M/c two-priority queues with heterogeneous servers. In R. L. Disney and T. J. Ott, editors, Applied probability - Computer science, The Interface, volume II, pages 207--222. Birkhauser, 1992.
[11]
I. Mitrani and P. King. Multiprocessor systems with preemptive priorities. Performance Evaluation, 1:118--125, 1981.
[12]
P. Nain. On a generalization of the preemptive resume priority queue. Advances in Applied Probability, 18:255--273, 1986.
[13]
M. Neuts. Moment formulas for the Markov renewal branching process. Advances in Applied Probabilities, 8:690--711, 1978.
[14]
T. Osogami, M. Harchol-Balter, and A. Scheller-Wolf. Analysis of cycle stealing with switching cost. In Proceedings of the ACM SIGMETRICS, pages 184--195, June 2003.
[15]
M. Squillante, C. Xia, D. Yao, and L. Zhang. Threshold-based priority policies for parallel-server systems with affinity scheduling. In Proceedings of the IEEE American Control Conference, pages 2992--2999, June 2001.
[16]
D. Stanford and W. Grassmann. Bilingual server call centers. In D. McDonald and S. Turner, editors, Analysis of Communication Networks: Call Centers, Traffic and Performance. American Mathematical Society, 2000.
[17]
A. Wierman, T. Osogami, M. Harchol-Balter, and A. Scheller-Wolf. Analyzing the effect of prioritized background tasks in multiserver systems. Technical Report CMU-CS-03--213, School of Computer Science, Carnegie Mellon University, 2004.

Cited By

View all
  • (2010)Network layered priority mapping theoryScience China Information Sciences10.1007/s11432-010-4047-053:9(1713-1726)Online publication date: 5-Sep-2010
  • (2008)User-perceived QoS mechanism under SCTP/IPv6Proceedings of the International Conference on Mobile Technology, Applications, and Systems10.1145/1506270.1506382(1-7)Online publication date: 10-Sep-2008
  • (2008)Queuing Analysis of Priority Multi-Connection and Multi-Path Architecture2008 4th International Conference on Wireless Communications, Networking and Mobile Computing10.1109/WiCom.2008.1039(1-4)Online publication date: Oct-2008
  • Show More Cited By
  1. A recursive analysis technique for multi-dimensionally infinite Markov chains

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGMETRICS Performance Evaluation Review
    ACM SIGMETRICS Performance Evaluation Review  Volume 32, Issue 2
    September 2004
    53 pages
    ISSN:0163-5999
    DOI:10.1145/1035334
    Issue’s Table of Contents

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 September 2004
    Published in SIGMETRICS Volume 32, Issue 2

    Check for updates

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 03 Mar 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2010)Network layered priority mapping theoryScience China Information Sciences10.1007/s11432-010-4047-053:9(1713-1726)Online publication date: 5-Sep-2010
    • (2008)User-perceived QoS mechanism under SCTP/IPv6Proceedings of the International Conference on Mobile Technology, Applications, and Systems10.1145/1506270.1506382(1-7)Online publication date: 10-Sep-2008
    • (2008)Queuing Analysis of Priority Multi-Connection and Multi-Path Architecture2008 4th International Conference on Wireless Communications, Networking and Mobile Computing10.1109/WiCom.2008.1039(1-4)Online publication date: Oct-2008
    • (2006)Performance analysis of concurrent PCOs in TTCN-3Proceedings of the 18th IFIP TC6/WG6.1 international conference on Testing of Communicating Systems10.1007/11754008_10(149-160)Online publication date: 16-May-2006

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media