Starting from version 1.0.0, the queueing
package
(formely known as qnetworks toolbox) is included in
Octave-Forge. This has many benefits for the users. Installation
is much easier: you can type pkg install -forge queueing
at the Octave prompt to install the package without the need to
download anything by hand. Moreover, all new development happens on
the Subversion
repository on SourceForge, so developers can get the
latest/greatest version of the queueing
package without
waiting for an official stable release.
queueing-1.2.3
has been released. This release includes new features; see the ChangeLog for details.queueing-1.2.2
has been released. This is a bug fix release. See the ChangeLog for details.queueing-1.2.1
has been released. This version includes new features. See the ChangeLog for details.queueing-1.2.0
has been released. This version includes many bug fixes and new features. See the ChangeLog for details.queueing-1.1.1
has been released. This version fixes some spurious errors raised by the embedded test blocks. See the ChangeLog for details.queueing-1.1.0
has been released! This is a major improvement over the previous version, and includes many new functions for Markov chain analysis; see the ChangeLog for details.The queueing
package is a software package for
queueing networks and Markov chains analysis written in GNU Octave. The package
currently includes the following algorithms:
The queueing
package requires some knowledge of
queueing theory; furthermore, it (currently) does not include a GUI
for interactively draw queueing networks. See the additional Resources below for a (non
comprehensive) list of software packages for queueing networks
analysis.
The queueing
package is under active
development. New versions are released frequently.
queueing
is released WITHOUT ANY WARRANTY, see the file
COPYING for details.
I developed the queueing
package to support my own
research, and I am releasing it in the hope it can be useful to
others. If you use the queueing
package for teaching or
research purposes, I would like to hear about your experience with
it.
queueing
package source files using subversion:svn checkout svn://svn.code.sf.net/p/octave/code/trunk/octave-forge/main/queueing queueing
Note that there is no binary distribution, as
queueing
is entirely implemented as Octave scripts;
therefore, queueing
should run on any system where GNU
Octave has been ported.
queueing
is released under the GNU General Public
License, version 3 or later. See the file COPYING for details; this file is also included in
the software distribution.
The user manual is available in the following formats:
If you use this package in some published work, please cite it as follows:
Other publications:
qnetworks
Toolbox: A
Software Package for Queueing Networks Analysis, Technical
Report UBLCS-2010-04,
Department of Computer Science, University of Bologna, Italy, February
2010queueing
package directly from the Octave
prompt:
pkg install -forge queueing
pkg install -forge -local queueing
pkg load queueing
.octaverc
on Linux) to automatically load queueing
when Octave starts.
-forge
option is not recognized, you need to
manually download the installation tarball from the package
Octave-Forge page and type the following at the Octave prompt:
pkg install queueing-1.2.3.tar.gz
pkg load queueing
.m
files from the inst/
directory to a
location where Octave can find them. You can start Octave with the
-p path
option to tell it to add path
to its search path, so that it will find the functions automatically
without the need to move them:
octave -p /path/to/queueing/inst
Refer to the documentation for the
list of functions provided by queueing
.
The documentation for each function can be accessed from the Octave
prompt with the help command. For example, you can get the
documentation for function qncsmva
with the command:
help qncsmva
Also, most of the functions have inline tests and demos. Tests are
used to check the correctness of the results, while demos provide
snippets of code which demonstrates how the function can be used.
For example, to show and execute the demos for qncsmva
,
type the following command:
demo qncsmva
In this section we give some basic usage example for
queueing
. Refer to the documentation for more examples.
Suppose that we want to analyze the following closed network:
The routing probabilities are shown in the picture. To analyze this
network we use the qnclosed()
function. This function has
the following signature:
[U, R, Q, X] = qnclosed (N, S, V, ...)
where N
is the number of requests in the (closed)
network, S
and V
are arrays such that
S(k)
is the service time at center k
, and
V(k)
is the visit count at center
k
. The visit counts V
for a closed network
satisfy the equality V*P == V
with the additional
constraint V(1) == 1
. V
can be computed from
the routing probability matrix P
using the
qncsvisits
function, as follows:
P = [0 0.3 0.7; 1 0 0; 1 0 0]; V = qncsvisits(P)
V = 1.00000 0.30000 0.70000
By default, qncsvisits
uses station 1 as the reference
station; the reference station is used for two purposes: its
throughput is considered the system throughput, and a job returning to
the reference station is assumed to have completed one interaction
with the system. It is possible to specify a different reference
station, use the command help qncsvisits
for details.
Let us suppose that there are N=10
requests in the
system. We let the average service times be S = [1 2 0.8]
.
We analyze the network as follows:
N = 10; S = [1 2 0.8]; P = [0 0.3 0.7; 1 0 0; 1 0 0]; V = qncsvisits(P); [U R Q X] = qnclosed( N, S, V )
U = 0.99139 0.59483 0.55518 R = 7.4360 4.7531 1.7500 Q = 7.3719 1.4136 1.2144 X = 0.99139 0.29742 0.69397
where U
is the vector of per-node utilizations,
R
is the vector of per-node response times,
Q
is the vector of average queue lengths and
X
is the vector of throughputs. Thus, the utilization of
service center 1 is U(1)==0.99139
, which is very close to
1.0. We can conclude that the service center 1 is the bottleneck
device.
Analyzing open networks is very similar. Consider the open network shown in Fig. 2
Assume that the average service times are as in the previous
example (S = [1 2 0.8]
). Furthermore, assume an external
arrival rate of 0.3 requests/s to center 1, and no external arrivals
to other centers.
Again, we need first to compute the visit counts. The function
qnosvisits
can be used to compute the visit counts for
open networks; the function accepts the routing probability matrix
P
as the first parameter, and the vector of external
arrival rates as the second. The vector of external arrival rates is
lambda = [0.3 0 0]
. Thus, we can issue the following
Octave commands:
P = [0 0.3 0.5; 1 0 0; 1 0 0]; lambda = [0.15 0 0]; V = qnosvisits(P,lambda)
V = 5.0000 1.5000 2.5000
We might also verify that the external arrival rate is less than the processing capacity of the network, which by definition is the inverse of the maximum service demand:
S = [1 2 0.8]; D = V .* S
D = 5.0000 3.0000 2.0000
1/max(D)
ans = 0.20000
sum(lambda)
ans = 0.15000
Since sum(lambda) < 1/max(D)
, it is possible to
analyze the steady-state behavior of the network. We use the
qnopen
function to compute the results of interest:
[U R Q X] = qnopen( sum(lambda), S, V )
U = 0.75000 0.45000 0.30000 R = 4.0000 3.6364 1.1429 Q = 3.00000 0.81818 0.42857 X = 0.75000 0.22500 0.37500
Finally, we consider a more complete example. The following is
embedded as a demo function of the qnclosed.m
source file, and you can execute it by issuing this command at the
Octave prompt:
demo qnclosed
In this demo we want to compute the bounds on the system throughput
for the network in Fig. 3, which
is very similar to the one of Fig. 1, with the only addition of an external
think time. We are going to use the qnclosedab
and qnclosedbsb
functions, to compute the bounds on the
system throughput for increasing values of the population size N, and
compare the results with the exact throughput provided by the MVA algorithm.
P = [0 0.3 0.7; 1 0 0; 1 0 0]; # Transition probability matrix S = [1 0.6 0.2]; # Average service times m = ones(size(S)); # All centers are single-server Z = 2; # External delay N = 15; # Maximum population to consider V = qncsvisits(P); # Compute number of visits from P X_bsb_lower = X_bsb_upper = X_ab_lower = X_ab_upper = X_mva = zeros(1,N); for n=1:N [X_bsb_lower(n) X_bsb_upper(n)] = qncsbsb(n, S, V, m, Z); [X_ab_lower(n) X_ab_upper(n)] = qncsaba(n, S, V, m, Z); [U R Q X] = qnclosed( n, S, V, m, Z ); X_mva(n) = X(1)/V(1); endfor close all; plot(1:N, X_ab_lower,"g;Asymptotic Bounds;", \ 1:N, X_bsb_lower,"k;Balanced System Bounds;", \ 1:N, X_mva,"b;MVA;", "linewidth", 2, \ 1:N, X_bsb_upper,"k", 1:N, X_ab_upper,"g" ); axis([1,N,0,1]); legend("location","southeast"); xlabel("Number of Requests n"); ylabel("System Throughput X(n)");
The result is shown in Fig. 4.
Fig. 4: Balanced System Bounds and Asymptotic Bounds on the system throughput X(N) as a function of the population size N for the three-node, closed network in Fig. 3.
Finally, starting from version 0.8.0 of queueing
,
there are a couple of functions which facilitate the definition and
analysis of QN models. These functions are qnmknode
and
qnsolve
. The first one is used to create appropriate data
structures describing certain kind of QN nodes; the second one is used
to analyze a model represented by those data structures. It should be
observed that qnsolve
(re)implements the same algorithms
used by other functions such as qnopensingle
,
qnclosedsingle
and so on; only the input parameters are
different.
Consider again the closed network shown in Fig. 3. Using the new functions, the network can be described and analyzed as follows:
P = [0 0.3 0.7; 1 0 0; 1 0 0]; V = qncsvisits(P); QQ = { qnmknode("m/m/m-fcfs", 1), \ qnmknode("m/m/m-fcfs", 0.6), \ qnmknode("m/m/m-fcfs", 0.2) }; Z = 2; # external delay N = 10; # population [U R Q X] = qnsolve("closed", N, QQ, V, Z);
The qnmknode
function can be used to instantiate
different kind of nodes (see the documentation for details). If can
also be used to create multi-class nodes, or general load-dependent
nodes, which can be analyzed with qnsolve
. Again, see the
documentation for details.
The software can be improved in many ways: