Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-22T17:26:05.775Z Has data issue: false hasContentIssue false
  • English
  • Français

Queueing output processes

Published online by Cambridge University Press:  01 July 2016

D. J. Daley
D. J. Daley*
Affiliation:
Australian National University
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper reviews various aspects, mostly mathematical, concerning the output or departure process of a general queueing system G/G/s/N with general arrival process, mutually independent service times, s servers (1 ≦ s ≦ ∞), and waiting room of size N (0 ≦ N ≦ ∞), subject to the assumption of being in a stable stationary condition. Known explicit results for the distribution of the stationary inter-departure intervals {Dn} for both infinite and finite-server systems are given, with some discussion on the use of reversibility in Markovian systems. Some detailed results for certain modified single-server M/G/1 systems are also available. Most of the known second-order properties of {Dn} depend on knowing that the system has either Poisson arrivals or exponential service times. The related stationary point process for which {Dn} is the stationary sequence of the corresponding Palm–Khinchin distribution is introduced and some of its second-order properties described. The final topic discussed concerns identifiability, and questions of characterizations of queueing systems in terms of the output process being a renewal process, or uncorrelated, or infinitely divisible.

Keywords

OUTPUT PROCESSDEPARTURE PROCESSPOINT PROCESSREVERSIBILITYRENEWAL PROCESS CHARACTERIZATIONS
Type
Research Article
Information
Advances in Applied Probability , Volume 8 , Issue 2 , June 1976 , pp. 395 - 415
Copyright
Copyright © Applied Probability Trust 1976 

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

