Perfect sampling for queues and network models

ABSTRACT

We review Propp and Wilson's [1996] CFTP algorithm and Wilson's [2000] ROCFTP algorithm. We then use these to construct perfect samplers for several queueing and network models: Poisson arrivals and exponential service times, several types of customers, and a trunk reservation protocol for accepting new customers; a similar protocol on a network switching model; a queue with a general arrival process; and a queue with both general arrivals and service times. Our samplers give effective ways to generate random samples from the steady-state distributions of these queues.

REFERENCES

• 1: Sigrún Andradóttir , Mehdi Hosseini-Nasab, Efficiency of Time Segmentation Parallel Simulation of Finite Markovian Queueing Networks, Operations Research, v.51 n.2, p.272-280, March 2003 [doi>10.1287/opre.51.2.272.12778]
• 2: Sigrún Andradóttir , Teunis J. Ott, Time-segmentation parallel simulation of networks of queues with loss or communication blocking, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.4, p.269-305, Oct. 1995 [doi>10.1145/226275.226276]
• 3: Feller, W. 1966. An Introduction to Probability Theory and its Applications, Vol. 2. John Wiley & Sons, Inc., New York.
• 4: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 5: Meng, X.-L. 2000. Towards a more general Propp-Wilson algorithm: Multistage backward coupling. In Proceedings of the Workshop on MCMC Methods, October 1998, N. Madras, Ed. Fields Institute, Toronto, 85--93.
• 6: Murdoch, D. J. and Green, P. J. 1998. Exact sampling from a continuous state space. Scandinavian J. Stat. 25, 483--502.
• 7: Duncan J. Murdoch , Jeffrey S. Rosenthal, Efficient use of exact samples, Statistics and Computing, v.10 n.3, p.237-243, July 2000 [doi>10.1023/A:1008991527785]
• 8: James Gary Propp , David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures & Algorithms, v.9 n.1-2, p.223-252, Aug./Sept. 1996
• 9: Keith W. Ross , Peter J. Hancock, Multiservice Loss Models for Broadband Telecommunication Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 10: Thorisson, H. 2000. Coupling, Stationarity, and Regeneration. Springer, Inc., New York.
• 11: David Bruce Wilson, How to couple from the past using a read-once source of randomness, Random Structures & Algorithms, v.16 n.1, p.85-113, Jan.1.2000 [doi>10.1002/(SICI)1098-2418(200001)16:1<85::AID-RSA6>3.0.CO;2-H]
• 12: Wolff, R. W. 1982. Poisson arrivals see time averages. Oper. Res. 30, 223--231.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

General Terms:
Algorithms

Keywords:
Coupling from the past, networks, perfect simulation, queues