The importance and complexity of modern IT systems increased in the last decades. To ensure resource efficiency and Quality-of-Service demands, performance evaluation is useful at every stage in the life cycle of an IT system. Simulation-based performance analysis has a wide application, but computational costs grow the more complex the system of interest gets.
However, analytical methods have a relatively high accuracy in the performance measures and in efficiency, so results can often be computed significantly faster. This thesis focuses on basic queueing theory. To represent complex IT systems Queueing Network models have been extensively applied. Possibilities and limitations of mapping basic queueing formulas on Queueing Network models are presented by using theoretical knowledge and practical comparison of a self-developed analysis tool with a simulation tool. Deviations in performance measures and savings on computational costs of the analytical solver are shown and by this the usefulness of analytical procedures will be underlined exemplarily.
Abstract
The importance and complexity of modern IT systems increased in the last decades. To ensure resource efficiency and Quality-of-Service demands, performance evaluation is useful at every stage in the life cycle of an IT system. Simulation-based performance analysis has a wide application, but computational costs grow the more complex the system of interest gets. However analytical methods have a relatively high accuracy in the performance measures and in efficiency, so results can often be computed significantly faster. This thesis focuses on basic queueing theory. To represent complex IT systems Queueing Network models have been extensively applied. Possibilities and limitations of mapping basic queueing formulas on Queueing Network models are presented by using theoretical knowledge and practical comparison of a self-developed analysis tool with a simulation tool. Deviations in performance measures and savings on computational costs of the analytical solver are shown and by this the usefulness of analytical procedures will be underlined exemplarily.
Zusammenfassung
Die Bedeutung und Komplexit¨at moderner IT-Systeme ist in den letzten Jahrzehnten deutlich angestiegen. Um effiziente Nutzung von Ressourcen und Quality-of-Service Anforderungen zu gew¨ahrleisten, ist eine Leistungsbewertung in jedem Lebenszyklus eines IT-Systems nu¨tzlich. Simulationsbasierte Werkzeuge zur Leistungsbewertung haben ein breites Anwendungsgebiet, jedoch k¨onnen die Rechenkosten steigen, je komplexer das zu bewertende System wird. Analytische Methoden sind hingegen sowohl relativ genau wie auch effizient, daher ist ein analytisches Verfahren h¨aufig deutlich schneller. Der Fokus dieser Arbeit liegt auf grundlegenden Erkenntnissen der Warteschlangentheorie. Um komplexe IT-Systeme abzubilden, sind Modelle aus Warteschlangennetzwerken umfassend zum Einsatz gekommen. M ¨oglichkeiten und Grenzen der Anwendung grundlegender Warteschlangenformeln auf Warteschlangennetzwerke werden mit Hilfe von theoretischen Erkenntnissen und praktischen Vergleichen eines selbst entwickelten analytischen Werkzeugs mit einem Simulationswerkzeug pr¨asentiert. Abweichungen der Leistungskennzahlen und Einsparungen an Rechenkosten des analytischen Werkzeugs werden dargestellt und damit der Nutzen analytischer Verfahren exemplarisch unterstrichen.
Contents
1 Introduction.. 1
2 Foundation.. 3
2.1 Queues.. 3
2.2 Queueing Networks.. 5
2.3 Solving System-Level Performance Models.. 6
2.3.1 Performance Measures and Typical Assumptions.. 6
2.3.2 Generalized System-Level Model.. 7
3 Goals and Approach.. 9
3.1 Goals.. 9
3.2 Approach.. 9
4 Markovian Queue Solver.. 13
4.1 Performance Formulas of Markovian Queues.. 13
4.1.1 M/M/1 Queue.. 15
4.1.2 M/M/m Queue.. 16
4.1.3 M/M/1/∞/N Queue.. 17
4.1.4 M/M/m/∞/N Queue.. 18
4.1.5 M/M/1/K Queue.. 19
4.1.6 M/M/m/K Queue.. 20
4.1.7 M/M/1/K/N Queue.. 21
4.1.8 M/M/m/K/N Queue.. 22
4.2 Implementation.. 22
5 Mapping Performance Formulas of Markovian Queues on Queueing Networks.. 25
5.1 Open Queueing Networks.. 26
5.1.1 Queueing Networks with Tandem Topology.. 26
5.1.2 Queueing Networks with Routing Probabilities.. 27
5.1.3 Summary.. 28
5.2 Closed Queueing Networks.. 29
5.2.1 Discussion of Applicability of Basic Queueing Formulas.. 29
5.2.2 Overview of Algorithms for Product-Form Queueing Networks.. 30
6 Evaluation.. 33
6.1 Performance Measures of Queues.. 33
6.2 Performance Measures of Queueing Networks.. 36
6.3 Savings in Computational Costs.. 38
7 Conclusion.. 41
Bibliography.. 45
8 Appendix.. 47
1. Introduction
At the beginning of the 21st century computers are omnipresent and widely accepted in both professional and private sectors. The importance and complexity of modern IT systems grew in the last decades. For example, factors such as globalization and outsourcing have led to an increased demand of companies for an effectual IT system and environment. In this context it is significant to ensure resource efficiency and Quality-of-Service demands. A main goal of computer system designers, administrators and users is to obtain or provide a high performance at a low cost. To reach that goal, performance evaluation is useful at every stage in the life cycle of a computer system, e.g. when new systems are designed or existing systems are optimized (reconfiguration, update) or adapted to new environments. The more complex the systems and relations are, the more difficult but also the more important is the analyze. Besides constructing models of IT systems performance prediction analysis is very valuable to finally evaluate these models.
To represent IT systems with a large number of resources, Queueing Network models have been extensively applied. A lot of research has shown that these models are robust and versatile for performance evaluation and prediction. Basic queueing systems were first introduced to study congestion in telephonic system by one service center and then it was extended to analyze congestion in computer and communication systems (cf. [Bal00]). Queueing Network models consist of basic queueing systems. The models are composed of interconnected and interacting service centers/resources and are ideal for mapping modern IT systems. To get performance predictions, several assumptions for Queueing Networks (e.g. for the class of product-form QNs) might be necessary, but they have been recognized to be very powerful models by different researchers.
The analysis of performance models such as Queueing Networks can either be simulation-based or analytical-based. Both approaches share differences, advantages as well as disadvantages. In simulations as well as in analytical processes the input parameters are measured or invented. Simulations are general and have a wide application, while analytical methods, which are based on mathematical relationships, have a set of assumptions and limitations. On the other hand computational costs of simulations grow the more complex the system of interest gets. The big advantage of analytical approaches however is the significantly lower computational costs. E.g. the necessary time to get a result from a simulation is often much longer than by using an analytical formula. Analytical methods have a relatively high accuracy in the performance measures and in efficiency. In cases where computer system designers or administrators want to find the best design or system, they have to compare a number of alternatives, so an analytical tool may be more suitable.
This thesis focuses on an analytical solution of performance metrics. Basic queueing theory formulas are considered because performance results can be computed very fast by them. Possibilities and limitations of mapping the basic formulas on Queueing Network models are presented by using theoretical knowledge and practical comparison of a self-developed analysis tool with an existing simulation tool. Deviations in performance metrics and savings on computational costs of the analytical solver in contrast to a simulation tool are shown and by this the usefulness of analytical procedures will be underlined exemplarily.
The remainder of this paper is divided into six sections. Chapter 2 describes the foundation of this thesis, where queues, Queueing Networks and the solution possibility for system-level performance models are shown. Chapter 3 gives an overview of the main goals and the approach of this paper. In chapter 4 basic queueing formulas are derived and a self-developed tool for solving performance measures of queueing models by analytical formulas is presented. The possibility and the way of mapping basic performance formulas on Queueing Networks is discussed in chapter 5 on a theoretical level. The evaluation of the self-developed solving tool in chapter 6 has a practical aspect. Performance results of the analytical tool and a simulation tool as well as time savings of the analytical procedure are illustrated there. Chapter 7 provides some conclusions and directions for future work.
2. Foundation
This Chapter introduces fundamental concepts and models. Queueing models are described in section 2.1 and afterwards Queueing Networks in section 2.2. Solving system-level performance models is discussed in section 2.3.
2.1 Queues
A queue model is a resource model e.g. of a CPU or disk represented by a waiting line, a service station of one or more servers (single or multiple servers), an arrival and a service process and a scheduling discipline (cf. figure 2.1). The waiting line is a buffer space for waiting elements such as database transactions, batch jobs and different requests called customers. When a server is free, the next customer according to the scheduling discipline will be processed. The scheduling discipline orders which customers are served next at the service station. There are several types, only typical ones will be explained below (cf. [MADD04] and [ Kou05]).
[Figures and tables are omitted from this preview.]
Figure 2.1: single queue with one server
• FCFS/FIFO (First-Come-First-Served / First-In-First-Out): Customers are served in the same order they arrived in.
• LCFS/LIFO (Last-Come-First-Served / Last-In-First-Out): Customers are served in the reverse order they arrived in.
• SIRO (Service-In-Random-Order): Customers are served in a random order independent of the order they arrived in.
• PNPN (Priority Service): Customers with the highest priority are served next. FCFS is used, when the priority is equal. Many variations are possible: static vs. dynamic priorities (priority does not change vs. change with time), preemptive (arrival customer of higher priority directly seize a server which is busy by a lower prioritized customer) vs. non-preemptive.
• RR (Round-Robin): Customers get equal time slices of a defined length and are served according to FCFS.
• PS (Process Sharing): All customers are served simultaneously and the server speed is divided similarly among them. This discipline is like RR but with infinitesimally small time slices.
Moreover, resources/service stations can be grouped in three different types (cf. [MADD04], p. 46):
• Load-independent (LI): Service rate of the resource is constant independent of the load (i.e. number of customers in the queue). Resources such as CPUs and disks are usually load-independent.
• Load-dependant (LD): Service rate is dependant of the load and can be represented by the number of customers in the queue. The service rate can both increase or decrease (depending on the resource) as the number of requests grows.
• Delay (D): Customers are served immediately so there is no waiting line.
Usually Kendall’s notation is used to classify a single queueing node by an A/S/m notation which can also be extended to A/S/m/K/N/D (cf. [Kou05]).
• A describes the arrival process (request inter-arrival time distribution).
• S describes the service process (request service time distribution).
• m is the number of servers in the queue.
• K describes the capacity or the maximum number of customers allowed in the queue (incl. those in servers). The number can be limited (finite queue size) but also unlimited (infinite queue size). In the latter case no argument is needed.
• N describes the population size or the maximum allowed number of customers that can arrive in the system. The population size can be limited (finite population size) as well as unlimited (infinite population size). In the latter case no argument is needed.
• D describes the scheduling discipline. For FCFS no argument is needed. Some possible distributions for the arrival and service processes are:
• M (Markovian) for Poisson or exponential distribution
• D for deterministic (constant) distribution
• Ek for Erlang distribution with scale parameter k
• Ck for Coxian distribution with scale parameter k
• G for general distribution
For example a M/M/1 queue describes a resource with exponentially distributed arrival and service processes. Moreover the queue has a single server, no limitations in capacity and population size and the scheduling discipline is FCF.
2.2 Queueing Networks
A Queueing Network (QN) is defined as a collection of interconnected queues, which describes an IT system (cf. figure 2.2). Customers move between the queues on a path until they complete their execution. According to their different behaviours, they are often grouped into customer classes, which can either be open or closed.
[Figures and tables are omitted from this preview.]
Figure 2.2: Example of a Queueing Network
Customers of an open class arrive from an external source, get served in the QN and depart. The main characteristic is the unbounded population size. The workload is described by an arrival rate. Customers of a closed class do not arrive from an external source and do not depart from the QN but they circulate in the network. Closed classes have a bounded and known number of customers in the system (finite population) and their workload is described by the population size and a think time. In an open QN all customer classes are open, in a closed QN all customer classes are closed and in a mixed QN there are closed and open customer classes.
The network topology describes how the queues are interconnected and how the customers move between them. In figure 2.3 (a) the QN is open and the network topology is tandem, in (b) the QN is closed and the network topology is cyclic. In (c) the QN is also closed and the network topology is central server, where p is the probability that a customer moves to the displayed queue after getting served by the central server queue. The sum of all probabilities have to be one. See [Bal00] for more details.
[Figures and tables are omitted from this preview.]
Figure 2.3: Example of queueing network topologies
QNs are often distinguished in product-form and non-product-form, since product-form QNs are easier to analyse. To calculate performance measures of QNs, system steady-state probabilities are to be considered. If the solution of the steady-state probabilities can be expressed as a product of factors describing the state of each queue of a Queueing Network, it is called to be product-form. In other words, product-form Queueing Networks have a simple expression of the stationary state distribution. These QNs have a special structure. Efficient algorithms to evaluate average performance measures were defined for them. The most famous result of product-form QNs is the BCMP theorem (presented by Baskett, Chandy, Muntz and Palacios in 1975). It defined a class of BCMP queueing networks with product-form solutions for open, closed and mixed models with multiple classes of jobs, various service disciplines and service time distributions (cf. [Bal00]). For more information see [Ste09] pp. 598.
[...]
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.