pepsy-qns: an efficient tool for solving queueing networks
Kuki Attila,
Sztrik János,
Kossuth Lajos University, Debrecen, Hungary
Günter Bolch,
Friedrich Alexander University, Erlangen, Germany
Abstract
The PEPSY-QNS (Performance Evaluation and Prediction SYstem for Queueing NetworkS) was developed in the 90's at University of Erlangen. It has a very simple and user-friendly interface. So far there has been more than 50 analysing methods built in the system.
PEPSY-QNS consists of the basic system - so called PEPSY - and the graphical XPEPSY. PEPSY consists of three parts that were designed to fit together. This paper demonstrates using of PEPSY on queueing networks and handling different system files eg. input and output data.
An example has been given for calculating the main system characteristics such as throughput, utilization, average response time, average waiting times etc..
1. Introduction
1.1. The problem
If we consider a complex computer system we can observe that the programs are not simply run but compete each oter for the limited resources, eg. CPU, RAM, peripheries etc. The high level of complexity of these systems causes that to achieve an optimal performance is a very difficult task.
A possible solution is using hardware and software monitors in existing systems, but a significant disadvantage of this method is that building a monitor system is an expensive and complex process and it could not be used at the designing and engineering phases. The other method is the modelling. Making some abstractions the considered system may be so simple that it can be handled and investigated easily.
Large number of problems in computer systems and manufacturing systems can efficiently be modelled by the help of queueing systems or queueing networks (see in. [1], [2], [3]).
1.2 Queueing systems
The considered queueing networks consist of one or more nodes with a given structure. The jobs to be served move between these nodes.
The nodes consist of a waiting queue and one or more servers. If an arriving job does not find a free server it joins the queue. The members of this queue will be served by a pre defined serving method. When a job is finished it moves to an other node with a given transition probabilitiy or it leaves the node.
The queueing systems can be described by the help of Kendall notation:
A/B/m-serving principle,
where A is the distribution of arrival times of jobs and B is the distribution of serving times. m is the number of servers.
If the considered distribution is exponential it is denoted by M (Markovian) and in case of general distribution it is denoted by G.
Serving principles can be the followings:
FCFS - First Come First Served,
LCFS - Last Come First Served,
PS - Processzor Sharig,
IS - Infinite Server,
FCFS PRE, (FCFS NONPRE) jobs with higher priority can (can not) interrupt jobs with lower priority,
FCFS ASYM servers works with different serving times.
The M/M/m FCFS, M/G/1 pS, M/G/inf IS and M/G/1 LCFS PRE nodes are called as product form nodes. For queueing networks which consist of only these types of nodes an exact solution can be given.
The network is called open network one if jobs come from outside (with a given intensity) and after visiting the appropriate nodes leave it. In case of closed networks given number of jobs circulate within the network
We can compute the characteristics of a queueing network, eg.
overall throughput,
utilization,
average queue length,
average vaiting times, etc.
by the help of exact and approximate algorithms.
2. A PEPSY-QNS
The PEPSY-QNS (Performance Evaluation and Prediction SYstem for Queueing NetworkS) system was developed at University of Erlangen in the 90’s. There are more than 50 analysing methods built in the system.
A PEPSY-QNS consists of two systems. The first one is the PEPSY basic system, which can be used under UNIX OS and it has three homogenously fitted modules:
- interactive model input,
-
- guided choice of analysing methods,
-
- analysing modul.
-
The second one is the so called XPEPSY which requires graphical interface. The bases of XPEPSY are the modules of PEPSY.
3 The programs of PEPSY-QNS
The main programs of PEPSY-QNS are the followings.
Program 'eingabe' The structure and characteristics of the network be can defined by the help of' 'eingabe'. We can specify
Type of network (open, closed or mixed),
Number of nodes,
Type of nodes (Kendall notations),
Number of job classes,
Arrival rate,
Serving rates,
Quadratic coefficients,
Transition probabilities,
Visiting ratios.
Program 'zusatz' Some analysing methods need further input information which can be given by using of this program.
Program 'auswahl' After definig the network, 'auswahl' lists the applicable analysing methods. The list consists of two parts. There are methods which can be used without specifying any further information and there are ones which require the 'zusatz' program for some additional data
Program 'analyse' This program is the heart of PEPSY-QNS. It solves the problem and generates an output consisting the required system characteristics.
The architecture of the PEPSY system can be seen in Figure 1.
Figure 1 /*system.bmp*/
3.1 An example
Consider the following simple queueing network. It consists of four nodes. The transition probabilities and the structure of nodes can be seen in Figure 2.
Figure 2 /*example.bmp*/
By the help of 'eingabe' the queueing network can be described with the following input file.
# inputfile version 3
#
#
# filename e_angol
#
NUMBER NODES: 4
NUMBER CLASSES: 1
NODE SPECIFICATION
node | name | type
------+------+------
1 | node 1 | M/M/1-FCFS
2 | node 2 | M/G/1-PS
3 | node 3 | M/G/1-PS
4 | node 4 | M/M/1-FCFS
CLASS SPECIFICATION
class | arrival rate number of jobs
------+------
1 | 0.3 -
CLASS SPECIFIC PARAMETERS
CLASS 1
node | service_rate squared_coeff._of_variation
------+------
node 1 | 1 1
node 2 | 2 1
node 3 | 2 1
node 4 | 1 1
SWITCHING PROBABILITIES
from/to | outside node 1 node 2 node 3 node 4
------+------
outside | 0.000000 1.000000 0.000000 0.000000 0.000000
node 1 | 0.000000 0.000000 0.333000 0.500000 0.167000
node 2 | 1.000000 0.000000 0.000000 0.000000 0.000000
node 3 | 1.000000 0.000000 0.000000 0.000000 0.000000
node 4 | 1.000000 0.000000 0.000000 0.000000 0.000000
After definig the network, by the help of 'auswahl' the applicable analysing methods can be listed.
Then the program 'analyse' using the choosen methods (eg. sopenpfn) solves the problem and produces the following output:
PERFORMANCE_INDICES FOR NET: angol
description of the network is in file 'e_angol'
the open net was analysed with method 'sopenpfn' .
jobclass 1
sopenpfn | lambda e 1/mue rho mvz maa mwz mwsl
------+------
node 1 | 0.300 1.000 1.000 0.300 1.429 0.429 0.429 0.129
node 2 | 0.100 0.333 0.500 0.050 0.526 0.053 0.026 0.003
node 3 | 0.150 0.500 0.500 0.075 0.541 0.081 0.041 0.006
node 4 | 0.050 0.167 1.000 0.050 1.053 0.053 0.053 0.003
characteristic indices:
sopenpfn | lambda mvz maa
------+------
| 0.300 2.050 0.615
legend
e : average number of visits mue : service rate
rho : utilisation lambda: mean throughput
mvz : average response time
maa : average number of jobs
mwz : average waiting time
mwsl: average queue-length
4 XPEPSY
XPEPSY is the graphical version of PEPSY. XPEPSY uses the same PEPSY modules and inout/output files.
Modell description can be done in the working area and with dialog boxes.
A screen shot of the working area can be seen in Figure 3.
Figure 3 /*xpepsy.bmp*/
By the help of menu items we can choose the analysing methods and run the analyse program. The output will be provided in the same format as in PEPSY.
References
[1] Bolch G., Greiner S., de Meer H., Trivedi K.S. Queueing Networks and Markov Chains John Wiley & Sons Inc. New York, 1998.
[2] Kleinrock L. Sorbanállás - Kiszolgálás; Bevezetés a tömegkiszolgálási rendszerek elméletébe Műszaki Könyvkiadó Budapest, 1979.
[3] Sztrik J. Bevezetés a sorbanállási elméletbe és alkalmazásaiba Egyetemi jegyzet KLTE Debrecen, 1994.