You are in: Home » Software » Octave queueing package

A Queueing Package for GNU Octave

[ What is the queueing package? | Download | Documentation | Installation | Usage examples | Todo | Resources ]

The Octave Queueing Package is now included in Octave-Forge!

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.

2014/03/12
queueing-1.2.3 has been released. This release includes new features; see the ChangeLog for details.
2013/06/29
queueing-1.2.2 has been released. This is a bug fix release. See the ChangeLog for details.
2013/02/05
queueing-1.2.1 has been released. This version includes new features. See the ChangeLog for details.
2012/11/05
queueing-1.2.0 has been released. This version includes many bug fixes and new features. See the ChangeLog for details.
2012/09/08
queueing-1.1.1 has been released. This version fixes some spurious errors raised by the embedded test blocks. See the ChangeLog for details.
2012/04/06
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.

About

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.

Download

Latest stable release

Development version

Old versions

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.

GPL v3 Logo 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.

Documentation

The user manual is available in the following formats:

If you use this package for research, please cite the following publication:

Other technical reports:

Installation

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

Usage examples

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:

Three-nodes Central Server Closed Queueing Network Model

Fig. 1: Three-nodes central server queueing network model (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

Three-nodes Central Server Open Queueing Network Model

Fig. 2: Three-nodes Central Server Queueing Network Model (Open network)

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
Three-nodes Central Server Closed Queueing Model, with terminals

Fig. 3: Three-nodes Central Server Queueing Model (Closed network), with terminals

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.

Bounds for the three-nodes closed network

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.

TODO

The software can be improved in many ways:

Additional Resources

Other Queueing Packages

References

This page validates as XHTML 1.0 strict This page validates as CSS Check the accessibility of this page with WAVE
This page was last updated on March 12 2014