Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-08T07:32:29.174Z Has data issue: false hasContentIssue false
  • English
  • Français

THROUGHPUT AND BOTTLENECK ANALYSIS OF TANDEM QUEUES WITH NESTED SESSIONS

Published online by Cambridge University Press:  05 June 2017

A. Hristov ,
J.W. Bosman ,
R.D. van der Mei  and
S. Bhulai
A. Hristov
Affiliation:
CWI, Stochastics, Science Park 123, 1098XG Amsterdam, The Netherlands and Department of Mathematics, Faculty of Sciences, Vrije Universiteit Amsterdam, 1081HV AmsterdamThe Netherlands E-mail: [email protected]; [email protected]; [email protected]; [email protected]
J.W. Bosman
Affiliation:
CWI, Stochastics, Science Park 123, 1098XG Amsterdam, The Netherlands and Department of Mathematics, Faculty of Sciences, Vrije Universiteit Amsterdam, 1081HV AmsterdamThe Netherlands E-mail: [email protected]; [email protected]; [email protected]; [email protected]
R.D. van der Mei
Affiliation:
CWI, Stochastics, Science Park 123, 1098XG Amsterdam, The Netherlands and Department of Mathematics, Faculty of Sciences, Vrije Universiteit Amsterdam, 1081HV AmsterdamThe Netherlands E-mail: [email protected]; [email protected]; [email protected]; [email protected]
S. Bhulai
Affiliation:
CWI, Stochastics, Science Park 123, 1098XG Amsterdam, The Netherlands and Department of Mathematics, Faculty of Sciences, Vrije Universiteit Amsterdam, 1081HV AmsterdamThe Netherlands E-mail: [email protected]; [email protected]; [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Various types of systems across a broad range of disciplines contain tandem queues with nested sessions. Strong dependence between the servers has proved to make such networks complicated and difficult to study. Exact analysis is in most of the cases intractable. Moreover, even when performance metrics such as the saturation throughput and the utilization rates of the servers are known, determining the limiting factor of such a network can be far from trivial. In our work, we present a simple, tractable and nevertheless relatively accurate method for approximating the above mentioned performance measurements for any server in a given network. In addition, we propose an extension to the intuitive “slowest server rule” for identification of the bottleneck, and show through extensive numerical experiments that this method works very well.

Keywords

bottleneck identificationlayered queueing networknested sessionsperformance analysistandem queuethroughput
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 32 , Issue 3 , July 2018 , pp. 396 - 408
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Bard, Y. (1979). Some extensions to multiclass queueing network analysis. In Proceedings of the 3rd International Symposium on Modelling and Performance Evaluation of Computer Systems, pp. 51–62.Google Scholar
2.Blanc, J.P.C. (1993). Performance evaluation of computer and communication systems, Lecture notes in Computer Science, chapter – Performance analysis and optimization with the power-series algorithm. Berlin, Heidelberg: Springer, pp. 53–80.Google Scholar
3.Buitenhek, R., van Houtum, G.J.J.A.N., & Zijm, H. (2000). AMVA-based solution procedures for open queueing networks with population constraints. Annals of Operations Research 93: 15–40.Google Scholar
4.Chandy, K.M. & Neuse, D. (1982). Linearizer: A heuristic algorithm for queueing network models of computing systems. Communications of the ACM 25: 126–134.Google Scholar
5.Dorsman, J.L., Perel, N., & Vlasiou, M. (2016). Server waiting times in infinite supply polling systems with preparation times. Probability in the Engineering and Informational Sciences 30(2): 153–184.Google Scholar
6.Dorsman, J.L., van der Mei, R.D., & Vlasiou, M. (2013). Analysis of a two-layered network by means of the power-series algorithm. Performance Evaluation 70: 1072–1089.Google Scholar
7.Franks, G., Al-Omari, T., Woodside, M., Das, O., & Derisavi, S. (2009). Enhanced modeling and solution of layered queueing networks. IEEE Transactions on Software Engineering 35(2): 148–161.Google Scholar
8.Franks, G., Petriu, D., Woodside, M., Xu, J., & Tregunno, P. (2006). Layered bottlenecks and their mitigation. In Proceedings of the 3rd International Conference on the Quantitative Evaluation of Systems (QEST ’06), pp. 103–114. IEEE Computer Society.Google Scholar
9.Herzog, U. & Rolia, J.A. (2001). Performance validation tools for software/hardware systems. Performance Evaluation 45: 125–146.Google Scholar
10.Neuts, M.F. (1981). Matrix-geometric solutions in stochastic models: an algorithmic approach. Baltimore: Johns Hopkins University Press.Google Scholar
11.Perel, E. & Yechiali, U. (2008). Queues where customers of one queue act as servers of the other queue. Queueing Systems 60: 271–288.Google Scholar
12.Perel, E. & Yechiali, U. (2013). On customers acting as servers. Asia-Pacific Journal of Operational Research 30: 1–23.Google Scholar
13.Perel, E. & Yechiali, U. (2016). Finite two layered queueing systems. Probability in the Engineering and Informational Sciences 30(3): 492–513.Google Scholar
14.Reiser, M. & Lavenberg, S.S. (1980). Mean-value analysis of closed multichain queuing networks. Journal of the ACM 27: 313–322.Google Scholar
15.Rolia, J.A. & Sevcik, K.C. (1995). The method of layers. IEEE Transactions on Software Engineering 21(8): 689–700.Google Scholar
16.Roser, C., Nakano, M., & Tanaka, M. (2001). A practical bottleneck detection method. In Proceedings of the 33rd Conference on Winter Simulation (WSC ’01), pp. 949–953. IEEE Computer Society.Google Scholar
17.Schweitzer, P.J. (1979). Approximate analysis of multiclass closed networks of queues. In Proceedings of the International Conference on Stochastic Control and Optimization, pp. 25–29.Google Scholar
18.Shousha, C., Petriu, D.C., Jalnapurkar, A., & Ngo, K. (1998). Applying performance modelling to a telecommunication system. In Proceedings of the 1st International Workshop of Software and Performance, pp. 1–6.Google Scholar
19.Tregunno, P. (2003). Practical analysis of software bottlenecks. Master's thesis, Department of Systems and Computer Engineering, Carleton University.Google Scholar
20.Tribastone, M. (2010). Relating layered queueing networks and process algebra models. In Proceedings of the 1st Joint WOSP/SIPEW International Conference on Performance Engineering, pp. 183–194.Google Scholar
21.Tribastone, M. (2013). A fluid model for layered queueing networks. IEEE Transactions on Software Engineering 39(6): 744–756.Google Scholar
22.Woodsode, C.M., Neilson, J.E., Petriu, D.C., & Majumdar, S. (1995). The stochastic rendezvous network model for performance of synchronous client-server-like distributed software. IEEE Transactions on Computers 44: 20–34.Google Scholar
23.Yom-Tov, G. & Mandelbaum, A. (2008). Queues in hospitals: Semi-open queueing networks in the qed regime. Technical report, Technion, Israeli Institute of Technology.Google Scholar