Open tandem networks with blocking analysis – two approaches

• Autorzy: Oniszczuk W.
• Języki publikacji: EN

Abstrakty

EN

The paper describes an analytical study of open twonode (tandem) network models with blocking. Here, a specific tandem configuration is chosen: the first node is treated as an infinite server (IS - often referred to as the ample-server), meaning that any incoming task can find at least one empty line for service in this node, and the second node has several parallel lines that can serve input task streams simultaneously. Between these two nodes there is a buffer with finite capacity. In this type of network, if the buffer is full, the accumulation of new tasks by the second node is temporarily suspended (blocking factor) and tasks must wait at the first node until the transmission process is resumed. In this paper, the two-node model is investigated using two different methods. The first is the multi-step exact algorithm, involving a numerical part for solving a set of linear equations, and the second is an approximate algorithm using a product form solution. The numerical part is used for solving a system of linear equations and for calculating the state probability vector. Finally, after comparing both algorithms, some recommendations as to when each method can be used are given.

Słowa kluczowe

EN

two-node network with blocking; multi-server tandem queues; exact algorithm; product form solution

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: Vol. 43, no. 1
• Strony: 111--132
• Opis fizyczny: Bibliogr. 40 poz.

Twórcy

autor

Oniszczuk W.

• Faculty of Computer Science, Bialystok Technical University, ul. Wiejska 45A, 15-351 Bia lystok, Poland

Bibliografia

• 1. AKYILDIZ I. F. (1998) Mean Value Analysis for Blocking Queuing Networks. IEEE Transaction on Software Engineering 14 (4), 418-428.
• 2. AMADOR J. and ARTALEJO J. R. (2009) Transient analysis of the successful and blocked events in retrial queues. Telecommunication Systems 41, 255- 265.
• 3. AZADEH A., EBRAHIM R. M. and EIVAZY H. (2010) Parameter optimization of tandem queue systems with finite intermediate buffers via fuzzy simulation. Performance Evaluation 67, 353-360.
• 4. BALSAMO S., DE NITTO PERSONE V. (1994) A survey of product form queueing networks with blocking and their equivalences. Annals of Operations Research 48 (1/4), 31-61.
• 5. BALSAMO S., DE NITTO PERSONE V. and ONVURAL R. (2001) Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Boston.
• 6. BALSAMO S., DE NITTO PERSONE V. and INVERARDI P. (2003) A review on queueing network models with finite capacity queues for software architectures performance predication. Performance Evaluation 51 (2-4), 269-288.
• 7. BADRAH A., CZACH´ORSKI T., DOMA´ NSKA J., FOURNEAU J.-M. and QUESSETTE F. (2002) Performance evaluation of multistage interconnection networks with blocking – discrete and continuous time Markov models. Archiwum Informatyki Teoretycznej i Stosowanej 14 (2), 145- 162.
• 8. BOLCH G., GREINER S., DE MEER H. and TRIVEDI K. S. (1998) Queueing Networks and Markov Chains. Modeling and Performance Evaluation with Computer Science Applications. John Wiley, New York.
• 9. BOSE A., JIANG X., LIU B. and LI G. (2006) Analysis of manufacturing blocking systems with Network Calculus. Performance Evaluation 63, 1216-1234.
• 10. BOUCHERIE R. J. and VAN DIJK N. M. (1997) On the arrival theorem for product form queueing networks with blocking. Performance Evaluation 29 (3), 155-176.
• 11. BOUHCHOUCH A., FREIN Y. and DALLERY Y. (1996) Performance evaluation of closed tandem queueing networks. Performance Evaluation 26, 115-132.
• 12. BRANDWAJN A. and JOW Y-L. L. (1988) An approximate method for tandem queues with blocking. Operations Research 36 (1), 73-83.
• 13. CASALE G., MUNTZ R. R. and SERAZZI G. (2008) Geometric Bounds: A Noniterative Analysis Technique for Closed Queueing Networks. IEEE Transactions on Computers 57 (6), 780-794.
• 14. CLO M. C. (1998) MVA for product-form cyclic queueing networks with blocking. Annals of Operations Research 79, 83-96.
• 15. ECONOMOU A. and FAKINOS D. (1998) Product form stationary distributions for queueing networks with blocking and rerouting. Queueing Systems 30 (3/4), 251-260.
• 16. GAVER D. P., JACOBS P. A. and LATOUCHE G. (1984) Finite birth-anddeath models in randomly changing environments. Advances in Applied Probability 16, 715-731.
• 17. GOMEZ-CORRAL A. (2002) A Tandem Queue with Blocking and Markovian Arrival Process. Queueing Systems 41, 343-370.
• 18. GOMEZ-CORRAL A. and MARTOS M. E. (2006) Performance of two-stage tandem queues with blocking: The impact of several flows of signals. Performance Evaluation 63, 910-938.
• 19. KIM C. S., KLIMENOK V., TSARENKOV G., BREUER L. and DUDIN A. (2007) The BMAP/G/1→•/PH/1/M tandem queue with feedback and losses. Performance Evaluation 64, 802-818.
• 20. KOUVATSOS D. and ALMOND J. (1988)Maximum entropy two-station cyclic queues with multiple general servers. Acta Informatica 26, 241-267.
• 21. KOUVATSOS D., AVAN I., FRETWELL R. and DIMAKOPOULOS G. (2000) A cost-effective approximation for SRD traffic in arbitrary multi-buffered networks. Computer Networks 34, 97-113.
• 22. KWIECIE´N J. and FILIPOWICZ B. (2012) Firefly algorithm in optimization of queueing systems. Bulletin of the Polish Academy of Sciences: Technical Sciences 60 (2), 363-368.
• 23. LENZINI L., MINGOZZI E. and STEA G. (2008) A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems. Performance Evaluation 65, 922-943.
• 24. MARTIN J. B. (2002) Large Tandem Queueing Networks with Blocking. Queueing Systems 41 (1/2), 45-72.
• 25. MORRISON J. A. (1996) Blocking probabilities for multiple class batched arrivals to a shared resource. Performance Evaluation 25, 131-150.
• 26. ONISZCZUKW. (2005)Modele, algorytmy kolejkowe i strategie obs lugi w sieciach komputerowych (Models, queuing algorithms and service strategies In computer networks; in Polish). Wydawnictwo Politechniki Bia lostockiej, Bia lystok.
• 27. ONISZCZUK W. (2006) Tandem Models with Blocking in the Computer Subnetworks Performance Analysis. In: K. Saeed et al., eds., Biometrics, Computer Security Systems and Artificial Intelligence Applications. Springer Science+Business Media, 259-267.
• 28. ONISZCZUK W. (2009) Semi-Markov-based approach for analysis of open tandem networks with blocking and truncation. International Journal of Applied Mathematics and Computer Science 19 (1), 151-163.
• 29. ONISZCZUK W. (2010) Loss Tandem Networks with Blocking Analysis – A Semi-Markov Approach. Bulletin of the Polish Academy of Sciences: Technical Sciences 58 (4), 673-681.
• 30. ONVURAL R. (1990) Survey of closed queuing networks with blocking. Computer Survey 22 (2), 83-121.
• 31. PERROS H. G. (1994) Queuing Networks with Blocking. Exact and Approximate Solution. Oxford University Press, New York.
• 32. RAMESH S. and PERROS H. G. (2000) A two-level queueing network model with blocking and non-blocking messages. Annals of Operations Research 93 (1/4), 357-372.
• 33. SERENO M. (1999) Mean value analysis of product form solution queueing networks with repetitive service blocking. Performance Evaluation 36- 37, 19-33.
• 34. SHARMA V. and VIRTAMO J. T. (2002) A finite buffer queue with priorities. Performance Evaluation 47, 1-22.
• 35. STEWART W. J. (1994) Introduction to the Numerical Solution of Markov Chains. Princeton University Press, New Jersey.
• 36. STRELEN J. CH., B¨ ARK B., BECKER J. and JONAS V. (1998) Analysis of queueing networks with blocking using a new aggregation technique. Annals of Operations Research 79, 121-142.
• 37. TOLIO T. and GERSHWIN S. B. (1998) Throughput estimation in cyclic queueing networks with blocking. Annals of Operations Research 79, 207- 229.
• 38. VAN VUUREN M., ADAN I. J. B. F. and RESING-SASSEN S. A. E. (2005) Performance analysis of multi-server tandem queues with finite buffers and blocking. OR Spectrum 27, 315-338.
• 39. ZHUANG L., BUZACOTT J. A. and LIU X-G. (1994) Approximate mean value performance analysis of cyclic queueing networks with production blocking. Queueing Systems 16, 139-165.
• 40. ZHUANG L. (1996) Acceptance instant distributions in product-form closed queueing networks with blocking. Performance Evaluation 26, 133-144.