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

Walenty Oniszczuk

International Journal of Applied Mathematics and Computer Science (2009)

  • Volume: 19, Issue: 1, page 151-163
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Walenty Oniszczuk. "Semi-Markov-based approach for the analysis of open tandem networks with blocking and truncation." International Journal of Applied Mathematics and Computer Science 19.1 (2009): 151-163. <http://eudml.org/doc/207916>.

@article{WalentyOniszczuk2009,
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 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.},
author = {Walenty Oniszczuk},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {two-node network with blocking and truncation; semi-Markov model; Markov exact algorithm},
language = {eng},
number = {1},
pages = {151-163},
title = {Semi-Markov-based approach for the analysis of open tandem networks with blocking and truncation},
url = {http://eudml.org/doc/207916},
volume = {19},
year = {2009},
}

TY - JOUR
AU - Walenty Oniszczuk
TI - Semi-Markov-based approach for the analysis of open tandem networks with blocking and truncation
JO - International Journal of Applied Mathematics and Computer Science
PY - 2009
VL - 19
IS - 1
SP - 151
EP - 163
AB - 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.
LA - eng
KW - two-node network with blocking and truncation; semi-Markov model; Markov exact algorithm
UR - http://eudml.org/doc/207916
ER -

References

top
  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. Zbl0790.90037
  3. Balsamo, S., de Nito Persone, V. and Onvural, R. (2001). Analysis of Queueing Networks with Blocking, Kluwer Academic Publishers, Boston, MA. Zbl0977.68007
  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. Zbl0900.68051
  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. Zbl0903.90063
  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. Zbl0919.90064
  12. Gomez-Corral, A. (2002). A tandem queue with blocking and Markovian arrival process, Queueing Systems 41(4): 343-370. Zbl0993.90024
  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. Zbl0875.90307
  15. Korolyuk, V.S. and Korolyuk, V.V. (1999). Stochastic Models of Systems, Kluwer Academic Publishers, Dordrecht. Zbl0960.60004
  16. Kouvatsos, D. and Almond, J. (1988). Maximum entropy twostation cyclic queues with multiple general servers, Acta Informatica 26(3): 241-267. Zbl0634.90022
  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. Zbl1053.60098
  19. Morrison, J.A. (1996). Blocking probabilities for multiple class batched arrivals to a shared resource, Performance Evaluation 25(2): 131-150. Zbl0875.68259
  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. Zbl0849.90064
  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. Zbl0946.90004
  24. Sereno, M. (1999). Mean value analysis of product form solution queueing networks with repetitive service blocking, Performance Evaluation 36-37(1): 19-33. Zbl1051.68530
  25. Sharma, V. and Virtamo, J.T. (2002). A finite buffer queue with priorities, Performance Evaluation 47(1): 1-22. Zbl1013.68040
  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. Zbl0895.90094
  27. Tolio, T. and Gershwin, S.B. (1998). Throughput estimation in cyclic queueing networks with blocking, Annals of Operations Research 79(0): 207-229. Zbl0899.90089
  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. Zbl0794.60094
  29. Zhuang, L. (1996). Acceptance instant distributions in productform closed queueing networks with blocking, Performance Evaluation 26(2): 133-144. Zbl0875.68108

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.