Hostname: page-component-cc8bf7c57-ksm4s Total loading time: 0 Render date: 2024-12-11T22:58:19.791Z Has data issue: false hasContentIssue false
  • English
  • Français

Embedded renewal processes in the GI/G/s queue

Published online by Cambridge University Press:  14 July 2016

Ward Whitt
Ward Whitt*
Affiliation:
Yale University
Get access Rights & Permissions [Opens in a new window]

Abstract

The stable GI/G/s queue (ρ < 1) is sometimes studied using the “fact” that epochs just prior to an arrival when all servers are idle constitute an embedded persistent renewal process. This is true for the GI/G/1 queue, but a simple GI/G/2 example is given here with all interarrival time and service time moments finite and ρ < 1 in which, not only does the system fail to be empty ever with some positive probability, but it is never empty. Sufficient conditions are then given to rule out such examples. Implications of embedded persistent renewal processes in the GI/G/1 and GI/G/s queues are discussed. For example, functional limit theorems for time-average or cumulative processes associated with a large class of GI/G/s queues in light traffic are implied.

Keywords

QUEUESERVICE SYSTEMCONGESTION THEORYGI/G/s QUEUEMULTI-SERVER QUEUEBUSY PERIODSEMBEDDED RENEWAL PROCESSRENEW AL PROCESSBUSYCYCLE FUNCTIONAL LIMIT THEOREMS FOR QUEUESLIMIT THEOREMS FOR QUEUESBUSY CYCLES AS RECURRENT EVENTS FOR QUEUES
Type
Research Papers
Information
Journal of Applied Probability , Volume 9 , Issue 3 , June 1972 , pp. 650 - 658
Copyright
Copyright © Applied Probability Trust 1972 

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] Blackwell, D. (1953) Extension of a renewal theorem. Pacific J. Math. 3, 315–320.Google Scholar
[2] Brown, M. and Ross, S. M. (1970) Asymptotic properties of cumulative processes. Technical Report No. 120, Department of Operations Research, Cornell University.Google Scholar
[3] Chung, K. L. (1968) A Course in Probability Theory. Harcourt, Brace and World, New York.Google Scholar
[4] De Smit, J. H. A. (1971) Many Server Queueing Systems. Ph.D. Thesis, Technische Hogeschool, Delft. Google Scholar
[5] Feller, W. (1966) An Introduction to Probability Theory and its Applications. Vol. 2. John Wiley and Sons, New York.Google Scholar
[6] Feller, W. (1968) An Introduction to Probability Theory and Its Applications. Vol. 1, 3rd. Ed. John Wiley and Sons, New York.Google Scholar
[7] Finch, P. D. (1959) On the distribution of queue size in queueing problems. Acta Math. Acad. Sci. Hung. 10, 327–336.Google Scholar
[8] Heyde, C. C. (1964) Two probability theorems and their applications to some first passage problems. J. Aust. Math. Soc. 4, 214–222.CrossRefGoogle Scholar
[9] Iglehart, D. (1971a) Functional limit theorems for the queue GI/G/1 in light traffic. Adv. Appl. Prob. 3, 269–281.CrossRefGoogle Scholar
[10] Iglehart, D. (1971b) Extreme values in the GI/G/1 queue. To appear in Ann. Math. Statist. 43.Google Scholar
[11] Jacobs, D. R. Jr. (1971) Some Results about Stochastically Ordered Queues. Ph.D. Thesis (Technical Report No. 154), Department of Statistics, The Johns Hopkins University.Google Scholar
[12] Kiefer, J. and Wolfowitz, J. (1955) On the theory of queues with many servers. Trans. Amer. Math. Soc. 78, 1–18.Google Scholar
[13] Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process, with applications to random walk. Ann. Math. Statist. 27, 147–161.Google Scholar
[14] Kingman, J. F. C. (1966) On the Algebra of Queues. Methuen Review Series in Applied Probability, London. Also in J. Appl. Prob. 3, 285–326.Google Scholar
[15] Lindley, D. V. (1952) The theory of queues with a single server. Proc. Camb. Phil. Soc. 48, 277–289.Google Scholar
[16] Loynes, R. M. (1962a) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
[17] Loynes, R. M. (1962b) Stationary waiting-time distributions for single-server queues. Ann. Math. Statist. 33, 1323–1339.Google Scholar
[18] Miller, D. R. (1971) On the Asymptotic Behavior of Regenerative Processes and Functionals of Regenerative Processes. Ph.D. Thesis (Technical Report No. 137), Department of Operations Research, Cornell University.Google Scholar
[19] Ross, S. M. (1970) Identifiability in GI/G/k queues. J. Appl. Prob. 7, 776–780.Google Scholar
[20] Serfozo, R. F. (1971) Semi-stationary processes. Report, Department of Industrial Engineering, Syracuse University. To appear in Zeit. Wahrscheinlichkeitsth. Google Scholar
[21] Smith, W. L. (1953) On the distribution of queueing times. Proc. Camb. Phil. Soc. 49, 449–461.Google Scholar
[22] Smith, W. L. (1955) Regenerative stochastic processes. Proc. Roy. Soc. A 232, 6–31.Google Scholar
[23] Smith, W. L. (1958) Renewal theory and its ramifications. J. R. Statist. Soc. B 20, 243–302.Google Scholar
[24] Spitzer, F. (1964) Principles of Random Walk. Van Nostrand, Princeton, New Jersey.Google Scholar
[25] Stidham, S. Jr. (1971) Regenerative processes in the theory of queues, with applications to the alternating-priority queue. Technical Report No. 130, Department of Operations Research, Cornell University.Google Scholar
[26] Takács, L. (1963) The limiting distribution of the virtual waiting time and the queue size for a single-server queue with recurrent input and general service times. Sankhya A 25, 91–100.Google Scholar
[27] Whitt, W. (1971) Classical limit theorems for queues. Technical Report, Department of Administrative Sciences, Yale University.Google Scholar