Abstract
It is known that correlations in an arrival stream offered to a single-server queue profoundly affect mean waiting times as compared to a corresponding renewal stream offered to the same server. Nonetheless, this paper uses appropriately constructed GI/G/1 models to create viable approximations for queues with correlated arrivals. The constructed renewal arrival process, called PMRS (Peakedness Matched Renewal Stream), preserves the peakedness of the original stream and its arrival rate; furthermore, the squared coefficient of variation of the constructed PMRS equals the index of dispersion of the original stream. Accordingly, the GI/G/1 approximation is termed PMRQ (Peakedness Matched Renewal Queue). To test the efficacy of the PMRQ approximation, we employed a simple variant of the TES+ process as the autocorrelated arrival stream, and simulated the corresponding TES +/G/1 queue for several service distributions and traffic intensities. Extensive experimentation showed that the proposed PMRQ approximations produced mean waiting times that compared favorably with simulation results of the original systems. Markov-modulated Poisson process (MMPP) is also discussed as a special case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Altıok and B. Melamed, The case for modeling correlation in manufacturing systems, IIE Trans. 33 (2001) 779–791.
P. Bratley, B.L. Fox and L.E. Schrage, A Guide to Simulation (Springer, Berlin, 1987).
D.R. Cox, Renewal Theory (Methuen, London, 1962) pp. 46–53.
D.R. Cox and P.A.W. Lewis, The Statistical Analysis of Series of Events (Methuen, London, 1968).
A.E. Eckberg, A generalization of peakedness to arbitrary arrival processes and service time distributions, Bell Laboratories Technical Memorandum (1976).
A.E. Eckberg, Generalized peakedness of teletraffic processes, in: Proc. of the 10th Internat. Teletraffic Congress, Montreal, Canada, 1983.
A.E. Eckberg, Approximations for bursty (and smoothed) arrival delays based on generalized peakedness, in: Proc. of the 11th Internat. Teletraffic Congress, Kyoto, Japan, 1985.
K.W. Fendick, V.R. Saksena and W. Whitt, Dependence in packet queues, IEEE Trans. Commun. 37 (1989) 1173–1183.
W. Fischer and K. Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation 18 (1992) 149–171.
R. Gusella, Characterizing the variability of arrival processes with indexes of dispersion, IEEE J. Selected Areas Commun. 9(2) (1991) 203–211.
B. Hajek and L. He, On variations of queue response for inputs with the same mean and autocorrelation function, IEEE/ACM Trans. Networking 6(5) (1998) 588–598.
D.L. Jagerman, Methods in traffic calculations, Bell System Tech. J. 63(7) (1984) 1283–1310.
D.L. Jagerman, Approximations for waiting time in GI/G/1 systems, Queueing Systems 2 (1987) 351–362.
D.L. Jagerman, T. Altıok, B. Melamed and B. Balcıoglu, Mean waiting time approximations in the G/G/1 queue, Technical Report IE 01-104, Rutgers University, New Jersey (2001).
D.L. Jagerman and B. Melamed, The transition and autocorrelation structure of TES processes Part I: General theory, Stochastic Models 8(2) (1992) 193–219.
D.L. Jagerman and B. Melamed, The transition and autocorrelation structure of TES processes Part II: Special cases, Stochastic Models 8(3) (1992) 499–527.
D.L. Jagerman and B. Melamed, On Markovian traffic with applications to TES processes, J. Appl. Math. Stochastic Anal. 7(3) (1994) 373–396.
D.L. Jagerman and B. Melamed, Burstiness descriptors of traffic streams: Indices of dispersion and peakedness, in: Proc. of the 28th Annual Conf. on Information Sciences and Systems, Vol. 1, Princeton, NJ, March 1994, pp. 1–5.
D.L. Jagerman, B. Melamed and W. Willinger, Stochastic modeling of traffic processes (invited chapter), in: Frontiers in Queueing: Models and Applications in Science and Engineering, ed. J.H. Dshalalow (CRC Press, Boca Raton, FL, 1997) pp. 271–320.
L. Kleinrock, L. Queueing Systems, Vol. I: Theory (Wiley, New York, 1975).
M. Livny, B. Melamed and A.K. Tsiolis, The impact of autocorrelation on queuing systems, Managm. Sci. 39(3) (1993) 322–339.
R. Marie, Modelisation par reseaux de files d'attente, Ph.D. thesis, l'Université de Rennes, Rennes, France (1978).
B. Melamed, TES: A class of methods for generating autocorrelated uniform variates, ORSA J. Computing 3 (1991) 317–329.
B. Melamed, An overview of TES processes and modeling methodology, in: Performance Evaluation of Computer and Communications Systems, eds. L. Donatiello and R. Nelson, Lecture Notes in Computer Science (Springer, New York, 1993) pp. 359–393.
W.E. Milne, Numerical Calculus (Princeton Univ. Press, Princeton, NJ, 1949) pp. 154–163, 280.
B.E. Patuwo, R.L. Disney and D.C. McNickle, The effects of correlated arrivals on queues, IIE Trans. 25(3) (1993) 105–110.
J.G. Shantikumar and J.A. Buzacott, On the approximation to the single server queue, Internat. J. Prod. Res. 18(6) (1980) 761–773.
R. Wilkinson, Theories of toll traffic engineering in the USA, Bell System Tech. J. 35(2) (1956).
R.W. Wolff, Stochastic Modeling and the Theory of Queues (Prentice-Hall, Englewood Cliffs, NJ, 1989) p. 116.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jagerman, D.L., Balcıoglu, B., Altıok, T. et al. Mean Waiting Time Approximations in the G/G/1 Queue. Queueing Systems 46, 481–506 (2004). https://doi.org/10.1023/B:QUES.0000027996.28824.89
Issue Date:
DOI: https://doi.org/10.1023/B:QUES.0000027996.28824.89