Abstract
We introduce the first class of perfect sampling algorithms for the steady-state distribution of multi-server queues with general interarrival time and service time distributions. Our algorithm is built on the classical dominated coupling from the past protocol. In particular, we use a coupled multi-server vacation system as the upper bound process and develop an algorithm to simulate the vacation system backward in time from stationarity at time zero. The algorithm has finite expected termination time with mild moment assumptions on the interarrival time and service time distributions.
Similar content being viewed by others
References
Asmussen, S.: Applied Probability and Queues, 2nd edn. Springer, Berlin (2003)
Asmussen, S., Glynn, P., Thorisson, H.: Stationarity detection in the initial transient problem. ACM Trans. Model. Comput. Simul. (TOMACS) 2(2), 130–157 (1992)
Blanchet, J., Chen, X.: Steady-state simulation of reflected Brownian motion and related stochastic networks (2013). arXiv preprint arXiv:1202.2062
Blanchet, J., Dong, J.: Perfect sampling for infinite server and loss systems. Adv. Appl. Probab. 47(3), 761–786 (2014). Forthcoming
Blanchet, J., Sigman, K.: On exact sampling of stochastic perpetuities. J. Appl. Probab. 48(A), 165–182 (2011)
Blanchet, J., Wallwater, A.: Exact sampling for the stationary and time-reversed queues. ACM Trans. Model. Comput. Simul. (TOMACS) 25(4), 26:1–26:27 (2015)
Chen, H., Yao, D.: Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization, vol. 46. Springer, Berlin (2013)
Connor, S., Kendall, W.: Perfect simulation for a class of positive recurrent Markov chains. Ann. Appl. Probab. 17(3), 781–808 (2007)
Connor, S., Kendall, W.: Perfect simulation of M/G/c queues. Adv. Appl. Probab. 47(4), 1039–1063 (2015)
Corcoran, J., Tweedie, R.: Perfect sampling of ergodic Harris chains. Ann. Appl. Probab. 11(2), 438–451 (2001)
Ensor, K., Glynn, P.: Simulating the maximum of a random walk. J. Stat. Plan. Inference 85, 127–135 (2000)
Foss, S.: On the approximation of multichannel service systems. Sibirsk. Mat. Zh. 21(6), 132–140 (1980)
Foss, S., Chernova, N.: On optimality of the FCFS discipline in multiserver queueing systems and networks. Sib. Math. J. 42(2), 372–385 (2001)
Foss, S., Konstantopoulos, T.: Lyapunov function methods. Lecture Notes. http://www2.math.uu.se/~takis/L/StabLDC06/notes/SS_LYAPUNOV.pdf (2006)
Foss, S., Tweedie, R.: Perfect simulation and backward coupling. Stoch. Models 14, 187–203 (1998)
Garmarnik, D., Goldberg, D.: Steady-state GI/GI/n queue in the Halfin–Whitt regime. Ann. Appl. Probab. 23, 2382–2419 (2013)
Hillier, F.S., Lo, F.D.: Tables for multiple-server queueing systems involving Erlang distributions. Tech. Rep. 31, Department of Operations Research, Stanford University (1971)
Kelly, F.: Reversibility and Stochastic Networks, vol. 40. Wiley, Chichester (1979)
Kendall, W.: Perfect simulation for the area-interaction point process. In: Accardi, L., Heyde, C.C. (eds.) Probability towards 2000, pp. 218–234. Springer, New York (1998)
Kendall, W.: Geometric ergodicity and perfect simulation. Electron. Comm. Probab. 9, 140–151 (2004)
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)
Liu, Z., Nain, P., Towsley, D.: Sample path methods in the control of queues. Queueing Syst. 21(1–2), 293–335 (1995)
Propp, J., Wilson, D.: Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Alg. 9, 223–252 (1996)
Rubinstein, R., Kroese, D.: Simulation and the Monte Carlo method, vol. 707. Wiley, New York (2011)
Sigman, K.: Exact simulation of the stationary distribution of the FIFO M/G/c queue. J. Appl. Probab. 48A, 209–216 (2011)
Sigman, K.: Exact sampling of the stationary distribution of the FIFO M/G/c queue: the general case for \(\rho <c\). Queueing Syst. 70, 37–43 (2012)
Wolff, R.: An upper bound for multi-channel queues. J. Appl. Probab. 14, 884–888 (1977)
Author information
Authors and Affiliations
Corresponding author
Additional information
Support from NSF through the Grants CMMI-1538217, DMS-1320550 and DMS-1720433 is gratefully acknowledged.
Appendix: A list of selected notation
Appendix: A list of selected notation
Notation | Meaning |
---|---|
\(A_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Interarrival time between the arrivals at \(T^0_n\) and \(T^{0,+}_n\) (Sect. 2.1) |
\(D_n^0:n\in {\mathbb {Z}}\backslash \{0\}\) | Waiting time of the customer arriving at \(T^0_n\) in the vacation system (Sect. 2.1.2) |
\(E_u(t;z):t\ge 0\) | Time elapsed since previous arrival at time \(u+t\) when the time elapsed since previous arrival at time u is the corresponding subvector of z, i.e., e (Sect. 2.2.1) |
\(i(n):n\in {\mathbb {Z}}\backslash \{0\}\) | Label of the server who serves the customer arriving at \(T^0_n\) (Sect. 2.1.2) |
\(M(t):t\ge 0\) | Running time maximum of process \(\{X(s):s\ge t\}\) (Sect. 4) |
\(N^0_u(t):t\ge 0\) | Number of arrivals during \([u,u+t]\) (Sect. 2.1) |
\(N^0(t)\) | Number of arrivals during [0, t] if \(t\ge 0\) or in [t, 0] if \(t<0\) (Sect. 2.1) |
\(N^i_u(t):t\ge 0\) | Number of activities initiated by server i during \([u,u+t]\) (Sect. 2.1) |
\(N^i(t)\) | Number of activities initiated by server i during [0, t] if \(t\ge 0\) or [t, 0] if \(t<0\) (Sect. 2.1) |
\(Q_u(t;z):t\ge 0\) | Number of people waiting in queue at time \(u+t\) of a GI/GI/c queue that starts at time u and is initialized with z (Sect. 2.2.1) |
\(Q_v(t)\) | Number of people waiting in queue in stationary vacation system at time t (Sect. 2.1.1) |
\(R_u(t;z):t\ge 0\) | Ordered (non-decreasing) remaining service times of all c servers at time \(u+t\) of a GI/GI/c queue that starts at time u and is initialized with z (Sect. 2.2.1) |
\(\{S^{(0)}_n:n\ge 0\}\) | Random walk with negative drift associated with the arrival renewal process (Sect. 4) |
\(\{S^{(i)}_n:n\ge 0\}\) | Random walk with negative drift associated with the activity renewal process of server i (Sect. 4) |
\(T^0_n:n\in {\mathbb {Z}}\backslash \{0\}\) | n-th (\((-n)\)-th) arrival time counting forward (backward) in time from time 0 (Sect. 2.1) |
\(T^{0,+}_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Next arrival time after \(T^0_n\) (Sect. 2.1) |
\(T^{0,-}_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Previous arrival time before \(T^0_n\) (Sect. 2.1) |
\(T^i_n:n\in {\mathbb {Z}}\backslash \{0\}\) | n-th (\((-n)\)-th) activity initiation time of server i counting forward (backward) in time from time 0 (Sect. 2.1) |
\(T^{i,+}_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Next activity initiation time of server i after \(T^i_n\) (Sect. 2.1) |
\(T^{i,-}_n:n\ge {\mathbb {Z}}\backslash \{0\}\) | Previous activity initiation time of server i before \(T^i_n\) (Sect. 2.1) |
\(U^0(t)\) | Time until next arrival from time t (Sect. 2.2.2) |
\(U^i(t)\) | Time until next activity initiated by server i from time t (Sect. 2.2.2) |
U(t) | c-dimensional vector \(\left( U^1(t),\ldots ,U^c(t)\right) ^T\) (Sect. 2.2.2) |
\(V_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Service time of the customer who arrives at \(T^0_n\) (Sect. 2.1.1) |
\(V^i_n:n\in {\mathbb {Z}}\backslash \{0\}\) | Length of the activity of server i that is initiated at \(T^i_n\) (Sect. 2.1) |
\(W(n):n\in {\mathbb {Z}}\backslash \{0\}\) | Kiefer–Wolfowitz workload vector at time \(T^0_n\) of a stationary GI/GI/c queue (Sect. 2.2.1) |
\(W_k\left( T_n^0;w\right) \): \(n\ge k\) and \(n,k\in {\mathbb {Z}}\backslash \{0\}\) | Kiefer–Wolfowitz workload vector at time \(T^0_n\) of a GI/GI/c queue which has its workload vector at time \(T^0_k\) being w (Sect. 2.2.1) |
\(W_v(n):n\in {\mathbb {Z}}\backslash \{0\}\) | Analog Kiefer–Wolfowitz workload vector at time \(T^0_n\) of the stationary vacation system (Sect. 2.2.2) |
\(W_v(n+):n\in {\mathbb {Z}}\backslash \{0\}\) | Analog Kiefer–Wolfowitz workload vector at time \(T^{0,+}_n\) of the stationary vacation system (Sect. 2.2.2) |
X(t) | \(X_0(t)\) if \(t\ge 0\) or \(X_t(-t)\) if \(t<0\) (Sect. 2.1.1) |
\(X_u(t):t\ge 0\) | \(N^0_u(t)-\sum _{i=1}^cN^i_u(t)\) (Sect. 2.1.1) |
Z(t) | State vector of a stationary GI/GI/c queue at time t |
\(Z_u(t;z):t\ge 0\) | State vector at time \(u+t\) of a GI/GI/c queue that starts at time u and is initialized with z (Sect. 2.2.1) |
\(\sigma ^i_u(t):t\ge 0\) | Number of service initiations by server i during \([u,u+t]\) (Sect. 2.1.2) |
\(\varPhi _j^i:j\ge 0,0\le i\le c\) | j-th downward “milestone” of random walk \(\{S^{(i)}_n:n\ge 0\}\) (Sect. 4) |
\(\varUpsilon _j^i:j\ge 0,0\le i\le c\) | j-th upward “milestone” of random walk \(\{S^{(i)}_n:n\ge 0\}\) (Sect. 4) |
Rights and permissions
About this article
Cite this article
Blanchet, J., Dong, J. & Pei, Y. Perfect sampling of GI/GI/c queues. Queueing Syst 90, 1–33 (2018). https://doi.org/10.1007/s11134-018-9573-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-018-9573-2