Asymptotic behavior of the expansion method for open finite queueing networks. (English) Zbl 0662.60105

The paper presents an approximation technique for the modeling of finite capacity queueing networks.
In the first part, the ‘expansion method’, already discussed in earlier papers, is described. The basic idea behind it is the introduction of ‘holding nodes’ representing the additional waiting times incurred by customers due to blocking. In limiting the analysis to exponential service times and an external Poisson arrival process, an exhaustive set of recursive equations is derived based on mean value computation and well-known approximations [see J. Labetoulle and G. Pujolle, IEEE Trans. Software Eng. SE-6, No.4 (1980)].
In part two, the value of the expansion method with regard to meeting an upper bound throughput criterion [P. C. Bell, Oper. Res. Lett. 1, 230-235 (1982; Zbl 0499.90039)] even for quite ‘unbalanced’ service rates is demonstrated.
Reviewer: G.Wieber


60K25 Queueing theory (aspects of probability theory)
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems


Zbl 0499.90039
Full Text: DOI


[1] Chandy, K.M.; Sauer, C.H., Approximate methods for analyzing queueing network models of computing systems, Comput. surveys, 10, 281-317, (1978) · Zbl 0385.68039
[2] Kobayashi, H., Application of the diffusion approximation to queueing networks I: equilibrium queue distributions, J. assoc. comput. machinery, 21, 316-328, (April 1974)
[3] Reiser, M.; Kobayashi, H., Accuracy of the diffusion approximation for some queueing systems, IBM J. res. dev., 18, (1974) · Zbl 0275.68014
[4] Halachimi, B.; Franta, W.R., A diffusion approximation solution the G/G/k queueing system, Comput. opns res., 4, 37-46, (1977)
[5] Gelenbe, E.; Pujolle, G., The behavior of a single queue in a general queueing network, Acta inform., 7, 123-136, (1976) · Zbl 0349.60091
[6] Newell, G.F., Approximate behavior of tandem queues, (1980), Springer Berlin · Zbl 0497.90017
[7] Sauer, C.H.; Chandy, K.M., Computer systems performance modeling, (1981), Prentice-Hall Englewood Cliffs, N.J
[8] Jackson, J.R., Networks of waiting lines, Opns res., 5, 518-521, (1957)
[9] Kuehn, P.J., Approximate analysis of general networks by decomposition, IEEE transact. commun., COM-27, 113-126, (January 1979)
[10] Whitt, W., Approximations for networks of queues: A simple two-parameter linear algorithm, (1982), Bell Laboratories Holmdel N.J
[11] Buzacott, J.; Shanthikumar, J., Approximate queueing models of dynamic job shops, Mgmt sci., 31, 870-887, (1985)
[12] Smith, J.M.; Bouanaka, B., Queueing networks decomposition in facilities planning, Comput. opns res., 12, 1-16, (1985)
[13] Perros, H.G., Queueing networks with blocking: a bibliography, ACM sigmet., 12, 8-12, (1984)
[14] Labetoulle, J.; Pujolle, G., Isolation method in a network of queues, IEEE transact. software engng, SE-6, 4, (July 1980)
[15] Boxma, O.; Konheim, A., Approximate analysis of exponential queueing systems with blocking, Acta inform., 15, 19-26, (1981) · Zbl 0442.60091
[16] Caseau, P.; Pujolle, G., Throughput capacity of a sequence of queues with blocking due to finite waiting room, IEEE trans. soft. engng, SE-5, 631-642, (1979) · Zbl 0428.68002
[17] Fredericks, A.A.; Reisner, G.A., Approximations to stochastic service systems, with an application to a retrial model, The Bell syst. techn. J., 58, 557-576, (1979) · Zbl 0402.90043
[18] Fredericks, A.A., Congestion in blocking systems—A simple approximation technique, The Bell syst. tech. J., 59, 805-827, (1980) · Zbl 0439.90037
[19] Millier, F.S.; Boling, R.W., Finite queues in series with exponential or Erlang service times—A numerical approach, Opns res., 15, 286-303, (1967) · Zbl 0171.16302
[20] Takahashi, Y.; Miyahara, H.; Hasegawa, T., An approximation method for open restricted queueing networks, Opns res., 28, 594-602, (June 1980), (Part I, May)
[21] Altiok, T., Approximate analysis of exponential tandem queues with blocking, Eur. J. opns res., 11, 390-398, (1982) · Zbl 0497.60096
[22] Altiok, T.; Perros, H.G., Open networks of queues with blocking: split and merge configurations, ()
[23] Kerbache, L., Analysis of open finite queueing networks, ()
[24] Suri, R.; Diehl, G.W., A new building block for performance evaluation of queueing networks with finite buffer, ()
[25] Kleinrock, L., Theory, () · Zbl 0161.13701
[26] Brown, K.M., A quadratically convergent Newton-like method based upon Gaussian elimination, SIAM J. numer. anal., 6, 560-569, (1969) · Zbl 0245.65023
[27] Talebi, K., Stochastic network evacuation models, ()
[28] Bell, P.C., The use of decomposition techniques for the analysis of open restricted queueing networks, Opns res. lett., 1, 230-235, (1982) · Zbl 0499.90039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.