Semi-Markov-Based Approach for the Analysis of Open Tandem Networks with Blocking and Truncation

Oniszczuk, Walenty

doi:10.2478/v10006-009-0014-6

Abstract

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 non-exponentially distributed with means s^A and s^B, 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 two-dimensional 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.

References

Akyildiz, I.F. (1988). Mean value analysis for blocking queuing networks, IEEE Transactions on Software Engineering 14(4): 418-428.10.1109/32.4663
Search in Google Scholar
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.10.1007/BF02023094
Search in Google Scholar
Balsamo, S., de Nito Persone, V. and Onvural, R. (2001). Analysis of Queueing Networks with Blocking, Kluwer Academic Publishers, Boston, MA.10.1007/978-1-4757-3345-7
Search in Google Scholar
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.10.1016/S0166-5316(02)00099-8
Search in Google Scholar
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.
Search in Google Scholar
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.10.1016/S0166-5316(96)00045-4
Search in Google Scholar
Bouhchouch, A., Frein, Y. and Dallery, Y. (1996). Performance evaluation of closed tandem queueing networks, Performance Evaluation 26: 115-132.10.1016/0166-5316(95)00022-4
Search in Google Scholar
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.
Search in Google Scholar
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.1016/j.peva.2004.10.007
Search in Google Scholar
Clo, M.C. (1998). MVA for product-form cyclic queueing networks with blocking, Annals of Operations Research 79: 83-96.
Search in Google Scholar
Economou, A. and Fakinos, D. (1998). Product form stationary distributions for queueing networks with blocking and rerouting, Queueing Systems 30(3/4): 251-260.10.1023/A:1019117121530
Search in Google Scholar
Gomez-Corral, A. (2002). A tandem queue with blocking and Markovian arrival process, Queueing Systems 41(4): 343-370.10.1023/A:1016235415066
Search in Google Scholar
Heindl, A. (2003). Decomposition of general queueing networks with MMPP inputs and customer losses, Performance Evaluation 51(2-4): 117-136.10.1016/S0166-5316(02)00091-3
Search in Google Scholar
Kaufman, J.S. and Rege, K.M. (1996). Blocking in a shared resource environment with batched arrival processes, Performance Evaluation 24(4): 249-263.10.1016/0166-5316(94)00029-8
Search in Google Scholar
Korolyuk, V.S. and Korolyuk, V.V. (1999). Stochastic Models of Systems, Kluwer Academic Publishers, Dordrecht.10.1007/978-94-011-4625-8
Search in Google Scholar
Kouvatsos, D. and Almond, J. (1988). Maximum entropy two-station cyclic queues with multiple general servers, Acta Informatica 26(3): 241-267.10.1007/BF00299634
Search in Google Scholar
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.10.1016/S1389-1286(00)00099-2
Search in Google Scholar
Martin, J.B. (2002). Large tandem queueing networks with blocking, Queueing Systems 41(1/2): 45-72.10.1023/A:1015729701521
Search in Google Scholar
Morrison, J.A. (1996). Blocking probabilities for multiple class batched arrivals to a shared resource, Performance Evaluation 25(2): 131-150.10.1016/0166-5316(94)00042-5
Search in Google Scholar
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.10.1007/978-0-387-36503-9_24
Search in Google Scholar
Onvural, R. (1990). Survey of closed queuing networks with blocking, Computer Survey 22(2): 83-121.10.1145/78919.78920
Search in Google Scholar
Perros, H.G. (1994). Queuing Networks with Blocking. Exact and Approximate Solution, Oxford University Press, New York, NY.
Search in Google Scholar
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.10.1023/A:1018932108865
Search in Google Scholar
Sereno, M. (1999). Mean value analysis of product form solution queueing networks with repetitive service blocking, Performance Evaluation 36-37(1): 19-33.10.1016/S0166-5316(99)00038-3
Search in Google Scholar
Sharma, V. and Virtamo, J.T. (2002). A finite buffer queue with priorities, Performance Evaluation 47(1): 1-22.10.1016/S0166-5316(01)00053-0
Search in Google Scholar
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.10.1023/A:1018914503645
Search in Google Scholar
Tolio, T. and Gershwin, S.B. (1998). Throughput estimation in cyclic queueing networks with blocking, Annals of Operations Research 79(0): 207-229.10.1023/A:1018970621392
Search in Google Scholar
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.10.1007/BF01158953
Search in Google Scholar
Zhuang, L. (1996). Acceptance instant distributions in product-form closed queueing networks with blocking, Performance Evaluation 26(2): 133-144.10.1016/0166-5316(95)00003-8
Search in Google Scholar

Semi-Markov-Based Approach for the Analysis of Open Tandem Networks with Blocking and Truncation

Abstract

Paradigm

My account