Open Tandem Networks with Blocking Analysis - Two Approaches

• Autorzy: Walenty Oniszczuk
• 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. (original abstract)

Słowa kluczowe

PL

Algorytmy; Modele optymalizacyjne

EN

Algorithms; Optimizing models

• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: 43
• Numer: nr 1
• Strony: 111-132

Twórcy

autor

Walenty Oniszczuk

• Bialystok Technical University

Bibliografia

• AKYILDIZ I. F. (1998) Mean Value Analysis for Blocking Queuing Networks. IEEE Transaction on Software Engineering 14 (4), 418-428.
• AMADOR J. and ARTALEJO J. R. (2009) Transient analysis of the successful and blocked events in retrial queues. Telecommunication Systems 41, 255- 265.
• 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.
• 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.
• BALSAMO S., DE NITTO PERSONE V., ONVURAL R. (2001), Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Boston.
• BALSAMO S., DE NITTO PERSONE V., 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.
• BADRAH A., CZACHÓRSKI T., DOMAŃSKA J., FOURNEAU J.-M., 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.
• BOLCH G., GREINER S., DE MEER H., TRIVEDI K. S. (1998), Queueing Networks and Markov Chains. Modeling and Performance Evaluation with Computer Science Applications. John Wiley, New York.
• BOSE A., JIANG X., LIU B., LI G. (2006), Analysis of manufacturing blocking systems with Network Calculus. Performance Evaluation 63, 1216-1234.
• BOUCHERIE R. J., VAN DIJK N. M. (1997), On the arrival theorem for product form queueing networks with blocking. Performance Evaluation 29 (3), 155-176.
• BOUHCHOUCH A., FREIN Y., DALLERY Y. (1996), Performance evaluation of closed tandem queueing networks. Performance Evaluation 26, 115-132.
• BRANDWAJN A., JOW Y-L. L. (1988), An approximate method for tandem queues with blocking. Operations Research 36 (1), 73-83.
• CASALE G., MUNTZ R. R., SERAZZI G. (2008), Geometric Bounds: A Noniterative Analysis Technique for Closed Queueing Networks. IEEE Transactions on Computers 57 (6), 780-794.
• CLO M. C. (1998), MVA for product-form cyclic queueing networks with blocking. Annals of Operations Research 79, 83-96.
• ECONOMOU A., FAKINOS D. (1998), Product form stationary distributions for queueing networks with blocking and rerouting. Queueing Systems 30 (3/4), 251-260.
• GAVER D. P., JACOBS P. A., LATOUCHE G. (1984), Finite birth-anddeath models in randomly changing environments. Advances in Applied Probability 16, 715-731.
• GOMEZ-CORRAL A. (2002), A Tandem Queue with Blocking and Markovian Arrival Process. Queueing Systems 41, 343-370.
• GOMEZ-CORRAL A., MARTOS M. E. (2006), Performance of two-stage tandem queues with blocking: The impact of several flows of signals. Performance Evaluation 63, 910-938.
• KIM C. S., KLIMENOK V., TSARENKOV G., BREUER L., DUDIN A. (2007), The BMAP/G/1→•/PH/1/M tandem queue with feedback and losses. Performance Evaluation 64, 802-818.
• KOUVATSOS D., ALMOND J. (1988), Maximum entropy two-station cyclic queues with multiple general servers. Acta Informatica 26, 241-267.
• KOUVATSOS D., AVAN I., FRETWELL R., DIMAKOPOULOS G. (2000), A cost-effective approximation for SRD traffic in arbitrary multi-buffered networks. Computer Networks 34, 97-113.
• KWIECIE´N J., FILIPOWICZ B. (2012), Firefly algorithm in optimization of queueing systems. Bulletin of the Polish Academy of Sciences: Technical Sciences 60 (2), 363-368.
• LENZINI L., MINGOZZI E., STEA G. (2008), A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems. Performance Evaluation 65, 922-943.
• MARTIN J. B. (2002), Large Tandem Queueing Networks with Blocking. Queueing Systems 41 (1/2), 45-72.
• MORRISON J. A. (1996), Blocking probabilities for multiple class batched arrivals to a shared resource. Performance Evaluation 25, 131-150.
• 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.
• 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.
• 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.
• 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.
• ONVURAL R. (1990), Survey of closed queuing networks with blocking. Computer Survey 22 (2), 83-121.
• PERROS H. G. (1994,) Queuing Networks with Blocking. Exact and Approximate Solution. Oxford University Press, New York.
• RAMESH S., 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.
• SERENO M. (1999), Mean value analysis of product form solution queueing networks with repetitive service blocking. Performance Evaluation 36- 37, 19-33.
• SHARMA V., VIRTAMO J. T. (2002), A finite buffer queue with priorities. Performance Evaluation 47, 1-22.
• STEWART W. J. (1994), Introduction to the Numerical Solution of Markov Chains. Princeton University Press, New Jersey.
• STRELEN J. CH., BÄRK B., BECKER J., JONAS V. (1998), Analysis of queueing networks with blocking using a new aggregation technique. Annals of Operations Research 79, 121-142.
• TOLIO T., GERSHWIN S. B. (1998), Throughput estimation in cyclic queueing networks with blocking. Annals of Operations Research 79, 207- 229.
• VAN VUUREN M., ADAN I. J. B. F., RESING-SASSEN S. A. E. (2005), Performance analysis of multi-server tandem queues with finite buffers and blocking. OR Spectrum 27, 315-338.
• ZHUANG L., BUZACOTT J. A., LIU X-G. (1994), Approximate mean value performance analysis of cyclic queueing networks with production blocking. Queueing Systems 16, 139-165.
• ZHUANG L. (1996), Acceptance instant distributions in product-form closed queueing networks with blocking. Performance Evaluation 26, 133-144.