Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T13:16:36.051Z Has data issue: false hasContentIssue false
  • English
  • Français

Transient analytical solution of M/D/1/N queues

Part of: Special processes Computer system organization

Published online by Cambridge University Press:  14 July 2016

Jean-Marie Garcia ,
Olivier Brun  and
David Gauchard
Jean-Marie Garcia*
Affiliation:
LAAS-CNRS
Olivier Brun*
Affiliation:
LAAS-CNRS
David Gauchard*
Affiliation:
LAAS-CNRS
*
∗ Postal address: Laboratoire d’Analyse et d’Architecture des Systèmes du CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France.
∗ Postal address: Laboratoire d’Analyse et d’Architecture des Systèmes du CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France.
∗ Postal address: Laboratoire d’Analyse et d’Architecture des Systèmes du CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

An analytical expression of the time-dependent probability distribution of M/D/1/N queues initialised in an arbitrary deterministic state is derived. We also obtain a simple analytical expression of the differential equation governing the transient average traffic which only involves probabilities of boundary states. As a by-product, a closed form solution of the departure rate from the system is also determined.

Keywords

Finite capacity M/D/1 queuestransient probability distribution

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M20: Performance evaluation; queueing; scheduling
Type
Research Papers
Information
Journal of Applied Probability , Volume 39 , Issue 4 , December 2002 , pp. 853 - 864
Copyright
Copyright © Applied Probability Trust 2002 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]. Abate, J., and Whitt, W. (1987). Transient behavior of the M/M/1 queue: starting at the origin. Queueing Systems 2, 41–65.Google Scholar
[2]. Brun, O., and Garcia, J. M. (2000). Analytical solution of finite capacity M/D/1 queues. J. Appl. Prob. 37, 1092–1098.Google Scholar
[3]. Bruni, C., D’Andrea, P., Mocci, U., and Scoglio, C. (1994). Optimal capacity management of virtual paths in an ATM network. In Proc. IEEE Globecom 94 (San Francisco, 28 November–2 December 1994), IEEE, New York, pp. 207–211.Google Scholar
[4]. Gafarian, A. V., Ancker, C. J., and Morisaku, T. (1978). Evaluation of commonly used rules for detecting steady state in computer simulation. Naval Res. Logistics Quart. 25, 511–529.Google Scholar
[5]. Gaver, D. P., and Shedler, G. S. (1971). Control variable methods in the simulation of multiprogrammed computer system. Naval Res. Logistics Quart. 18, 435–450.Google Scholar
[6]. Gravey, A., Louvion, J. R., and Boyer, P. (1990). On the Geo/D/1 and Geo/D/1/N queues. Performance Evaluation 11, 117–125.Google Scholar
[7]. Kelton, W. D. (1985). Transient exponential-Erlang queues and steady-state simulation. Commun. ACM 28, 741–749.Google Scholar
[8]. Kelton, W. D., and Law, A. M. (1983). A new approach for dealing with the startup problem in discrete event simulation. Naval Res. Logistics Quart. 30, 641–658.Google Scholar
[9]. Kelton, W. D., and Law, A. M. (1985). The transient behavior of the M/M/s queue, with implications for steady-state simulation. Operat. Res. 33, 378–396.CrossRefGoogle Scholar
[10]. Kleinrock, L. (1975). Queueing Systems, Vol. 1, Theory. John Wiley, New York.Google Scholar
[11]. Lee, D. S., and Li, S. Q. (1993). Transient analysis of a switched Poisson arrival queue under overload control. Performance Evaluation 17, 13–29.Google Scholar
[12]. Lee, I. J., and Roth, E. (1993). A heuristic for the transient expected queue length of Markovian queueing systems. Operat. Res. Lett. 14, 25–27.Google Scholar
[13]. Murray, J. R., and Kelton, W. D. (1988). The transient behavior of the M/Ek /2 queue and steady-state simulation. Comput. Operat. Res. 15, 357–367.Google Scholar
[14]. Odoni, A. R., and Roth, E. (1983). An empirical investigation of the transient behavior of stationary queueing systems. Operat. Res. 31, 432–455.Google Scholar
[15]. Roberts, J., Mocci, U., and Virtamo, J. (eds) (1996). Broadband Network Teletraffic, Final Report of Action Cost 242. Springer, Berlin.CrossRefGoogle Scholar
[16]. Saaty, T. L. (1960). Time-dependent solution of the many-server Poisson queue. Operat. Res. 8, 755–772.Google Scholar
[17]. Schruben, L. W. (1982). Detecting initialization bias in simulation output. Operat. Res. 30, 569–590.CrossRefGoogle Scholar
[18]. Taaffe, M. R., and Horn, S. A. (1983). External control variance reduction for non stationary simulation. In Proc. 1983 Winter Simulation Conf. (Arlington, VA, 12–14 December 1983), ACM, New York, pp. 341–344.Google Scholar
[19]. Takacs, L. (1962). Introduction to the Theory of Queues. Oxford University Press.Google Scholar
[20]. Tijms, H. C. (1994). Stochastic Models: An Algorithmic Approach. John Wiley, New York.Google Scholar
[21]. Vicari, N., and Tran-Gia, P. (1996). A numerical analysis of the Geo/D/N queueing system. Res. Rep. 151, Institute of Computer Science, University of Wurzburg.Google Scholar
[22]. Wang, C.-L. (1999). On the transient delays of M/G/1 queues. J. Appl. Prob. 36, 882–893.Google Scholar
[23]. Wilson, J. R., and Pritsker, A. A. B. (1978). Evaluation of startup policies in simulation experiments. Simulation 31, 79–89.Google Scholar