Raif O. Onvural
Skip Abstract Section
Abstract
Closed queueing networks are frequently used to model complex service systems such as production systems, communication systems, computer systems, and flexible manufacturing systems. When limitations are imposed on the queue sizes (i.e., finite queues), a phenomenon called blocking occurs. Queueing networks with blocking are, in general, difficult to treat. Exact closed form solutions have been reported only in a few special cases. Hence, most of the techniques that are used to analyze such queueing networks are in the form of approximations, numerical analysis, and simulation. In this paper, we give a systematic presentation of the literature related to closed queueing networks with finite queues. The results are significant for both researchers and practitioners.
- AKYILDIZ, I. F. 1987. Exact product form solutions for queueing networks with blocking. IEEE Trans. Comput. I, 121-126.Google Scholar
- ALYILDIZ, I. F. 1988a. General Closed Queueing Networks with Blocking, Performance '87, Courtois and Latouche, eds. Elsevier North Holland, Amsterdam, 282-303. Google Scholar
- AKYILDIZ, I. F. 1988b. On the exact and approximate throughput analysis of closed queueing networks with blocking. IEEE Trans. Softw. Eng. SE~14, 62-71. Google Scholar
- AKYILDIZ, I. F. 1988c. Mean value analysis for blocking queueing networks. IEEE Trans. So/tw. Eng. SE-14 (1), 418-429. Google Scholar
- AKYILDIZ, I. F. 1989a. Product form approximations for queueing networks with multiple servers and blocking. IEEE Trans. Cornput. 38, 99-115. Google Scholar
- AKYILDIZ, I. F. 1989b. Analysis of queueing networks with rejection blocking. In First International Workshop on Queueing Networks with Blocking, Perros and Altiok, eds. Elsevier North Holland, Amsterdam.Google Scholar
- AKYILDIZ, i. F., AND LIEBEHERR, J. 1989. Application of Norton's theorem on queueing networks with finite capacities. In the Proceedings of INFOCOM 89, pp. 914-923.Google Scholar
- AKYILDIZ, I. F., AND Vos BRAND, H. 1990. Dual and selfdual networks of queues with rejection blocking. Comput. J. To appear. Google Scholar
- AKYILDIZ, I. F., AND VON BRAND, H 1989a. Exact solutions for open, closed and mixed queueing networks with rejection blocking. Theor. Comput. Sci. J. 64, 203-219. Google Scholar
- AKYILDIZ, I. F., AND VON BRAND, H. 1989b. Computation of performance measures for open, closed and mixed networks with rejection blocking. Acta Info. 26, 559-576. Google Scholar
- AKYILDIZ, I. F., AND VON BRAND, H. 1989c. Central server models with multiple job classes, state dependent routing and rejection blocking. IEEE Trans. Softw. Eng. To appear. Google Scholar
- ALTIOK, T., AND PERROS, H. G. 1987. Approximate analysis of arbitrary configurations of queueing networks with blocking. Ann. OR 9, 481-509.Google Scholar
- AMMAR, M. H., AND GERSHWIN, S. B. 1987. Equivalence relations in queueing models of assembly/ disassembly networks. Working paper. Georgia Institute of Technology.Google Scholar
- BALSAMO, S., AND DONATIELLO, L. 1988. Two-stage cyclic network with blocking: Cycle time distribution and equivalence properties. In the Proceedings of Modeling Techniques and Tools for Computer Performance Evaluation. Potier and Puigjaner, eds. pp. 513-528.Google Scholar
- BALSAMO, S., AND IAZEOLLA, G. 1983. Some equivalence properties for queueing networks with and without blocking. In Performance '83, Agrawala and Tripathi, eds. North-Holland Publishing Company, Amsterdam, pp. 351-360. Google Scholar
- BALSAMO, S., V. DE NITRO PERSONE, AND IAZEOLLA, G. 1986. Some equivalencies of blocking mechanisms in queueing networks with finite capacity. Manuscript, Dipartimento di Informatica, Universite di Pisa, Italy.Google Scholar
- BASKETR, F., CHANDY, K. M., MUNTZ, R. R., AND PALACIOS, F. G. 1975. Open, closed and mixed networks of queues with different classes of customers. J. A CM 22, 2, 249-260. Google Scholar
- BOXMA, O., AND KONHEIM, A. 1981. Approximate analysis of exponential queueing systems with blocking. Acta In{o. 15, 19-66.Google Scholar
- CASEAU, P., AND PUJOLLE, G. 1979. Throughput capacity of a sequence of transfer lines with blocking due to finite waiting room. IEEE Trans. Softw. Eng. 5, 631-642.Google Scholar
- CHANDY, K. M., AND SAVER, C. H. 1978. Approximate methods for analyzing queueing network models of computing systems. A CM Comput. Surv. 10, 3, 281-317. Google Scholar
- CHANDY, K. M., HERZOG, U., AND Woo, L. 1975. Parametric analysis of queueing networks. IBM J. Res. Dev. 19, 43-49.Google Scholar
- COFFMAN, E. G., ELPHICK, M. J., AND SHOSHANI, A. 1971. System deadlocks. ACM Comput. Surv. 2, 4, 67-78. Google Scholar
- COHEN, J. W. 1969. The Single Server Queue. North Holland Publishing Company, Amsterdam.Google Scholar
- COURTOIS, P. J. 1977. Decomposability: Queueing and Computer System Applications. Academic Press, New York.Google Scholar
- Cox, D. R. 1955. A use of complex probabilities in the theory of stochastic processes. In the Proceedings o/the Cambridge Philosophical Society, voI. 51, pp. 313-319.Google Scholar
- DALLERY, Y., AND FREIN, Y. 1989. A decomposition method for the approximate analysis of closed queueing networks with blocking. In the Proceedings of the l st International Workshop on Queueing Networks with Blocking, Perros and Altiok, eds. Elsevier North Holland, Amsterdam.Google Scholar
- DALLERY, Y., AND YAO, D. D. 1986. Modeling a system of flexible manufacturing cells. In Modeling and Design of Flexible Manufacturing Systems, Kusiak, ed. Elsevier North Holland, Amsterdam, pp. 289-300.Google Scholar
- DIEHL, G. W. 1984. A buffer equivalency decomposition approach to finite buffer queueing networks. Ph.D. dissertation. Eng. Sci., Harvard Univ.Google Scholar
- GERSHWIN, S., AND BERMAN, U. 1981. Analysis of transfer lines consisting of two unreliable machines with random processing times and finite storage buffers. AIIE Trans. 13, (1), 2-11.Google Scholar
- GORDON, W. J., AND NEWELL, G. F. 1967a. Cyclic queueing systems with restricted queues. Oper. Res. 15, 266-278.Google Scholar
- GORDON, W. J., AND NEWELL, G. F. 1967b. Closed queueing systems with exponential servers. Oper. Res. 15, 254-265.Google Scholar
- GROSS, D., AND HARRIS, C. M. 1974. Fundamentals of Queueing Theory. John Wiley, New York. Google Scholar
- HIGHLEYMAN, W. H. 1989. Performance Analysis of Transaction Processing Systems. Prentice Hall, Englewood Cliffs, N.J. Google Scholar
- HORDIJK, A., AND VAN DIJK, N. 1981. Networks of queues with blocking. In Performance '81. Klystra, ed. North Holland, Amsterdam, pp. 51-65.Google Scholar
- HORDIJK, A., AND VAN DIJK, N. 1982. Adjoint processes, job local balance and insensitivity of stochastic networks. Bull:44 session. Int. Stat. Inst. 50, 776-788.Google Scholar
- HORDIJK, A., AND VAN DIJK, N. 1983. Networks of queues: Part I--Job local balance and the adjoint process; Part II--General routing and service characteristics. In the Proceedings International Conference Modeling Computing Systems, Vol. 60, pp. 158-205.Google Scholar
- JACKSON, J. R. 1963. Jobshop-like queueing systems. Manage. Sci. 10 (1), 131-142.Google Scholar
- JENNINGS, A. 1977. Matrix Computation for Engineers and Scientists. John Wiley, New York.Google Scholar
- JUN, K. P. 1988. Approximate analysis of open queueing networks with blocking. Ph.D. dissertation, Operations Research Program, North Carolina State Univ.Google Scholar
- KELLY, K. P. 1979. Reversibility and Stochastic Networks. John Wiley, Chichester, England.Google Scholar
- KENDALL, D. G. 1953. Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains. Ann. Math. Statist. 24, 338-354.Google Scholar
- KLEINROCK, L. 1976. Queueing Systems. Vol. II. John Wiley, New York.Google Scholar
- KOUVATSOS, D. D. 1983. Maximum entropy methods for general queueing networks. Tech. Rep. RCC34, Univ. Bradford, U.K.Google Scholar
- KOUVATSOS, D. D., AND XENIOS, N. P. 1989. Maximum entropy analysis of general queueing networks with blocking. First International Workshop on Queueing Networks with Blocking, Perros and Altiok, eds. North Holland, Amsterdam.Google Scholar
- KUNDU, S., AND AKYILDIZ, I. F. 1989. Deadlock free buffer allocation in closed queueing networks. Queue. Syst. J. 4, 47-56.Google Scholar
- LAW, A. M., AND KELTON, W. D. 1982. Simulation Modeling and Analysis. McGraw Hill, New York. Google Scholar
- LITTLE, J. D. C. 1961. A proof of the queueing formula L = ~ W. Oper. Res. 9, 383-387.Google Scholar
- MARIE, R. 1979. An approximate analytical method for general queueing networks. IEEE Trans. Softw. Eng. SE-5 (5), 530-538.Google Scholar
- MINOURA, T. 1982. Deadlock avoidance revisited. J. ACM 29 (4), 1023-1048. Google Scholar
- MITRA, D., AND MITRANI, I. 1988. Analysis of a novel discipline for cell coordination in production lines. AT&T Bell Labs Res. Rep.Google Scholar
- MUNTZ, R. R. 1978. Queueing networks: A critique of the state of the art directions for the future. ACM Comput. Surv. 10, 3, 353-359. Google Scholar
- ONVURAL, R. O. 1987. Closed queueing networks with finite buffers. Ph.D. dissertation, CSE/OR, North Carolina State Univ.Google Scholar
- ONVURAL, R. O. 1989a. On the exact decomposition of exponential closed queueing networks with blocking. First International Workshop on Queueing Networks with Blocking, Perros and Altiok, eds. North Holland, Amsterdam.Google Scholar
- ONVURAL, R. O. 1989b. Some product form solutions of multi-class queueing networks with blocking. Perform. Eval. Special Issue on Queueing Networks with Blocking, Akyildiz and Perros, eds. 10-11,247-254. Google Scholar
- ONVURAL, R. O., AND PERROS, H. G. 1986. On equivalencies of blocking mechanisms in queueing networks with blocking. Oper. Res. Lett. 5, (6), 293-298.Google Scholar
- ONVURAL, R. O., AND PERROS, H. G. 1988. Equivalencies between open and closed queueing networks with finite buffers. International Seminar on the Performance Evaluation of Distributed and Parallel Systems, Kyoto, Japan. Perform. Eval., 9, 263-269. Google Scholar
- ONVURAL, R. O., AND PERROS, H. G. 1989a. Some equivalencies on closed exponential queueing networks with blocking. Perform. Eval. 9, 111-118. Google Scholar
- ONVURAL, R. O., AND PERROS, H. G. 1989b. Throughput analysis in cyclic queueing networks with blocking. IEEE Trans. Softw. Eng. SE-15, (6), 800-808. Google Scholar
- PERROS, H. G. 1984. Queueing networks with blocking: A bibliography. ACM Sigmetrics, Perf. Eval. Rev. 12, (2), 8-12. Google Scholar
- PERROS, H. G. 1989. Open queueing networks with blocking. In Stochastic Analysis of Computer and Communications Systems, Takagi, ed. Elsevier North Holland, New York.Google Scholar
- PERROS, H. G., NILSSON, A., AND LIU, Y. G. 1988. Approximate analysis of product form type queueing networks with blocking and deadlock. Perform. Eval. 8, 19-39. Google Scholar
- PERSONE, DE NITTO, V., AND GRILLO, D. 1987. Managing blocking in finite capacity symmetrical ring networks. In the 3rd Conference on Data and Communication Systems and Their Performance, Rio de Janeiro, Brazil.Google Scholar
- PITTEL, B. 1979. Closed exponential networks of queues with saturation: The Jackson type stationary distribution and its asymptotic analysis. Math. Oper. Res. 4, 367-378.Google Scholar
- REISER, M. 1979. A queueing network analysis of computer communications networks with window flow control. IEEE Trans. Comm. 27, 1199-1209.Google Scholar
- SHANTHIKUMAR, G. J., AND YAO, D. D. 1989. Monotonicity properties in cyclic queueing networks with finite buffers. First International Workshop on Queueing Networks with Blocking. Perros and Altiok, eds. North Holland, Amsterdam.Google Scholar
- SOLOMON, S. L. 1983. Simulation of Waiting Line Systems. Prentice Hall, Englewood Cliffs, N.J.Google Scholar
- SURI, R., AND DIEHL, G. W. 1984. A new building block for performance evaluation of queueing networks with finite buffers. In the Proceedings of the A CM Sigmetrics on Measurement and Modeling of Computer Systems, 134-142. Google Scholar
- SURI, R., AND DIEHL, G. W. 1986. A variable buffer size model and its use in analytical closed queueing networks with blocking. Manage. Sci. 32 (2), 206-225. Google Scholar
- VAN DIJK, N. M., AND TIJMS, H. C. 1986. Insensitivity to Two Node Blocking Models with Applications, Teletraffic Analysis and Computer Performance Evaluation. Boxma, Cohen, and Tijms, eds. Elsevier North Holland, Amsterdam, The Netherlands, pp. 329-340. Google Scholar
- YAO, D. D., AND BUZACOTT, J. A. 1985a. Modeling a class of state dependent routing in flexible manufacturing systems. Ann. OR 3, 153-167.Google Scholar
- YAO, D. D., AND BUZACOTT, J. A. 1985b. Queueing models for flexible machining station Part I: Diffusion approximation. Eur. J. Oper. Res. 19, 233-240.Google Scholar
- YAO, D. D., AND BUZACOTT, J. A. 1985c. Queueing models for flexible machining stations Part II: The method of Coxian phases. Eur. J. Oper. Res. 19, 241-252.Google Scholar
- YAO, D. D., AND BUZACOTT, J. A. 1986. The exponentialization approach to flexible manufacturing system models with general processing times. Eur. J. Oper. Res. 24, 410-416.Google Scholar
Recommendations
Closed Queueing Networks Under Congestion: Nonbottleneck Independence and Bottleneck Convergence
We analyze the behavior of closed multiclass product-form queueing networks when the number of customers grows to infinity and remains proportionate on each route or class. First, we focus on the stationary behavior and prove the conjecture that the ...
Reversibility of Tandem Blocking Queueing Systems
<P>This paper is concerned with queueing systems of several service stations in series in which each station may consist of multi-servers. An infinite number of customers always waits in front of the first station, and each customer passes through all ...
Higher-order distributional properties in closed queueing networks
In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form ...
Reviews
Taghi J. Mirsepassi
I recommend this paper highly to both researchers and practitioners involved with queueing networks, particularly if they anticipate problems associated with limited node capacities. The first nine pages provide comprehensive coverage of queueing network applications, terminology, and basic governing equations; some practical network configurations; and definitions of network “blocking” and “deadlock.” The next 28 pages deal exclusively with blocking and deadlock problems. The author presents a systematic survey of the existing literature and its specific contributions to the analytical, numerical, and approximation solution techniques of these problems. The important mathematical conclusions and computational techniques developed in various surveyed papers are presented in the form of 16 lemmas and 10 algorithms. The last two pages provide an elaborate listing of more than 70 papers that the author has consulted and referenced throughout the paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments