Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-12T20:30:19.801Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE DISCRETE-TIME G/GI/∞ QUEUE*

Published online by Cambridge University Press:  25 September 2008

Iddo Eliazar
Iddo Eliazar
Affiliation:
Department of Technology Management, Holon Institute of Technology, Holon 58102, IsraelE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The discrete-time G/GI/∞ queue model is explored. Jobs arrive to an infinite-server queuing system following an arbitrary input process X; job sizes are general independent and identically distributed random variables. The system's output process Y (of job departures) and queue process N (tracking the number of jobs present in the system) are analyzed. Various statistics of the stochastic maps X↦ Y and X↦ N are explicitly obtained, including means, variances, autocovariances, cross-covariances, and multidimensional probability generating functions. In the case of stationary inputs, we further compute the spectral densities of the stochastic maps, characterize the fixed points (in the L2 sense) of the input–output map, precisely determine when the output and queue processes display either short-ranged or long-ranged temporal dependencies, and prove a decomposition result regarding the intrinsic L2 structure of general stationary G/GI/∞ systems.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 22 , Issue 4 , October 2008 , pp. 557 - 585
Copyright
Copyright © Cambridge University Press 2008

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.Bingham, N.H., Goldie, C.M. & Teugels, J.L. (1987). Regular variation. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
2.Altman, E. (2005). On stochastic recursive equations and infinite server queues. Proceedings of the IEEE Infocom, Miami.CrossRefGoogle Scholar
3.Cox, D.R. (1955). Some statistical models related with series of events. Journal of the Royal Statistical Society B 17: 129–164.Google Scholar
4.Cox, D.R. (1984). Long-range dependence: A review. In David, H.A. & David, H.T. (eds.), Statistics: An appraisal. Ames, IA: Iowa State University Press, pp. 54–74.Google Scholar
5.Cox, D.R. & Isham, V. (1980). Point processes. New York: Chapman & Hall.Google Scholar
6.Cox, D.R. & Miller, H.D. (1965). The theory of stochastic processes. London: Methuen.Google Scholar
7.Eliazar, I. (2007). The M/G/∞ queue revisited: Finiteness, summability, long-range dependence, and reverse-engineering. Queueing Systems 55: 71–82.Google Scholar
8.Feller, W. (1948). On probability problems in the theory of counters. Courant 1948: 105–115.Google Scholar
9.Guerin, C., Nyberg, H., Perrin, O., Resnick, S., Rootzen, H. & Starica, C. (2003). Empirical testing of the infinite source Poisson data traffic model. Stochastic Models 19: 151–200.Google Scholar
10.Hammersley, J.M. (1953). On counters with random dead time I. Proceedings of the Cambridge Philosophical Society 49: 623–637.CrossRefGoogle Scholar
11.Kingman, J.F.C. (1993). Poisson processes. Oxford: Oxford University Press.Google Scholar
12.Levert, C. & Scheen, W.L. (1943). Probability fluctuations of discharges in a Geiger–Müller counter produced by cosmic radiation. Physica 10: 225–238.Google Scholar
13.Mikosch, T., Resnick, S., Rootzen, H. & Stegeman, A. (2002). Is network traffic approximated by stable Lévy motion or fractional Brownian motion? Annals of Applied Probability 12: 23–68.Google Scholar
14.Parulekar, M. & Makowski, A. (1997). M/G/∞ input processes: A versatile class of models for traffic network. Proceedings of INFOCOM 1997, Kobe (Japan), pp. 419–426.CrossRefGoogle Scholar
15.Parulekar, M. & Makowski, A. (1997). Tail probabilities for M/G/∞ processes (I): Preliminary asymptotics. Queueing Systems 27: 271–296.Google Scholar
16.Pollaczek, F. (1954). Sur la théory stochastique des compteurs. Comptes Rendres de l'Academie des Sciences Paris 238: 766–768.Google Scholar
17.Rangarajan, G. & Ding, M. (eds.) (2003). Processes with long-range correlations: Theory and applications. Lecture Notes in Physics, Vol. 621. New York: Springer-Verlag.Google Scholar
18.Schiff, L.I. (1936). Statistical analysis of counter data. Physics Review 50: 88–96.CrossRefGoogle Scholar
19.Shiryaev, A.N. (1995). Probability. New York: Springer-Verlag.Google Scholar
20.Sousa-Vieira, M.E., Suarez-Gonzalez, A., Lopez-Garcia, C., Fernandez-Veiga, M. & Lopez-Ardao, J.C. (2002). A highly efficient M/G/∞ model for generating self-similar traces. In Yücesan, E. et al. (eds.), Proceedings of the 2002 Winter Simulation Conference pp. 2003–2010.Google Scholar
21.Suarez-Gonzalez, A., Lopez-Ardao, J.C., Lopez-Garcia, C., Fernandez-Veiga, M., Rodriguez-Rubio, R. & Sousa-Vieira, M.E. (2002). A new heavy-tailed discrete distribution for LRD M/G/∞ sample generation. Performance Evaluation 47: 197–219.Google Scholar
22.Takacs, L. (1962). Introduction to the theory of queues. Oxford: Oxford University Press.Google Scholar
23.Takacs, L. (1955). On processes of happenings generated by means of Poisson process. Acta Mathematica Hungarica 6: 81–99.Google Scholar
24.Taqqu, M. & Oppenheim, G. (eds.) (2002). Theory and applications of long-range dependence. Boston: Birkhauser.Google Scholar
25.Eliazar, I. (2008). Spectral analysis of source-medium-sink flows. European Physics Letters 82: 30005.Google Scholar