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

Oniszczuk, W.

International Journal of Applied Mathematics and Computer Science, Tome 19 (2009) no. 1, pp. 151-163.

Résumé

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.

Détail

Keywords: two-node network, blocking, truncation, semi-Markov model, Markov exact algorithm
Mots-clés : sieć komputerowa, blokowanie, obcinanie, model semi-Markova

Bibliographie

[1] Akyildiz, I.F. (1988). Mean value analysis for blocking queuing networks, IEEE Transactions on Software Engineering 14(4): 418-428.

[2] 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.

[3] Balsamo, S., de Nito Persone, V. and Onvural, R. (2001). Analysis of Queueing Networks with Blocking, Kluwer Academic Publishers, Boston, MA.

[4] 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.

[5] 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.

[6] 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.

[7] Bouhchouch, A., Frein, Y. and Dallery, Y. (1996). Performance evaluation of closed tandem queueing networks, Performance Evaluation 26: 115-132.

[8] 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.

[9] 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.

[10] Clo, M.C. (1998). MVA for product-form cyclic queueing networks with blocking, Annals of Operations Research 79: 83-96.

[11] Economou, A. and Fakinos, D. (1998). Product form stationary distributions for queueing networks with blocking and rerouting, Queueing Systems 30(3/4): 251-260.

[12] Gomez-Corral, A. (2002). A tandem queue with blocking and Markovian arrival process, Queueing Systems 41(4): 343-370.

[13] Heindl, A. (2003). Decomposition of general queueing networks with MMPP inputs and customer losses, Performance Evaluation 51(2-4): 117-136.

[14] Kaufman, J.S. and Rege, K.M. (1996). Blocking in a shared resource environment with batched arrival processes, Performance Evaluation 24(4): 249-263.

[15] Korolyuk, V.S. and Korolyuk, V.V. (1999). Stochastic Models of Systems, Kluwer Academic Publishers, Dordrecht.

[16] Kouvatsos, D. and Almond, J. (1988). Maximum entropy twostation cyclic queues with multiple general servers, Acta Informatica 26(3): 241-267.

[17] 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.

[18] Martin, J.B. (2002). Large tandem queueing networks with blocking, Queueing Systems 41(1/2): 45-72.

[19] Morrison, J.A. (1996). Blocking probabilities for multiple class batched arrivals to a shared resource, Performance Evaluation 25(2): 131-150.

[20] 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.

[21] Onvural, R. (1990). Survey of closed queuing networks with blocking, Computer Survey 22(2): 83-121.

[22] Perros, H.G. (1994). Queuing Networks with Blocking. Exact and Approximate Solution, Oxford University Press, New York, NY.

[23] 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.

[24] Sereno, M. (1999). Mean value analysis of product form solution queueing networks with repetitive service blocking, Performance Evaluation 36-37(1): 19-33.

[25] Sharma, V. and Virtamo, J.T. (2002). A finite buffer queue with priorities, Performance Evaluation 47(1): 1-22.

[26] 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.

[27] Tolio, T. and Gershwin, S.B. (1998). Throughput estimation in cyclic queueing networks with blocking, Annals of Operations Research 79(0): 207-229.

[28] 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.

[29] Zhuang, L. (1996). Acceptance instant distributions in productform closed queueing networks with blocking, Performance Evaluation 26(2): 133-144.