Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Stochastic grey-box modeling of queueing systems: fitting birth-and-death processes to data

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

This paper explores grey-box modeling of queueing systems. A stationary birth-and-death (BD) process model is fitted to a segment of the sample path of the number in the system in the usual way. The birth (death) rates in each state are estimated by the observed number of arrivals (departures) in that state divided by the total time spent in that state. Under minor regularity conditions, if the queue length (number in the system) has a proper limiting steady-state distribution, then the fitted BD process has that same steady-state distribution asymptotically as the sample size increases, even if the actual queue-length process is not nearly a BD process. However, the transient behavior may be very different. We investigate what we can learn about the actual queueing system from the fitted BD process. Here we consider the standard \(GI/GI/s\) queueing model with \(s\) servers, unlimited waiting room and general independent, non-exponential, interarrival-time and service-time distributions. For heavily loaded \(s\)-server models, we find that the long-term transient behavior of the original process, as partially characterized by mean first passage times, can be approximated by a deterministic time transformation of the fitted BD process, exploiting the heavy-traffic characterization of the variability.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Abate, J., Choudhury, G.L., Whitt, W.: Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Syst. 16, 311–338 (1994)

    Article  Google Scholar 

  2. Abate, J., Whitt, W.: A heavy-traffic expansion for the asymptotic decay rates of tail probabilities in multi-channel queues. Op. Res. Lett. 15, 223–230 (1994)

    Article  Google Scholar 

  3. Armony, M., Israelit, S., Mandelbaum, A., Marmor, Y., Tseytlin, Y., Yom-Tov, G.: Patient flow in hospitals: a data-based queueing-science perspective. New York University. Available at http://ie.technion.ac.il/serveng/References/ (2014). Accessed 19 Oct 2014

  4. Bhat, U.N., Miller, G.K., Rao, S.S.: Statistical analysis of queueing systems. In: Dshalalow, J.H. (ed.) Frontiers in Queueing Theory, pp. 351–394. CRC Press, Boca Raton, FL (1997)

    Google Scholar 

  5. Billingsley, P.: Statistical Inference for Markov Processes. University of Chicago Press, Chicago (1961)

    Google Scholar 

  6. Bohlin, T.: Practical Grey-Box Process Identification. Springer, London (2006)

    Google Scholar 

  7. Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S., Zhao, L.: Statistical analysis of a telephone call center: a queueing-science perspective. J. Am. Stat. Assoc. 100, 36–50 (2005)

    Article  Google Scholar 

  8. Buzen, J.: Fundamental operational laws of computer system performance. Acta Inform. 14, 167–182 (1976)

    Article  Google Scholar 

  9. Buzen, J.: Operational analysis: an alternative to stochastic modeling. In: Ferarri, D. (ed.) Performance of Computer Installations, pp. 175–194. North Holland, Amsterdam (1978)

    Google Scholar 

  10. Cerbone, G., Ricciardi, L.M., Sacerdote, L.: Mean, variance and the skewness of the first passage time for the Ornstein–Uhlenbeck process. Cybern. Syst. 14(2), 395–429 (1981)

    Article  Google Scholar 

  11. Choudhury, G.L., Whitt, W.: Heavy-traffic asymptotic expansions for the asymptotic decay rates in the \(BMAP/G/1\) queue. Stoch. Models 10(2), 453–498 (1994)

    Article  Google Scholar 

  12. Cohen, J.W.: Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Probab. 10(2), 343–353 (1973)

    Article  Google Scholar 

  13. Cooper, R.B.: Introduction to Queueing Theory, 2nd edn. North Holland, Amsterdam (1982)

    Google Scholar 

  14. Cox, D.R., Lewis, P.A.W.: The Statistical Analysis of Series of Events. Methuen, London (1966)

    Book  Google Scholar 

  15. Denning, P.J., Buzen, P.J.: The operational analysis of queueing network models. Comput. Surv. 10, 225–261 (1978)

    Article  Google Scholar 

  16. Dong, J., Whitt, W.: Stationary birth-and-death processes fit to queues with periodic arrival rate functions. In preparation (2014)

  17. Duffield, N.G., Whitt, W.: Control and recovery from rare congestion events in a large multi-server system. Queueing Syst. 26, 69–104 (1997)

    Article  Google Scholar 

  18. Eick, S.G., Massey, W.A., Whitt, W.: The physics of the \(M_t/G/\infty \) queue. Oper. Res. 41, 731–742 (1993)

    Article  Google Scholar 

  19. El-Taha, M., Stidham, S.: Sample-Path Analysis of Queueing Systems. Kluwer, Boston (1999)

    Book  Google Scholar 

  20. Fendick, K.W., Whitt, W.: Measurements and approximations to describe the offered traffic and predict the average workload in a single-server queue. Proc. IEEE 71(1), 171–194 (1989)

    Article  Google Scholar 

  21. Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Op. Res. 29(3), 567–588 (1981)

    Article  Google Scholar 

  22. Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning, 2nd edn. Springer, New York (2009)

    Book  Google Scholar 

  23. Iglehart, D.L.: Limit diffusion approximations for the many-server queue and the repairman problem. J. Appl. Probab. 2, 429–441 (1965)

    Article  Google Scholar 

  24. Iglehart, D.L., Whitt, W.: Multiple channel queues in heavy traffic. I. Adv. Appl. Probab. 2(1), 150–177 (1970)

    Article  Google Scholar 

  25. Iglehart, D.L., Whitt, W.: Multiple channel queues in heavy traffic, II: sequences, networks and batches. Adv. Appl. Probab. 2(2), 355–369 (1970)

    Article  Google Scholar 

  26. Keiding, N.: Maximum likelihood estimation in the birth-and-death process. Ann. Stat. 3, 363–372 (1975)

    Article  Google Scholar 

  27. Kim, S., Whitt, W.: Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manuf. Serv. Op. Manag. 16(3), 464–480 (2014)

    Google Scholar 

  28. Kim, S., Whitt, W.: Choosing arrival process models for service systems: tests of a nonhomogeneous Poisson process. Nav. Res. Logist. 17, 307–318 (2014)

    Google Scholar 

  29. Kristensen, N.R., Madsen, H., Jorgensen, S.B.: Parameter estimation in stochastic grey-box models. Automatica 40(2), 225–237 (2004)

    Article  Google Scholar 

  30. Pakes, A.G.: On the tails of waiting-time distributions. J. Appl. Probab. 12, 555–564 (1975)

    Article  Google Scholar 

  31. Pang, G., Talreja, R., Whitt, W.: Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4, 193–267 (2007)

    Article  Google Scholar 

  32. Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65, 325–364 (2010)

    Article  Google Scholar 

  33. Pang, G., Whitt, W.: The impact of dependent service times on large-scale service systems. Manuf. Serv. Op. Manag. 14(2), 262–278 (2012)

    Google Scholar 

  34. Pang, G., Whitt, W.: Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73(2), 119–146 (2013)

    Article  Google Scholar 

  35. Puhalskii, A.A., Reiman, M.I.: The multiclass \(GI/PH/N\) queue in the Halfin–Whitt regime. Adv. Appl. Probab. 32, 564–595 (2000)

    Article  Google Scholar 

  36. Ross, J.V., Taimre, T., Pollett, P.K.: Estimation for queues from queue-length data. Queueing Syst. 55, 131–138 (2007)

    Article  Google Scholar 

  37. Ross, S.M.: Stochastic Processes, 2nd edn. Wiley, New York (1996)

  38. Sigman, K.: Stationary Marked Point Processes: An Intuitive Approach. Chapman and Hall/CRC, New York (1995)

    Google Scholar 

  39. Sriram, K., Whitt, W.: Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE J. Sel. Areas Commun. SAC–4(6), 833–846 (1986)

    Article  Google Scholar 

  40. Stone, C.J.: Limit theorems for random walks, birth and death processes and diffusion processes. Ill. J. Math. 4, 638–660 (1963)

    Google Scholar 

  41. Thomas, M.U.: Some mean first-passage time approximations for the Ornstein–Uhlenbeck process. J. Appl. Probab. 12(3), 600–604 (1975)

    Article  Google Scholar 

  42. Vasilakis, C., Marshall, A.H.: Modelling nationwide hospital length of stay: opening the black box. J. Op. Res. Soc. 56(3), 862–869 (2005)

    Article  Google Scholar 

  43. Whitt, W.: Comparing counting processes and queues. Adv. Appl. Probab. 13, 207–220 (1981)

    Article  Google Scholar 

  44. Whitt, W.: Approximating a point process by a renewal process: two basic methods. Op. Res. 30, 125–147 (1982)

    Article  Google Scholar 

  45. Whitt, W.: On the heavy-traffic limit theorem for \(GI/G/\infty \) queue. Adv. Appl. Probab. 14(1), 171–190 (1982)

    Article  Google Scholar 

  46. Whitt, W.: Untold horrors of the waiting room. What the equilibrium distribution will never tell about the queue-length process. Manag. Sci. 29(4), 395–408 (1983)

    Article  Google Scholar 

  47. Whitt, W.: Departures from a queue with many busy servers. Math. Op. Res. 9(4), 534–544 (1984)

    Article  Google Scholar 

  48. Whitt, W.: Planning queueing simulations. Manag. Sci. 35(11), 1341–1366 (1989)

    Article  Google Scholar 

  49. Whitt, W.: Understanding the efficiency of multi-server service systems. Manag. Sci. 38(5), 708–723 (1992)

    Article  Google Scholar 

  50. Whitt, W.: Stochastic-Process Limits. Springer, New York (2002)

    Google Scholar 

  51. Whitt, W.: A diffusion approximation for the \(G/GI/n/m\) queue. Op. Res. 52(6), 922–941 (2004)

    Article  Google Scholar 

  52. Whitt, W.: Engineering solution of a basic call-center model. Manag. Sci. 51, 221–235 (2005)

    Article  Google Scholar 

  53. Whitt, W.: Staffing a call center with uncertain arrival rate and absenteeism. Prod. Op. Manag. 15(1), 88–102 (2006)

    Google Scholar 

  54. Whitt, W.: Fitting birth-and-death queueing models to data. Stat. Probab. Lett. 82, 998–1004 (2012)

    Article  Google Scholar 

  55. Whitt, W.: Heavy-traffic limits for queues with periodic arrival rates. Op. Res. Lett. 42, 458–461 (2014)

    Article  Google Scholar 

  56. Whitt, W.: The steady-state distribution of the \(M_t/M/\infty \) queue with a sinusoidal arrival rate function. Op. Res. Lett. 42, 311–318 (2014)

    Article  Google Scholar 

  57. Wolff, R.W.: Problems for statistical inference for birth and death queueing models. Op. Res. 13, 343–357 (1965)

    Article  Google Scholar 

  58. Wolff, R.W.: The effect of service-time regularity on system performance. In: Chandy, K.M., Reiser, M. (eds.) Comput. Perform., pp. 297–304. North-Holland, Amsterdam (1977)

    Google Scholar 

  59. Yin, L., Uttamchandani, S., Katz, R.: An empirical exploration of black-box performance models for storage systems. In: Proceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, MASCOTS 2006. IEEE, pp. 433–440 (2006)

Download references

Acknowledgments

This research was begun while the first author was an undergraduate in the IEOR Department at Columbia University. The second author acknowledges support from NSF Grants CMMI 1066372 and 1265070.

Author information

Authors and Affiliations

  1. School of Operations Research and Information Engineering, Cornell University, 287 Rhodes Hall, Ithaca, NY, 14850, USA

    James Dong

  2. Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, 10027, USA

    Ward Whitt

Authors
  1. James Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ward Whitt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ward Whitt.

Appendix: Additional simulation results for the \(GI/GI/1\) queue

Appendix: Additional simulation results for the \(GI/GI/1\) queue

We now supplement Fig. 1 and Table 1 in Sect. 2.1, which display estimated birth rates \(\bar{\lambda }_k\) and estimated death rates \(\bar{\mu }_k\) for several \(GI/GI/1\) queues with traffic intensity \(\rho = 0.8\). Here Fig. 6 and Table 6 show the corresponding estimates of birth and death rates for \(\rho = 0.9\).

Fig. 6
figure 6

Fitted birth rates \(\bar{\lambda }_k\) (left) and death rates \(\bar{\mu }_k\) (right) for nine \(GI/GI/1\) models with \(\rho = \lambda = 0.9\) and \(\mu = 1\)

Full size image
Table 6 Estimates of the asymptotic fitted birth rate \(\bar{\lambda }\), death rate \(\bar{\mu }\), traffic intensity \(\bar{\rho }\) and speed ratio \(\bar{\omega }\) via (2.2) for the nine \(GI/GI/1\) models with \(\rho =0.9\) in Fig. 6
Full size table

