Perfect Sampling for Multiclass Closed Queueing Networks | SpringerLink
Skip to main content
Springer Nature Link
Log in

Perfect Sampling for Multiclass Closed Queueing Networks

  • Conference paper
  • First Online:
Quantitative Evaluation of Systems (QEST 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9259))

Included in the following conference series:

Abstract

In this paper we present an exact sampling method for multiclass closed queuing networks. We consider networks for which stationary distribution does not necessarily have a product form. The proposed method uses a compact representation of sets of states, that is used to derive a bounding chain with significantly lower complexity of one-step transition in the coupling from the past scheme. The coupling time of this bounding chain can be larger than the coupling time of the exact chain, but it is finite in expectation. Numerical experiments show that coupling time is close to that of the exact chain. Moreover, the running time of the proposed algorithm outperforms the classical algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Algorithm 1 is the variant of the CFTP algorithm from [17] that doubles the value of n at each iteration. In the case when all the states are considered, the basic CFTP algorithm can be used, but this choice has been made to simplify comparison with Algorithm 3 in Sect. 3.

References

  1. Asmussen, S., Glynn, P.W.: Stochastic simulation: algorithms and analysis. Springer, New York (2007)

    Google Scholar 

  2. Balsamo, S.: Queueing networks with blocking: analysis, solution algorithms and properties. In: Kouvatsos, D.D. (ed.) Next Generation Internet: Performance Evaluation and Applications. LNCS, vol. 5233, pp. 233–257. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  3. Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22, 248–260 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baynat, B., Dallery, Y.: A product-form approximation method for general closed queueing networks with several classes of customers. Perform. Eval. 24(3), 165–188 (1996)

    Article  MATH  Google Scholar 

  5. Bouillard, A., Busic, A., Rovetta, C.: Perfect sampling for multiclass closed queueing networks. hal-01159962. June 2015

    Google Scholar 

  6. Bouillard, A., Bušić, A., Rovetta, C.: Clones: closed queueing networks exact sampling. In: 8th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2014, ICST (2014)

    Google Scholar 

  7. Bouillard, A., Bušić, A., Rovetta, C.: Perfect sampling for closed queueing networks. Perform. Eval. 79, 146–159 (2014)

    Article  Google Scholar 

  8. Bušić, A., Vliegen, I., Scheller-Wolf, A.: Comparing Markov chains: aggregation and precedence relations applied to sets of states, with applications to assemble-to-order systems. Math. Oper. Res. 37(2), 259–287 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bušić, A., Gaujal, B., Perronnin, F.: Perfect sampling of networks with finite and infinite capacity queues. In: Al-Begain, K., Fiems, D., Vincent, J.-M. (eds.) ASMTA 2012. LNCS, vol. 7314, pp. 136–149. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  10. Bušić, A., Gaujal, B., Pin, F.: Perfect sampling of Markov chains with piecewise homogeneous events. Perform. Eval. 69(6), 247–266 (2012)

    Article  Google Scholar 

  11. Gordon, W., Newel, G.: Closed queueing systems with exponential servers. Oper. Res. 15(2), 254–265 (1967)

    Article  MATH  Google Scholar 

  12. Huber, M.: Perfect sampling using bounding chains. Ann. Appl. Probab. 14(2), 734–753 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kendall, W., Møller, J.: Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. Appl. Probab. 32(3), 844–865 (2000)

    Article  MATH  Google Scholar 

  14. Kijima, S., Matsui, T.: Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers. Ann. Oper. Res. 162(1), 35–55 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Levin, D., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times. American Mathematical Society, New York (2009)

    MATH  Google Scholar 

  16. Marie, R.: An approximate analytical method for general queueing networks. IEEE Trans. Softw. Eng. 5(5), 530–538 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  17. Propp, J.G., Wilson, D.B.: Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Algorithms 9(1–2), 223–252 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  18. Satyam, K., Krishnamurthy, A., Kamath, M.: Solving general multi-class closed queuing networks using parametric decomposition. Comput. Oper. Res. 40, 1777–1789 (2013)

    Article  MathSciNet  Google Scholar 

  19. Sigman, K.: Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for \(\rho <c\). Queueing Sys. 70(1), 37–43 (2012)

    Google Scholar 

  20. van Dijk, N.M.: Bounds and error bounds for queueing networks. Ann. Oper. Res. 79, 295–319 (1998)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The work presented in this paper has been carried out at LINCS (www.lincs.fr) and has been founded by the French National Research Agency grant ANR-12-MONU-0019.

Author information

Authors and Affiliations

  1. École Normale Supérieure and Inria Paris-Rocquencourt, Paris, France

    Anne Bouillard, Ana Bušić & Christelle Rovetta

Authors
  1. Anne Bouillard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ana Bušić
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christelle Rovetta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christelle Rovetta .

Editor information

Editors and Affiliations

  1. Universidad de Zaragoza, Zaragoza, Spain

    Javier Campos

  2. University of Twente, Enschede, The Netherlands

    Boudewijn R. Haverkort

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Bouillard, A., Bušić, A., Rovetta, C. (2015). Perfect Sampling for Multiclass Closed Queueing Networks. In: Campos, J., Haverkort, B. (eds) Quantitative Evaluation of Systems. QEST 2015. Lecture Notes in Computer Science(), vol 9259. Springer, Cham. https://doi.org/10.1007/978-3-319-22264-6_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-22264-6_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-22263-9

  • Online ISBN: 978-3-319-22264-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation