Mercurial > forge

changeset 11063:50fab14a8eb6 octave-forge

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added new functions qnclosedmultiab and qnclosedsingleab
author mmarzolla
date Sat, 13 Oct 2012 16:02:52 +0000
parents c8879e931487
children 06f5ad59c9c1
files main/queueing/ChangeLog main/queueing/doc/INSTALL main/queueing/doc/queueingnetworks.txi main/queueing/inst/qnclosedab.m main/queueing/inst/qnclosedgb.m main/queueing/inst/qnclosedmultiab.m main/queueing/inst/qnclosedmultimva.m main/queueing/inst/qnclosedsingleab.m main/queueing/inst/qnclosedsinglemva.m
diffstat 9 files changed, 346 insertions(+), 66 deletions(-) [+]
line wrap: on
line diff
--- a/main/queueing/ChangeLog	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/ChangeLog	Sat Oct 13 16:02:52 2012 +0000
@@ -3,6 +3,11 @@
 	* Version 1.1.2 released
 	* Restructured the documentation
 	* Fixed function qncmva()
+	* Reduced space requirement for qnclosedsinglemva() when
+	  there are no LD servers
+	* qnclosedsingleab() added
+	* qnclosedmultiab() added
+	* Changed interface for qnclosedab()
 
 2012-09-08 Moreno Marzolla <marzolla@cs.unibo.it>
 
--- a/main/queueing/doc/INSTALL	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/doc/INSTALL	Sat Oct 13 16:02:52 2012 +0000
@@ -16,7 +16,7 @@
 1.1 Installation through Octave package management system
 =========================================================
 
-The most recent version of `queueing' is 1.1.2 and can be downloaded
+The most recent version of `queueing' is 1.2.0 and can be downloaded
 from Octave-Forge
 
    `http://octave.sourceforge.net/queueing/'
@@ -38,7 +38,7 @@
      octave:1>pkg list queueing
      Package Name  | Version | Installation directory
      --------------+---------+-----------------------
-         queueing  |   1.1.2 | /home/moreno/octave/queueing-1.1.2
+         queueing  |   1.2.0 | /home/moreno/octave/queueing-1.2.0
 
      Note: Starting from version 1.1.1, `queueing' is no longer
      automatically loaded on startup. To load the package you need to
@@ -51,7 +51,7 @@
 then, to install the package in the system-wide location issue this
 command at the Octave prompt:
 
-     octave:1> pkg install _queueing-1.1.2.tar.gz_
+     octave:1> pkg install _queueing-1.2.0.tar.gz_
 
 (you may need to start Octave as root in order to allow the
 installation to copy the files to the target locations). After this,
@@ -60,7 +60,7 @@
 
    If you do not have root access, you can do a local install using:
 
-     octave:1> pkg install -local queueing-1.1.2.tar.gz
+     octave:1> pkg install -local queueing-1.2.0.tar.gz
 
    This will install `queueing' within your home directory, and the
 package will be available to your user only.
@@ -79,8 +79,8 @@
 If you want to manually install `queueing' in a custom location, you
 can download the tarball and unpack it somewhere:
 
-     tar xvfz queueing-1.1.2.tar.gz
-     cd queueing-1.1.2/queueing/
+     tar xvfz queueing-1.2.0.tar.gz
+     cd queueing-1.2.0/queueing/
 
    Copy all `.m' files from the `inst/' directory to some target
 location. Then, start Octave with the `-p' option to add the target
--- a/main/queueing/doc/queueingnetworks.txi	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/doc/queueingnetworks.txi	Sat Oct 13 16:02:52 2012 +0000
@@ -1144,6 +1144,10 @@
 @c
 @GETHELP{qnclosedab}
 
+@GETHELP{qnclosedsingleab}
+
+@GETHELP{qnclosedmultiab}
+
 @noindent @strong{REFERENCES}
 
 @noindent Edward D. Lazowska, John Zahorjan, G.  Scott Graham, and Kenneth
--- a/main/queueing/inst/qnclosedab.m	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/inst/qnclosedab.m	Sat Oct 13 16:02:52 2012 +0000
@@ -17,86 +17,83 @@
 
 ## -*- texinfo -*-
 ##
-## @deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedab (@var{N}, @var{D})
-## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedab (@var{N}, @var{D}, @var{Z})
+## @deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedab (@var{N}, @var{S}, @dots{})
 ##
 ## @cindex bounds, asymptotic
 ## @cindex closed network
 ##
-## Compute Asymptotic Bounds for single-class, closed Queueing Networks
-## with @math{K} service centers.
-##
-## @strong{INPUTS}
-##
-## @table @var
+## This function computes Asymptotic Bounds for throughput and response
+## time of closed, single or multiclass queueing networks. Single server
+## and delay centers are allowed. Multiple server nodes are not
+## supported.
 ##
-## @item N
-## number of requests in the system (scalar, @code{@var{N}>0}).
+## This function dispatches the computation to @code{qnclosedsingleab}
+## or @code{qnclosedmultiab}.
 ##
-## @item D
-## @code{@var{D}(k)} is the service demand of service center @math{k},
-## @code{@var{D}(k) @geq{} 0}.
-##
-## @item Z
-## external delay (think time, scalar, @code{@var{Z} @geq{} 0}). If
-## omitted, it is assumed to be zero.
+## @itemize
 ##
-## @end table
-##
-## @strong{OUTPUTS}
-##
-## @table @var
+## @item If @var{N} is a scalar, the network is assumed to have a single
+## class of requests and control is passed to @code{qnclosedsingleab}.
 ##
-## @item Xl
-## @itemx Xu
-## Lower and upper bound on the system throughput.
+## @item If @var{N} is a vector, the network is assumed to have multiple
+## classes of requests, and control is passed to @code{qnclosedmultiab}.
 ##
-## @item Rl
-## @itemx Ru
-## Lower and upper bound on the system response time.
+## @end itemize
 ##
-## @end table
-##
-## @seealso{qnclosedbsb, qnclosedgb, qnclosedpb}
+## @seealso{qnclosedsingleab, qnclosedmultiab}.
 ##
 ## @end deftypefn
 
 ## Author: Moreno Marzolla <marzolla(at)cs.unibo.it>
 ## Web: http://www.moreno.marzolla.name/
 
-function [Xl Xu Rl Ru] = qnclosedab( N, D, Z )
-  if ( nargin < 2 || nargin > 3 )
+function [Xl Xu Rl Ru] = qnclosedab( N, varargin )
+  if ( nargin < 2 || nargin > 5 )
     print_usage();
   endif
-  ( isscalar(N) && N > 0 ) || \
-      error( "N must be a positive integer" );
-  ( isvector(D) && length(D)>0 && all( D >= 0 ) ) || \
-      error( "D must be a vector of nonnegative floats" );
-  if ( nargin < 3 )
-    Z = 0;
+
+  if (isscalar(N))
+    [Xl Xu Rl Ru] = qnclosedsingleab(N, varargin{:});
   else
-    ( isscalar(Z) && Z >= 0 ) || \
-        error( "Z must be a nonnegative scalar" );
+    [Xl Xu Rl Ru] = qnclosedmultiab(N, varargin{:});
   endif
-  
-  D_tot = sum(D);
-  D_max = max(D);
-  Xl = N/(N*D_tot+Z);
-  Xu = min( N/(D_tot+Z), 1/D_max );
-  Rl = max( D_tot, N*D_max-Z );
-  Ru = N*D_tot;
 endfunction
 
 %!test
 %! fail( "qnclosedab( 1, [] )", "vector" );
-%! fail( "qnclosedab( 1, [0 -1])", "vector" );
+%! fail( "qnclosedab( 1, [0 -1])", ">= 0" );
 %! fail( "qnclosedab( 0, [1 2] )", "positive integer" );
 %! fail( "qnclosedab( -1, [1 2])", "positive integer" );
 
 ## Example 9.6 p. 913 Bolch et al.
 %!test
 %! N = 20;
-%! D = [ 4.6*2 8 ];
+%! S = [ 4.6*2 8 ];
 %! Z = 120;
-%! [X_l X_u R_l R_u] = qnclosedab(N, D, Z);
+%! [X_l X_u R_l R_u] = qnclosedab(N, S, 1, 1, Z);
 %! assert( [X_u R_l], [0.109 64], 1e-3 );
+
+%!demo
+%! D = [10 7 5 4; \
+%!      5  2 4 6];
+%! NN=20;
+%! Xl = Xu = Xmva = zeros(NN,2);
+%! for n=1:NN
+%!   N=[n,10];
+%!   [a b] = qnclosedab(N,D);
+%!   [U R Q X] = qnclosedmultimva(N,D);
+%!   Xl(n,:) = a;
+%!   Xu(n,:) = b;
+%!   Xmva(n,:) = X(:,1)';
+%! endfor
+%! subplot(2,1,1);
+%! plot(1:NN,Xl(:,1),"linewidth", 2, \
+%!      1:NN,Xu(:,1),"linewidth", 2, \
+%!      1:NN,Xmva(:,1),";MVA;");
+%! title("Class 1 throughput");
+%! subplot(2,1,2);
+%! plot(1:NN,Xl(:,2),"linewidth", 2, \
+%!      1:NN,Xu(:,2), "linewidth", 2,\
+%!      1:NN,Xmva(:,2),";MVA;");
+%! title("Class 2 throughput");
+%! xlabel("Number of class 1 requests");
\ No newline at end of file
--- a/main/queueing/inst/qnclosedgb.m	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/inst/qnclosedgb.m	Sat Oct 13 16:02:52 2012 +0000
@@ -93,7 +93,7 @@
   L_max = max(L);
   M = length(L);
   if ( nargin < 4 ) 
-    [X_minus X_plus] = qnclosedab(N,L,Z);
+    [X_minus X_plus] = qnclosedsingleab(N,L,ones(size(L)),ones(size(L)),Z);
   endif
   ##[X_minus X_plus] = [0 1/L_max];
   [Q_lower Q_upper] = __compute_Q( N, L, Z, X_plus, X_minus);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main/queueing/inst/qnclosedmultiab.m	Sat Oct 13 16:02:52 2012 +0000
@@ -0,0 +1,136 @@
+## Copyright (C) 2012 Moreno Marzolla
+##
+## This file is part of the queueing toolbox.
+##
+## The queueing toolbox is free software: you can redistribute it and/or
+## modify it under the terms of the GNU General Public License as
+## published by the Free Software Foundation, either version 3 of the
+## License, or (at your option) any later version.
+##
+## The queueing toolbox is distributed in the hope that it will be
+## useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with the queueing toolbox. If not, see <http://www.gnu.org/licenses/>.
+
+## -*- texinfo -*-
+##
+## @deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedmultiab (@var{N}, @var{S})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedmultiab (@var{N}, @var{S}, @var{V})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedmultiab (@var{N}, @var{S}, @var{V}, @var{m})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedmultiab (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})
+##
+## @cindex bounds, asymptotic
+## @cindex closed network
+##
+## Compute Asymptotic Bounds for multiclass networks.
+## Single-server and infinite-server nodes are supported.
+## Multiple-server nodes and general load-dependent servers are not
+## supported.
+##
+## @strong{INPUTS}
+##
+## @table @var
+##
+## @item N
+## @code{@var{N}(c)} is the number of class @math{c} requests in the system.
+##
+## @item S
+## @code{@var{S}(c, k)} is the mean service time of class @math{c}
+## requests at center @math{k}
+## (@code{@var{S}(c,k) @geq{} 0}).
+##
+## @item V
+## @code{@var{V}(c,k)} is the average number of visits of class @math{c}
+## requests to center
+## @math{k} (@code{@var{V}(c,k) @geq{} 0}). Default is 1.
+##
+## @item Z
+## @code{@var{Z}(c)} is class @math{c} external delay
+## (@code{@var{Z}(c) @geq{} 0}). Default is 0.
+##
+## @item m
+## @code{@var{m}(k)} is the number of servers at center @math{k}
+## (if @var{m} is a scalar, all centers have that number of servers). If
+## @code{@var{m}(k) < 1}, center @math{k} is a delay center (IS);
+## if @code{@var{m}(k) = 1}, center @math{k} is a M/M/1-FCFS server.
+## This function does not support multiple-server nodes. Default
+## is 1.
+##
+## @end table
+##
+## @strong{OUTPUTS}
+##
+## @table @var
+##
+## @item Xl
+## @itemx Xu
+## Lower and upper class @math{c} throughput bounds.
+##
+## @item Rl
+## @itemx Ru
+## Lower and upper class @math{c} response time bounds.
+##
+## @end table
+##
+## @seealso{qnclosedsingleab}
+##
+## @end deftypefn
+
+## Author: Moreno Marzolla <marzolla(at)cs.unibo.it>
+## Web: http://www.moreno.marzolla.name/
+
+function [Xl Xu Rl Ru] = qnclosedmultiab( N, S, V, m, Z )
+
+  if ( nargin<2 || nargin>5 )
+    print_usage();
+  endif
+
+  ( isvector(N) && all(N >= 0) ) || \
+      error( "N must be a positive integer" );
+  N = N(:)';
+  sum(N)>0 || \
+      error( "The network has no requests" );
+
+  C = length(N); # number of classes
+
+  ( ismatrix(S) && rows(S) == C && all(all(S>=0))) || \
+      error("S must be a matrix >=0 with %d rows", C);
+  
+  K = columns(S);
+
+  if ( nargin<3 )
+    V = ones(size(S));
+  else
+    (ismatrix(V) && size_equal(S,V) && all(all(V>=0))) || \
+	error("V must be a %d x %d matrix >=0", C, K);
+  endif
+
+  if ( nargin<4 )
+    m = ones(1,K);
+  else
+    (isvector(m) && length(m) == K && all(m<=1)) || \
+	error("m must be a vector with %d elements <=1", K);
+    m = m(:)';
+  endif
+
+  if (nargin<5)
+    Z = zeros(1,C);
+  else
+    (isvector(Z) && length(Z) == C && all(Z>=0) ) || \
+	error("Z must be a vector >=0 with %d elements", C);
+    Z = Z(:)';
+  endif
+
+  D = S .* V;
+
+  Dc_single = sum(D(:,(m==1)),2)'; # class c demand on single-server nodes
+  Dc_delay = sum(D(:,(m<1)),2)'; # class c demand on delay centers
+  Dc = sum(D,2)'; # class c total demand
+  Dcmax = max(D,[],2)'; # maximum class c demand at any server
+  Xl = N ./ ( dot(N,Dc_single) .+ Dc_delay .+ Z);
+  Xu = min( 1./Dcmax, N ./ (Dc .+ Z) );
+  Rl = Ru = [];
+endfunction
--- a/main/queueing/inst/qnclosedmultimva.m	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/inst/qnclosedmultimva.m	Sat Oct 13 16:02:52 2012 +0000
@@ -143,7 +143,7 @@
 ##
 ## @item X
 ## @code{@var{X}(c,k)} is the class @math{c} throughput at
-## center @math{k}. The class @math{c} system throughput can be computed
+## center @math{k}. The class @math{c} throughput can be computed
 ## as @code{@var{X}(c,1) / @var{V}(c,1)}.
 ##
 ## @end table
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main/queueing/inst/qnclosedsingleab.m	Sat Oct 13 16:02:52 2012 +0000
@@ -0,0 +1,136 @@
+## Copyright (C) 2012 Moreno Marzolla
+##
+## This file is part of the queueing toolbox.
+##
+## The queueing toolbox is free software: you can redistribute it and/or
+## modify it under the terms of the GNU General Public License as
+## published by the Free Software Foundation, either version 3 of the
+## License, or (at your option) any later version.
+##
+## The queueing toolbox is distributed in the hope that it will be
+## useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with the queueing toolbox. If not, see <http://www.gnu.org/licenses/>.
+
+## -*- texinfo -*-
+##
+## @deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedsingleab (@var{N}, @var{S})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedsingleab (@var{N}, @var{S}, @var{V})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedsingleab (@var{N}, @var{S}, @var{V}, @var{m})
+## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnclosedsingleab (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})
+##
+## @cindex bounds, asymptotic
+## @cindex closed network
+##
+## Compute Asymptotic Bounds for single closed networks. Single-server
+## and infinite-server nodes are supported. Multiple-server nodes and
+## general load-dependent servers are not supported.
+##
+## @strong{INPUTS}
+##
+## @table @var
+##
+## @item N
+## number of requests in the system (scalar, @code{@var{N}>0}).
+##
+## @item S
+## @code{@var{S}(k)} is the mean service time at center @math{k}
+## (@code{@var{S}(k) @geq{} 0}).
+##
+## @item V
+## @code{@var{V}(k)} is the average number of visits to center
+## @math{k} (@code{@var{V}(k) @geq{} 0}). Default is 1.
+##
+## @item Z
+## External delay (@code{@var{Z} @geq{} 0}). Default is 0.
+##
+## @item m
+## @code{@var{m}(k)} is the number of servers at center @math{k}
+## (if @var{m} is a scalar, all centers have that number of servers). If
+## @code{@var{m}(k) < 1}, center @math{k} is a delay center (IS);
+## if @code{@var{m}(k) = 1}, center @math{k} is a M/M/1-FCFS server.
+## This function does not support multiple-server nodes. Default
+## is 1.
+##
+## @end table
+##
+## @strong{OUTPUTS}
+##
+## @table @var
+##
+## @item Xl
+## @itemx Xu
+## Lower and upper system throughput bounds.
+##
+## @item Rl
+## @itemx Ru
+## Lower and upper response time bounds.
+##
+## @end table
+##
+## @seealso{qnclosedmultiab}
+##
+## @end deftypefn
+
+## Author: Moreno Marzolla <marzolla(at)cs.unibo.it>
+## Web: http://www.moreno.marzolla.name/
+
+function [Xl Xu Rl Ru] = qnclosedsingleab( N, S, V, m, Z )
+  
+  if (nargin<2 || nargin>5)
+    print_usage();
+  endif
+
+  ( isscalar(N) && N > 0 ) || \
+      error( "N must be a positive integer" );
+  isvector(S) || \
+      error( "S must be a vector" );
+  S = S(:)';
+
+  if ( nargin < 3 )
+    V = 1;
+  else
+    isvector(V) || \
+	error( "V must be a vector" );
+    V = V(:)';
+  endif
+  if ( nargin < 4 )
+    m = 1;
+  else
+    isvector(m) || \
+	error( "m must be a vector" );
+    m = m(:)';
+  endif
+
+  [err S V m] = common_size(S, V, m);
+  (err == 0) || \
+      error( "S, V and m are of incompatible size" );
+  all(m<=1) || \
+      error( "multiple server nodes are not supported" );
+  all(S>=0) || \
+      error( "S must be >= 0 ");
+  all(V>=0) || \
+      error( "V must be >= 0" );
+
+  if ( nargin < 5 )
+    Z = 0;
+  else
+    ( isscalar(Z) && Z >= 0 ) || \
+        error( "Z must be a nonnegative scalar" );
+  endif
+
+  D = S.*V;
+
+  Dtot_single = sum(D(m==1)); # total demand at single-server nodes
+  Dtot_delay = sum(D(m<1)); # total demand at IS nodes
+  Dtot = sum(D); # total demand
+  Dmax = max(D); # max demand
+
+  Xl = N/(N*Dtot_single + Dtot_delay + Z);
+  Xu = min( N/(Dtot+Z), 1/Dmax );
+  Rl = max( Dtot, N*Dmax - Z );
+  Ru = N*Dtot_single + Dtot_delay;
+endfunction
--- a/main/queueing/inst/qnclosedsinglemva.m	Sat Oct 13 06:33:48 2012 +0000
+++ b/main/queueing/inst/qnclosedsinglemva.m	Sat Oct 13 16:02:52 2012 +0000
@@ -46,8 +46,8 @@
 ## @code{@var{U} = @var{R} = @var{Q} = @var{X} = 0}
 ##
 ## @item S
-## @code{@var{S}(k)} is the mean service time on server @math{k}
-## (@code{@var{S}(k)>0}).
+## @code{@var{S}(k)} is the mean service time at center @math{k}
+## (@code{@var{S}(k) @geq{} 0}).
 ##
 ## @item V
 ## @code{@var{V}(k)} is the average number of visits to service center
@@ -166,15 +166,17 @@
     return;
   endif
 
-  ## Initialize results
-  p = zeros( K, max(m)+1 ); # p(i,j+1) is the probability that there are j jobs at server i
-  p(:,1) = 1;
-  X_s = 0; # System throughput
-
   i_single = find( m==1 );
   i_multi = find( m>1 );
   i_delay = find( m<1 );
 
+  ## Initialize results
+  if ( length(i_multi)>0 )
+    p = zeros( K, max(m)+1 ); # p(i,j+1) is the probability that there are j jobs at server i
+    p(:,1) = 1;
+  endif
+  X_s = 0; # System throughput
+
   ## Main MVA loop, iterates over the population size
   for n=1:N