Abstract
Consider an open network of single-server stations, each with a first-in-first-out discipline. The network may be populated by various customer types, each with its own routing and service requirements. Routing may be either deterministic or stochastic, and the interarrival and service time distributions may be arbitrary. In this paper a general method for steady-state performance analysis is described and illustrated. This analytical method, called QNET, uses both first and second moment information, and it is motivated by heavy traffic theory. However, our numerical examples show that QNET compares favorably with W. Whitt's Queueing Network Analyzer (QNA) and with other approximation schemes, even under conditions of light or moderate loading.
In the QNET method one first replaces the original queueing network by what we call an approximating Brownian system model, and then one computes the stationary distribution of the Brownian model. The second step amounts to solving a certain highly structured partial differential equation problem; a promising general approach to the numerical solution of that PDE problem is described by Harrison and Dai [8] in a companion paper. Thus far the numerical solution technique has been implemented only for two-station networks, and it is clear that the computational burden will grow rapidly as the number of stations increases. Thus we also describe and investigate a cruder approach to two-moment network analysis, called ΠNET, which is based on a product form approximation, or decomposition approximation, to the stationary distribution of the Brownian system model.
In very broad terms, ΠNET is comparable to QNA in its level of sophistication, whereas QNET captures more subtle system interactions. In our numerical examples the performance of ΠNET and QNA is similar; the performance of QNET is generally better, sometimes much better.
Similar content being viewed by others
References
F. Baskett, K.M. Chandy, R.R. Muntz and F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. ACM 22 (1975) 248–260.
G. Bitran and D. Tirupati, Multiproduct queueing networks with deterministic routing: decomposition approach and the notion of interference, Mgt. Sci. 34 (1988) 75–100.
J.R. Fraker, Approximate techniques for the analysis of tandem queueing systems, Ph.D. Thesis, Department of Industrial Engineering, Clemson University (1971).
B.S. Greenberg, Queueing systems with returning customers and the order of tandem queues, Ph.D. Thesis, University of California, Berkeley (1986).
J.M. Harrison, The diffusion approximation for tandem queues in heavy traffic, Adv. Appl. Prob. 10 (1978) 886–905.
J.M. Harrison,Brownian Motion and Stochastic Flow Systems (Wiley, New York, 1985).
J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, in:Stochastic Differential Systems, Stochastic Control Theory and their Applications, W. Fleming and P.-L. Lions (Eds.), vol. 10 in the IMA Series on Mathematics and its Applications (Springer, New York, 1988) pp. 147–186.
J.M. Harrison and J. Dai, Computing the stationary distribution of reflected Brownian motion in an unbounded domain, in preparation.
J.M. Harrison and M.I. Reiman, Reflected Brownian motion on an orthant, Ann. Prob. 9 (1981) 302–308.
J.M. Harrison and R.J. Williams, Multidimensional reflected Brownian motions having exponential stationary distributions, Ann. Prob. 15 (1987) 115–137.
J.M. Harrison and R.J. Williams, Brownian models of open queueing networks with homogeneous customer populations, Stochastics 22 (1987) 77–15.
J.R. Jackson, Networks of waiting lines, Oper. Res. 5 (1957) 518–521.
J.R. Jackson, Jobshop-like queueing systems, Mgt. Sci. 10 (1963) 131–142.
F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
P.J. Kuehn, Approximate analysis of general queueing networks by decomposition, IEEE Trans. Comm. COM-27 (1979) 113–126.
W.P. Peterson, Diffusion approximations for networks of queues with multiple customer types, Ph.D. Thesis, Department of Operations Research, Stanford University (1985).
M.I. Reiman, The heavy traffic diffusion approximation for sojourn times in Jackson networks, in:Applied Probability — Computer Science: The Interface, R.L. Disney and T. Ott (eds.), vol. 2 (Birkhäuser, Boston, 1982) pp. 409–422.
M.I. Reiman, Open queueing networks in heavy traffic, Math. Oper. Res. 9 (1984) 441–458.
M.I. Reiman, A multiclass feedback queue in heavy traffic, Adv. Appl. Prob. 20 (1988) 179–207.
M.I. Reiman, A network of priority queues in heavy traffic: one bottleneck station, unpublished manuscript (currently being revised for publication).
M. Segal and W. Whitt, A queueing network analyzer for manufacturing, in:Teletraffic Science for New Cost Effective Systems, Networks and Service, ITC-12 (Elsevier North-Holland, 1989) pp. 1146–1152.
W. Whitt, The queueing network analyzer, Bell Sys. Tech. J. 62 (1983) 2779–2815.
W. Whitt, Performance of the queueing network analyzer, Bell Sys. Tech. J. 62 (1983) 2817–2843.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Harrison, J.M., Nguyen, V. The QNET method for two-moment analysis of open queueing networks. Queueing Syst 6, 1–32 (1990). https://doi.org/10.1007/BF02411463
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02411463