Aleksandrov, A. M. (1968) Output flows of a class of queueing systems (In Russian). Izv. Akad. Nauk SSSR Tehn Kibernet. 1968 4, 3–11 (Engrg. Cybernetics (1968) 4, 1–8).Google Scholar
Ambartzumian, R. V. (1965) Two inverse problems concerning the superposition of recurrent point processes. J. Appl. Prob. 2, 449–454.CrossRefGoogle Scholar
Boes, D. C. (1969) Note on the output of a queueing system. J. Appl. Prob. 6, 459–461.Google Scholar
Bokucava, I. T. (1967) Concerning a queueing system with losses (In Russian). Bull. Acad. Sci. Georgian SSR 47, 541–544.Google Scholar
Bokucava, I. T., Donadze, N. K. and Geldiasvili, N.I. (1969) On the output flow of a system with losses. Bull. Acad. Sci. Georgian SSR 53, 37–40.Google Scholar
Brillinger, D. R. (1974) Cross-spectral analysis of processes with stationary increments including the stationary G/G/∞ queue. Ann. Prob. 2, 815–827.Google Scholar
Brillinger, D. R. (1975) The identification of point process systems. Ann. Prob. 3, 909–929.CrossRefGoogle Scholar
Brown, M. (1969) An invariance property of Poisson processes. J. Appl. Prob. 6, 453–458.Google Scholar
Brown, M. (1970) An M/G/∞ estimation problem. Ann. Math. Statist. 41, 651–654.Google Scholar
Brown, M. (1972) Low density traffic streams. Adv. Appl. Prob. 4, 177–192.Google Scholar
Burke, P. J. (1956) The output of a queueing system. Operat. Res. 4, 699–704.Google Scholar
Burke, P. J. (1964) The dependence of delays in tandem queues. Ann. Math. Statist. 35, 874–875.Google Scholar
Burke, P. J. (1968) The output process of a stationary M/M/s queueing system. Ann. Math. Statist. 39, 1144–1152.Google Scholar
Burke, P. J. (1969) The dependence of sojourn times in tandem M/M/s queues. Operat. Res. 17, 754–755.Google Scholar
Burke, P. J. (1973) Output processes and tandem queues. Proc. Symp. Computer-Communications Network and Teletraffic (Microwave Res. Inst. Symp. 22), 419–428.Google Scholar
Wei, Chang (1963) Output distribution of a single channel queue. Operat. Res 11, 620–623.Google Scholar
Cherry, W. P. and Disney, R. L. (1974) Some topics in queueing network theory. In Mathematical Methods in Queueing Theory, ed. Clarke, A. B., Lecture Notes in Economics and Mathematical Systems 98, Springer-Verlag, New York, 23–44.Google Scholar
Cohen, J. W. (1969) The Single Server Queue. North-Holland, Amsterdam.Google Scholar
Cox, D. R. (1965) Some problems of statistical analysis connected with congestion (with Discussion). In Congestion Theory, ed. Smith, W. L. and Wilkinson, W. E., University of North Carolina Press, Chapel Hill. 289–316.Google Scholar
Cox, D. R. and Lewis, P. A. W. (1966) The Statistical Analysis of Series of Events. Methuen, London.Google Scholar
Daley, D. J. (1968) The correlation structure of the output process of some single server queueing systems. Ann. Math. Statist. 39, 1007–1019.Google Scholar
Daley, D. J. (1971) Weakly stationary point processes and random measures. J. R. Statist. Soc. B 33, 406–428.Google Scholar
Daley, D. J. (1972) A bivariate Poisson queueing process that is not infinitely divisible. Proc. Camb. Phil. Soc. 72, 449–450.Google Scholar
Daley, D. J. (1974a) Characterizing pure loss GI/G/1 queues with renewal output. Proc. Camb. Phil. Soc. 75, 103–107.Google Scholar
Daley, D. J. (1974b) Notes on queueing output processes. In Mathematical Methods in Queueing Theory, ed. Clarke, A. B., Lecture Notes in Economics and Mathematical Systems 98, Springer-Verlag, New York, 351–358.Google Scholar
Daley, D. J. (1975) Further second-order properties of certain single-server queueing systems. Stoch. Proc. Appl. 3, 185–191.Google Scholar
Daley, D. J. and Shanbhag, D. N. (1975) Independent inter-departure times in M/G/1/N queues. J. R. Statist. Soc. B 37, 259–263.Google Scholar
Daley, D. J. and Vere-Jones, D. (1972) A summary of the theory of point processes. In Stochastic Point Processes, ed. Lewis, P. A. W., Wiley, New York. 299–383.Google Scholar
Disney, R. L., Farrell, R. L. and de Morais, P. R. (1973) A characterization of M/G/1/N queues with renewal departure processes. Management Sci. 19, 1222–1228.Google Scholar
Dobrusin, R. L. (1956) On the Poisson law for distribution of particles in space (In Russian). Ukrain. Mat. Z. 8, 127–134.Google Scholar
Doob, J. L. (1953) Stochastic Processes. Wiley, New York.Google Scholar
Finch, P. D. (1959) The output process of the queueing system M/G/1. J. R. Statist. Soc. B 21, 375–380.Google Scholar
Fleischmann, K. (1975) Über den Output unempfindlicher verallgemeinerter Erlangscher Bedienungsprozesse. Math. Nachr. 66, 195–200.Google Scholar
Gaver, D. P. (1972) Asymptotic service system output, with application to multiprogramming. SIAM J. Comput. 1, 138–145.Google Scholar
Hadidi, N. (1972) On the output process of a state-dependent queue. Skand. Aktuartidskr. 55, 182–186.Google Scholar
Hadidi, N. (1974) A basically Poisson queue with non-Poisson output (Abstract). Adv. Appl. Prob. 6, 254–255.Google Scholar
Ivnitskii, V. A. (1969) Recovery of characteristics of single-server systems with constraints on the duration of presence from observations on the output flow. (In Russian). Izv. Akad. Nauk SSSR Tehn. Kibernet. 1969 3, 60–65 (Engrg. Cybernetics 1969 3, 52–56).Google Scholar
Jenkins, J. H. (1966) On the correlation structure of the departure process of the M/Eλ/1 queue. J. R. Statist. Soc. B 28, 336–344.Google Scholar
Kaplan, E. L. (1955) Transformation of stationary random sequences. Math. Scand. 3, 127–149.Google Scholar
Kendall, D. G. (1964) Some recent work and further problems in the theory of queues. Teor. Veroyat. 9, 3–15 (Theory Prob. Appl. 9, 1–13).Google Scholar
Kendall, D. G. and Lewis, T. (1965) On the structural information contained in the output of GI/G/∞. Z. Wahrscheinlichkeitsth. 4, 144–148.Google Scholar
King, R. A. (1971) The covariance structure of the departure process from M/G/1 queues with finite waiting lines. J. R. Statist. Soc. B 33, 401–406.Google Scholar
Kosten, L. (1973) Stochastic Theory of Service Systems. Pergamon Press, Oxford.Google Scholar
Kovalenko, I. N. (1965) The recovery of the characteristics of a system from observations on the output flow (In Russian). Dokl. Akad. Nauk SSSR 164, 979–981 (Soviet Math. 6, 1328–1331).Google Scholar
Laslett, G. M. (1975a) Characterizing the finite capacity GI/M/1 queue with renewal output. Management Sci. 22, 106–110.Google Scholar
Laslett, G. M. (1975b) Some problems concerning cluster processes and other point processes. Ph. D. thesis, Australian National University.Google Scholar
Lewis, P. A. W. and Shedler, G. (1973) Empirically derived models for sequences of page references and for sequences of page exceptions. IBM J. Res. Develop. 17, 86–100.Google Scholar
Lewis, T. and Govier, L. J. (1964) Some properties of counts of events for certain types of point processes. J. R. Statist. Soc. B 26, 325–337.Google Scholar
Marshall, K. T. (1968) Some inequalities in queueing. Operat. Res. 16, 651–665.Google Scholar
Mecke, J. (1975) A result on the output of stationary Erlang processes. (To appear.) Google Scholar
Milne, R. K. (1970) Identifiability for random translations of Poisson processes. Z. Wahrscheinlichkeitsth. 15, 195–201.Google Scholar
Mirasol, N. M. (1963) The output of an M/G/∞ queueing system is Poisson. Operat. Res. 11, 282–284.Google Scholar
Nelsen, R. B. and Williams, T. (1968) Randomly delayed appointment streams. Nature 219, 573–574.Google Scholar
Nelsen, R. B. and Williams, T. (1970) Random displacements of regularly spaced events. J. Appl. Prob. 7, 183–195.Google Scholar
Newell, G. F. (1966) The M/G/∞ queue. SIAM J. Appl. Math. 14, 86–88.Google Scholar
Pack, C. D. (1975a) A comparison of the output process of an M/D/1 queue as measured from an arbitrary departure epoch to that measured from an arbitrary instant in time. SIAM J. Appl. Math. 28, 367–375.CrossRefGoogle Scholar
Pack, C. D. (1975b) The output of an M/D/1 queue. Operat. Res. 23, 750–760.Google Scholar
Reich, E. (1957) Waiting times when queues are in tandem. Ann. Math. Statist. 28, 768–773.Google Scholar
Reich, E. (1963) Note on queues in tanden. Ann. Math. Statist. 34, 338–341.Google Scholar
Reich, E. (1965) Departure processes (with discussion). In Congestion Theory, ed. Smith, W. L. and Wilkinson, W. E., University of North Carolina Press, Chapel Hill, 439–457.Google Scholar
Ross, S. M. (1970) Identifiability in GI/G/k queues. J. Appl. Prob. 7, 776–780.Google Scholar
Ryll-Nardzewski, C. (1954) Remarks on the Poisson stochastic process, III. Studia Math. 14, 314–318.Google Scholar
Schmidt, G. (1967) Über die in einem einfachen Verlustsystem induzierten stochastischen Prozesse. Z. Operat. Res. (Unternehmensforschung) 11, 95–110.Google Scholar
Shanbhag, D. N. (1972) Letter to the Editor. J. Appl. Prob. 9, 470.Google Scholar
Shanbhag, D. N. (1973) Characterization for the queueing system M/G/∞. Proc. Camb. Phil. Soc. 74, 141–143.Google Scholar
Shanbhag, D. N. and Tambouratzis, D. (1973) Erlang's formula and some results on the departure process of a loss system. J. Appl. Prob. 10, 233–240.Google Scholar
Simonova, S. N. (1969) The output flow of a single-line service system (In Russian). Ukrain. Mat. Z. 21, 501–510.Google Scholar
Smith, W. L. (1957) On renewal theory, counter problems, and quasi-Poisson processes. Proc. Camb. Phil. Soc. 53, 175–193.Google Scholar
Syski, R. (1962) Introduction to Congestion Theory in Telephone Systems. Oliver and Boyd, London.Google Scholar
Takács, L. (1962) An Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
Thedéen, T. (1969) On road traffic with free overtaking. J. Appl. Prob. 6, 524–549.Google Scholar
Vere-Jones, D. (1966) Simple stochastic models for the release of quanta of transmitter from a nerve terminal. Austral. J. Statist. 8, 53–63.Google Scholar
Vere-Jones, D. (1968) Some applications of probability generating functionals to the study of input-output streams. J. R. Statist. Soc. B 30, 321–333.Google Scholar
Vlach, T. L. and Disney, R. L. (1969) The departure process from the GI/G/1 queue. J. Appl. Prob. 6, 704–707.Google Scholar
Yarovitskii, N. V. (1961) On the outgoing flow of a unilinear service system with losses (Ukrainian). Dop. Akad. Nauk Ukrain. RSR 1961, 1251–1254.Google Scholar
Yarovitskii, N. V. (1962) On some properties of simply connected dependent streams (In Russian). Ukrain. Mat. Z. 14, 170–179.Google Scholar
References added in proof but not mentioned in the text. Google Scholar
McNickle, D. C. (1974) The number of departures from a semi-Markov queue. J. Appl. Prob. 11, 825–828.Google Scholar
Natvig, B. (1975) On the input and output processes for a general birth-and-death queueing model. Adv. Appl. Prob. 7, 576–592.Google Scholar