Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-13T06:50:52.372Z Has data issue: false hasContentIssue false

On stability of state-dependent queues and acyclic queueing networks

Published online by Cambridge University Press:  01 July 2016

Nicholas Bambos
Affiliation:
University of California, Berkeley
Jean Walrand*
Affiliation:
University of California, Berkeley
*
Department of Electrical Engineering and Computer Sciences and Electronic Research Laboratory, University of California, Berkeley CA 94720, USA.

Abstract

We consider a single server first-come-first-served queue with a stationary and ergodic input. The service rate is a general function of the workload in the queue. We provide the necessary and sufficient conditions for the stability of the system and the asymptotic convergence of the workload process to a finite stationary process at large times. Then, we consider acyclic networks of queues in which the service rate of any queue is a function of the workloads of this and of all the preceding queues. The stability problem is again studied. The results are then extended to analogous systems with periodic inputs.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1989 

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

Arnold, V. I. (1973) Ordinary Differential Equations. MIT Press, Cambridge, Massachusetts.Google Scholar
Baccelli, F. and Bremaud, P. (1987) Palm Probabilities and Stationary Queues. Lecture Notes in Statistics 41, Springer-Verlag, Berlin.Google Scholar
Bambos, N. and Walrand, J. (1989) On queues with periodic inputs. J. Appl. Prob. Google Scholar
Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
Çinlar, E. and Pinsky, M. (1971) A stochastic integral in storage theory. Z. Wahrscheinlichkeitsth. 17, 227240.CrossRefGoogle Scholar
Franken, P., Konig, D., Arndt, U., and Schmidt, V. (1982) Queues and Point Processes. Akademie Verlag, Berlin.Google Scholar
Hadidi, N. (1974) Busy period of queues with state-dependent arrival and service rates. J. Appl. Prob. 11, 842848.Google Scholar
Harris, C. M. (1967) Queues with state-dependent stochastic service rates. ORSA Journal 15, 117130.Google Scholar
Jacod, J. and Shiryaev, A. N. (1987) Limit Theorems for Stochastic Processes. Springer-Verlag, Berlin.Google Scholar
Knessl, C., Matkowsky, B. J., Schuss, Z., and Tier, C. (1986) On the performance of state-dependent single server queues. SIAM J. Appl. Math. 46, 657697.Google Scholar
König, D. and Jansen, U. (1976) Eine Invarianzeigenschaft zufälliger Bedienungsprozesse mit positiven Geschwindigkeiten. Math. Nachr. 70, 321364.Google Scholar
König, D. and Schmidt, V. (1980) Imbedded and non-imbedded stationary characteristics of queueing systems with varying service rate and point processes. J. Appl. Prob. 17, 753767.Google Scholar
Loomis, L. H. and Sternberg, S. (1968) Advanced Calculus. Addison-Wesley, Reading, Mass.Google Scholar
Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497520.Google Scholar
Matthes, K., Kerstan, J., and Mecke, J. (1978) Infinitely Divisible Point Processes. Akademie Verlag, Berlin.Google Scholar
Walrand, J. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Walters, P. (1982) An Introduction to Ergodic Theory. Springer-Verlag, Berlin.CrossRefGoogle Scholar