Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T10:29:07.805Z Has data issue: false hasContentIssue false
  • English
  • Français

Diffusion Limits for Open Networks of Finite-Buffer Queues

Published online by Cambridge University Press:  27 July 2009

Indrajit Bardhan
Indrajit Bardhan
Affiliation:
Goldman Sachs International, Peterborough Court, 133 Fleet Street, London EC4A 2BB, U.K.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents diffusion limits for congestion in networks of finite-buffer queues. We consider both loss networks, such as those in communication systems, and networks with manufacturing blocking. In both cases, the number in system process, under conditions of approximate balance under heavy traffic and appropriate scaling of buffers, is shown to behave like a multidimensional Brownian motion reflected to stay within a rectangle in the positive orthant. The two limits differ in directions of reflection off the faces representing full buffers. The limits suggest possible diffusion approximations for finitebuffer networks.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 3 , July 1996 , pp. 341 - 361
Copyright
Copyright © Cambridge University Press 1996

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.Bardhan, I. (1992). General rate conservation law and its applications to diffusion approximations. Ph.D. dissertation, Department of Industrial Engineering and Operations Research, Columbia University, New York.Google Scholar
2.Bardhan, I. (1994). Separable densities for Brownian motion in a box (working paper).Google Scholar
3.Bardhan, I. & Mithal, S. (1993). Diffusion limit for a network with overflow routing (working paper).Google Scholar
4.Berger, A.W. & Whitt, W. (1991). The Brownian approximation for rate controlled throttles and the G/G/I/C queue. Preprint.Google Scholar
5.Billingsley, P. (1968). Convergence of probability measures. New York: Wiley.Google Scholar
6.Chen, H. & Mandelbaum, A. (1990). Stochastic Leontief systems in continuous time. In Proceedings of the Imperial College Workshop on Applied Stochastic Processes. Gordon and Breach Science (to appear).Google Scholar
7.Chen, H. & Mandelbaum, A. (1991). Discrete flow networks: Bottleneck analysis and fluid approximation. Mathematics of Operations Research 16: 408–446.CrossRefGoogle Scholar
8.Chen, H. & Mandelbaum, A. (1991). Discrete flow networks: Diffusion approximations and bottlenecks. Annals of Probability (to appear).CrossRefGoogle Scholar
9.Chen, H. & Whitt, W. (1991). Diffusion approximations for open queueing networks with service interruptions. Preprint.Google Scholar
10.Dai, J.G. & Harrison, J.M. (1991). Steady-state analysis of RBM in a rectangle: Numerical results and a queuing application. Annals of Applied Probability 1: 16–35.CrossRefGoogle Scholar
11.Dai, J.G. & Harrison, J.M. (1992). Reflected Brownian motion in an orthant: Numerical methods for steady-state analysis. Annals of Applied Probability 2: 65–86.CrossRefGoogle Scholar
12.Dai, J.G., Nguyen, V., & Reiman, M.I. (1994). Sequential bottleneck decomposition: An approximation method for generalized Jackson networks. Operations Research 42: 119–136.CrossRefGoogle Scholar
13.Dupuis, P. & Ishii, H. (1989). On when the solution to the Skorohod problem is Lipschitz continuous, with applications. Department of Mathematics and Statistics, University of Massachusetts, Amherst.Google Scholar
14.Dupuis, P. & Ishii, H. (1991). On oblique derivative problems for fully nonlinear second-order elliptic PDEs on domains with corners. Hokaido Math Journal 20: 135–164.Google Scholar
15.Dupuis, P. & Ishii, H. (1993). SDE's with oblique reflection on nonsmooth domains. Annals of Probability 21: 554–580.CrossRefGoogle Scholar
16.Gihman, I.I. & Skorohod, A.V. (1972). Stochastic differential equations. New York: Springer-Verlag.CrossRefGoogle Scholar
17.Glynn, P. & Whitt, W. (1988). Ordinary CLT and WLLN versions of L = λW. Mathematics of Operations Research 13: 674–692.CrossRefGoogle Scholar
18.Harrison, J.M. (1985). Brownian motion and stochastic flow systems. New York: Wiley.Google Scholar
19.Harrison, J.M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In Fleming, W. & Lions, P.L. (eds.), Stochastic differential systems, stochastic controt theory and their applications. Vol. 10. IMA Series on Mathematics and Its Applications. New York: Springer-Verlag, pp. 147–186.CrossRefGoogle Scholar
20.Harrison, J.M. & Nguyen, V. (1990). The QNET method for two-moment analysis of open queueing networks. Queueing Systems 6: 1–32.CrossRefGoogle Scholar
21.Harrison, J.M. & Nguyen, V. (1993). Brownian models of multiclass queueing networks: Current status and open problems. QUESTA 13: 5–40.Google Scholar
22.Harrison, J.M. & Reiman, M.I. (1981). Reflected Brownian motion on an orthant. Annals of Probability 9: 302–308.CrossRefGoogle Scholar
23.Harrison, J.M. & Williams, R.J. (1987). Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22: 77–115.CrossRefGoogle Scholar
24.Johnson, D.P. (1983). Diffusion approximations for optimal filtering of jump processes and for queueing networks. Ph.D. dissertation, University of Wisconsin, Madison.Google Scholar
25.Kushner, H.J. & Dupuis, P.G. (1992). Numerical methods for stochastic control problems in continuous time. New York: Springer-Verlag.CrossRefGoogle Scholar
26.Martins, L.F. & Kushner, H.J. (1990). Routing and singular control for queueing networks in heavy-traffic. SIAM Journal of Control & Optimization 28: 1209–1233.CrossRefGoogle Scholar
27.Reiman, M.I. (1984). Open queueing networks in heavy traffic. Mathematics of Operations Research 9: 441–458.CrossRefGoogle Scholar
28.Reiman, M.I. & Williams, R.J. (1986). A boundary property of semimartingale reflecting Brownian motions. Stochastics 22: 77–115.Google Scholar
29.Wolff, R.W. (1989). Stochastic modeling and the theory of queues. New York: Prentice-Hall.Google Scholar
30.Zhang, H., Hsu, G., & Wang, R. (1990). Strong approximations for multiple channel queues in heavy traffic. Journal of Applied Probability 27: xxx–xxx.Google Scholar