Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T07:34:42.206Z Has data issue: false hasContentIssue false
  • English
  • Français

The throughput of a series of buffers

Published online by Cambridge University Press:  01 July 2016

F. P. Kelly
F. P. Kelly*
Affiliation:
University of Cambridge
*
∗Postal address: Statistical Laboratory, 16 Mill Lane, Cambridge, CB2 1SB, U.K.
Get access Rights & Permissions [Opens in a new window]

Abstract

Messages are to be transmitted through a series of n nodes linked by communication channels. The lengths of successive messages are independent identically distributed random variables, and the time taken to transmit a message through a channel is determined by its length. Each node has a finite buffer, and when the number of messages at a node reaches the buffer size transmission from the preceding node is interrupted. This paper is concerned with the maximum rate at which messages can pass through the system, called the throughput. We investigate the asymptotic behaviour of throughput as the series length increases, and determine the rate at which buffer sizes should grow to ensure that throughput does not decline to 0.

Keywords

SERIES OF QUEUESBLOCKINGTHROUGHPUTCOMMUNICATION CHANNELSJOB-SHOPSEXTREME VALUES
Type
Research Article
Information
Advances in Applied Probability , Volume 14 , Issue 3 , September 1982 , pp. 633 - 653
Copyright
Copyright © Applied Probability Trust 1982 

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.)

Footnotes

Research supported by the National Science Foundation under Grant ENG-7903879 A01, and carried out while the author was visiting the Department of Electrical Engineering and Computer Sciences and the Electronics Research Laboratory, University of California, Berkeley, CA 94720, U.S.A.

References

Boel, R. (1981) Martingale methods for the semi-Markov analysis of queues with blocking. Stochastics 5, 115–133.Google Scholar
Boxma, O. J. (1979) On a tandem queueing model with identical service times at both counters. Adv. Appl. Prob. 11, 616–659.Google Scholar
Boxma, O. J. and Konheim, A. G. (1981) Approximate analysis of exponential queueing systems with blocking. Acta Informatica 15, 19–66.Google Scholar
Breiman, L. (1968) Probability. Addison-Wesley, Reading, MA.Google Scholar
Crane, M. A. and Lemoine, A. J. (1977) An Introduction to the Regenerative Method for Simulation Analysis. Lecture Notes in Control and Information Sciences, Vol. 4, Springer-Verlag, Berlin.Google Scholar
Galambos, J. (1978) The Asymptotic Theory of Extreme Order Statistics. Wiley, New York.Google Scholar
Hille, E. and Phillips, R. S. (1957) Functional Analysis and Semi-Groups. American Mathematical Society, Providence, RI.Google Scholar
Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, Chichester.Google Scholar
Kingman, J. F. C. (1968) The ergodic theory of subadditive stochastic processes. J. R. Statist. Soc. B 30, 499–510.Google Scholar
Kingman, J. F. C. (1973) Subadditive ergodic theory. Ann. Prob. 1, 883–909.CrossRefGoogle Scholar
Liggett, T. M. (1975) Ergodic theorems for the asymmetric simple exclusion process. Trans. Amer. Math. Soc. 213, 237–261.Google Scholar
Neuts, M. F. (1968) Two queues in series with a finite, intermediate waiting room. J. Appl. Prob. 5, 123–142.Google Scholar
Pickands, J. (1968) Moment convergence of sample extremes. Ann. Math. Statist. 39, 881–889.Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar