Queueing Networks with Blocking: Analysis, Solution Algorithms and Properties

详细信息    查看全文

• 作者：Simonetta Balsamo (17)
  
• 关键词：Queueing Networks ; Blocking ; Product ; form models ; Equivalence properties
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：5233
• 期：1
• 页码：258-283
• 全文大小：360KB
• 参考文献：1. Akyildiz, I.F.: On the Exact and Approximate Throughput Analysis of Closed Queueing Networks with Blocking. IEEE Trans. Soft. Eng.聽14, 62鈥?1 (1988) CrossRef
  2. Akyildiz, I.F.: Mean value analysis of blocking queueing networks. IEEE Trans. Soft. Eng聽14, 418鈥?29 (1988) CrossRef
  3. Akyildiz, I.F., Von Brand, H.: Exact solutions for open, closed and mixed queueing networks with rejection blocking. J. Theor. Comp. Sci.聽64, 203鈥?19 (1989) CrossRef
  4. Altiok, T., Perros, H.G.: Approximate analysis of arbitrary configurations of queueing networks with blocking. Ann. Oper. Res.聽9, 481鈥?09 (1987) CrossRef
  5. Awan, I.U., Kouvatsos, D.D.: Approximate analysis of QNMs with space and service priorities. In: Kouvatsos, D.D. (ed.) Performance Analysis of ATM Networks, ch. 25, pp. 497鈥?21. Kluwer, IFIP Publication (1999)
  6. Balsamo, S.: Closed Queueing Networks with Finite Capacity Queues: Approximate analysis. In: Proc. ESM 2000, SCS, Europ. Sim. Multiconf. Ghent, May 23-26 (2000)
  7. Balsamo, S., Clo鈥? C., Donatiello, L.: Cycle Time Distribution of Cyclic Queueing Network with Blocking. Performance Evaluation聽14(3) (1993)
  8. Balsamo, S., Clo鈥? C.: A Convolution Algorithm for Product Form Queueing Networks with Blocking. Annals of Operations Research聽79, 97鈥?17 (1998) CrossRef
  9. Balsamo, S., De Nitto, V.: A survey of Product-form Queueing Networks with Blocking and their Equivalences. Annals of Operations Research聽48 (1994)
  10. Balsamo, S., De Nitto, V., Onvural, R.: Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Dordrecht (2001)
  11. Balsamo, S., Donatiello, L.: On the Cycle Time Distribution in a Two-stage Queueing Network with Blocking. IEEE Trans. on Soft. Eng.聽13, 1206鈥?216 (1989) CrossRef
  12. Balsamo, S., Iazeolla, G.: Some Equivalence Properties for Queueing Networks with and without Blocking. In: Agrawala, Tripathi (eds.) Performance 1983. North-Holland, Amsterdam (1983)
  13. Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, G.: Open, closed, and mixed networks of queues with different classes of customers. J. of ACM聽22, 248鈥?60 (1975) CrossRef
  14. Boucherie, R., Van Dijk, N.: On the arrival theorem for product form queueing networks with blocking. Performance Evaluation聽29, 155鈥?76 (1997) CrossRef
  15. Boxma, O., Konheim, A.G.: Approximate analysis of exponential queueing systems with blocking. Acta Informatica聽15, 19鈥?6 (1981) CrossRef
  16. Brandwajn, A., Jow, Y.L.: An approximation method for tandem queueing systems with blocking. Operations Research聽1, 73鈥?3 (1988) CrossRef
  17. Buzacott, J.A., Shanthikumar, J.G.: Design of Manufacturing Systems using Queueing Models. Queueing Systems: Theory and Applications (1992)
  18. Cheng, D.W.: Analysis of a tandem queue with state dependent general blocking: a GSMP perspective. Performance Evaluation聽17, 169鈥?73 (1993) CrossRef
  19. Clo鈥? C.: MVA for Product-Form Cyclic Queueing Networks with RS Blocking. Annals of Operations Research聽79 (1998)
  20. Dallery, Y., Frein, Y.: On decomposition methods for tandem queueing networks with blocking. Operations Research聽14, 386鈥?99 (1993) CrossRef
  21. Dallery, Y., Liu, Z., Towsley, D.F.: Equivalence, reversibility, symmetry and concavity properties in fork/join queueing networks with blocking. J. of the ACM聽41, 903鈥?42 (1994) CrossRef
  22. Dallery, Y., Towsley, D.F.: Symmetry property of the throughput in closed tandem queueing networks with finite buffers. Op. Res. Letters聽10, 541鈥?47 (1991) CrossRef
  23. Frein, Y., Dallery, Y.: Analysis of Cyclic Queueing Networks with Finite Buffers and Blocking Before Service. Performance Evaluation聽10, 197鈥?10 (1989) CrossRef
  24. Gershwin, S.B.: An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking. Oper. Res.聽35, 291鈥?05 (1987) CrossRef
  25. Gordon, W.J., Newell, G.F.: Cyclic queueing systems with restricted queues. Oper. Res.聽15, 286鈥?02 (1967) CrossRef
  26. Hillier, F.S., Boling, W.: Finite queues in series with exponential or Erlang service times - a numerical approach. Oper. Res.聽15, 286鈥?03 (1967) CrossRef
  27. Hordijk, A., Van Dijk, N.: Networks of queues with blocking. In: Kylstra, K.J. (ed.) Performance 1981, pp. 51鈥?5. North Holland, Amsterdam (1981)
  28. Jun, K.P., Perros, H.G.: An approximate analysis of open tandem queueing networks with blocking and general service times. Europ. Journal of Operations Research聽46, 123鈥?35 (1990) CrossRef
  29. Kouvatsos, D.D.: Maximum Entropy Methods for General Queueing Networks. In: Potier (ed.) Proc. Modeling Tech. and Tools for Perf. Analysis, pp. 589鈥?08. North-Holland, Amsterdam (1983)
  30. Kouvatsos, D.D.: A Universal Maximum Entropy Solution for Complex Queueing Systems and Networks. In: Karmeshu (ed.) Entropy Measures, maximum Entropy Principles and Emerging Applications, pp. 137鈥?62. Springer, Heidelberg (2003)
  31. Kouvatsos, D., Awan, I.U.: Arbitrary closed queueing networks with blocking and multiple job classes. In: Proc. Third Int. Work. on Queueing Networks with Finite Capacity, Bradford, UK, July 6-7 (1995)
  32. Kouvatsos, D.D., Awan, I.U.: MEM for arbitrary closed queueing networks with RS blocking and multiple job classes. Annals of Oper. Res.聽79, 231鈥?69 (1998) CrossRef
  33. Kouvatsos, D., Awan, I.U.: Entropy maximization and open queueing networks with priorities and blocking. Performance Evaluation聽51, 191鈥?27 (2003) CrossRef
  34. Kouvatsos, D., Denazis, S.G.: Entropy maximized queueing networks with blocking and multiple job classes. Performance Evaluation聽17, 189鈥?05 (1993) CrossRef
  35. Kouvatsos, D.D., Xenios, N.P.: MEM for arbitrary queueing networks with multiple general servers and repetitive-service blocking. Perf. Ev.聽10, 106鈥?95 (1989)
  36. Lam, S.S.: Queueing networks with capacity constraints. IBM J. Res. Develop.聽21, 370鈥?78 (1977) CrossRef
  37. Lee, H.S., Bouhchouch, A., Dallery, Y., Frein, Y.: Performance Evaluation of open queueing networks with arbitrary configurations and finite buffers. In: Proc. Third Int. Work. on Queueing Networks with Finite Capacity, Bradford, UK, July 6-7 (1995)
  38. Mishra, S., Fang, S.C.: A maximum entropy optimization approach to tandem queues with generalized blocking. Perf. Evaluation聽30, 217鈥?41 (1997) CrossRef
  39. Mitra, D., Mitrani, I.: Analysis of a Kanban discipline for cell coordination in production lines I. Management Science聽36, 1548鈥?566 (1990) CrossRef
  40. Onvural, R.O.: Some Product Form Solutions of Multi-Class Queueing Networks with Blocking. Perf. Evaluation聽10(3) (1989)
  41. Onvural, R.O.: A Note on the Product Form Solutions of Multiclass Closed Queueing Networks with Blocking. Performance Evaluation聽10, 247鈥?53 (1989) CrossRef
  42. Onvural, R.O.: Survey of Closed Queueing Networks with Blocking. ACM Computing Surveys聽22(2), 83鈥?21 (1990) CrossRef
  43. Onvural, R.O., Perros, H.G.: On Equivalencies of Blocking Mechanisms in Queueing Networks with Blocking. Oper. Res. Letters聽5, 293鈥?98 (1986) CrossRef
  44. Onvural, R.O., Perros, H.G.: Equivalencies Between Open and Closed Queueing Networks with Finite Buffers. Performance Evaluation (1988)
  45. Onvural, R.O., Perros, H.G.: Some equivalencies on closed exponential queueing networks with blocking. Performance Evaluation聽9, 111鈥?18 (1989) CrossRef
  46. Onvural, R.O., Perros, H.G.: Throughput Analysis in Cyclic Queueing Networks with Blocking. IEEE Trans. Software Engineering聽15, 800鈥?08 (1989) CrossRef
  47. Perros, H.G.: Queueing networks with blocking. Oxford University Press, Oxford (1994)
  48. Perros, H.G., Altiok, T.: Approximate analysis of open networks of queues with blocking: tandem configurations. IEEE Trans. Soft. Eng.聽12, 450鈥?61 (1986)
  49. Raiser, M., Lavenberg, S.S.: Mean Value Analysis of closed multi-chain queueing networks. Journal of ACM聽27, 217鈥?24 (1989)
  50. Sereno, M.: Mean Value Analysis of product form solution queueing networks with repetitive service blocking. Performance Evaluation聽36-37, 19鈥?3 (1999) CrossRef
  51. Skianis, C.A., Kouvatsos, D.D.: Arbitrary open queueing networks with service vacation periods and blocking. Annals of Operations Research聽79, 143鈥?80 (1998) CrossRef
  52. Shanthikumar, G.J., Yao, D.D.: Monotonicity Properties in Cyclic Queueing Networks with Finite Buffers. In: Perros, Altiok (eds.) First Int. Work. on Queueing Networks with Blocking. North Holland, Amsterdam (1989)
  53. Akyildiz, Perros (eds.): Special Issue on Queueing Networks with Finite Capacity Queues. Performance Evaluation, vol.聽10(3). North Holland, Amsterdam (1989)
  54. Onvural, R.O. (ed.): Special Issue on Queueing Networks with Finite Capacity. Performance Evaluation, vol.聽17(3). North-Holland, Amsterdam (1993)
  55. Balsamo, S., Kouvatsos, D.: Special Issue on Queueing Networks with Blocking Performance Evaluation Journal, vol.聽51(2-4). North Holland, Amsterdam (2003)
  56. Suri, R., Diehl, G.W.: A variable buffer size model and its use in analytical closed queueing networks with blocking. Management Sci.聽32(2), 206鈥?25 (1986) CrossRef
  57. van Dijk, N.: On stop = repeat servicing for non-exponential queueing networks with blocking. J. Appl. Prob.聽28, 159鈥?73 (1991) CrossRef
  58. van Dijk, N.: Stop = recirculate for exponential product form queueing networks with departure blocking. Oper. Res. Lett.聽10, 343鈥?51 (1991) CrossRef
  59. Van Dijk, N.: Queueing networks and product form. John Wiley, Chichester (1993)
  60. Yao, D.D., Buzacott, J.A.: Modeling a Class of State Dependent Routing in Flexible Manufacturing Systems. Annals of Oper. Research聽3, 153鈥?67 (1985) CrossRef
  61. Yao, D.D., Buzacott, J.A.: Modeling a class of flexible manufacturing systems with reversible routing. Oper. Res.聽35, 87鈥?3 (1987) CrossRef
  
• 作者单位：Simonetta Balsamo (17)
  
  17. Dipartimento di Informatica, Universit脿 Ca鈥?Foscari di Venezia, via Torino, 155, Mestre-Venezia, Italy
  
• ISSN：1611-3349

文摘

Queueing network models with finite capacity queues and blocking are used for modeling and performance evaluation of systems with finite resources and population constraints, such as communication and computer systems, traffic, production and manufacturing systems. Various blocking types can be defined to represent different system behaviors, network protocols and technologies. Queueing networks with blocking are difficult to analyze, except for the special class of product-form networks. Most of the analytical methods proposed in literature provide an approximate solution with a limited computational cost. We introduce queueing networks with finite capacity queues and blocking, the main solution techniques for their analysis, both exact and approximate algorithms, and some network properties. We discuss the conditions under which exact solutions can be derived, and criteria for the appropriate selection of approximate methods. We present equivalence properties among different types of blocking types, the analysis of heterogeneous networks, and some application examples.