Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T16:56:13.909Z Has data issue: false hasContentIssue false
  • English
  • Français

Storage-Limited Queues in Heavy Traffic

Published online by Cambridge University Press:  27 July 2009

E. G. Coffman Jr ,
A. A. Pukhalskii  and
M. I. Reiman
E. G. Coffman Jr
Affiliation:
AT&T Bell Laboratories Murray Hill, New Jersey 07974
A. A. Pukhalskii
Affiliation:
Institute for Problems of In formation Transmission Moscow, U.S.S.R.
M. I. Reiman
Affiliation:
AT&T Bell Laboratories Murray Hill, New Jersey 07974
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper models primary computer storage in the context of a general (GI/GI/l) queueing system. Queued items are described by sizes, or storage requirements, as well as by arrival and service times; the sum of the sizes of the items in the system is the occupied storage. Capacity constraints are represented by two different protocols for determining whether an arriving item is admitted to the system: (1) an item is accepted if and only if at its arrival time the currently occupied storage does not exceed a given constant C > 0, and (2) an item is accepted if and only if at its arrival time the occupied storage is at most C, and the occupied storage plus the item's size is at most C(l + ε) for some given ε > 0. We prove for both systems that in heavy traffic the occupied storage, suitably normalized, converges weakly to reflected Brownian motion with boundaries at 0 and at C. A distinctive feature of the proof is the characterization of reflected Brownian motion as a limit of unrestricted penalized processes.

These results make more plausible an earlier conjecture of the authors, i.e., that one obtains the same heavy traffic limit when the admission rule is: accept an item if and only if at its arrival time the occupied storage plus the item's size is no greater than C.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 5 , Issue 4 , October 1991 , pp. 499 - 522
Copyright
Copyright © Cambridge University Press 1991

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

Aven, O.I., Coffman, E.G. Jr, & Kogan, Y.A. (1987). Stochastic analysis of computer storage. Dordrecht, Holland: Reidel Publishing Company.Google Scholar
Billingsley, P. (1968). Convergence of probability measures. New York: Wiley.Google Scholar
Bremaud, P. (1981). Point processes and queues: Martingale dynamics. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Coffman, E.G. Jr & Reiman, M.I. (1983). Diffusion approximations for storage processes in computer systems. Proceedings of the ACM SIGMETRICS Conference, pp. 93–117.CrossRefGoogle Scholar
Dellacherie, C. (1972). Capacités et processus stochastiques. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Ikeda, N. & Watanabe, S. (1989). Stochastic differential equations and diffusion processes, 2nd ed.Amsterdam: North Holland.Google Scholar
Jacod, J. (1979). Calcul stochastique et problèmes de martingales. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Jacod, J. & Shiryaev, A.N. (1987). Limit theoremsfor stochastic processes. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Krichagina, E.V. (1989). A diffusion approximation for the many-server queue with phase service. Automatic and Remote Control 3: 73–83.Google Scholar
Lenglart, E. (1977). Relations de domination entre deux processus. Annales de l'Institut H. Poincaré Serie B 13: 171–179.Google Scholar
Lions, P.L., Menaldi, J.L., & Sznitman, A.S. (1981). Construction de processus de diffusion réflechis par pénalization du domaine. Comptes Rendus de l'Academie des Sciences (Paris) 292: 559–562.Google Scholar
Liptser, R.Sh. & Shiryaev, A.N. (1989). Theory of martingales. Dordrecht, Holland: Kluwer.CrossRefGoogle Scholar
Menaldi, J.L. (1983). A stochastic variational inequality for reflected diffusion. Indiana University Mathematics Journal 32: 733–744.CrossRefGoogle Scholar
Shalaumov, A. (1979). On the behaviour of a diffusion process with a large drift coefficient in a halfspace. Theory of Probability and Its Applications 24: 592–598.CrossRefGoogle Scholar
Tanaka, H. (1979). Stochastic differential equations with reflecting boundary conditions in convex regions. Hiroshima Mathematical Journal 9: 163–177.CrossRefGoogle Scholar
Whitt, W. (1980). Some useful functions for functional limit theorems. Mathematics of Operations Research 5: 67–85.CrossRefGoogle Scholar
Yamada, K. (1986). Multi-dimensional Bessel processes as heavy traffic limits of certain tandem queues. Stochastic Processes Applications 23: 35–56.CrossRefGoogle Scholar