You are in: Home > Software > qnetworks

qnetworks—a Queueing Networks analysis package for GNU Octave

About qnetworks

qnetworks is a Queueing Networks analysis package written in GNU Octave. It includes implementations of some QN algorithms. At the moment, the following algorithms are available:

• Exact analysis of single or multi-class, product-form open Queueing Networks (Jackson networks or BCMP networks).
• Mean Value Analysis (MVA) for single or multi-class closed networks.
• MVA for multiclass, mixed (open/closed) networks.
• Approximate MVA for closed, multi-class QN, using Bard-Schweitzer approximation.
• The convolution algorithm for closed, single-class product-form networks.
• MVABLO for closed, single-class QN with blocking.
• Computation of Asymptotic, Balanced System and Geometric bounds.
• Transient as well as steady-state analysis of Markov chains (computation of sojourn times and expected time to absorption for continuous-time Markov chains).
• Analysis of the following single-station queueing systems: M/M/1, M/M/m, M/M/∞, M/M/1/K and M/M/m/K finite-capacity systems, Asymmetric M/M/m, M/G/1, H/H_m/1.

qnetworks is released under the GNU General Public License, version 3 or later.

Please note that qnetworks is under active development. New versions are released frequently, and both the code and the documentation are being corrected.

Return to top

Download and Installation

Please note: qnetworks version 0.8.2.2 fixes a serious bug which was introduced in version 0.8.2.1 which resulted in many internal tests failing. Please update to the latest version as soon as possible.

qnetworks downloads

Description	Size (bytes)	Date updated
qnetworks-0.8.2.2.tar.gz	483669	February 02 2010
qnetworks documentation (PDF format)	420804	February 02 2010
qnetworks documentation (HTML format)	233013	February 02 2010

Download qnetworks-0.8.2.2.tar.gz, unpack it somewhere and copy all .m files from the inst/ directory to a location where Octave can find them. You can also 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:

Alternatively, you can use the pkg install Octave command to install the tarball directly. Start GNU Octave, and at the prompt type the following command:

For the list of functions provided by the qnetworks package, please see the package documentation, which is available in pdf and html format. The user manual can be automatically generated from the source files by issuing the make command from the top level directory.

The documentation for each function can also be accessed from the Octave prompt using the help Octave command. For example, you can get the documentation for qnclosedmultimva by issuing this command at the Octave prompt:

Moreover, most of the functions have inline test and demo functions. Test functions can be used to check the correctness of the computed results on some test cases, while demo functions provide snippets of code which demonstrates how the functions can be used. See the test and demo Octave commands for more information.

Return to top

Usage 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 qnclose function. This function requires the visit counts (average number of visits) for each node as one of its parameters. The visit count can be computed from the routing matrix using the qnvisits function, as follows:

The visit counts V for a closed network satisfy the equality V*P == V with the additional constraint V(1) == 1.

Now, let us suppose that there are N=10 requests in the system. We let the average service times S = [1 2 0.8]. To analyze the network we use the following commands:

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 lenghts and X is the vector of thorughputs. 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 qnvisits can be used to compute the visit counts as in the previous example, but in this case we need to pass the vector of external arrival rates as an additional parameter. The vector of external arrival rates is lambda = [0.3 0 0]. Thus, we can issue the following Octave commands:

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:

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:

Since the queueing network shown in Fig. 2 is a Jackson Network, you can also use the qnjackson function to compute the exact same results using the routing probability matrix P directly.

Finally, let us see 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:

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.

The results are shown in Fig. 4.

Finally, starting from version 0.8.0 of qnetworks, 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:

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.

Return to top

TODO

The software can be improved in many ways:

• Keep the documentation up-to-date; add missing chapters.
• Add more function tests. More tests are always important.
• Implement additional QN algorithms. Some references are G. Bolch, S. Greiner, H. de Meer, K. Trivedi, Queueing Networks and Markov Chains—Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998; L. Kleinrock, Queueing Systems Volume 1: Theory, Wiley-Interscience; 1 edition (January 2, 1975), ISBN 978-0471491101.

Return to top

Resources

• Java Modelling Tools (JMT), developed by the Performance Evaluation Lab of the Politecnico di Milano, Italy
• List of Queueing Theory Software, maintained by Myron Hlynka
• Edward D. Lazowska, John Zahorjan, G. Scott Graham, Kenneth C. Sevcik, Quantitative System Performance—Computer System Analysis Using Queueing Network Models, Prentice-Hall, 1984. This book is the source of some of the algorithms implemented in the qnetworks package. Furthermore, the PDF version of the book is freely downloadable.

Return to top

This page was last updated on February 02 2010