Semi-Markov-based approach for the analysis of open tandem networks with blocking and truncation

• Autorzy: Walenty Oniszczuk
• Języki publikacji: EN

Abstrakty

EN

This paper describes an analytical study of open two-node (tandem) network models with blocking and truncation. The study is based on semi-Markov process theory, and network models assume that multiple servers serve each queue. Tasks arrive at the tandem in a Poisson fashion at the rate λ, and the service times at the first and the second node are nonexponentially distributed with means sA and sB , respectively. Both nodes have buffers with finite capacities. In this type of network, if the second buffer is full, the accumulation of new tasks by the second node is temporarily suspended (a blocking factor) and tasks must wait on the first node until the transmission process is resumed. All new tasks that find the first buffer full are turned away and are lost (a truncation factor). First, a Markov model of the tandem is investigated. Here, a twodimensional state graph is constructed and a set of steady-state equations is created. These equations allow calculating state probabilities for each graph state. A special algorithm for transforming the Markov model into a semi-Markov process is presented. This approach allows calculating steady-state probabilities in the semi-Markov model. Next, the algorithms for calculating the main measures of effectiveness in the semi-Markov model are presented. In the numerical part of this paper, the author investigates examples of several semi-Markov models. Finally, the results of calculating both the main measures of effectiveness and quality of service (QoS) parameters are presented.

Słowa kluczowe

EN

two-node network with blocking and truncation; semi-Markov model; Markov exact algorithm

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2009
• Tom: 19
• Numer: 1
• Strony: 151-163

Daty

wydano

2009

otrzymano

2007-06-14

Twórcy

autor

Walenty Oniszczuk

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

Bibliografia

• Akyildiz, I.F. (1988). Mean value analysis for blocking queuing networks, IEEE Transactions on Software Engineering 14(4): 418-428.
• Balsamo, S. and 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 Nito Persone, V. and Onvural, R. (2001). Analysis of Queueing Networks with Blocking, Kluwer Academic Publishers, Boston, MA.
• Balsamo, S., de Nito 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.
• Badrah, A., Czachórski, T., Domańska, 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.
• 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.
• Bouhchouch, A., Frein, Y. and Dallery, Y. (1996). Performance evaluation of closed tandem queueing networks, Performance Evaluation 26: 115-132.
• Bradley, J.T. and Davies, N.J. (2000). A matrix-based method for analysing stochastic process algebras, Proceedings of the 8-th International Workshop on Process Algebra and Performance Modelling, ICALP Workshops, PAPM'00, Geneva, Switzerland, pp. 579-590.
• Bradley, J.T. and Wilson, H.J. (2005). Iterative convergence of passage-time densities in semi-Markov performance models, Performance Evaluation 60(1-4): 237-254.
• Clo, M.C. (1998). MVA for product-form cyclic queueing networks with blocking, Annals of Operations Research 79: 83-96.
• Economou, A. and Fakinos, D. (1998). Product form stationary distributions for queueing networks with blocking and rerouting, Queueing Systems 30(3/4): 251-260.
• Gomez-Corral, A. (2002). A tandem queue with blocking and Markovian arrival process, Queueing Systems 41(4): 343-370.
• Heindl, A. (2003). Decomposition of general queueing networks with MMPP inputs and customer losses, Performance Evaluation 51(2-4): 117-136.
• Kaufman, J.S. and Rege, K.M. (1996). Blocking in a shared resource environment with batched arrival processes, Performance Evaluation 24(4): 249-263.
• Korolyuk, V.S. and Korolyuk, V.V. (1999). Stochastic Models of Systems, Kluwer Academic Publishers, Dordrecht.
• Kouvatsos, D. and Almond, J. (1988). Maximum entropy twostation cyclic queues with multiple general servers, Acta Informatica 26(3): 241-267.
• Kouvatsos, D.D., Awan, I.U., Fretwell, R.J. and Dimakopoulos, G. (2000). A cost-effective approximation for SRD traffic in arbitrary multi-buffered networks, Computer Networks 34(1):97-113.
• 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(2): 131-150.
• Oniszczuk, W. (2006). Tandem models with blocking in the computer subnetworks performance analysis, in K. Saeed, J. Pejaś and R. Mosdorf (Eds.), Biometrics, Computer Security Systems and Artificial Intelligence Applications, Springer, New York, NY, pp. 259-267.
• 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, NY.
• 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.
• Sereno, M. (1999). Mean value analysis of product form solution queueing networks with repetitive service blocking, Performance Evaluation 36-37(1): 19-33.
• Sharma, V. and Virtamo, J.T. (2002). A finite buffer queue with priorities, Performance Evaluation 47(1): 1-22.
• Strelen, J.Ch., Bärk, B., Becker, J. and Jonas, V. (1998). Analysis of queueing networks with blocking using a new aggregation technique, Annals of Operations Research 79(0): 121-142.
• Tolio, T. and Gershwin, S.B. (1998). Throughput estimation in cyclic queueing networks with blocking, Annals of Operations Research 79(0): 207-229.
• 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(1-2): 139-165.
• Zhuang, L. (1996). Acceptance instant distributions in productform closed queueing networks with blocking, Performance Evaluation 26(2): 133-144.

Identyfikatory

DOI

10.2478/v10006-009-0014-6