Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-17T12:20:17.610Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect simulation of M/G/c queues

Part of: Probabilistic methods, simulation and stochastic differential equations Special processes Markov processes

Published online by Cambridge University Press:  21 March 2016

Stephen B. Connor  and
Wilfrid S. Kendall
Stephen B. Connor*
Affiliation:
University of York
Wilfrid S. Kendall*
Affiliation:
University of Warwick
*
∗ Postal address: Department of Mathematics, University of York, York YO10 5DD, UK. Email address: [email protected]
∗∗ Postal address: Department of Statistics, University of Warwick, Coventry CV4 7AL, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we describe a perfect simulation algorithm for the stable M/G/c queue. Sigman (2011) showed how to build a dominated coupling-from-the-past algorithm for perfect simulation of the super-stable M/G/c queue operating under first-come-first-served discipline. Sigman's method used a dominating process provided by the corresponding M/G/1 queue (using Wolff's sample path monotonicity, which applies when service durations are coupled in order of initiation of service). The method exploited the fact that the workload process for the M/G/1 queue remains the same under different queueing disciplines, in particular under the processor sharing discipline, for which a dynamic reversibility property holds. We generalise Sigman's construction to the stable case by comparing the M/G/c queue to a copy run under random assignment. This allows us to produce a naïve perfect simulation algorithm based on running the dominating process back to the time it first empties. We also construct a more efficient algorithm that uses sandwiching by lower and upper processes constructed as coupled M/G/c queues started respectively from the empty state and the state of the M/G/c queue under random assignment. A careful analysis shows that appropriate ordering relationships can still be maintained, so long as service durations continue to be coupled in order of initiation of service. We summarise statistical checks of simulation output, and demonstrate that the mean run-time is finite so long as the second moment of the service duration distribution is finite.

Keywords

Coalescencedominated coupling-from-the-pastdynamic reversibilityfirst-come-first-served disciplinefirst-in-first-out disciplineKiefer-Wolfowitz workload vectorpathwise dominationperfect simulationprocessor sharing disciplineM/G/c queuerandom assignment disciplinesandwichingstable queuestochastic orderingsuper-stable queue

MSC classification

Primary: 65C05: Monte Carlo methods
Secondary: 60K25: Queueing theory 60J05: Discrete-time Markov processes on general state spaces 68U20: Simulation
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 4 , December 2015 , pp. 1039 - 1063
Copyright
Copyright © Applied Probability Trust 2015 

References

Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
Beskos, A. and Roberts, G. O. (2005). Exact simulation of diffusions. Ann. Appl. Prob. 15, 2422–2444.CrossRefGoogle Scholar
Blanchet, J. and Dong, J. (2015). Perfect sampling for infinite server and loss systems. Adv. Appl. Prob. 47, 761–786.Google Scholar
Blanchet, J. and Wallwater, A. (2014). Exact sampling of stationary and time-reversed queues. Preprint. Available at http://arxiv.org/abs/1403.8117.Google Scholar
Borovkov, A. A. and Foss, S. G. (1992). Stochastically recursive sequences and their generalizations. Siberian Adv. Math. 2, 16–81.Google Scholar
Chen, X. and Blanchet, J. (2015). Steady-state simulation of reflected Brownian motion and related stochastic networks. To appear in Ann. Appl. Prob. 25, 3209–3250.Google Scholar
Connor, S. B. and Fort, G. (2009). State-dependent Foster–Lyapunov criteria for subgeometric convergence of Markov chains. Stoch. Proces. Appl. 119, 4176-4193.Google Scholar
Connor, S. B. and Kendall, W. S. (2007). Perfect simulation for a class of positive recurrent Markov chains. Ann. Appl. Prob. 17, 781–808, 1808–1810.CrossRefGoogle Scholar
Ferrari, P. A., Fernández, R. and Garcia, N. L. (2002). Perfect simulation for interacting point processes, loss networks and Ising models. Stoch. Process. Appl. 102, 63-88.Google Scholar
Foss, S. and Korshunov, D. (2012). On large delays in multi-server queues with heavy tails. Math. Operat. Res. 37, 201–218.Google Scholar
Grimmett, G. (1995). The stochastic random-cluster process and the uniqueness of random-cluster measures. Ann. Prob. 23, 1461–1510.Google Scholar
Gupta, V., Harchol-Balter, M., Dai, J. G. and Zwart, B. (2010). On the inapproximability of M/G/K: why two moments of job size distribution are not enough. Queueing Systems 64, 5–48.Google Scholar
Hou, Z. and Liu, Y. (2004). Explicit criteria for several types of ergodicity of the embedded M/G/1 and GI/M/n queues. J. Appl. Prob. 41, 778–790.Google Scholar
Kendall, W. S. (1998). Perfect simulation for the area-interaction point process. In Probability Towards 2000, Springer, New York, pp. 218–234.Google Scholar
Kendall, W. S. (2004). Geometric ergodicity and perfect simulation. Electron. Commun. Prob. 9, 140–151.CrossRefGoogle Scholar
Kendall, W. (2005). Notes on perfect simulation. In Markov Chain Monte Carlo, World Scientific, Hackensack, NJ, pp. 93–146.Google Scholar
Kendall, W. S. (2015). Coupling, local times, immersions. Bernoulli 21, 1014–1046.CrossRefGoogle Scholar
Kendall, W. S. and M⊘ller, J. (2000). Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. Appl. Prob. 32, 844–865.Google Scholar
Kiefer, J. and Wolfowitz, J. (1955). On the theory of queues with many servers. Trans. Amer. Math. Soc. 78, 1-18.Google Scholar
Loynes, R. M. (1962). The stability of a queue with non-independent interarrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
Meyn, S. and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press.Google Scholar
Mousavi, M. and Glynn, P. W. (2013). Exact simulation of non-stationary reflected Brownian motion. Preprint. Available at http://arxiv.org/abs/1312.6456.Google Scholar
Moyal, P. (2013). A pathwise comparison result for parallel queues. Preprint. Available at http://arxiv.org/abs/1301.6364.Google Scholar
Murdoch, D. J. and Takahara, G. (2006). Perfect sampling for queues and network models. ACM Trans. Model. Comput. Simul. 16, 76–92.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.Google Scholar
Ross, S. M. (1996). Stochastic Processes, 2nd edn. John Wiley, New York.Google Scholar
Shah, S. R. (2005). Perfection in conditioning and coverage. Doctoral thesis, Department of Statistics, University of Warwick.Google Scholar
Sigman, K. (2011). Exact simulation of the stationary distribution of the FIFO M/G/c queue. In New Frontiers in Applied Probability (J. Appl. Prob. Spec. Vol. 48A), Applied Probability Trust, Sheffield, pp. 209–213.Google Scholar
Sigman, K. (2012). Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for ρ < c . Queueing Systems 70, 37–43.Google Scholar
Sigman, K. (2013). Using the M/G1 queue under processor sharing for exact simulation of queues. Ann. Operat. Res. Available at http://dx.doi.org/10.1007/s10479-013-1408-2.Google Scholar
Wolff, R. W. (1977). An upper bound for multi-channel queues. J. Appl. Prob. 14, 884–888.Google Scholar
Wolff, R. W. (1987). Upper bounds on work in system for multichannel queues. J. Appl. Prob. 24, 547–551.Google Scholar