As in Sect. 2.1, we estimated the rates from \(30\) independent replications of \(1\) million customers. This large sample size is sufficient for \(95\,\%\) confidence intervals of the state-dependent rates to be within \(1\,\%\) of the rates for states \(k\) with steady-state probability \(\alpha _k \ge 0.01\).

Paralleling Fig. 4 in Sect. 3.3, we also estimated the steady-state queue-length probabilities \(\alpha _k\) and their logarithms. The statistical precision is less with the higher traffic intensity \(\rho = 0.9\) instead of \(\rho = 0.8\), as expected from [48]. To illustrate, the estimate of \(\alpha _{10}\) in the \(H_2/M/1\) model with \(\rho = 0.9\) was \(\bar{\alpha }_{10} = 0.03251\). The sample standard deviation from the \(30\) replications was \(0.000351\). Using the Student \(t\) distribution with \(29\) degrees of freedom, the \(t\) value for a two-sided \(95\,\%\) confidence interval is \(2.045\). Thus, the halfwidth of the \(95\,\%\) confidence interval is \((2.045 \times 0.000351)/\sqrt{30} = 0.37340 \times 0.000351 = 0.000131\), which is less than \(0.5\,\%\) of the estimated value (Fig. 7).

Fig. 7
figure 7

Estimated steady-state probabilities \(\bar{\alpha }_k\) (left) and their logarithms \(\log _\mathrm{e}{\bar{\alpha }_k}\) (right) for nine \(GI/GI/1\) models with \(\rho = \lambda = 0.9\) and \(\mu = 1\)

Full size image

This is contrasted with the case with traffic intensity \(\rho = 0.8\). The estimate of \(\alpha _{10}\) in the \(H_2(2)/M/1\) model with \(\rho = 0.8\) was \(\bar{\alpha }_{10} = 0.02839\). The sample standard deviation from the \(30\) replications was \(0.000282\). Using the procedure as above, the halfwidth of the \(95\,\%\) confidence interval was found to be \(0.000105\), which is less than \(0.4\,\%\) of the estimated value, about \(0.37\,\%\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dong, J., Whitt, W. Stochastic grey-box modeling of queueing systems: fitting birth-and-death processes to data. Queueing Syst 79, 391–426 (2015). https://doi.org/10.1007/s11134-014-9429-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-014-9429-3

Keywords

Mathematics Subject Classification

Search

Navigation